PostgreSQL bloom index


bloom provides an index access method based on Bloom filters .

A Bloom filter is a space-efficient data structure that is used to test whether an element is a member of a set .

In the case of an index access method, it allows fast exclusion of non-matching tuples via signatures whose size is determined at index creation.

A signature is a lossy representation of the indexed attribute(s), and as such is prone to reporting false positives; that is, it may be reported that an element is in the set, when it is not.

So index search results must always be rechecked using the actual attribute values from the heap entry.

Larger signatures reduce the odds of a false positive and thus reduce the number of useless heap visits, but of course also make the index larger and hence slower to scan.

This type of index is most useful when a table has many attributes and queries test arbitrary combinations of them.

A traditional btree index is faster than a bloom index, but it can require many btree indexes to support all possible queries where one needs only a single bloom index.

Note however that bloom indexes only support equality queries, whereas btree indexes can also perform inequality and range searches.