Well, first off, a btree index is fairly useless for this query, because btree has no concept that the hstore has any sub-structure. A GIN index or GIST index could work though. Secondly, you have to remember that indexable WHERE conditions in Postgres are *always* of the form "WHERE indexed_column indexable_operator some_comparison_value".