the app details truly don't matter to the question

If you're asking a question, it means you don't know the answer. In this case it is a bit presumptuous to hide information because you feel it's not relevant: in order to know if the information is relevant, you'd need to know the answer, which you do not, because you're asking the question ;)

if you must know, it's for a dating app with very extensive profile information, many fields of which can be added to search criteria

An excellent solution for a large number of low cardinality columns is a bloom filter index. You have to load the extension:

CREATE EXTENSION bloom

Unfortunately it only supports up to 32 columns, so if you have more columns you'll need several indices. Still for 100 columns... 4 indices will probably use less resources than 100 indices.

Another option is to give each (attribute_name,value) pair a number, store that into an integer array, and put a gist index on it. It's a bit cumbersome, for example "hair=blonde" would maybe correspond to "there is the number 123 in the array".

I did a little benchmark with 1M rows and bloom index won by a large margin.

So I recommend you give it a try and benchmark with your most common search queries, also tune bloom parameters like signature length. Due to the 32 column limit, how you split columns into indices is likely to be important too.

Note your problem is identical to fulltext search. Finding rows with "hair=blonde and status=single" is exactly the same as encoding the attributes into keywords and doing a fulltext search on "hair_blonde status_single".

So another option is to just use a fast fulltext engine. But database integration is likely to suck. I wouldn't recommend using postgres' full text engine since it is based on gist indices, which means you'd get better performance using gist indices directly.

the app details truly don't matter to the question

If you're asking a question, it means you don't know the answer. In this case it is a bit presumptuous to hide information because you feel it's not relevant: in order to know if the information is relevant, you'd need to know the answer, which you do not, because you're asking the question ;)

if you must know, it's for a dating app with very extensive profile information, many fields of which can be added to search criteria

An excellent solution for a large number of low cardinality columns is a bloom filter index. You have to load the extension:

CREATE EXTENSION bloom

Unfortunately it only supports up to 32 columns, so if you have more columns you'll need several indices. Still for 100 columns... 4 indices will probably use less resources than 100 indices.

Another option is to give each (attribute_name,value) pair a number, store that into an integer array, and put a gist index on it. It's a bit cumbersome, for example "hair=blonde" would maybe correspond to "there is the number 123 in the array".

I did a little benchmark with 1M rows and bloom index won by a large margin.

So I recommend you give it a try and benchmark with your most common search queries, also tune bloom parameters like signature length. Due to the 32 column limit, how you split columns into indices is likely to be important too.

Note your problem is identical to fulltext search. Finding rows with "hair=blonde and status=single" is exactly the same as encoding the attributes into keywords and doing a fulltext search on "hair_blonde status_single".

So another option is to just use a fast fulltext engine. But database integration is likely to suck. I wouldn't recommend using postgres' full text engine since it is based on gist indices, which means you'd get better performance using gist indices directly.

--

Data generation script for benchmark

SELECT * FROM profiles_bloom WHERE a01=1 AND a02=1 AND a03=1 AND a10=1 AND a11=1 AND a12=1

Seq scan: 44ms
Bloom: 12ms
Btree: 26ms
gist (using integer array contains operator): 63ms
gin (same): 45ms

Rows are quite small, which makes bitmap index scan less efficient. With larger rows, each page flagged by the bitmap index scan contains less rows to filter out, so it should be faster.

Unfortunately bloom filter index does not support bools, so I used integer columns.