codekingpro/portable-devtools
115k
1<?xml version="1.0" encoding="UTF-8" standalone="no"?>2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>F.7. bloom — bloom filter index access method</title><link rel="stylesheet" type="text/css" href="stylesheet.css" /><link rev="made" href="pgsql-docs@lists.postgresql.org" /><meta name="generator" content="DocBook XSL Stylesheets Vsnapshot" /><link rel="prev" href="basic-archive.html" title="F.6. basic_archive — an example WAL archive module" /><link rel="next" href="btree-gin.html" title="F.8. btree_gin — GIN operator classes with B-tree behavior" /></head><body id="docContent" class="container-fluid col-10"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="5" align="center">F.7. bloom — bloom filter index access method</th></tr><tr><td width="10%" align="left"><a accesskey="p" href="basic-archive.html" title="F.6. basic_archive — an example WAL archive module">Prev</a> </td><td width="10%" align="left"><a accesskey="u" href="contrib.html" title="Appendix F. Additional Supplied Modules and Extensions">Up</a></td><th width="60%" align="center">Appendix F. Additional Supplied Modules and Extensions</th><td width="10%" align="right"><a accesskey="h" href="index.html" title="PostgreSQL 16.3 Documentation">Home</a></td><td width="10%" align="right"> <a accesskey="n" href="btree-gin.html" title="F.8. btree_gin — GIN operator classes with B-tree behavior">Next</a></td></tr></table><hr /></div><div class="sect1" id="BLOOM"><div class="titlepage"><div><div><h2 class="title" style="clear: both">F.7. bloom — bloom filter index access method <a href="#BLOOM" class="id_link">#</a></h2></div></div></div><div class="toc"><dl class="toc"><dt><span class="sect2"><a href="bloom.html#BLOOM-PARAMETERS">F.7.1. Parameters</a></span></dt><dt><span class="sect2"><a href="bloom.html#BLOOM-EXAMPLES">F.7.2. Examples</a></span></dt><dt><span class="sect2"><a href="bloom.html#BLOOM-OPERATOR-CLASS-INTERFACE">F.7.3. Operator Class Interface</a></span></dt><dt><span class="sect2"><a href="bloom.html#BLOOM-LIMITATIONS">F.7.4. Limitations</a></span></dt><dt><span class="sect2"><a href="bloom.html#BLOOM-AUTHORS">F.7.5. Authors</a></span></dt></dl></div><a id="id-1.11.7.17.2" class="indexterm"></a><p>3 <code class="literal">bloom</code> provides an index access method based on4 <a class="ulink" href="https://en.wikipedia.org/wiki/Bloom_filter" target="_top">Bloom filters</a>.5 </p><p>6 A Bloom filter is a space-efficient data structure that is used to test7 whether an element is a member of a set. In the case of an index access8 method, it allows fast exclusion of non-matching tuples via signatures9 whose size is determined at index creation.10 </p><p>11 A signature is a lossy representation of the indexed attribute(s), and as12 such is prone to reporting false positives; that is, it may be reported13 that an element is in the set, when it is not. So index search results14 must always be rechecked using the actual attribute values from the heap15 entry. Larger signatures reduce the odds of a false positive and thus16 reduce the number of useless heap visits, but of course also make the index17 larger and hence slower to scan.18 </p><p>19 This type of index is most useful when a table has many attributes and20 queries test arbitrary combinations of them. A traditional btree index is21 faster than a bloom index, but it can require many btree indexes to support22 all possible queries where one needs only a single bloom index. Note23 however that bloom indexes only support equality queries, whereas btree24 indexes can also perform inequality and range searches.25 </p><div class="sect2" id="BLOOM-PARAMETERS"><div class="titlepage"><div><div><h3 class="title">F.7.1. Parameters <a href="#BLOOM-PARAMETERS" class="id_link">#</a></h3></div></div></div><p>26 A <code class="literal">bloom</code> index accepts the following parameters in its27 <code class="literal">WITH</code> clause:28 </p><div class="variablelist"><dl class="variablelist"><dt><span class="term"><code class="literal">length</code></span></dt><dd><p>29 Length of each signature (index entry) in bits. It is rounded up to the30 nearest multiple of <code class="literal">16</code>. The default is31 <code class="literal">80</code> bits and the maximum is <code class="literal">4096</code>.32 </p></dd></dl></div><div class="variablelist"><dl class="variablelist"><dt><span class="term"><code class="literal">col1 — col32</code></span></dt><dd><p>33 Number of bits generated for each index column. Each parameter's name34 refers to the number of the index column that it controls. The default35 is <code class="literal">2</code> bits and the maximum is <code class="literal">4095</code>.36 Parameters for index columns not actually used are ignored.37 </p></dd></dl></div></div><div class="sect2" id="BLOOM-EXAMPLES"><div class="titlepage"><div><div><h3 class="title">F.7.2. Examples <a href="#BLOOM-EXAMPLES" class="id_link">#</a></h3></div></div></div><p>38 This is an example of creating a bloom index:39 </p><pre class="programlisting">40CREATE INDEX bloomidx ON tbloom USING bloom (i1,i2,i3)41 WITH (length=80, col1=2, col2=2, col3=4);42</pre><p>43 The index is created with a signature length of 80 bits, with attributes44 i1 and i2 mapped to 2 bits, and attribute i3 mapped to 4 bits. We could45 have omitted the <code class="literal">length</code>, <code class="literal">col1</code>,46 and <code class="literal">col2</code> specifications since those have the default values.47 </p><p>48 Here is a more complete example of bloom index definition and usage, as49 well as a comparison with equivalent btree indexes. The bloom index is50 considerably smaller than the btree index, and can perform better.51 </p><pre class="programlisting">52=# CREATE TABLE tbloom AS53 SELECT54 (random() * 1000000)::int as i1,55 (random() * 1000000)::int as i2,56 (random() * 1000000)::int as i3,57 (random() * 1000000)::int as i4,58 (random() * 1000000)::int as i5,59 (random() * 1000000)::int as i660 FROM61 generate_series(1,10000000);62SELECT 1000000063</pre><p>64 A sequential scan over this large table takes a long time:65</p><pre class="programlisting">66=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;67 QUERY PLAN68------------------------------------------------------------------------------------------------------69 Seq Scan on tbloom (cost=0.00..2137.14 rows=3 width=24) (actual time=16.971..16.971 rows=0 loops=1)70 Filter: ((i2 = 898732) AND (i5 = 123451))71 Rows Removed by Filter: 10000072 Planning Time: 0.346 ms73 Execution Time: 16.988 ms74(5 rows)75</pre><p>76 </p><p>77 Even with the btree index defined the result will still be a78 sequential scan:79</p><pre class="programlisting">80=# CREATE INDEX btreeidx ON tbloom (i1, i2, i3, i4, i5, i6);81CREATE INDEX82=# SELECT pg_size_pretty(pg_relation_size('btreeidx'));83 pg_size_pretty84----------------85 3976 kB86(1 row)87=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;88 QUERY PLAN89------------------------------------------------------------------------------------------------------90 Seq Scan on tbloom (cost=0.00..2137.00 rows=2 width=24) (actual time=12.805..12.805 rows=0 loops=1)91 Filter: ((i2 = 898732) AND (i5 = 123451))92 Rows Removed by Filter: 10000093 Planning Time: 0.138 ms94 Execution Time: 12.817 ms95(5 rows)96</pre><p>97 </p><p>98 Having the bloom index defined on the table is better than btree in99 handling this type of search:100</p><pre class="programlisting">101=# CREATE INDEX bloomidx ON tbloom USING bloom (i1, i2, i3, i4, i5, i6);102CREATE INDEX103=# SELECT pg_size_pretty(pg_relation_size('bloomidx'));104 pg_size_pretty105----------------106 1584 kB107(1 row)108=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;109 QUERY PLAN110---------------------------------------------------------------------------------------------------------------------111 Bitmap Heap Scan on tbloom (cost=1792.00..1799.69 rows=2 width=24) (actual time=0.388..0.388 rows=0 loops=1)112 Recheck Cond: ((i2 = 898732) AND (i5 = 123451))113 Rows Removed by Index Recheck: 29114 Heap Blocks: exact=28115 -> Bitmap Index Scan on bloomidx (cost=0.00..1792.00 rows=2 width=0) (actual time=0.356..0.356 rows=29 loops=1)116 Index Cond: ((i2 = 898732) AND (i5 = 123451))117 Planning Time: 0.099 ms118 Execution Time: 0.408 ms119(8 rows)120</pre><p>121 </p><p>122 Now, the main problem with the btree search is that btree is inefficient123 when the search conditions do not constrain the leading index column(s).124 A better strategy for btree is to create a separate index on each column.125 Then the planner will choose something like this:126</p><pre class="programlisting">127=# CREATE INDEX btreeidx1 ON tbloom (i1);128CREATE INDEX129=# CREATE INDEX btreeidx2 ON tbloom (i2);130CREATE INDEX131=# CREATE INDEX btreeidx3 ON tbloom (i3);132CREATE INDEX133=# CREATE INDEX btreeidx4 ON tbloom (i4);134CREATE INDEX135=# CREATE INDEX btreeidx5 ON tbloom (i5);136CREATE INDEX137=# CREATE INDEX btreeidx6 ON tbloom (i6);138CREATE INDEX139=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;140 QUERY PLAN141---------------------------------------------------------------------------------------------------------------------------142 Bitmap Heap Scan on tbloom (cost=24.34..32.03 rows=2 width=24) (actual time=0.028..0.029 rows=0 loops=1)143 Recheck Cond: ((i5 = 123451) AND (i2 = 898732))144 -> BitmapAnd (cost=24.34..24.34 rows=2 width=0) (actual time=0.027..0.027 rows=0 loops=1)145 -> Bitmap Index Scan on btreeidx5 (cost=0.00..12.04 rows=500 width=0) (actual time=0.026..0.026 rows=0 loops=1)146 Index Cond: (i5 = 123451)147 -> Bitmap Index Scan on btreeidx2 (cost=0.00..12.04 rows=500 width=0) (never executed)148 Index Cond: (i2 = 898732)149 Planning Time: 0.491 ms150 Execution Time: 0.055 ms151(9 rows)152</pre><p>153 Although this query runs much faster than with either of the single154 indexes, we pay a penalty in index size. Each of the single-column155 btree indexes occupies 2 MB, so the total space needed is 12 MB,156 eight times the space used by the bloom index.157 </p></div><div class="sect2" id="BLOOM-OPERATOR-CLASS-INTERFACE"><div class="titlepage"><div><div><h3 class="title">F.7.3. Operator Class Interface <a href="#BLOOM-OPERATOR-CLASS-INTERFACE" class="id_link">#</a></h3></div></div></div><p>158 An operator class for bloom indexes requires only a hash function for the159 indexed data type and an equality operator for searching. This example160 shows the operator class definition for the <code class="type">text</code> data type:161 </p><pre class="programlisting">162CREATE OPERATOR CLASS text_ops163DEFAULT FOR TYPE text USING bloom AS164 OPERATOR 1 =(text, text),165 FUNCTION 1 hashtext(text);166</pre></div><div class="sect2" id="BLOOM-LIMITATIONS"><div class="titlepage"><div><div><h3 class="title">F.7.4. Limitations <a href="#BLOOM-LIMITATIONS" class="id_link">#</a></h3></div></div></div><p>167 </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p>168 Only operator classes for <code class="type">int4</code> and <code class="type">text</code> are169 included with the module.170 </p></li><li class="listitem"><p>171 Only the <code class="literal">=</code> operator is supported for search. But172 it is possible to add support for arrays with union and intersection173 operations in the future.174 </p></li><li class="listitem"><p>175 <code class="literal">bloom</code> access method doesn't support176 <code class="literal">UNIQUE</code> indexes.177 </p></li><li class="listitem"><p>178 <code class="literal">bloom</code> access method doesn't support searching for179 <code class="literal">NULL</code> values.180 </p></li></ul></div><p>181 </p></div><div class="sect2" id="BLOOM-AUTHORS"><div class="titlepage"><div><div><h3 class="title">F.7.5. Authors <a href="#BLOOM-AUTHORS" class="id_link">#</a></h3></div></div></div><p>182 Teodor Sigaev <code class="email"><<a class="email" href="mailto:teodor@postgrespro.ru">teodor@postgrespro.ru</a>></code>,183 Postgres Professional, Moscow, Russia184 </p><p>185 Alexander Korotkov <code class="email"><<a class="email" href="mailto:a.korotkov@postgrespro.ru">a.korotkov@postgrespro.ru</a>></code>,186 Postgres Professional, Moscow, Russia187 </p><p>188 Oleg Bartunov <code class="email"><<a class="email" href="mailto:obartunov@postgrespro.ru">obartunov@postgrespro.ru</a>></code>,189 Postgres Professional, Moscow, Russia190 </p></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="basic-archive.html" title="F.6. basic_archive — an example WAL archive module">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="contrib.html" title="Appendix F. Additional Supplied Modules and Extensions">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="btree-gin.html" title="F.8. btree_gin — GIN operator classes with B-tree behavior">Next</a></td></tr><tr><td width="40%" align="left" valign="top">F.6. basic_archive — an example WAL archive module </td><td width="20%" align="center"><a accesskey="h" href="index.html" title="PostgreSQL 16.3 Documentation">Home</a></td><td width="40%" align="right" valign="top"> F.8. btree_gin — GIN operator classes with B-tree behavior</td></tr></table></div></body></html>