Indexing of a PostgreSQL bitstring (up to 20,000 bits each) I am building a table that contains chemical compounds (many millions of rows) and of those compounds certain predetermined features/fragments are flagged in a fixed length bitstring. 
This bitstring will have between 2000 and 20000 bits, further research needs to be done to determine more precise figures there.
When searching for compounds that have certain specific features, or lack specific features, a search is done on a select subset of this bitstring. This can be a different subset every time.

Is there an index type that can make these searches efficient in PostgreSQL (9.6 or 10)? 

Insertions are infrequent and done in a batch process, whereas searches are the mostly used operation and should preferably be quick and not have false positives or false negatives. 

To me this vaguely sounds like work for a GIN index, but my understanding of this index type is not enough to say for sure if that is realy the case.

Actually there could be another solution, and that is to create a separate 'fragment_index' table, with fragment identifiers (as they have a fixed position in the bitstring they also have a numerical identifier) + compound-id pairs.
My worry there is that that table can become enormous (20M compounds with avg 50 hits on fragments = 1G rows) and multiple joins against it (one for each fragment) where that join can also return up to 80% of matches with the compounds table (in some cases this is likely) will not perform at all.

I would be gratefull to get any suggestions towards a direction to get this on the road.

update: i tried a GIN index using the trigram module on a varchar array with codified shortcodes, it gave mixed results, mainly depending on the amount of data left over after the filter operations.

For the sake of giving examples that have any meaning let's assume the table looks like this:

CREATE TABLE testcompounds (
 id serial primary key,
 cd_structure text,
 features_as_text varchar(128),
 features_as_bits bit varying(32)
);

CREATE INDEX flags_testcompounds on testcompounds using gin (features_as_text gin_trgm_ops);


CREATE TABLE fragments (
 id serial primary key,
 smarts text,
 keystring varchar(4),
 frequency int 
);


insert into fragments (keystring,smarts) values('AAA', '*=O');
insert into fragments (keystring,smarts) values('AAB', '[#6]=O');
insert into fragments (keystring,smarts) values('AAC', '[#7]=O');
...
insert into fragments (keystring,smarts) values('AAN', '[#6]-F');
insert into fragments (keystring,smarts) values('AAO', '[#6]-Cl');
insert into fragments (keystring,smarts) values('AAP', '[#6]-Br');
...
etc.


and the features_as_text and features_as_bits fields have been fully populated.

An example of a query that can be ran on this would be:

select id, cd_structure from testcompounds 
where 
    (features_as_bits &amp; (B'00000000000000000000000000000001' &lt;&lt; (2-1)) = (B'00000000000000000000000000000001' &lt;&lt; (2-1))) 

AND (features_as_bits &amp; (B'00000000000000000000000000000001' &lt;&lt; (18-1)) = (B'00000000000000000000000000000000')) 
AND (features_as_bits &amp; (B'00000000000000000000000000000001' &lt;&lt; (19-1)) = (B'00000000000000000000000000000000')) 
AND (features_as_bits &amp; (B'00000000000000000000000000000001' &lt;&lt; (5-1)) = (B'00000000000000000000000000000000')) 
AND (features_as_bits &amp; (B'00000000000000000000000000000001' &lt;&lt; (6-1)) = (B'00000000000000000000000000000000')) 
AND (features_as_bits &amp; (B'00000000000000000000000000000001' &lt;&lt; (7-1)) = (B'00000000000000000000000000000000')) 
AND (features_as_bits &amp; (B'00000000000000000000000000000001' &lt;&lt; (8-1)) = (B'00000000000000000000000000000000')) 
AND (features_as_bits &amp; (B'00000000000000000000000000000001' &lt;&lt; (9-1)) = (B'00000000000000000000000000000000')) 


In words: get everything that has feature 2, and does not have any of features 18,19,5,6,7,8,9
Famous problem in cheminformatics.  You will have a hard time coming up with an index that will beat a full-table scan for this purpose.  The most performant solutions keep the bitstrings outside of the database, where they don't have to deal with transactional overhead, and are optimized for efficient use of popcnt hardware support.

You can take some shortcuts, by for example keeping the bitstring data sorted by the number of on bits.  If the query says "find me things with each of these 45 different bits turned on" then you can quickly skip all the records with less than 45 bits turned on, as they can't possibly qualify.  The problem is that queries are usually sparser in bits than whole compounds are, so the number of records skipped by this manner is pretty small.  Another optimization is to use something like a genetic algorithm to select out certain bits as being more important than others (trained on the nature of the queries you run), and sorting on the population count of just those select bits rather than the entire bitstring.

Anyway, I don't think you will find what you want in an in-core PostgreSQL index, so be prepared to do some heavy hacking.  You might want to look to Indigo source code for some inspiration.  (Or maybe you can just use Indigo for your intended purpose directly)