diff options
| author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-05-04 12:15:05 +0000 |
|---|---|---|
| committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-05-04 12:15:05 +0000 |
| commit | 46651ce6fe013220ed397add242004d764fc0153 (patch) | |
| tree | 6e5299f990f88e60174a1d3ae6e48eedd2688b2b /doc/src/sgml/html/bloom.html | |
| parent | Initial commit. (diff) | |
| download | postgresql-14-46651ce6fe013220ed397add242004d764fc0153.tar.xz postgresql-14-46651ce6fe013220ed397add242004d764fc0153.zip | |
Adding upstream version 14.5.upstream/14.5upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'doc/src/sgml/html/bloom.html')
| -rw-r--r-- | doc/src/sgml/html/bloom.html | 190 |
1 files changed, 190 insertions, 0 deletions
diff --git a/doc/src/sgml/html/bloom.html b/doc/src/sgml/html/bloom.html new file mode 100644 index 0000000..18f6e95 --- /dev/null +++ b/doc/src/sgml/html/bloom.html @@ -0,0 +1,190 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!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.5. bloom</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="auto-explain.html" title="F.4. auto_explain" /><link rel="next" href="btree-gin.html" title="F.6. btree_gin" /></head><body id="docContent" class="container-fluid col-10"><div xmlns="http://www.w3.org/TR/xhtml1/transitional" class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="5" align="center">F.5. bloom</th></tr><tr><td width="10%" align="left"><a accesskey="p" href="auto-explain.html" title="F.4. auto_explain">Prev</a> </td><td width="10%" align="left"><a accesskey="u" href="contrib.html" title="Appendix F. Additional Supplied Modules">Up</a></td><th width="60%" align="center">Appendix F. Additional Supplied Modules</th><td width="10%" align="right"><a accesskey="h" href="index.html" title="PostgreSQL 14.5 Documentation">Home</a></td><td width="10%" align="right"> <a accesskey="n" href="btree-gin.html" title="F.6. btree_gin">Next</a></td></tr></table><hr></hr></div><div class="sect1" id="BLOOM"><div class="titlepage"><div><div><h2 class="title" style="clear: both">F.5. bloom</h2></div></div></div><div class="toc"><dl class="toc"><dt><span class="sect2"><a href="bloom.html#id-1.11.7.14.7">F.5.1. Parameters</a></span></dt><dt><span class="sect2"><a href="bloom.html#id-1.11.7.14.8">F.5.2. Examples</a></span></dt><dt><span class="sect2"><a href="bloom.html#id-1.11.7.14.9">F.5.3. Operator Class Interface</a></span></dt><dt><span class="sect2"><a href="bloom.html#id-1.11.7.14.10">F.5.4. Limitations</a></span></dt><dt><span class="sect2"><a href="bloom.html#id-1.11.7.14.11">F.5.5. Authors</a></span></dt></dl></div><a id="id-1.11.7.14.2" class="indexterm"></a><p> + <code class="literal">bloom</code> provides an index access method based on + <a class="ulink" href="https://en.wikipedia.org/wiki/Bloom_filter" target="_top">Bloom filters</a>. + </p><p> + 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. + </p><p> + 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. + </p><p> + 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. + </p><div class="sect2" id="id-1.11.7.14.7"><div class="titlepage"><div><div><h3 class="title">F.5.1. Parameters</h3></div></div></div><p> + A <code class="literal">bloom</code> index accepts the following parameters in its + <code class="literal">WITH</code> clause: + </p><div class="variablelist"><dl class="variablelist"><dt><span class="term"><code class="literal">length</code></span></dt><dd><p> + Length of each signature (index entry) in bits. It is rounded up to the + nearest multiple of <code class="literal">16</code>. The default is + <code class="literal">80</code> bits and the maximum is <code class="literal">4096</code>. + </p></dd></dl></div><div class="variablelist"><dl class="variablelist"><dt><span class="term"><code class="literal">col1 — col32</code></span></dt><dd><p> + 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 <code class="literal">2</code> bits and the maximum is <code class="literal">4095</code>. + Parameters for index columns not actually used are ignored. + </p></dd></dl></div></div><div class="sect2" id="id-1.11.7.14.8"><div class="titlepage"><div><div><h3 class="title">F.5.2. Examples</h3></div></div></div><p> + This is an example of creating a bloom index: + </p><pre class="programlisting"> +CREATE INDEX bloomidx ON tbloom USING bloom (i1,i2,i3) + WITH (length=80, col1=2, col2=2, col3=4); +</pre><p> + 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 <code class="literal">length</code>, <code class="literal">col1</code>, + and <code class="literal">col2</code> specifications since those have the default values. + </p><p> + 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. + </p><pre class="programlisting"> +=# 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 +</pre><p> + A sequential scan over this large table takes a long time: +</p><pre class="programlisting"> +=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451; + QUERY PLAN +------------------------------------------------------------------------------------------------------ + Seq Scan on tbloom (cost=0.00..2137.14 rows=3 width=24) (actual time=16.971..16.971 rows=0 loops=1) + Filter: ((i2 = 898732) AND (i5 = 123451)) + Rows Removed by Filter: 100000 + Planning Time: 0.346 ms + Execution Time: 16.988 ms +(5 rows) +</pre><p> + </p><p> + Even with the btree index defined the result will still be a + sequential scan: +</p><pre class="programlisting"> +=# CREATE INDEX btreeidx ON tbloom (i1, i2, i3, i4, i5, i6); +CREATE INDEX +=# SELECT pg_size_pretty(pg_relation_size('btreeidx')); + pg_size_pretty +---------------- + 3976 kB +(1 row) +=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451; + QUERY PLAN +------------------------------------------------------------------------------------------------------ + Seq Scan on tbloom (cost=0.00..2137.00 rows=2 width=24) (actual time=12.805..12.805 rows=0 loops=1) + Filter: ((i2 = 898732) AND (i5 = 123451)) + Rows Removed by Filter: 100000 + Planning Time: 0.138 ms + Execution Time: 12.817 ms +(5 rows) +</pre><p> + </p><p> + Having the bloom index defined on the table is better than btree in + handling this type of search: +</p><pre class="programlisting"> +=# CREATE INDEX bloomidx ON tbloom USING bloom (i1, i2, i3, i4, i5, i6); +CREATE INDEX +=# SELECT pg_size_pretty(pg_relation_size('bloomidx')); + pg_size_pretty +---------------- + 1584 kB +(1 row) +=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451; + QUERY PLAN +--------------------------------------------------------------------------------------------------------------------- + Bitmap Heap Scan on tbloom (cost=1792.00..1799.69 rows=2 width=24) (actual time=0.388..0.388 rows=0 loops=1) + Recheck Cond: ((i2 = 898732) AND (i5 = 123451)) + Rows Removed by Index Recheck: 29 + Heap Blocks: exact=28 + -> Bitmap Index Scan on bloomidx (cost=0.00..1792.00 rows=2 width=0) (actual time=0.356..0.356 rows=29 loops=1) + Index Cond: ((i2 = 898732) AND (i5 = 123451)) + Planning Time: 0.099 ms + Execution Time: 0.408 ms +(8 rows) +</pre><p> + </p><p> + Now, the main problem with the btree search is that btree is inefficient + when the search conditions do not constrain the leading index column(s). + A better strategy for btree is to create a separate index on each column. + Then the planner will choose something like this: +</p><pre class="programlisting"> +=# CREATE INDEX btreeidx1 ON tbloom (i1); +CREATE INDEX +=# CREATE INDEX btreeidx2 ON tbloom (i2); +CREATE INDEX +=# CREATE INDEX btreeidx3 ON tbloom (i3); +CREATE INDEX +=# CREATE INDEX btreeidx4 ON tbloom (i4); +CREATE INDEX +=# CREATE INDEX btreeidx5 ON tbloom (i5); +CREATE INDEX +=# CREATE INDEX btreeidx6 ON tbloom (i6); +CREATE INDEX +=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451; + QUERY PLAN +--------------------------------------------------------------------------------------------------------------------------- + Bitmap Heap Scan on tbloom (cost=24.34..32.03 rows=2 width=24) (actual time=0.028..0.029 rows=0 loops=1) + Recheck Cond: ((i5 = 123451) AND (i2 = 898732)) + -> BitmapAnd (cost=24.34..24.34 rows=2 width=0) (actual time=0.027..0.027 rows=0 loops=1) + -> Bitmap Index Scan on btreeidx5 (cost=0.00..12.04 rows=500 width=0) (actual time=0.026..0.026 rows=0 loops=1) + Index Cond: (i5 = 123451) + -> Bitmap Index Scan on btreeidx2 (cost=0.00..12.04 rows=500 width=0) (never executed) + Index Cond: (i2 = 898732) + Planning Time: 0.491 ms + Execution Time: 0.055 ms +(9 rows) +</pre><p> + Although this query runs much faster than with either of the single + indexes, we pay a penalty in index size. Each of the single-column + btree indexes occupies 2 MB, so the total space needed is 12 MB, + eight times the space used by the bloom index. + </p></div><div class="sect2" id="id-1.11.7.14.9"><div class="titlepage"><div><div><h3 class="title">F.5.3. Operator Class Interface</h3></div></div></div><p> + 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 <code class="type">text</code> data type: + </p><pre class="programlisting"> +CREATE OPERATOR CLASS text_ops +DEFAULT FOR TYPE text USING bloom AS + OPERATOR 1 =(text, text), + FUNCTION 1 hashtext(text); +</pre></div><div class="sect2" id="id-1.11.7.14.10"><div class="titlepage"><div><div><h3 class="title">F.5.4. Limitations</h3></div></div></div><p> + </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p> + Only operator classes for <code class="type">int4</code> and <code class="type">text</code> are + included with the module. + </p></li><li class="listitem"><p> + Only the <code class="literal">=</code> operator is supported for search. But + it is possible to add support for arrays with union and intersection + operations in the future. + </p></li><li class="listitem"><p> + <code class="literal">bloom</code> access method doesn't support + <code class="literal">UNIQUE</code> indexes. + </p></li><li class="listitem"><p> + <code class="literal">bloom</code> access method doesn't support searching for + <code class="literal">NULL</code> values. + </p></li></ul></div><p> + </p></div><div class="sect2" id="id-1.11.7.14.11"><div class="titlepage"><div><div><h3 class="title">F.5.5. Authors</h3></div></div></div><p> + Teodor Sigaev <code class="email"><<a class="email" href="mailto:teodor@postgrespro.ru">teodor@postgrespro.ru</a>></code>, + Postgres Professional, Moscow, Russia + </p><p> + Alexander Korotkov <code class="email"><<a class="email" href="mailto:a.korotkov@postgrespro.ru">a.korotkov@postgrespro.ru</a>></code>, + Postgres Professional, Moscow, Russia + </p><p> + Oleg Bartunov <code class="email"><<a class="email" href="mailto:obartunov@postgrespro.ru">obartunov@postgrespro.ru</a>></code>, + Postgres Professional, Moscow, Russia + </p></div></div><div xmlns="http://www.w3.org/TR/xhtml1/transitional" class="navfooter"><hr></hr><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="auto-explain.html" title="F.4. auto_explain">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="contrib.html" title="Appendix F. Additional Supplied Modules">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="btree-gin.html" title="F.6. btree_gin">Next</a></td></tr><tr><td width="40%" align="left" valign="top">F.4. auto_explain </td><td width="20%" align="center"><a accesskey="h" href="index.html" title="PostgreSQL 14.5 Documentation">Home</a></td><td width="40%" align="right" valign="top"> F.6. btree_gin</td></tr></table></div></body></html>
\ No newline at end of file |