EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction

[Chris Wilson]

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,10);
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 >= 9;
explain analyze select * from brin_test where id >= 9 and r in (1,3);

With the following results:

testing=# explain analyze select * from brin_test where id >= 9;
   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 >= 9)
   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 >= 9)
Planning Time: 0.155 ms
Execution Time: 2.133 ms
(8 rows)

testing=# explain analyze select * from brin_test where id >= 9 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 >= 9) 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 >= 9) 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.

Re: EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction

[Simon Riggs]

On Thu, 20 Jun 2019 at 16:13, Chris Wilson 
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,10);
>
> *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 >= 9;
>
> *explain* *analyze* *select* * *from* brin_test *where* id >= 9 *and*
> r *in* (1,3);
>
>
>
> With the following results:
>
>
>
> testing=# explain analyze select * from brin_test where id >= 9;
>
>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 >= 9)
>
>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 >= 9)
>
> Planning Time: 0.155 ms
>
> Execution Time: 2.133 ms
>
> (8 rows)
>
>
>
> testing=# explain analyze select * from brin_test where id >= 9 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 >= 9) 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 >= 9) 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 Riggshttp://www.2ndQuadrant.com/

PostgreSQL Solutions for the Enterprise

RE: EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction

[Chris Wilson]

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 
Sent: 20 June 2019 16:57
To: Chris Wilson 
Cc: pgsql-performa...@postgresql.org
Subject: Re: EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction

On Thu, 20 Jun 2019 at 16:13, Chris Wilson 
mailto:chris.wil...@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,10);
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 >= 9;
explain analyze select * from brin_test where id >= 9 and r in (1,3);

With the following results:

testing=# explain analyze select * from brin_test where id >= 9;
   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 >= 9)
   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 >= 9)
Planning Time: 0.155 ms
Execution Time: 2.133 ms
(8 rows)

testing=# explain analyze select * from brin_test where id >= 9 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 >= 9) 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 >= 9) 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/
PostgreSQL Solutions for the Enterprise

Re: EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction

[Simon Riggs]

On Thu, 20 Jun 2019 at 17:01, Chris Wilson 
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 Riggshttp://www.2ndQuadrant.com/

PostgreSQL Solutions for the Enterprise

Re: EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction

[Justin Pryzby]

On Thu, Jun 20, 2019 at 05:18:33PM +0100, Simon Riggs wrote:
> On Thu, 20 Jun 2019 at 17:01, Chris Wilson 
> 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 >= 9 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 >= 9) AND (r = 1))

postgres=# explain analyze select * from brin_test where id >= 9 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 >= 9) AND (r = ANY ('{1,1}'::integer[])))

postgres=# explain analyze select * from brin_test where id >= 9 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 >= 9) 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

Re: EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction

[Simon Riggs]

On Thu, 20 Jun 2019 at 17:30, Justin Pryzby  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.wil...@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 >= 9 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 >= 9) AND (r = 1))
>
> postgres=# explain analyze select * from brin_test where id >= 9 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 >= 9) AND (r = ANY ('{1,1}'::integer[])))
>
> postgres=# explain analyze select * from brin_test where id >= 9 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 >= 9) 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 Riggshttp://www.2ndQuadrant.com/

PostgreSQL Solutions for the Enterprise

Re: EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction

[Michael Lewis]

For kicks I tried the example given and got the below which seems more
expected.


explain analyze select * from brin_test where id >= 9;

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 >= 9)
  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 >= 9)
Planning Time: 0.101 ms
Execution Time: *13.485 ms*


explain analyze select * from brin_test where id >= 9 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 >= 9) 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 >= 9) AND (r = ANY ('{1,3}'::integer[])))
Planning Time: 0.089 ms
Execution Time: *1.978 ms*

Re: EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction

[Justin Pryzby]

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 >= 9)

>   ->  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 >= 9) AND (r = ANY ('{1,3}'::integer[])))

Re: EXPLAIN ANALYZE of BRIN bitmap index scan with disjunction

[Michael Lewis]

I ran both many times and got the same result. ::shrug::