F.5. bloom

# F.5. bloom

F.5.1. Parameters F.5.2. Examples F.5.3. Operator Class Interface F.5.4. Limitations F.5.5. Authors

bloom provides an index access method based on Bloom filters (opens new window).

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.

# F.5.1. Parameters

A bloom index accepts the following parameters in its WITH clause:

length

Length of each signature (index entry) in bits. It is rounded up to the nearest multiple of 16. The default is 80 bits and the maximum is 4096.

col1 — col32

Number of bits generated for each index column. Each parameter's name refers to the number of the index column that it controls. The default is 2 bits and the maximum is 4095. Parameters for index columns not actually used are ignored.

# F.5.2. Examples

This is an example of creating a bloom index:

CREATE INDEX bloomidx ON tbloom USING bloom (i1,i2,i3)
       WITH (length=80, col1=2, col2=2, col3=4);

The index is created with a signature length of 80 bits, with attributes i1 and i2 mapped to 2 bits, and attribute i3 mapped to 4 bits. We could have omitted the length, col1, and col2 specifications since those have the default values.

Here is a more complete example of bloom index definition and usage, as well as a comparison with equivalent btree indexes. The bloom index is considerably smaller than the btree index, and can perform better.

=# CREATE TABLE tbloom AS
   SELECT
     (random() * 1000000)::int as i1,
     (random() * 1000000)::int as i2,
     (random() * 1000000)::int as i3,
     (random() * 1000000)::int as i4,
     (random() * 1000000)::int as i5,
     (random() * 1000000)::int as i6
   FROM
  generate_series(1,10000000);
SELECT 10000000

A sequential scan over this large table takes a long time:

=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
                                              QUERY PLAN                                              
### F.5.3. Operator Class Interface

 An operator class for bloom indexes requires only a hash function for the indexed data type and an equality operator for searching. This example shows the operator class definition for the `text` data type:

CREATE OPERATOR CLASS text_ops DEFAULT FOR TYPE text USING bloom AS OPERATOR 1 =(text, text), FUNCTION 1 hashtext(text);


### F.5.4. Limitations

* Only operator classes for `int4` and `text` are included with the module.

* Only the `=` operator is supported for search. But it is possible to add support for arrays with union and intersection operations in the future.

* `bloom` access method doesn't support `UNIQUE` indexes.

* `bloom` access method doesn't support searching for `NULL` values.

### F.5.5. Authors

 Teodor Sigaev `<[teodor@postgrespro.ru](mailto:teodor@postgrespro.ru)>`, Postgres Professional, Moscow, Russia

 Alexander Korotkov `<[a.korotkov@postgrespro.ru](mailto:a.korotkov@postgrespro.ru)>`, Postgres Professional, Moscow, Russia

 Oleg Bartunov `<[obartunov@postgrespro.ru](mailto:obartunov@postgrespro.ru)>`, Postgres Professional, Moscow, Russia