[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

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.pg@gmail.com> wrote:

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.

Done for B-tree, hash, GiST, GIN, SP-GiST, and bloom indexes.
Attached patch passes tests.

Also created a commit fest entry:
https://commitfest.postgresql.org/patch/7422/

--
David Geier

On Fri, Oct 9, 2026 at 2:12 AM David Geier <geidav.pg@gmail.com> wrote:

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.

Done for B-tree, hash, GiST, GIN, SP-GiST, and bloom indexes.
Attached patch passes tests.

Also created a commit fest entry:
https://commitfest.postgresql.org/patch/7422/

--
David Geier

Hi David,

I reviewed v2 and also looked back at my local benchmark results for
the B-tree batching path.

The commit message now explains the two relevant effects well: reuse
of the current TIDBitmap page entry and amortization of per-call
overhead.

One B-tree implementation detail still seems worth changing. The copy
loop updates so->currPos.itemIndex for every TID. Using a local index
and updating itemIndex once after the copy improved the 10M-row
workload by another 2.24% in my tests. The new hash code uses the same
pattern and could use the same cleanup.

I also measured a small regression for a B-tree scan returning ten
widely spaced keys:

baseline: 33.195 us
patched: 33.569 us
delta: +0.85%

I do not consider that a blocker, but it shows that copying into a
batch is not free for tiny sparse scans.

The main new aspect of v2 is that batching is now applied to hash,
GiST, GIN, SP-GiST, and bloom as well. I do not see an obvious
semantic problem with separating exact and recheck batches, since the
TIDBitmap recheck flag is maintained at page level.

However, my measurements demonstrate the benefit for B-tree, not
necessarily for all of the newly covered access methods. Their result
ordering and heap-page locality can be quite different. I think those
additions need targeted measurements, or could be split into follow-up
patches.

A couple of smaller points:

gistScanPage() allocates both page-sized arrays even for non-bitmap
scans.
The SP-GiST buffers enlarge every scan opaque, including tuple scans.
A comment explaining the B-tree primitive-scan loop and the
BTScanPosItem copy would help.
There are a few pgindent and 80-column issues in the new code.

The B-tree batching approach still looks worthwhile to me. I would
apply the local-index cleanup there, but I would want some performance
evidence for the newly added access methods before treating the whole
v2 patch as ready.

Thanks,
Haibo

On Sat, Sep 19, 2026 at 8:35 PM Tomás Senart <ts@perfloop.ai> wrote:

The v34 Index Prefetching patch [2] changes the same loop but still passes
one TID per bitmap call. We have not tested the changes together.

I'm interested in the ideas in this thread, but I'm thinking I'll wait
to see how the amgetbatch effort shakes out first.

--
John Naylor
Amazon Web Services

Hi Haibo!

Thanks for your review.

One B-tree implementation detail still seems worth changing. The copy
loop updates so->currPos.itemIndex for every TID. Using a local index
and updating itemIndex once after the copy improved the 10M-row
workload by another 2.24% in my tests. The new hash code uses the same
pattern and could use the same cleanup.

Good point. The compiler loaded and stored itemIndex every single loop
iteration instead of keeping it in a register.

I've improved the code in v2.

I also measured a small regression for a B-tree scan returning ten
widely spaced keys:

baseline: 33.195 us
patched: 33.569 us
delta: +0.85%

I do not consider that a blocker, but it shows that copying into a
batch is not free for tiny sparse scans.

The delta is very small. Are these results stable? If so, how did you
collect them? Can you share your benchmark?

I've included your example of 10 sparsely spaces TIDs in my benchmark
but cannot see a regression. Key idea of using sparse keys is that the
B-tree will do separate index searches for each key, which results in
the worst case for the optimization: each index search returns a single
row for which we pay the extra cost of the mempcpy() without saving any
hash map lookup.

I'm doubtful that you can actually measure the extra TID memcpy()
operation given all the other things going on. I've attached my extended
benchmark script.

The main new aspect of v2 is that batching is now applied to hash,
GiST, GIN, SP-GiST, and bloom as well. I do not see an obvious
semantic problem with separating exact and recheck batches, since the
TIDBitmap recheck flag is maintained at page level.

However, my measurements demonstrate the benefit for B-tree, not
necessarily for all of the newly covered access methods. Their result
ordering and heap-page locality can be quite different. I think those
additions need targeted measurements, or could be split into follow-up
patches.

I've included all other changed index types (GIN, GIST, SP-GIST, HASH,
BLOOM) in my benchmark script. The case with few TIDs isn't that useful
for all index types. For example GIN won't do separate index searches
because the index is inverted. That means we gain for any TID count > 1.
The same for some of the other index types. But it's certainly good to test.

Here are the results for just the Bitmap Index Scan plan node. The
relative saving varies because it depends on the total runtime of the
specific index AM but the absolute savings are give or take constant
across all index AMs. This makes sense as all "many TIDs" queries match
roughly the same number of rows and hence save the same number of hash
map lookups.

query | ms_master_bis | ms_patched_bis | speedup
-------------+---------------+----------------+---------
btree-many | 170.372 | 115.071 | 1.48
btree-few | 0.006 | 0.006 | 1.00
gin-many | 342.281 | 285.198 | 1.20
gin-few | 0.001 | 0.001 | 1.00
gist-many | 827.222 | 758.613 | 1.09
gist-few | 0.449 | 0.452 | 0.99
hash-many | 296.819 | 251.802 | 1.17
hash-few | 0.004 | 0.004 | 1.00
bloom-many | 3743.758 | 3707.017 | 1.00
bloom-few | 43.989 | 42.358 | 1.03
spgist-many | 572.892 | 518.730 | 1.10
spgist-few | 0.003 | 0.003 | 1.00

And these are the results for the entire query:

query | ms_master | ms_patched | speedup
-------------+-----------+------------+---------
btree-many | 807.545 | 728.455 | 1.10
btree-few | 0.031 | 0.030 | 1.03
gin-many | 1063.716 | 971.578 | 1.09
gin-few | 0.013 | 0.013 | 1.00
gist-many | 1427.066 | 1355.651 | 1.05
gist-few | 0.470 | 0.471 | 0.99
hash-many | 1169.467 | 1127.259 | 1.03
hash-few | 0.026 | 0.026 | 1.00
bloom-many | 3961.366 | 3931.871 | 1.00
bloom-few | 49.171 | 46.512 | 1.05
spgist-many | 1196.306 | 1130.279 | 1.05
spgist-few | 0.018 | 0.017 | 1.05

Despite configuring the system for stable results, there's some noise
which is visible in the "few rows" queries but only when looking at
total query runtime. The results for just the BIS are pretty stable and
show no regression which is not within noise.

A couple of smaller points:

gistScanPage() allocates both page-sized arrays even for non-bitmap
scans.
The SP-GiST buffers enlarge every scan opaque, including tuple scans.

I think that's fine. Do you mean to imply that we should allocate these
buffers dynamically? If we think they're too big, I would rather reduce
the batch size than allocating them dynamically.

A comment explaining the B-tree primitive-scan loop and the
BTScanPosItem copy would help.

Added to explain when _bt_next() will advance to the next page. Is there
something else you had in mind?

The B-tree batching approach still looks worthwhile to me. I would
apply the local-index cleanup there, but I would want some performance
evidence for the newly added access methods before treating the whole
v2 patch as ready.

What do you mean by "local-index cleanup"?

The only other change in v2, not yet discussed in this mail, is moving
the call to tbm_add_tuples() for the residual batch to after the outer
loop in blgetbitmap(). It was incorrectly placed after the block. But if
a block has few matches there's no need to flush the batch each time.

The patch passes all tests.

--
David Geier

On Fri, Oct 9, 2026 at 9:16 PM John Naylor <johncnaylorls@gmail.com> wrote:

I'm interested in the ideas in this thread, but I'm thinking I'll wait
to see how the amgetbatch effort shakes out first.

FWIW I don't think that amgetbatch changes the picture in a way that
affects this patch. This technique *should* be orthogonal.

The changes we're making to btgetbitmap are limited to making it use
AM-generic versions of the current nbtree-private BTScanPosData and
BTScanPosItem structs. Although btgetbitmap reuses batch
infrastructure internally, to enable code sharing with lower level
scan code shared with btgetbatch, it still works in a way that
requires only one batch for the scan's duration, which is palloc'd
exactly once. In short, we're making as few changes as possible to
btgetbitmap and its performance characteristics; unlike plain scans,
bitmap scans have nothing to gain from batching.

--
Peter Geoghegan

On Sun, Oct 18, 2026 at 8:18 PM Peter Geoghegan <pg@bowt.ie> wrote:

On Fri, Oct 9, 2026 at 9:16 PM John Naylor <johncnaylorls@gmail.com> wrote:

I'm interested in the ideas in this thread, but I'm thinking I'll wait
to see how the amgetbatch effort shakes out first.

FWIW I don't think that amgetbatch changes the picture in a way that
affects this patch. This technique *should* be orthogonal.

Thanks for weighing in!

--
John Naylor
Amazon Web Services