pg.ddx.io pgsql-performance@postgresql.org mailing list archive
help / color / mirror / Atom feedEXPLAIN ANALYZE of BRIN bitmap index scan with disjunction
12+ messages / 4 participants
[nested] [flat]
* EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction
@ 2019-06-20 15:12 Chris Wilson <chris.wilson@cantabcapital.com>
0 siblings, 2 replies; 12+ messages in thread
From: Chris Wilson @ 2019-06-20 15:12 UTC (permalink / raw)
To: pgsql-performance
Dear Postgres performance experts,
I noticed that when I added a BRIN index to a very large table, attempting to make a particular query faster, it became much slower instead. While trying to understand this, I noticed that the actual number of rows in the EXPLAIN ANALYZE output was much higher than I expected. I was able to produce a repeatable test case for this. I'm not sure if this is actually a bug, or simply that the "number of rows" means something different than I expected.
This reproducible test case is not especially slow, because I wanted to make it easy and fast to run and understand. Right now I'd just like to understand why it behaves this way.
The SQL is to create the test case is:
drop table brin_test;
create table brin_test AS SELECT generate_series as id, generate_series % 100 as r from generate_series(1,100000);
create index idx_brin_test_brin on brin_test using brin (id, r) with (pages_per_range = 32);
vacuum analyze brin_test;
And here are two queries to compare:
explain analyze select * from brin_test where id >= 90000;
explain analyze select * from brin_test where id >= 90000 and r in (1,3);
With the following results:
testing=# explain analyze select * from brin_test where id >= 90000;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on brin_test (cost=8.55..630.13 rows=10146 width=8) (actual time=0.474..1.796 rows=10001 loops=1)
Recheck Cond: (id >= 90000)
Rows Removed by Index Recheck: 3215
Heap Blocks: lossy=59
-> Bitmap Index Scan on idx_brin_test_brin (cost=0.00..6.02 rows=14286 width=0) (actual time=0.026..0.026 rows=640 loops=1)
Index Cond: (id >= 90000)
Planning Time: 0.155 ms
Execution Time: 2.133 ms
(8 rows)
testing=# explain analyze select * from brin_test where id >= 90000 and r in (1,3);
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on brin_test (cost=6.06..556.21 rows=219 width=8) (actual time=6.101..23.927 rows=200 loops=1)
Recheck Cond: ((id >= 90000) AND (r = ANY ('{1,3}'::integer[])))
Rows Removed by Index Recheck: 13016
Heap Blocks: lossy=59
-> Bitmap Index Scan on idx_brin_test_brin (cost=0.00..6.01 rows=7143 width=0) (actual time=0.038..0.038 rows=1280 loops=1)
Index Cond: ((id >= 90000) AND (r = ANY ('{1,3}'::integer[])))
Planning Time: 0.071 ms
Execution Time: 23.954 ms
(8 rows)
Note that introducing a disjunction (set of possible values) into the query doubles the number of actual rows returned, and increases the number removed by the index recheck. It looks to me as though perhaps the BRIN index does not completely support queries with a set of possible values, and executes the query multiple times (try adding more values of R to see what I mean). The execution time also increases massively.
Could anyone help me to understand what's going on here, and whether there's a bug or limitation of BRIN indexes? If it's a limitation, then the query planner does not seem to account for it, and chooses this plan even when it's a bad one (much worse than removing result rows using a filter).
Thanks, Chris.
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction
@ 2019-06-20 15:56 Simon Riggs <simon@2ndquadrant.com>
parent: Chris Wilson <chris.wilson@cantabcapital.com>
1 sibling, 1 reply; 12+ messages in thread
From: Simon Riggs @ 2019-06-20 15:56 UTC (permalink / raw)
To: Chris Wilson <chris.wilson@cantabcapital.com>; +Cc: pgsql-performance
On Thu, 20 Jun 2019 at 16:13, Chris Wilson <chris.wilson@cantabcapital.com>
wrote:
> Dear Postgres performance experts,
>
>
>
> I noticed that when I added a BRIN index to a very large table, attempting
> to make a particular query faster, it became much slower instead. While
> trying to understand this, I noticed that the actual number of rows in the
> EXPLAIN ANALYZE output was much higher than I expected. I was able to
> produce a repeatable test case for this. I’m not sure if this is actually a
> bug, or simply that the “number of rows” means something different than I
> expected.
>
>
>
> This reproducible test case is not especially slow, because I wanted to
> make it easy and fast to run and understand. Right now I’d just like to
> understand why it behaves this way.
>
>
>
> The SQL is to create the test case is:
>
>
>
> *drop* *table* brin_test;
>
> *create* *table* brin_test *AS* *SELECT* *generate_series* *as* id,
> *generate_series* % 100 *as* r *from* *generate_series*(1,100000);
>
> *create* *index* idx_brin_test_brin *on* brin_test *using* brin (id, r)
> *with* (pages_per_range = 32);
>
You've created the index on (id,r) rather than just (id)
> *vacuum* *analyze* brin_test;
>
>
>
> And here are two queries to compare:
>
>
>
> *explain* *analyze* *select* * *from* brin_test *where* id >= 90000;
>
> *explain* *analyze* *select* * *from* brin_test *where* id >= 90000 *and*
> r *in* (1,3);
>
>
>
> With the following results:
>
>
>
> testing=# explain analyze select * from brin_test where id >= 90000;
>
> QUERY PLAN
>
>
> ---------------------------------------------------------------------------------------------------------------------------------
>
> Bitmap Heap Scan on brin_test (cost=8.55..630.13 rows=10146 width=8)
> (actual time=0.474..1.796 rows=10001 loops=1)
>
> Recheck Cond: (id >= 90000)
>
> Rows Removed by Index Recheck: 3215
>
> Heap Blocks: lossy=59
>
> -> Bitmap Index Scan on idx_brin_test_brin (cost=0.00..6.02
> rows=14286 width=0) (actual time=0.026..0.026 rows=640 loops=1)
>
> Index Cond: (id >= 90000)
>
> Planning Time: 0.155 ms
>
> Execution Time: 2.133 ms
>
> (8 rows)
>
>
>
> testing=# explain analyze select * from brin_test where id >= 90000 and r
> in (1,3);
>
> QUERY PLAN
>
>
> ---------------------------------------------------------------------------------------------------------------------------------
>
> Bitmap Heap Scan on brin_test (cost=6.06..556.21 rows=219 width=8)
> (actual time=6.101..23.927 rows=200 loops=1)
>
> Recheck Cond: ((id >= 90000) AND (r = ANY ('{1,3}'::integer[])))
>
> Rows Removed by Index Recheck: 13016
>
> Heap Blocks: lossy=59
>
> -> Bitmap Index Scan on idx_brin_test_brin (cost=0.00..6.01 rows=7143
> width=0) (actual time=0.038..0.038 rows=1280 loops=1)
>
> Index Cond: ((id >= 90000) AND (r = ANY ('{1,3}'::integer[])))
>
> Planning Time: 0.071 ms
>
> Execution Time: 23.954 ms
>
> (8 rows)
>
>
>
> Note that introducing a disjunction (set of possible values) into the
> query doubles the number of actual rows returned, and increases the number
> removed by the index recheck.
>
Strange, yes.
> It looks to me as though perhaps the BRIN index does not completely
> support queries with a set of possible values, and executes the query
> multiple times (try adding more values of R to see what I mean).
>
That doesn't appear to be happening.
> The execution time also increases massively.
>
>
>
> Could anyone help me to understand what’s going on here, and whether
> there’s a bug or limitation of BRIN indexes? If it’s a limitation, then the
> query planner does not seem to account for it, and chooses this plan even
> when it’s a bad one (much worse than removing result rows using a filter).
>
The second column changes the way the index is defined. It appears there
is very little locality for the r column, so try removing it.
--
Simon Riggs http://www.2ndQuadrant.com/
<http://www.2ndquadrant.com/;
PostgreSQL Solutions for the Enterprise
^ permalink raw reply [nested|flat] 12+ messages in thread
* RE: EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction
@ 2019-06-20 16:00 Chris Wilson <chris.wilson@cantabcapital.com>
parent: Simon Riggs <simon@2ndquadrant.com>
0 siblings, 1 reply; 12+ messages in thread
From: Chris Wilson @ 2019-06-20 16:00 UTC (permalink / raw)
To: Simon Riggs <simon@2ndquadrant.com>; +Cc: pgsql-performance
Hi Simon,
I deliberately included r in the index, to demonstrate the issue that I’m seeing. I know that there is very little locality in this particular, dummy, arbitrary test case. I can try to produce a test case that has some locality, but I expect it to show exactly the same results, i.e. that the BRIN index performs much worse when we try to query on this column as well.
Thanks, Chris.
From: Simon Riggs <simon@2ndquadrant.com>
Sent: 20 June 2019 16:57
To: Chris Wilson <chris.wilson@cantabcapital.com>
Cc: pgsql-performance@postgresql.org
Subject: Re: EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction
On Thu, 20 Jun 2019 at 16:13, Chris Wilson <chris.wilson@cantabcapital.com<mailto:chris.wilson@cantabcapital.com>> wrote:
Dear Postgres performance experts,
I noticed that when I added a BRIN index to a very large table, attempting to make a particular query faster, it became much slower instead. While trying to understand this, I noticed that the actual number of rows in the EXPLAIN ANALYZE output was much higher than I expected. I was able to produce a repeatable test case for this. I’m not sure if this is actually a bug, or simply that the “number of rows” means something different than I expected.
This reproducible test case is not especially slow, because I wanted to make it easy and fast to run and understand. Right now I’d just like to understand why it behaves this way.
The SQL is to create the test case is:
drop table brin_test;
create table brin_test AS SELECT generate_series as id, generate_series % 100 as r from generate_series(1,100000);
create index idx_brin_test_brin on brin_test using brin (id, r) with (pages_per_range = 32);
You've created the index on (id,r) rather than just (id)
vacuum analyze brin_test;
And here are two queries to compare:
explain analyze select * from brin_test where id >= 90000;
explain analyze select * from brin_test where id >= 90000 and r in (1,3);
With the following results:
testing=# explain analyze select * from brin_test where id >= 90000;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on brin_test (cost=8.55..630.13 rows=10146 width=8) (actual time=0.474..1.796 rows=10001 loops=1)
Recheck Cond: (id >= 90000)
Rows Removed by Index Recheck: 3215
Heap Blocks: lossy=59
-> Bitmap Index Scan on idx_brin_test_brin (cost=0.00..6.02 rows=14286 width=0) (actual time=0.026..0.026 rows=640 loops=1)
Index Cond: (id >= 90000)
Planning Time: 0.155 ms
Execution Time: 2.133 ms
(8 rows)
testing=# explain analyze select * from brin_test where id >= 90000 and r in (1,3);
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on brin_test (cost=6.06..556.21 rows=219 width=8) (actual time=6.101..23.927 rows=200 loops=1)
Recheck Cond: ((id >= 90000) AND (r = ANY ('{1,3}'::integer[])))
Rows Removed by Index Recheck: 13016
Heap Blocks: lossy=59
-> Bitmap Index Scan on idx_brin_test_brin (cost=0.00..6.01 rows=7143 width=0) (actual time=0.038..0.038 rows=1280 loops=1)
Index Cond: ((id >= 90000) AND (r = ANY ('{1,3}'::integer[])))
Planning Time: 0.071 ms
Execution Time: 23.954 ms
(8 rows)
Note that introducing a disjunction (set of possible values) into the query doubles the number of actual rows returned, and increases the number removed by the index recheck.
Strange, yes.
It looks to me as though perhaps the BRIN index does not completely support queries with a set of possible values, and executes the query multiple times (try adding more values of R to see what I mean).
That doesn't appear to be happening.
The execution time also increases massively.
Could anyone help me to understand what’s going on here, and whether there’s a bug or limitation of BRIN indexes? If it’s a limitation, then the query planner does not seem to account for it, and chooses this plan even when it’s a bad one (much worse than removing result rows using a filter).
The second column changes the way the index is defined. It appears there is very little locality for the r column, so try removing it.
--
Simon Riggs http://www.2ndQuadrant.com/<http://www.2ndquadrant.com/;
PostgreSQL Solutions for the Enterprise
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction
@ 2019-06-20 16:18 Simon Riggs <simon@2ndquadrant.com>
parent: Chris Wilson <chris.wilson@cantabcapital.com>
0 siblings, 1 reply; 12+ messages in thread
From: Simon Riggs @ 2019-06-20 16:18 UTC (permalink / raw)
To: Chris Wilson <chris.wilson@cantabcapital.com>; +Cc: pgsql-performance
On Thu, 20 Jun 2019 at 17:01, Chris Wilson <chris.wilson@cantabcapital.com>
wrote:
> I deliberately included r in the index, to demonstrate the issue that I’m
> seeing. I know that there is very little locality in this particular,
> dummy, arbitrary test case. I can try to produce a test case that has some
> locality, but I expect it to show exactly the same results, i.e. that the
> BRIN index performs much worse when we try to query on this column as well.
>
I'm suggesting that adding the second column to the index is the source of
your problem, not adding the column to the query.
How does it perform with just the id column in the index?
--
Simon Riggs http://www.2ndQuadrant.com/
<http://www.2ndquadrant.com/;
PostgreSQL Solutions for the Enterprise
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction
@ 2019-06-20 16:30 Justin Pryzby <pryzby@telsasoft.com>
parent: Simon Riggs <simon@2ndquadrant.com>
0 siblings, 1 reply; 12+ messages in thread
From: Justin Pryzby @ 2019-06-20 16:30 UTC (permalink / raw)
To: Simon Riggs <simon@2ndquadrant.com>; +Cc: Chris Wilson <chris.wilson@cantabcapital.com>; pgsql-performance
On Thu, Jun 20, 2019 at 05:18:33PM +0100, Simon Riggs wrote:
> On Thu, 20 Jun 2019 at 17:01, Chris Wilson <chris.wilson@cantabcapital.com>
> wrote:
>
>
> > I deliberately included r in the index, to demonstrate the issue that I’m
> > seeing. I know that there is very little locality in this particular,
> > dummy, arbitrary test case. I can try to produce a test case that has some
> > locality, but I expect it to show exactly the same results, i.e. that the
> > BRIN index performs much worse when we try to query on this column as well.
> >
>
> I'm suggesting that adding the second column to the index is the source of
> your problem, not adding the column to the query.
But it *is* odd that the index returns more rows with a strictly tighter
conditions, right ?
Note, it's not an issue of rowcount estimate being confused by redundant
conditions, but real rowcount, and it returns more rows even when the
conditions are duplicative. Compare:
postgres=# explain analyze select * from brin_test where id >= 90000 and r in (1);
...
-> Bitmap Index Scan on brin_test_id_r_idx (cost=0.00..12.03 rows=28125 width=0) (actual time=0.136..0.137 rows=37120 loops=1)
Index Cond: ((id >= 90000) AND (r = 1))
postgres=# explain analyze select * from brin_test where id >= 90000 and r in (1,1);
...
-> Bitmap Index Scan on brin_test_id_r_idx (cost=0.00..12.03 rows=28125 width=0) (actual time=0.263..0.263 rows=74240 loops=1)
Index Cond: ((id >= 90000) AND (r = ANY ('{1,1}'::integer[])))
postgres=# explain analyze select * from brin_test where id >= 90000 and r in (1,1,1);
...
-> Bitmap Index Scan on brin_test_id_r_idx (cost=0.00..12.03 rows=28125 width=0) (actual time=0.387..0.387 rows=111360 loops=1)
Index Cond: ((id >= 90000) AND (r = ANY ('{1,1,1}'::integer[])))
Note, the docs say:
https://www.postgresql.org/docs/devel/indexes-multicolumn.html
|A multicolumn BRIN index can be used with query conditions that involve any
|subset of the index's columns. Like GIN and unlike B-tree or GiST, index search
|effectiveness is the same regardless of which index column(s) the query
|conditions use. The only reason to have multiple BRIN indexes instead of one
|multicolumn BRIN index on a single table is to have a different pages_per_range
|storage parameter.
Justin
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction
@ 2019-06-20 16:51 Simon Riggs <simon@2ndquadrant.com>
parent: Justin Pryzby <pryzby@telsasoft.com>
0 siblings, 1 reply; 12+ messages in thread
From: Simon Riggs @ 2019-06-20 16:51 UTC (permalink / raw)
To: Justin Pryzby <pryzby@telsasoft.com>; +Cc: Chris Wilson <chris.wilson@cantabcapital.com>; pgsql-performance
On Thu, 20 Jun 2019 at 17:30, Justin Pryzby <pryzby@telsasoft.com> wrote:
> On Thu, Jun 20, 2019 at 05:18:33PM +0100, Simon Riggs wrote:
> > On Thu, 20 Jun 2019 at 17:01, Chris Wilson <
> chris.wilson@cantabcapital.com>
> > wrote:
> >
> >
> > > I deliberately included r in the index, to demonstrate the issue that
> I’m
> > > seeing. I know that there is very little locality in this particular,
> > > dummy, arbitrary test case. I can try to produce a test case that has
> some
> > > locality, but I expect it to show exactly the same results, i.e. that
> the
> > > BRIN index performs much worse when we try to query on this column as
> well.
> > >
> >
> > I'm suggesting that adding the second column to the index is the source
> of
> > your problem, not adding the column to the query.
>
> But it *is* odd that the index returns more rows with a strictly tighter
> conditions, right ?
>
Oh, very. I was seeing this as an optimization issue rather than a bug
report.
> Note, it's not an issue of rowcount estimate being confused by redundant
> conditions, but real rowcount, and it returns more rows even when the
> conditions are duplicative. Compare:
>
> postgres=# explain analyze select * from brin_test where id >= 90000 and r
> in (1);
> ...
> -> Bitmap Index Scan on brin_test_id_r_idx (cost=0.00..12.03
> rows=28125 width=0) (actual time=0.136..0.137 rows=37120 loops=1)
> Index Cond: ((id >= 90000) AND (r = 1))
>
> postgres=# explain analyze select * from brin_test where id >= 90000 and r
> in (1,1);
> ...
> -> Bitmap Index Scan on brin_test_id_r_idx (cost=0.00..12.03
> rows=28125 width=0) (actual time=0.263..0.263 rows=74240 loops=1)
> Index Cond: ((id >= 90000) AND (r = ANY ('{1,1}'::integer[])))
>
> postgres=# explain analyze select * from brin_test where id >= 90000 and r
> in (1,1,1);
> ...
> -> Bitmap Index Scan on brin_test_id_r_idx (cost=0.00..12.03
> rows=28125 width=0) (actual time=0.387..0.387 rows=111360 loops=1)
> Index Cond: ((id >= 90000) AND (r = ANY ('{1,1,1}'::integer[])))
>
> Note, the docs say:
> https://www.postgresql.org/docs/devel/indexes-multicolumn.html
> |A multicolumn BRIN index can be used with query conditions that involve
> any
> |subset of the index's columns. Like GIN and unlike B-tree or GiST, index
> search
> |effectiveness is the same regardless of which index column(s) the query
> |conditions use. The only reason to have multiple BRIN indexes instead of
> one
> |multicolumn BRIN index on a single table is to have a different
> pages_per_range
> |storage parameter.
>
The min/max values of each column are held for each block range.
If it scans using the "r" column it will identify more block ranges to scan
than if it used the id column and hence would scan more real rows, so that
part is understandable.
The only question is why it chooses to scan on "r" and not "id", which
needs some investigation.
--
Simon Riggs http://www.2ndQuadrant.com/
<http://www.2ndquadrant.com/;
PostgreSQL Solutions for the Enterprise
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction
@ 2019-06-20 18:09 Michael Lewis <mlewis@entrata.com>
parent: Simon Riggs <simon@2ndquadrant.com>
0 siblings, 1 reply; 12+ messages in thread
From: Michael Lewis @ 2019-06-20 18:09 UTC (permalink / raw)
To: Simon Riggs <simon@2ndquadrant.com>; +Cc: Justin Pryzby <pryzby@telsasoft.com>; Chris Wilson <chris.wilson@cantabcapital.com>; pgsql-performance
For kicks I tried the example given and got the below which seems more
expected.
explain analyze select * from brin_test where id >= 90000;
Bitmap Heap Scan on brin_test (cost=5.78..627.36 rows=9861 width=8)
(actual time=0.373..7.309 rows=10001 loops=1)
Recheck Cond: (id >= 90000)
Rows Removed by Index Recheck: 3215
Heap Blocks: lossy=59
-> Bitmap Index Scan on idx_brin_test_brin (cost=0.00..3.32 rows=14286
width=0) (actual time=0.018..0.019 rows=640 loops=1)
Index Cond: (id >= 90000)
Planning Time: 0.101 ms
Execution Time: *13.485 ms*
explain analyze select * from brin_test where id >= 90000 and r in (1,3);
Bitmap Heap Scan on brin_test (cost=3.36..553.50 rows=197 width=8) (actual
time=0.390..1.829 rows=200 loops=1)
Recheck Cond: ((id >= 90000) AND (r = ANY ('{1,3}'::integer[])))
Rows Removed by Index Recheck: 13016
Heap Blocks: lossy=59
-> Bitmap Index Scan on idx_brin_test_brin (cost=0.00..3.31 rows=7143
width=0) (actual time=0.026..0.027 rows=1280 loops=1)
Index Cond: ((id >= 90000) AND (r = ANY ('{1,3}'::integer[])))
Planning Time: 0.089 ms
Execution Time: *1.978 ms*
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction
@ 2019-06-20 18:13 Justin Pryzby <pryzby@telsasoft.com>
parent: Michael Lewis <mlewis@entrata.com>
0 siblings, 1 reply; 12+ messages in thread
From: Justin Pryzby @ 2019-06-20 18:13 UTC (permalink / raw)
To: Michael Lewis <mlewis@entrata.com>; +Cc: Simon Riggs <simon@2ndquadrant.com>; Chris Wilson <chris.wilson@cantabcapital.com>; pgsql-performance
On Thu, Jun 20, 2019 at 12:09:13PM -0600, Michael Lewis wrote:
> For kicks I tried the example given and got the below which seems more
> expected.
Do you just mean that it ran faster the 2nd time ? Isn't that just due just to
cache effects ? Rerun them both back to back.
See that the "actual" rowcount of the Index Scan is higher with tigher
condition:
> -> Bitmap Index Scan on idx_brin_test_brin (cost=0.00..3.32 rows=14286 width=0) (actual time=0.018..0.019 rows=640 loops=1)
> Index Cond: (id >= 90000)
> -> Bitmap Index Scan on idx_brin_test_brin (cost=0.00..3.31 rows=7143 width=0) (actual time=0.026..0.027 rows=1280 loops=1)
> Index Cond: ((id >= 90000) AND (r = ANY ('{1,3}'::integer[])))
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction
@ 2019-06-20 18:16 Michael Lewis <mlewis@entrata.com>
parent: Justin Pryzby <pryzby@telsasoft.com>
0 siblings, 0 replies; 12+ messages in thread
From: Michael Lewis @ 2019-06-20 18:16 UTC (permalink / raw)
To: Justin Pryzby <pryzby@telsasoft.com>; +Cc: Simon Riggs <simon@2ndquadrant.com>; Chris Wilson <chris.wilson@cantabcapital.com>; pgsql-performance
I ran both many times and got the same result. ::shrug::
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction
@ 2019-06-21 09:17 Simon Riggs <simon@2ndquadrant.com>
parent: Chris Wilson <chris.wilson@cantabcapital.com>
1 sibling, 2 replies; 12+ messages in thread
From: Simon Riggs @ 2019-06-21 09:17 UTC (permalink / raw)
To: Chris Wilson <chris.wilson@cantabcapital.com>; +Cc: pgsql-performance
On Thu, 20 Jun 2019 at 16:13, Chris Wilson <chris.wilson@cantabcapital.com>
wrote:
> With the following results:
>
>
>
> testing=# explain analyze select * from brin_test where id >= 90000;
>
> QUERY PLAN
>
>
> ---------------------------------------------------------------------------------------------------------------------------------
>
> Bitmap Heap Scan on brin_test (cost=8.55..630.13 rows=10146 width=8)
> (actual time=0.474..1.796 rows=10001 loops=1)
>
> Recheck Cond: (id >= 90000)
>
> Rows Removed by Index Recheck: 3215
>
> Heap Blocks: lossy=59
>
> -> Bitmap Index Scan on idx_brin_test_brin (cost=0.00..6.02
> rows=14286 width=0) (actual time=0.026..0.026 rows=640 loops=1)
>
> Index Cond: (id >= 90000)
>
> Planning Time: 0.155 ms
>
> Execution Time: 2.133 ms
>
> (8 rows)
>
>
>
> testing=# explain analyze select * from brin_test where id >= 90000 and r
> in (1,3);
>
> QUERY PLAN
>
>
> ---------------------------------------------------------------------------------------------------------------------------------
>
> Bitmap Heap Scan on brin_test (cost=6.06..556.21 rows=219 width=8)
> (actual time=6.101..23.927 rows=200 loops=1)
>
> Recheck Cond: ((id >= 90000) AND (r = ANY ('{1,3}'::integer[])))
>
> Rows Removed by Index Recheck: 13016
>
> Heap Blocks: lossy=59
>
> -> Bitmap Index Scan on idx_brin_test_brin (cost=0.00..6.01 rows=7143
> width=0) (actual time=0.038..0.038 rows=1280 loops=1)
>
> Index Cond: ((id >= 90000) AND (r = ANY ('{1,3}'::integer[])))
>
> Planning Time: 0.071 ms
>
> Execution Time: 23.954 ms
>
> (8 rows)
>
>
>
> Note that introducing a disjunction (set of possible values) into the
> query doubles the number of actual rows returned, and increases the number
> removed by the index recheck. It looks to me as though perhaps the BRIN
> index does not completely support queries with a set of possible values,
> and executes the query multiple times (try adding more values of R to see
> what I mean). The execution time also increases massively.
>
>
>
> Could anyone help me to understand what’s going on here, and whether
> there’s a bug or limitation of BRIN indexes? If it’s a limitation, then the
> query planner does not seem to account for it, and chooses this plan even
> when it’s a bad one (much worse than removing result rows using a filter).
>
In both cases the index is returning a lossy bitmap of 59 heap blocks. The
second query is more restrictive, so the number removed by index recheck is
higher. The total of number rows returned plus the number of rows removed
by index recheck is the same in both cases.
The only weirdness is why the index reports it has returned 640 rows in one
query and 1280 in second query. Since a lossy bitmap is returned, that
figure can only be an estimate. The estimate differs between queries, but
is wrong in both cases.
--
Simon Riggs http://www.2ndQuadrant.com/
<http://www.2ndquadrant.com/;
PostgreSQL Solutions for the Enterprise
^ permalink raw reply [nested|flat] 12+ messages in thread
* RE: EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction
@ 2019-06-21 09:20 Chris Wilson <chris.wilson@cantabcapital.com>
parent: Simon Riggs <simon@2ndquadrant.com>
1 sibling, 0 replies; 12+ messages in thread
From: Chris Wilson @ 2019-06-21 09:20 UTC (permalink / raw)
To: Simon Riggs <simon@2ndquadrant.com>; +Cc: pgsql-performance
That makes perfect sense, thanks Simon!
Chris.
From: Simon Riggs <simon@2ndquadrant.com>
Sent: 21 June 2019 10:17
To: Chris Wilson <chris.wilson@cantabcapital.com>
Cc: pgsql-performance@postgresql.org
Subject: Re: EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction
On Thu, 20 Jun 2019 at 16:13, Chris Wilson <chris.wilson@cantabcapital.com<mailto:chris.wilson@cantabcapital.com>> wrote:
With the following results:
testing=# explain analyze select * from brin_test where id >= 90000;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on brin_test (cost=8.55..630.13 rows=10146 width=8) (actual time=0.474..1.796 rows=10001 loops=1)
Recheck Cond: (id >= 90000)
Rows Removed by Index Recheck: 3215
Heap Blocks: lossy=59
-> Bitmap Index Scan on idx_brin_test_brin (cost=0.00..6.02 rows=14286 width=0) (actual time=0.026..0.026 rows=640 loops=1)
Index Cond: (id >= 90000)
Planning Time: 0.155 ms
Execution Time: 2.133 ms
(8 rows)
testing=# explain analyze select * from brin_test where id >= 90000 and r in (1,3);
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on brin_test (cost=6.06..556.21 rows=219 width=8) (actual time=6.101..23.927 rows=200 loops=1)
Recheck Cond: ((id >= 90000) AND (r = ANY ('{1,3}'::integer[])))
Rows Removed by Index Recheck: 13016
Heap Blocks: lossy=59
-> Bitmap Index Scan on idx_brin_test_brin (cost=0.00..6.01 rows=7143 width=0) (actual time=0.038..0.038 rows=1280 loops=1)
Index Cond: ((id >= 90000) AND (r = ANY ('{1,3}'::integer[])))
Planning Time: 0.071 ms
Execution Time: 23.954 ms
(8 rows)
Note that introducing a disjunction (set of possible values) into the query doubles the number of actual rows returned, and increases the number removed by the index recheck. It looks to me as though perhaps the BRIN index does not completely support queries with a set of possible values, and executes the query multiple times (try adding more values of R to see what I mean). The execution time also increases massively.
Could anyone help me to understand what’s going on here, and whether there’s a bug or limitation of BRIN indexes? If it’s a limitation, then the query planner does not seem to account for it, and chooses this plan even when it’s a bad one (much worse than removing result rows using a filter).
In both cases the index is returning a lossy bitmap of 59 heap blocks. The second query is more restrictive, so the number removed by index recheck is higher. The total of number rows returned plus the number of rows removed by index recheck is the same in both cases.
The only weirdness is why the index reports it has returned 640 rows in one query and 1280 in second query. Since a lossy bitmap is returned, that figure can only be an estimate. The estimate differs between queries, but is wrong in both cases.
--
Simon Riggs http://www.2ndQuadrant.com/<http://www.2ndquadrant.com/;
PostgreSQL Solutions for the Enterprise
^ permalink raw reply [nested|flat] 12+ messages in thread
* RE: EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction
@ 2019-06-21 09:43 Chris Wilson <chris.wilson@cantabcapital.com>
parent: Simon Riggs <simon@2ndquadrant.com>
1 sibling, 0 replies; 12+ messages in thread
From: Chris Wilson @ 2019-06-21 09:43 UTC (permalink / raw)
To: Simon Riggs <simon@2ndquadrant.com>; +Cc: pgsql-performance
One possible optimisation occurred to me (that I guess we can’t currently do). If we use a larger example with some correlation in r, we can see that the time to execute the bitmap index scan is proportional to the number of items in the IN/ANY disjunction:
drop table brin_test;
create table brin_test AS SELECT g as id, ((g / 100) + (g % 100)) as r
from generate_series(1,10000000) as g;
create index idx_brin_test_brin on brin_test using brin (id, r) with (pages_per_range = 32);
vacuum analyze brin_test;
set max_parallel_workers_per_gather = 0;
/* Note that these queries return no results, so there is no time spent in bitmap heap scan, rechecking the conditions: */
explain analyze select * from brin_test where id >= 9000000 and r = any(array_fill(1, ARRAY[100]));
explain analyze select * from brin_test where id >= 9000000 and r = any(array_fill(1, ARRAY[1000]));
With the following results (long arrays elided):
testing=# explain analyze select * from brin_test where id >= 9000000 and r = any(array_fill(1, ARRAY[100]));
Bitmap Heap Scan on brin_test (cost=15.27..11781.13 rows=1031 width=8) (actual time=23.830..23.830 rows=0 loops=1)
Recheck Cond: ((id >= 9000000) AND (r = ANY ('{1,…,1}'::integer[])))
-> Bitmap Index Scan on idx_brin_test_brin (cost=0.00..15.01 rows=7231 width=0) (actual time=23.829..23.829 rows=0 loops=1)
Index Cond: ((id >= 9000000) AND (r = ANY ('{1,…,1}'::integer[])))
Planning Time: 0.092 ms
Execution Time: 23.853 ms
(6 rows)
testing=# explain analyze select * from brin_test where id >= 9000000 and r = any(array_fill(1, ARRAY[1000]));
Bitmap Heap Scan on brin_test (cost=17.59..36546.51 rows=10308 width=8) (actual time=237.748..237.748 rows=0 loops=1)
Recheck Cond: ((id >= 9000000) AND (r = ANY ('{1,…,1}'::integer[])))
-> Bitmap Index Scan on idx_brin_test_brin (cost=0.00..15.02 rows=14461 width=0) (actual time=237.747..237.747 rows=0 loops=1)
Index Cond: ((id >= 9000000) AND (r = ANY ('{1,…,1}'::integer[])))
Planning Time: 0.354 ms
Execution Time: 237.817 ms
(6 rows)
We can see that scanning 10x as many values takes 10x as long. It seems that we are checking each value in the array individually. However, since the BRIN index stores ranges of values in each block, all we care about (for the index scan) is whether the ranges overlap with the query. So we could compute the minimum and maximum in the array, and check whether each block contains any values in that range, and if so (and the other conditions are met) then emit the block for heap scanning. Does that make sense?
If I manually add those conditions to the query, it uses them and speeds up by about 1000 times:
testing=# explain analyze select * from brin_test where id >= 9000000 and r >= 1 and r <= 1 and r = any(array_fill(1, ARRAY[1000]));
Bitmap Heap Scan on brin_test (cost=15.01..19951.91 rows=1 width=8) (actual time=0.263..0.263 rows=0 loops=1)
Recheck Cond: ((id >= 9000000) AND (r >= 1) AND (r <= 1))
Filter: (r = ANY ('{1,…,1}'::integer[]))
-> Bitmap Index Scan on idx_brin_test_brin (cost=0.00..15.01 rows=7231 width=0) (actual time=0.261..0.262 rows=0 loops=1)
Index Cond: ((id >= 9000000) AND (r >= 1) AND (r <= 1))
Planning Time: 0.393 ms
Execution Time: 0.280 ms
(7 rows)
From: Chris Wilson
Sent: 21 June 2019 10:20
To: 'Simon Riggs' <simon@2ndquadrant.com>
Cc: pgsql-performance@postgresql.org
Subject: RE: EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction
That makes perfect sense, thanks Simon!
Chris.
From: Simon Riggs <simon@2ndquadrant.com<mailto:simon@2ndquadrant.com>>
Sent: 21 June 2019 10:17
To: Chris Wilson <chris.wilson@cantabcapital.com<mailto:chris.wilson@cantabcapital.com>>
Cc: pgsql-performance@postgresql.org<mailto:pgsql-performance@postgresql.org>
Subject: Re: EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction
On Thu, 20 Jun 2019 at 16:13, Chris Wilson <chris.wilson@cantabcapital.com<mailto:chris.wilson@cantabcapital.com>> wrote:
With the following results:
testing=# explain analyze select * from brin_test where id >= 90000;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on brin_test (cost=8.55..630.13 rows=10146 width=8) (actual time=0.474..1.796 rows=10001 loops=1)
Recheck Cond: (id >= 90000)
Rows Removed by Index Recheck: 3215
Heap Blocks: lossy=59
-> Bitmap Index Scan on idx_brin_test_brin (cost=0.00..6.02 rows=14286 width=0) (actual time=0.026..0.026 rows=640 loops=1)
Index Cond: (id >= 90000)
Planning Time: 0.155 ms
Execution Time: 2.133 ms
(8 rows)
testing=# explain analyze select * from brin_test where id >= 90000 and r in (1,3);
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on brin_test (cost=6.06..556.21 rows=219 width=8) (actual time=6.101..23.927 rows=200 loops=1)
Recheck Cond: ((id >= 90000) AND (r = ANY ('{1,3}'::integer[])))
Rows Removed by Index Recheck: 13016
Heap Blocks: lossy=59
-> Bitmap Index Scan on idx_brin_test_brin (cost=0.00..6.01 rows=7143 width=0) (actual time=0.038..0.038 rows=1280 loops=1)
Index Cond: ((id >= 90000) AND (r = ANY ('{1,3}'::integer[])))
Planning Time: 0.071 ms
Execution Time: 23.954 ms
(8 rows)
Note that introducing a disjunction (set of possible values) into the query doubles the number of actual rows returned, and increases the number removed by the index recheck. It looks to me as though perhaps the BRIN index does not completely support queries with a set of possible values, and executes the query multiple times (try adding more values of R to see what I mean). The execution time also increases massively.
Could anyone help me to understand what’s going on here, and whether there’s a bug or limitation of BRIN indexes? If it’s a limitation, then the query planner does not seem to account for it, and chooses this plan even when it’s a bad one (much worse than removing result rows using a filter).
In both cases the index is returning a lossy bitmap of 59 heap blocks. The second query is more restrictive, so the number removed by index recheck is higher. The total of number rows returned plus the number of rows removed by index recheck is the same in both cases.
The only weirdness is why the index reports it has returned 640 rows in one query and 1280 in second query. Since a lossy bitmap is returned, that figure can only be an estimate. The estimate differs between queries, but is wrong in both cases.
--
Simon Riggs http://www.2ndQuadrant.com/<http://www.2ndquadrant.com/;
PostgreSQL Solutions for the Enterprise
^ permalink raw reply [nested|flat] 12+ messages in thread
end of thread, other threads:[~2019-06-21 09:43 UTC | newest]
Thread overview: 12+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2019-06-20 15:12 EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction Chris Wilson <chris.wilson@cantabcapital.com>
2019-06-20 15:56 ` Simon Riggs <simon@2ndquadrant.com>
2019-06-20 16:00 ` Chris Wilson <chris.wilson@cantabcapital.com>
2019-06-20 16:18 ` Simon Riggs <simon@2ndquadrant.com>
2019-06-20 16:30 ` Justin Pryzby <pryzby@telsasoft.com>
2019-06-20 16:51 ` Simon Riggs <simon@2ndquadrant.com>
2019-06-20 18:09 ` Michael Lewis <mlewis@entrata.com>
2019-06-20 18:13 ` Justin Pryzby <pryzby@telsasoft.com>
2019-06-20 18:16 ` Michael Lewis <mlewis@entrata.com>
2019-06-21 09:17 ` Simon Riggs <simon@2ndquadrant.com>
2019-06-21 09:20 ` Chris Wilson <chris.wilson@cantabcapital.com>
2019-06-21 09:43 ` Chris Wilson <chris.wilson@cantabcapital.com>
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