"Why would you want this over a NoSQL store?"

If you can use a more general-purpose system like Postgres and get everything you need, then that's better than relying on special-purpose NoSQL systesm. The better question to ask is: why use a NoSQL system when Postgres works just fine and is useful in more situations?

The history of databases is a history of absorbing special-purpose systems into general-purpose SQL systems. XML databases were once a major topic (albeit misguided); now it's just a feature. Same with Columnar storage, or OO databases, or geospatial (postgres is a leader in geospatial, as well).

Because data integration is so incredibly valuable, it pushes strongly toward general-purpose systems and people dislike one-off special-purpose databases unless they deliver a huge amount of additional value.

"How does Postgres even index an hstore?"

It allows normal btree indexing of, for example, the values for some given key by using functional and/or partial indexes.

It also allows indexing of "contains", "contains key", "contains all of these keys" and "contains some of these keys" by using GiST and GIN indexes.

Depends on your needs really. The querying capability in Postgres is so much nicer than NoSql DB's and generally, or at least is the case with Mongo, you don't get transactions.

hstore supports indexing out of the box.

http://www.postgresql.org/docs/9.2/static/hstore.html

You can also create custom indexing functions using the PL/$language extensions.

See here for some benchmarks comparing Mongo to several Postgresql options: https://wiki.postgresql.org/images/b/b4/Pg-as-nosql-pgday-fo...

MongoDB is not that fast.

You can use gist indexes to index hstore's.

Personally, I'd like the ability to make a transactional update to records in different tables.