| 1 |
<!-- doc/src/sgml/bloom.sgml --> |
| 2 |
|
| 3 |
<sect1 id="bloom" xreflabel="bloom"> |
| 4 |
<title>bloom — bloom filter index access method</title> |
| 5 |
|
| 6 |
<indexterm zone="bloom"> |
| 7 |
<primary>bloom</primary> |
| 8 |
</indexterm> |
| 9 |
|
| 10 |
<para> |
| 11 |
<literal>bloom</literal> provides an index access method based on |
| 12 |
<ulink url="https://en.wikipedia.org/wiki/Bloom_filter">Bloom filters</ulink>. |
| 13 |
</para> |
| 14 |
|
| 15 |
<para> |
| 16 |
A Bloom filter is a space-efficient data structure that is used to test |
| 17 |
whether an element is a member of a set. In the case of an index access |
| 18 |
method, it allows fast exclusion of non-matching tuples via signatures |
| 19 |
whose size is determined at index creation. |
| 20 |
</para> |
| 21 |
|
| 22 |
<para> |
| 23 |
A signature is a lossy representation of the indexed attribute(s), and as |
| 24 |
such is prone to reporting false positives; that is, it may be reported |
| 25 |
that an element is in the set, when it is not. So index search results |
| 26 |
must always be rechecked using the actual attribute values from the heap |
| 27 |
entry. Larger signatures reduce the odds of a false positive and thus |
| 28 |
reduce the number of useless heap visits, but of course also make the index |
| 29 |
larger and hence slower to scan. |
| 30 |
</para> |
| 31 |
|
| 32 |
<para> |
| 33 |
This type of index is most useful when a table has many attributes and |
| 34 |
queries test arbitrary combinations of them. A traditional btree index is |
| 35 |
faster than a bloom index, but it can require many btree indexes to support |
| 36 |
all possible queries where one needs only a single bloom index. Note |
| 37 |
however that bloom indexes only support equality queries, whereas btree |
| 38 |
indexes can also perform inequality and range searches. |
| 39 |
</para> |
| 40 |
|
| 41 |
<sect2 id="bloom-parameters"> |
| 42 |
<title>Parameters</title> |
| 43 |
|
| 44 |
<para> |
| 45 |
A <literal>bloom</literal> index accepts the following parameters in its |
| 46 |
<literal>WITH</literal> clause: |
| 47 |
</para> |
| 48 |
|
| 49 |
<variablelist> |
| 50 |
<varlistentry> |
| 51 |
<term><literal>length</literal></term> |
| 52 |
<listitem> |
| 53 |
<para> |
| 54 |
Length of each signature (index entry) in bits. It is rounded up to the |
| 55 |
nearest multiple of <literal>16</literal>. The default is |
| 56 |
<literal>80</literal> bits and the maximum is <literal>4096</literal>. |
| 57 |
</para> |
| 58 |
</listitem> |
| 59 |
</varlistentry> |
| 60 |
</variablelist> |
| 61 |
<variablelist> |
| 62 |
<varlistentry> |
| 63 |
<term><literal>col1 — col32</literal></term> |
| 64 |
<listitem> |
| 65 |
<para> |
| 66 |
Number of bits generated for each index column. Each parameter's name |
| 67 |
refers to the number of the index column that it controls. The default |
| 68 |
is <literal>2</literal> bits and the maximum is <literal>4095</literal>. |
| 69 |
Parameters for index columns not actually used are ignored. |
| 70 |
</para> |
| 71 |
</listitem> |
| 72 |
</varlistentry> |
| 73 |
</variablelist> |
| 74 |
</sect2> |
| 75 |
|
| 76 |
<sect2 id="bloom-examples"> |
| 77 |
<title>Examples</title> |
| 78 |
|
| 79 |
<para> |
| 80 |
This is an example of creating a bloom index: |
| 81 |
</para> |
| 82 |
|
| 83 |
<programlisting> |
| 84 |
CREATE INDEX bloomidx ON tbloom USING bloom (i1,i2,i3) |
| 85 |
WITH (length=80, col1=2, col2=2, col3=4); |
| 86 |
</programlisting> |
| 87 |
|
| 88 |
<para> |
| 89 |
The index is created with a signature length of 80 bits, with attributes |
| 90 |
i1 and i2 mapped to 2 bits, and attribute i3 mapped to 4 bits. We could |
| 91 |
have omitted the <literal>length</literal>, <literal>col1</literal>, |
| 92 |
and <literal>col2</literal> specifications since those have the default values. |
| 93 |
</para> |
| 94 |
|
| 95 |
<para> |
| 96 |
Here is a more complete example of bloom index definition and usage, as |
| 97 |
well as a comparison with equivalent btree indexes. The bloom index is |
| 98 |
considerably smaller than the btree index, and can perform better. |
| 99 |
</para> |
| 100 |
|
| 101 |
<programlisting> |
| 102 |
=# CREATE TABLE tbloom AS |
| 103 |
SELECT |
| 104 |
(random() * 1000000)::int as i1, |
| 105 |
(random() * 1000000)::int as i2, |
| 106 |
(random() * 1000000)::int as i3, |
| 107 |
(random() * 1000000)::int as i4, |
| 108 |
(random() * 1000000)::int as i5, |
| 109 |
(random() * 1000000)::int as i6 |
| 110 |
FROM |
| 111 |
generate_series(1,10000000); |
| 112 |
SELECT 10000000 |
| 113 |
</programlisting> |
| 114 |
|
| 115 |
<para> |
| 116 |
A sequential scan over this large table takes a long time: |
| 117 |
<programlisting> |
| 118 |
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451; |
| 119 |
QUERY PLAN |
| 120 |
-------------------------------------------------------------------&zwsp;----------------------------------- |
| 121 |
Seq Scan on tbloom (cost=0.00..213744.00 rows=250 width=24) (actual time=357.059..357.059 rows=0.00 loops=1) |
| 122 |
Filter: ((i2 = 898732) AND (i5 = 123451)) |
| 123 |
Rows Removed by Filter: 10000000 |
| 124 |
Buffers: shared hit=63744 |
| 125 |
Planning Time: 0.346 ms |
| 126 |
Execution Time: 357.076 ms |
| 127 |
(6 rows) |
| 128 |
</programlisting> |
| 129 |
</para> |
| 130 |
|
| 131 |
<para> |
| 132 |
Even with the btree index defined the result will still be a |
| 133 |
sequential scan: |
| 134 |
<programlisting> |
| 135 |
=# CREATE INDEX btreeidx ON tbloom (i1, i2, i3, i4, i5, i6); |
| 136 |
CREATE INDEX |
| 137 |
=# SELECT pg_size_pretty(pg_relation_size('btreeidx')); |
| 138 |
pg_size_pretty |
| 139 |
---------------- |
| 140 |
386 MB |
| 141 |
(1 row) |
| 142 |
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451; |
| 143 |
QUERY PLAN |
| 144 |
-------------------------------------------------------------------&zwsp;----------------------------------- |
| 145 |
Seq Scan on tbloom (cost=0.00..213744.00 rows=2 width=24) (actual time=351.016..351.017 rows=0.00 loops=1) |
| 146 |
Filter: ((i2 = 898732) AND (i5 = 123451)) |
| 147 |
Rows Removed by Filter: 10000000 |
| 148 |
Buffers: shared hit=63744 |
| 149 |
Planning Time: 0.138 ms |
| 150 |
Execution Time: 351.035 ms |
| 151 |
(6 rows) |
| 152 |
</programlisting> |
| 153 |
</para> |
| 154 |
|
| 155 |
<para> |
| 156 |
Having the bloom index defined on the table is better than btree in |
| 157 |
handling this type of search: |
| 158 |
<programlisting> |
| 159 |
=# CREATE INDEX bloomidx ON tbloom USING bloom (i1, i2, i3, i4, i5, i6); |
| 160 |
CREATE INDEX |
| 161 |
=# SELECT pg_size_pretty(pg_relation_size('bloomidx')); |
| 162 |
pg_size_pretty |
| 163 |
---------------- |
| 164 |
153 MB |
| 165 |
(1 row) |
| 166 |
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451; |
| 167 |
QUERY PLAN |
| 168 |
-------------------------------------------------------------------&zwsp;-------------------------------------------------- |
| 169 |
Bitmap Heap Scan on tbloom (cost=1792.00..1799.69 rows=2 width=24) (actual time=22.605..22.606 rows=0.00 loops=1) |
| 170 |
Recheck Cond: ((i2 = 898732) AND (i5 = 123451)) |
| 171 |
Rows Removed by Index Recheck: 2300 |
| 172 |
Heap Blocks: exact=2256 |
| 173 |
Buffers: shared hit=21864 |
| 174 |
-> Bitmap Index Scan on bloomidx (cost=0.00..178436.00 rows=1 width=0) (actual time=20.005..20.005 rows=2300.00 loops=1) |
| 175 |
Index Cond: ((i2 = 898732) AND (i5 = 123451)) |
| 176 |
Index Searches: 1 |
| 177 |
Buffers: shared hit=19608 |
| 178 |
Planning Time: 0.099 ms |
| 179 |
Execution Time: 22.632 ms |
| 180 |
(11 rows) |
| 181 |
</programlisting> |
| 182 |
</para> |
| 183 |
|
| 184 |
<para> |
| 185 |
Now, the main problem with the btree search is that btree is inefficient |
| 186 |
when the search conditions do not constrain the leading index column(s). |
| 187 |
A better strategy for btree is to create a separate index on each column. |
| 188 |
Then the planner will choose something like this: |
| 189 |
<programlisting> |
| 190 |
=# CREATE INDEX btreeidx1 ON tbloom (i1); |
| 191 |
CREATE INDEX |
| 192 |
=# CREATE INDEX btreeidx2 ON tbloom (i2); |
| 193 |
CREATE INDEX |
| 194 |
=# CREATE INDEX btreeidx3 ON tbloom (i3); |
| 195 |
CREATE INDEX |
| 196 |
=# CREATE INDEX btreeidx4 ON tbloom (i4); |
| 197 |
CREATE INDEX |
| 198 |
=# CREATE INDEX btreeidx5 ON tbloom (i5); |
| 199 |
CREATE INDEX |
| 200 |
=# CREATE INDEX btreeidx6 ON tbloom (i6); |
| 201 |
CREATE INDEX |
| 202 |
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451; |
| 203 |
QUERY PLAN |
| 204 |
-------------------------------------------------------------------&zwsp;-------------------------------------------------------- |
| 205 |
Bitmap Heap Scan on tbloom (cost=9.29..13.30 rows=1 width=24) (actual time=0.032..0.033 rows=0.00 loops=1) |
| 206 |
Recheck Cond: ((i5 = 123451) AND (i2 = 898732)) |
| 207 |
Buffers: shared read=6 |
| 208 |
-> BitmapAnd (cost=9.29..9.29 rows=1 width=0) (actual time=0.047..0.047 rows=0.00 loops=1) |
| 209 |
Buffers: shared hit=6 |
| 210 |
-> Bitmap Index Scan on btreeidx5 (cost=0.00..4.52 rows=11 width=0) (actual time=0.026..0.026 rows=7.00 loops=1) |
| 211 |
Index Cond: (i5 = 123451) |
| 212 |
Index Searches: 1 |
| 213 |
Buffers: shared hit=3 |
| 214 |
-> Bitmap Index Scan on btreeidx2 (cost=0.00..4.52 rows=11 width=0) (actual time=0.007..0.007 rows=8.00 loops=1) |
| 215 |
Index Cond: (i2 = 898732) |
| 216 |
Index Searches: 1 |
| 217 |
Buffers: shared hit=3 |
| 218 |
Planning Time: 0.264 ms |
| 219 |
Execution Time: 0.047 ms |
| 220 |
(15 rows) |
| 221 |
</programlisting> |
| 222 |
Although this query runs much faster than with either of the single |
| 223 |
indexes, we pay a penalty in index size. Each of the single-column |
| 224 |
btree indexes occupies 88.5 MB, so the total space needed is 531 MB, |
| 225 |
over three times the space used by the bloom index. |
| 226 |
</para> |
| 227 |
</sect2> |
| 228 |
|
| 229 |
<sect2 id="bloom-operator-class-interface"> |
| 230 |
<title>Operator Class Interface</title> |
| 231 |
|
| 232 |
<para> |
| 233 |
An operator class for bloom indexes requires only a hash function for the |
| 234 |
indexed data type and an equality operator for searching. This example |
| 235 |
shows the operator class definition for the <type>text</type> data type: |
| 236 |
</para> |
| 237 |
|
| 238 |
<programlisting> |
| 239 |
CREATE OPERATOR CLASS text_ops |
| 240 |
DEFAULT FOR TYPE text USING bloom AS |
| 241 |
OPERATOR 1 =(text, text), |
| 242 |
FUNCTION 1 hashtext(text); |
| 243 |
</programlisting> |
| 244 |
</sect2> |
| 245 |
|
| 246 |
<sect2 id="bloom-limitations"> |
| 247 |
<title>Limitations</title> |
| 248 |
<para> |
| 249 |
<itemizedlist> |
| 250 |
<listitem> |
| 251 |
<para> |
| 252 |
Only operator classes for <type>int4</type> and <type>text</type> are |
| 253 |
included with the module. |
| 254 |
</para> |
| 255 |
</listitem> |
| 256 |
|
| 257 |
<listitem> |
| 258 |
<para> |
| 259 |
Only the <literal>=</literal> operator is supported for search. But |
| 260 |
it is possible to add support for arrays with union and intersection |
| 261 |
operations in the future. |
| 262 |
</para> |
| 263 |
</listitem> |
| 264 |
|
| 265 |
<listitem> |
| 266 |
<para> |
| 267 |
<literal>bloom</literal> access method doesn't support |
| 268 |
<literal>UNIQUE</literal> indexes. |
| 269 |
</para> |
| 270 |
</listitem> |
| 271 |
|
| 272 |
<listitem> |
| 273 |
<para> |
| 274 |
<literal>bloom</literal> access method doesn't support searching for |
| 275 |
<literal>NULL</literal> values. |
| 276 |
</para> |
| 277 |
</listitem> |
| 278 |
</itemizedlist> |
| 279 |
</para> |
| 280 |
</sect2> |
| 281 |
|
| 282 |
<sect2 id="bloom-authors"> |
| 283 |
<title>Authors</title> |
| 284 |
|
| 285 |
<para> |
| 286 |
Teodor Sigaev <email>[email protected]</email>, |
| 287 |
Postgres Professional, Moscow, Russia |
| 288 |
</para> |
| 289 |
|
| 290 |
<para> |
| 291 |
Alexander Korotkov <email>[email protected]</email>, |
| 292 |
Postgres Professional, Moscow, Russia |
| 293 |
</para> |
| 294 |
|
| 295 |
<para> |
| 296 |
Oleg Bartunov <email>[email protected]</email>, |
| 297 |
Postgres Professional, Moscow, Russia |
| 298 |
</para> |
| 299 |
</sect2> |
| 300 |
|
| 301 |
</sect1> |