Bloom filter indexes

A Bloom filter sets a few bits per value, chosen by hash functions. If any of a value’s bits is unset the value is absent; if all are set it is probably present, so every hit is rechecked. PostgreSQL’s bloom extension stores one signature per row, 80 bits by default with 2 bits per column, over up to 32 columns, so one index serves equality on any combination of them. Rerunning its documentation example on PostgreSQL 18 (10 million rows, six integer columns): the bloom index took 153 MB and a six-column B-tree 386 MB, and WHERE i2 = 898732 AND i5 = 123451 took 155 ms through bloom, rechecking 2,363 false positives, against 468 ms for the sequential scan the planner chose over the B-tree. It ships operator classes only for int4 and text, supports only =, and can’t enforce uniqueness or find NULLs.

Elsewhere Bloom filters skip bigger units. RocksDB puts a filter in every SST file so a point lookup skips files that can’t hold the key; about 10 bits per key gives a false-positive rate near 1%. ClickHouse’s bloom_filter skipping index defaults to a 0.025 false-positive rate per block of granules. Parquet defines split block Bloom filters per column chunk for high-cardinality columns that min/max statistics and dictionaries can’t rule out, and PostgreSQL 14’s BRIN bloom classes keep one filter per block range.