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

Hi David,

Thanks. I'm glad the core idea holds up and extends beyond. Going forward,
it seems preferable that you treat the patches we send as purely
provisional starting points that prove an idea, as you did here.

Best,
Tomás

On Wed, Oct 7, 2026 at 7:34 AM David Geier <geidav(dot)pg(at)gmail(dot)com> wrote:

> 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