PostgreSQL: hstore trgm search on fixed key
With only 10-20 distinct keys, I would urgently consider one separate column per key in the same row. Unused keys stay NULL. Related case:


JSONB vs BRIN Index


That said, there is a way to get the list of distinct key names from a document type column like jsonb or hstore comparatively quickly:

Create a btree expression index on the sorted array of key names (or a concatenated string), traverse it with a recursive CTE to emulate a loose index scan and condense the distinct set of keys from the distinct set of combinations of keys.

That will read 1000 index tuples for 1000 combinations (ideally in an index-only scan) instead of all 10kk of rows. A difference of factor 10k.

You need an IMMUTABLE function extracting the array or list of keys for the index - like akeys() for hstore.

A btree index on an array is rarely useful. This is the rare case.

Related code examples:


GROUP BY one column, while sorting by another in PostgreSQL