From: Daniel Westermann (DWE) <daniel.westermann@dbi-services.com>
To: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Subject: Wrong example in the bloom documentation
Date: Thu, 8 Oct 2020 06:34:32 +0000
Message-ID: <GVAP278MB01028F3C84C0A724412854EDD20B0@GVAP278MB0102.CHEP278.PROD.OUTLOOK.COM> (raw)
In-Reply-To: <ZR0P278MB0122119FAE78721A694C30C8D2340@ZR0P278MB0122.CHEP278.PROD.OUTLOOK.COM>
References: <ZR0P278MB0122119FAE78721A694C30C8D2340@ZR0P278MB0122.CHEP278.PROD.OUTLOOK.COM>
Hi,
as this does not get any attention on the docs-list, once again here.
Any thoughts on this?
Regards
Daniel
From: Daniel Westermann (DWE)
Sent: Sunday, September 27, 2020 17:58
To: Pg Docs <pgsql-docs@lists.postgresql.org>
Subject: Wrong example in the bloom documentation
Hi,
I've briefly discussed this with Bruce some time ago in [1].
Replaying the example referenced in the documentation does not give a Bitmap Heap Scan on tbloom but a parallel seq scan with the default configuration:
-- tested on head
postgres=# CREATE TABLE tbloom AS
postgres-# SELECT
postgres-# (random() * 1000000)::int as i1,
postgres-# (random() * 1000000)::int as i2,
postgres-# (random() * 1000000)::int as i3,
postgres-# (random() * 1000000)::int as i4,
postgres-# (random() * 1000000)::int as i5,
postgres-# (random() * 1000000)::int as i6
postgres-# FROM
postgres-# generate_series(1,10000000);
SELECT 10000000
postgres=# CREATE INDEX bloomidx ON tbloom USING bloom (i1, i2, i3, i4, i5, i6);
CREATE INDEX
postgres=# CREATE index btreeidx ON tbloom (i1, i2, i3, i4, i5, i6);
CREATE INDEX
postgres=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------
Gather (cost=1000.00..127220.00 rows=250 width=24) (actual time=2134.851..2221.836 rows=0 loops=1)
Workers Planned: 2
Workers Launched: 2
-> Parallel Seq Scan on tbloom (cost=0.00..126195.00 rows=104 width=24) (actual time=1770.691..1770.692 rows=0 loops=3)
Filter: ((i2 = 898732) AND (i5 = 123451))
Rows Removed by Filter: 3333333
Planning Time: 0.895 ms
JIT:
Functions: 6
Options: Inlining false, Optimization false, Expressions true, Deforming true
Timing: Generation 65.512 ms, Inlining 0.000 ms, Optimization 46.328 ms, Emission 40.658 ms, Total 152.499 ms
Execution Time: 2288.056 ms
(12 rows)
As bloom was introduced in 9.6 I quickly tried with 9.6.17 and indeed for this version the example is correct:
postgres=# select version();
version
----------------------------------------------------------------------------------------------------------
PostgreSQL 9.6.17 on x86_64-pc-linux-gnu, compiled by gcc (GCC) 8.3.1 20190507 (Red Hat 8.3.1-4), 64-bit
(1 row)
postgres=# CREATE TABLE tbloom AS
postgres-# SELECT
postgres-# (random() * 1000000)::int as i1,
postgres-# (random() * 1000000)::int as i2,
postgres-# (random() * 1000000)::int as i3,
postgres-# (random() * 1000000)::int as i4,
postgres-# (random() * 1000000)::int as i5,
postgres-# (random() * 1000000)::int as i6
postgres-# FROM
postgres-# generate_series(1,10000000);
SELECT 10000000
postgres=# CREATE INDEX bloomidx ON tbloom USING bloom (i1, i2, i3, i4, i5, i6);
CREATE INDEX
postgres=# CREATE index btreeidx ON tbloom (i1, i2, i3, i4, i5, i6);
CREATE INDEX
postgres=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on tbloom (cost=178436.06..179392.83 rows=250 width=24) (actual time=2279.363..2279.363 rows=0 loops=1)
Recheck Cond: ((i2 = 898732) AND (i5 = 123451))
Rows Removed by Index Recheck: 2329
Heap Blocks: exact=2288
-> Bitmap Index Scan on bloomidx (cost=0.00..178436.00 rows=250 width=0) (actual time=994.406..994.406 rows=2329 loops=1)
Index Cond: ((i2 = 898732) AND (i5 = 123451))
Planning time: 282.059 ms
Execution time: 2286.138 ms
(8 rows)
The reason is that parallel execution is disabled by default in 9.6, and if that is turned on the plan changes there as well:
postgres=# set max_parallel_workers_per_gather = 2;
SET
postgres=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
Gather (cost=1000.00..127194.29 rows=1 width=24) (actual time=1148.047..1148.206 rows=0 loops=1)
Workers Planned: 2
Workers Launched: 2
-> Parallel Seq Scan on tbloom (cost=0.00..126194.19 rows=1 width=24) (actual time=1039.501..1039.501 rows=0 loops=3)
Filter: ((i2 = 898732) AND (i5 = 123451))
Rows Removed by Filter: 3333333
Planning time: 0.580 ms
Execution time: 1148.247 ms
(8 rows)
Starting with PostgreSQL 10 the example in the documentation is therefore wrong. Attached a proposal to fix this. The new example starts with 100x reduced rows (as suggested by Bruce in [1] and adds a note that the behavior changes as soon as parallel execution is cheaper than the index access.
Thoughts?
Regards
Daniel
[1] https://www.postgresql.org/message-id/flat/20191105231854.GA26542%40momjian.us#7859b106ce614dd953094...Attachments:bloom-doc-fix-v01.patch (text/x-patch, 8.8K) downloaddiff --git a/doc/src/sgml/bloom.sgml b/doc/src/sgml/bloom.sgmlindex 285b67b3f1..1af9b8fbab 100644--- a/doc/src/sgml/bloom.sgml+++ b/doc/src/sgml/bloom.sgml@@ -108,77 +108,81 @@ CREATE INDEX bloomidx ON tbloom USING bloom (i1,i2,i3)
(random() * 1000000)::int as i5,
(random() * 1000000)::int as i6
FROM
- generate_series(1,10000000);-SELECT 10000000+ generate_series(1,10000);+SELECT 10000
=# 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+ pg_size_pretty
----------------
- 153 MB+ 168 kB
(1 row)
=# CREATE index btreeidx ON tbloom (i1, i2, i3, i4, i5, i6);
CREATE INDEX
=# SELECT pg_size_pretty(pg_relation_size('btreeidx'));
- pg_size_pretty+ pg_size_pretty
----------------
- 387 MB+ 416 kB
(1 row)
</programlisting>
<para>
- A sequential scan over this large table takes a long time:+ Wihtout the two indexes being created, a parallel sequential scan will happen for the query below:
<programlisting>
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
- QUERY PLAN--------------------------------------------------------------------&zwsp;------------------------------------------ Seq Scan on tbloom (cost=0.00..213694.08 rows=1 width=24) (actual time=1445.438..1445.438 rows=0 loops=1)+ QUERY PLAN +---------------------------------------------------------------------------------------------------+ Seq Scan on tbloom (cost=0.00..214.00 rows=1 width=24) (actual time=2.729..2.731 rows=0 loops=1)
Filter: ((i2 = 898732) AND (i5 = 123451))
- Rows Removed by Filter: 10000000- Planning time: 0.177 ms- Execution time: 1445.473 ms+ Rows Removed by Filter: 10000+ Planning Time: 0.257 ms+ Execution Time: 2.764 ms
(5 rows)
</programlisting>
</para>
<para>
So the planner will usually select an index scan if possible.
- With a btree index, we get results like this:+ But even with the btree index defined the result will still be a sequential scan:
<programlisting>
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
- QUERY PLAN--------------------------------------------------------------------&zwsp;-------------------------------------------------------------- Index Only Scan using btreeidx on tbloom (cost=0.56..298311.96 rows=1 width=24) (actual time=445.709..445.709 rows=0 loops=1)- Index Cond: ((i2 = 898732) AND (i5 = 123451))- Heap Fetches: 0- Planning time: 0.193 ms- Execution time: 445.770 ms-(5 rows)+ QUERY PLAN +-----------------------------------------------------------------------------------------------------------------------------+ Gather (cost=1000.00..127220.00 rows=250 width=24) (actual time=2191.907..2271.154 rows=0 loops=1)+ Workers Planned: 2+ Workers Launched: 2+ -> Parallel Seq Scan on tbloom (cost=0.00..126195.00 rows=104 width=24) (actual time=1591.546..1591.547 rows=0 loops=3)+ Filter: ((i2 = 898732) AND (i5 = 123451))+ Rows Removed by Filter: 3333333+ Planning Time: 31.985 ms+ JIT:+ Functions: 6+ Options: Inlining false, Optimization false, Expressions true, Deforming true+ Timing: Generation 468.814 ms, Inlining 0.000 ms, Optimization 67.622 ms, Emission 97.406 ms, Total 633.842 ms+ Execution Time: 2745.745 ms+(12 rows)
</programlisting>
</para>
<para>
- Bloom is better than btree in handling this type of search:+ Having the bloom index defined on the table is better than btree in handling this type of search:
<programlisting>
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
- QUERY PLAN--------------------------------------------------------------------&zwsp;--------------------------------------------------------- Bitmap Heap Scan on tbloom (cost=178435.39..178439.41 rows=1 width=24) (actual time=76.698..76.698 rows=0 loops=1)+ QUERY PLAN +-------------------------------------------------------------------------------------------------------------------+ Bitmap Heap Scan on tbloom (cost=184.00..188.02 rows=1 width=24) (actual time=0.212..0.215 rows=0 loops=1)
Recheck Cond: ((i2 = 898732) AND (i5 = 123451))
- Rows Removed by Index Recheck: 2439- Heap Blocks: exact=2408- -> Bitmap Index Scan on bloomidx (cost=0.00..178435.39 rows=1 width=0) (actual time=72.455..72.455 rows=2439 loops=1)+ Rows Removed by Index Recheck: 3+ Heap Blocks: exact=3+ -> Bitmap Index Scan on bloomidx (cost=0.00..184.00 rows=1 width=0) (actual time=0.135..0.136 rows=3 loops=1)
Index Cond: ((i2 = 898732) AND (i5 = 123451))
- Planning time: 0.475 ms- Execution time: 76.778 ms+ Planning Time: 0.466 ms+ Execution Time: 0.272 ms
(8 rows)
</programlisting>
- Note the relatively large number of false positives: 2439 rows were+ Note the number of false positives: 3 rows were
selected to be visited in the heap, but none actually matched the
query. We could reduce that by specifying a larger signature length.
- In this example, creating the index with <literal>length=200</literal>- reduced the number of false positives to 55; but it doubled the index size- (to 306 MB) and ended up being slower for this query (125 ms overall).
</para>
<para>
@@ -188,24 +192,44 @@ CREATE INDEX
Then the planner will choose something like this:
<programlisting>
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
- QUERY PLAN--------------------------------------------------------------------&zwsp;------------------------------------------------------------ Bitmap Heap Scan on tbloom (cost=9.29..13.30 rows=1 width=24) (actual time=0.148..0.148 rows=0 loops=1)- Recheck Cond: ((i5 = 123451) AND (i2 = 898732))- -> BitmapAnd (cost=9.29..9.29 rows=1 width=0) (actual time=0.145..0.145 rows=0 loops=1)- -> Bitmap Index Scan on tbloom_i5_idx (cost=0.00..4.52 rows=11 width=0) (actual time=0.089..0.089 rows=10 loops=1)- Index Cond: (i5 = 123451)- -> Bitmap Index Scan on tbloom_i2_idx (cost=0.00..4.52 rows=11 width=0) (actual time=0.048..0.048 rows=8 loops=1)- Index Cond: (i2 = 898732)- Planning time: 2.049 ms- Execution time: 0.280 ms-(9 rows)+ QUERY PLAN +-----------------------------------------------------------------------------------------------------------------------+ Index Scan using tbloom_i2_idx on tbloom (cost=0.29..8.30 rows=1 width=24) (actual time=0.051..0.052 rows=0 loops=1)+ Index Cond: (i2 = 898732)+ Filter: (i5 = 123451)+ Planning Time: 0.749 ms+ Execution Time: 0.152 ms+(5 rows)
</programlisting>
Although this query runs much faster than with either of the single
indexes, we pay a large penalty in index size. Each of the single-column
- btree indexes occupies 214 MB, so the total space needed is over 1.2GB,+ btree indexes occupies 240 kB, so the total space needed is over 1.2MB,
more than 8 times the space used by the bloom index.
</para>
+ <para>+ The more rows the base tables contains, the more likely it is that parallel+ execution will kick in. Replaying the example with 10000000 instead+ of 100000 rows will show the effect:+<programlisting>+# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;+ QUERY PLAN +-----------------------------------------------------------------------------------------------------------------------------+ Gather (cost=1000.00..127220.00 rows=250 width=24) (actual time=2396.384..2494.623 rows=0 loops=1)+ Workers Planned: 2+ Workers Launched: 2+ -> Parallel Seq Scan on tbloom (cost=0.00..126195.00 rows=104 width=24) (actual time=2116.296..2116.297 rows=0 loops=3)+ Filter: ((i2 = 898732) AND (i5 = 123451))+ Rows Removed by Filter: 3333333+ Planning Time: 0.852 ms+ JIT:+ Functions: 6+ Options: Inlining false, Optimization false, Expressions true, Deforming true+ Timing: Generation 62.110 ms, Inlining 0.000 ms, Optimization 116.191 ms, Emission 104.750 ms, Total 283.051 ms+ Execution Time: 2558.945 ms+(12 rows)+</programlisting>+ In this case the bloom index as well as the btree index do not help for this query.+ </para>
</sect2>
<sect2>
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-docs@postgresql.org
Cc: daniel.westermann@dbi-services.com, pgsql-hackers@lists.postgresql.org
Subject: Re: Wrong example in the bloom documentation
In-Reply-To: <GVAP278MB01028F3C84C0A724412854EDD20B0@GVAP278MB0102.CHEP278.PROD.OUTLOOK.COM>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox