Re: [PATCH v1] Batch B-tree TIDs when building a bitmap

Hi Tomas,

> I would like review of this B-tree bitmap-scan patch. Perfloop's agent
> found and implemented it; the patch and submission packet used AI
> assistance. I am the contact.
>
> btgetbitmap calls tbm_add_tuples once per matching TID. The patch batches
> saved leaf-page spans to reuse that API's within-call heap-block cache [1].

Good find but the code is AI slop at its best. The same goes for the
repro steps. A simple .sql file would have been much easier to work with
for others.

I found the finding relevant enough to re-implement the patch myself
properly. While being at it, I've simplified the control flow
significantly. See attached patched.
The same optimization can be applied, by the way, to at least the GIST,
the GIN and the HASH index implementations. I'll do that the next days
when I find some time.

I tested the patch with a simple query that puts pressure on the Bitmap
Index Scan (BIS) by scanning through a lot of index pages and finding a
lot of matches.

CREATE TABLE table3 (col0 bigint, col1 bigint, filler char(80));
INSERT INTO table3 SELECT g, g FROM generate_series(0, 9999999) AS g;
CREATE INDEX idx_table3_col0 ON table3(col0);
VACUUM ANALYZE table3;
SET max_parallel_workers_per_gather = 0;
SET enable_seqscan = false;
SET enable_indexscan = false;
SELECT sum(col1) from table3 where col0 < 10000000;

The result is quite impressive. For that query we save ~1/3rd of the
execution time of the BIS (164 ms -> 110 ms).

master

-> Bitmap Index Scan on idx_table3_col0 (actual time=164.878..164.878
rows=10000000.00 loops=1)
Index Cond: (col0 < 10000000)
Index Searches: 1
Buffers: shared hit=1 read=27324

patched

-> Bitmap Index Scan on idx_table3_col0 (actual time=110.669..110.670
rows=10000000.00 loops=1)
Index Cond: (col0 < 10000000)
Index Searches: 1
Buffers: shared hit=1 read=27324

The patch shouldn't regress anything. If we only find a single match in
a block, the only thing we do extra is allocating some stack memory and
copying the TID. Both operations are basically free compared to all the
rest that is happening.

--
David Geier