Using a custom index implementation that uses bloom filters internally is probably going to work out better in the long run. It should be way more efficient than storing the data in a bit field, using app-layer code to generate the bloom filter values, then doing bitwise comparisons on-the-fly at query time.

The Postgres query planner can also recheck constraints automatically to recover from bloom filter false positive matches at query time.

FYI -- bloom filters are already used internally within the PostgreSQL intarray contrib module and the full-text search functionality.

See: http://postgresql.1045698.n5.nabble.com/bloom-filter-indexes... http://code.google.com/p/postgres-learning/wiki/BloomFilter

EDIT: for clarity, typo correction