Debian Codegraph @

doc/src/sgml/bloom.sgml

raw
1 <!-- doc/src/sgml/bloom.sgml -->
2
3 <sect1 id="bloom" xreflabel="bloom">
4 <title>bloom &mdash; 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 &mdash; 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 -&gt; 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 -&gt; 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 -&gt; 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 -&gt; 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>