Bitmap reuse

From: Jeff Janes <jeff(dot)janes(at)gmail(dot)com>
To: PostgreSQL Hackers <pgsql-hackers(at)lists(dot)postgresql(dot)org>
Subject: Bitmap reuse
Date: 2021-07-20 23:10:41
Message-ID: CAMkU=1zcpYOOpz-08-dA75TT+TNmPfW_O2OwHLSA34SyFiSLrA@mail.gmail.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

For some queries PostgreSQL can spend most of its time creating the exact
same bitmap over and over. For example, in the below case: (also attached
as a file because line-wrapping is going to make a mess of it)

drop table if exists foo;
create table foo (x daterange, i int, t text);
insert into foo select daterange(x::date,x::date+3), random()*3000 from
(select now()-interval '3 years'*random() as x from
generate_series(1,1e6))foo;
vacuum analyze foo;
create index ON foo using gist ( x);
create index ON foo ( i);
explain (analyze, buffers) select * from generate_series(1,20) g(i), foo
where x && '[2019-08-09,2019-08-11)' and g.i=foo.i;

QUERY PLAN

---------------------------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=170.21..3563.24 rows=33 width=54) (actual
time=1.295..24.890 rows=28 loops=1)
Buffers: shared hit=543 read=8
I/O Timings: read=0.040
-> Function Scan on generate_series g (cost=0.00..0.20 rows=20
width=4) (actual time=0.007..0.014 rows=20 loops=1)
-> Bitmap Heap Scan on foo (cost=170.21..178.13 rows=2 width=50)
(actual time=1.238..1.240 rows=1 loops=20)
Recheck Cond: ((i = g.i) AND (x &&
'[2019-08-09,2019-08-11)'::daterange))
Heap Blocks: exact=28
Buffers: shared hit=543 read=8
I/O Timings: read=0.040
-> BitmapAnd (cost=170.21..170.21 rows=2 width=0) (actual
time=1.234..1.234 rows=0 loops=20)
Buffers: shared hit=515 read=8
I/O Timings: read=0.040
-> Bitmap Index Scan on foo_i_idx (cost=0.00..6.92
rows=333 width=0) (actual time=0.031..0.031 rows=327 loops=20)
Index Cond: (i = g.i)
Buffers: shared hit=55 read=8
I/O Timings: read=0.040
-> Bitmap Index Scan on foo_x_idx (cost=0.00..161.78
rows=5000 width=0) (actual time=1.183..1.183 rows=3670 loops=20)
Index Cond: (x && '[2019-08-09,2019-08-11)'::daterange)
Buffers: shared hit=460

Note that the fast bitmap index scan is parameterized to the other side of
the nested loop, so has to be recomputed. While the slow one is
parameterized to a constant, so it could in principle just be reused.

What kind of infrastructure would be needed to detect this case and reuse
that bitmap?

Cheers,

Jeff

Attachment Content-Type Size
reuse_bitmap.sql text/plain 2.1 KB

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Tom Lane 2021-07-20 23:25:29 Re: Bitmap reuse
Previous Message Tomas Vondra 2021-07-20 23:08:40 Re: POC: GROUP BY optimization