Hi, 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]. The first TID keeps the scalar path. Remaining spans use a buffer with less than 8 KiB of payload for 8 KiB pages, allocated once per primitive scan and reused. All-singleton scans avoid allocation. No API, disk format, planner rule, or TID order changes. One-, two-, and eight-span tests found no clear target benefit from larger batches. Eight helped the largest scattered control by 0.97%; one uses less memory. On one Linux/x86-64 GCP VM, ten paired runs per query showed: 10M rows, 3M matches: 29.937 ms paired saving (14.2%). 2M rows, 200K matches: 1.766 ms paired saving (13.6%). These are whole-run mean transaction times from single-client pgbench, with forced bitmap plans. Copy and allocation costs are included. Nine controls, including scattered and single-row queries, passed a predeclared 5% practical-loss ceiling. This does not prove zero regression. All 240 core regression tests passed. Full test counts, skips, build limits, paired intervals, and reproduction instructions are attached. The scripts do not require Perfloop. Base: master 0c5d6269614e107d1d2d669f82f63f7e232b30c9 (20devel). 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 would welcome review of the batching boundary, small-scan path, and other workload cases. Thanks, Tomás [1] https://github.com/postgres/postgres/commit/f5ae3ba4828ece02bae2d16b4cbce847fbcea850 [2] https://www.postgresql.org/message-id/attachment/203026/v34-0003-Add-amgetbatch-interface-and-adopt-it-in-nbtree.patch
From 30bfe08c1c78e9eb177103cd545a3944fd24b6af Mon Sep 17 00:00:00 2001 From: Perfloop Agent <[email protected]> Date: Sat, 19 Sep 2026 01:01:30 +0200 Subject: [PATCH] Batch B-tree TIDs when building a bitmap Pass each saved leaf-page span to tbm_add_tuples in one call. This lets the existing within-call heap-block cache serve adjacent TIDs. Copy the TIDs because BTScanPosItem does not store them as a contiguous array. Keep the first TID on the scalar path. Use a separate non-inlined helper only when another saved item is available. Allocate one bounded buffer per primitive scan and reuse it for its remaining leaf-page spans. Keep scan order, tuple counts, recheck behavior, and scalar-array progression unchanged. Add regression coverage for duplicate keys in a scalar-array scan and for a small span with both scalar and batched TIDs. --- src/backend/access/nbtree/nbtree.c | 86 +++++++++++++++++++------ src/test/regress/expected/bitmapops.out | 19 ++++++ src/test/regress/sql/bitmapops.sql | 9 +++ 3 files changed, 96 insertions(+), 18 deletions(-) diff --git a/src/backend/access/nbtree/nbtree.c b/src/backend/access/nbtree/nbtree.c index 0abdd7b49f..7196b38378 100644 --- a/src/backend/access/nbtree/nbtree.c +++ b/src/backend/access/nbtree/nbtree.c @@ -284,6 +284,58 @@ btgettuple(IndexScanDesc scan, ScanDirection dir) return res; } +/* + * _btgetbitmap_batch() -- add the rest of a primitive scan in batches + * + * The caller has found a saved leaf-page span with more than one item. + * Keeping the batch state in this helper leaves the common singleton path in + * btgetbitmap with the same local state as the original scalar loop. + */ +static pg_noinline int64 +_btgetbitmap_batch(IndexScanDesc scan, TIDBitmap *tbm) +{ + BTScanOpaque so = (BTScanOpaque) scan->opaque; + int64 ntids = 0; + ItemPointerData *heapTids; + int firstItem; + int lastItem; + int nitems; + + heapTids = palloc_array(ItemPointerData, MaxTIDsPerBTreePage); + firstItem = so->currPos.itemIndex; + lastItem = so->currPos.lastItem; + nitems = lastItem - firstItem + 1; + + for (;;) + { + /* + * The heap TIDs are not contiguous in BTScanPosItem, so copy them + * into a contiguous array before adding them to the bitmap. Pass the + * saved leaf-page span in one call so tbm_add_tuples can reuse its + * current-block lookup cache within the span. + */ + for (int i = 0; i < nitems; i++) + heapTids[i] = so->currPos.items[firstItem + i].heapTid; + tbm_add_tuples(tbm, heapTids, nitems, false); + ntids += nitems; + + /* + * Mark the current page consumed before letting _bt_next move to the + * next one. + */ + so->currPos.itemIndex = lastItem; + if (!_bt_next(scan, ForwardScanDirection)) + break; + + firstItem = so->currPos.itemIndex; + lastItem = so->currPos.lastItem; + nitems = lastItem - firstItem + 1; + } + + pfree(heapTids); + return ntids; +} + /* * btgetbitmap() -- gets all matching tuples, and adds them to a bitmap */ @@ -292,7 +344,6 @@ btgetbitmap(IndexScanDesc scan, TIDBitmap *tbm) { BTScanOpaque so = (BTScanOpaque) scan->opaque; int64 ntids = 0; - ItemPointer heapTid; Assert(scan->heapRelation == NULL); @@ -302,28 +353,27 @@ btgetbitmap(IndexScanDesc scan, TIDBitmap *tbm) /* Fetch the first page & tuple */ if (_bt_first(scan, ForwardScanDirection)) { - /* Save tuple ID, and continue scanning */ - heapTid = &scan->xs_heaptid; - tbm_add_tuples(tbm, heapTid, 1, false); - ntids++; - for (;;) { - /* - * Advance to next tuple within page. This is the same as the - * easy case in _bt_next(). - */ - if (++so->currPos.itemIndex > so->currPos.lastItem) + /* Keep the current tuple on the original scalar path. */ + tbm_add_tuples(tbm, &scan->xs_heaptid, 1, false); + ntids++; + + ++so->currPos.itemIndex; + if (so->currPos.itemIndex <= so->currPos.lastItem) { - /* let _bt_next do the heavy lifting */ - if (!_bt_next(scan, ForwardScanDirection)) - break; + /* + * A later item in the current span is available, so the + * helper can consume the rest of this primitive scan in + * batches. + */ + ntids += _btgetbitmap_batch(scan, tbm); + break; } - /* Save tuple ID, and continue scanning */ - heapTid = &so->currPos.items[so->currPos.itemIndex].heapTid; - tbm_add_tuples(tbm, heapTid, 1, false); - ntids++; + /* let _bt_next do the heavy lifting */ + if (!_bt_next(scan, ForwardScanDirection)) + break; } } /* Now see if we need another primitive index scan */ diff --git a/src/test/regress/expected/bitmapops.out b/src/test/regress/expected/bitmapops.out index 64068e0469..948d8e3d81 100644 --- a/src/test/regress/expected/bitmapops.out +++ b/src/test/regress/expected/bitmapops.out @@ -44,5 +44,24 @@ SELECT count(*) FROM bmscantest WHERE a = 1 OR b = 1; 2485 (1 row) +-- Test a scalar-array B-tree bitmap scan, including duplicate index keys. +SELECT count(*) FROM bmscantest WHERE a IN (1, 2, 3); + count +------- + 3963 +(1 row) + +-- Two matches on one leaf page must include the scalar and batched TIDs. +CREATE TABLE bmscan_small (a int); +INSERT INTO bmscan_small VALUES (1), (2), (3); +CREATE INDEX bmscan_small_idx ON bmscan_small(a); +SELECT a FROM bmscan_small WHERE a BETWEEN 1 AND 2 ORDER BY a; + a +--- + 1 + 2 +(2 rows) + +DROP TABLE bmscan_small; -- clean up DROP TABLE bmscantest; diff --git a/src/test/regress/sql/bitmapops.sql b/src/test/regress/sql/bitmapops.sql index 1b175f6ff9..a56b7ea871 100644 --- a/src/test/regress/sql/bitmapops.sql +++ b/src/test/regress/sql/bitmapops.sql @@ -42,6 +42,15 @@ SELECT count(*) FROM bmscantest WHERE a = 1 AND b = 1; -- Test bitmap-or. SELECT count(*) FROM bmscantest WHERE a = 1 OR b = 1; +-- Test a scalar-array B-tree bitmap scan, including duplicate index keys. +SELECT count(*) FROM bmscantest WHERE a IN (1, 2, 3); + +-- Two matches on one leaf page must include the scalar and batched TIDs. +CREATE TABLE bmscan_small (a int); +INSERT INTO bmscan_small VALUES (1), (2), (3); +CREATE INDEX bmscan_small_idx ON bmscan_small(a); +SELECT a FROM bmscan_small WHERE a BETWEEN 1 AND 2 ORDER BY a; +DROP TABLE bmscan_small; -- clean up DROP TABLE bmscantest; base-commit: 0c5d6269614e107d1d2d669f82f63f7e232b30c9 -- 2.50.0
# B-tree bitmap contribution results The batch comparison, all nine performance controls, and native tests pass. Nothing has been sent upstream. ## Result and batch choice One saved leaf-page span is the proposed batch size. It gives material gains on both target queries. A direct comparison did not resolve a target gain from two or eight spans. This supports the smaller design; it does not prove that the sizes are equivalent or that one is a global optimum. These are new Linux/x86-64 measurements, not a new Perfloop Case verdict. Each sample is whole-run mean transaction time from single-client pgbench TPS. The tables report medians across ten samples and medians of paired savings. Thus paired savings need not equal subtraction of the displayed arm medians. Percentages are medians of paired percentage savings, not log-score changes. | Target | Baseline median | One-span median | Paired saving | Saving interval | | --- | ---: | ---: | ---: | ---: | | 10M rows; 3M matches | 214.199 ms | 183.940 ms | 29.937 ms (14.170%) | 26.914 to 34.559 ms | | 2M rows; 200K matches | 13.047 ms | 11.242 ms | 1.766 ms (13.568%) | 1.354 to 2.311 ms | Each interval uses the second-smallest through second-largest of ten paired differences. It has 97.85% distribution-free coverage for the median under the sampling assumptions. These are per-comparison intervals, not simultaneous family-wide guarantees. Both target lower bounds exceed 5% of their baseline median. Both baseline and candidate arm intervals are disjoint. ### Direct batch comparison Positive values mean the larger batch was faster than one span. | Workload | One to two: saving and interval | One to eight: saving and interval | | --- | ---: | ---: | | 10M target | −1.626 ms [−5.234, 1.268] | −2.844 ms [−8.303, 1.945] | | 2M target | 0.095 ms [−0.125, 0.763] | 0.040 ms [−0.488, 0.730] | | Scattered, 5,001 matches | −0.000169 ms [−0.008448, 0.020399] | 0.001220 ms [−0.007440, 0.012857] | | Scattered, 50,001 matches | 0.009457 ms [−0.191207, 0.105257] | −0.027808 ms [−0.084727, 0.096280] | | Scattered, 500,001 matches | 0.584 ms [−0.072, 0.924] | 0.415 ms [0.035, 0.812] | Two spans had no resolved advantage over one in these comparisons. Eight had a resolved 0.968% saving on the largest scattered control, but no resolved target advantage. We retain that result and choose the smaller one-span buffer. ### Scattered-row controls The two-million-row table has unique keys in a fixed affine permutation. Adjacent key-order row addresses share a heap block in at most 1% of pairs; the driver checks this for each match count. Each sample checks exact count and sum results and records its actual bitmap plan. | Matches | Baseline median | One-span median | Paired saving | Saving interval | | --- | ---: | ---: | ---: | ---: | | 5,001 | 0.419111 ms | 0.413778 ms | 0.006463 ms (1.546%) | −0.018708 to 0.014884 ms | | 50,001 | 4.008435 ms | 3.910858 ms | 0.103823 ms (2.623%) | 0.010240 to 0.178940 ms | | 500,001 | 43.827044 ms | 43.118676 ms | 1.028463 ms (2.344%) | 0.165227 to 1.824066 ms | All three meet the frozen 5% practical-loss ceiling. This is a bounded-loss test, not proof of zero regression. The smallest control permits a loss up to 0.020956 ms; its observed lower saving bound is −0.018708 ms. No limit was changed after results. The medium and large controls have positive intervals. ### Final six controls These use the simplified final patch, ten balanced pairs, and the frozen transaction counts. All six pass the same 5% practical-loss ceiling. | Control | Baseline median | One-span median | Paired saving | Saving interval | | --- | ---: | ---: | ---: | ---: | | Selective | 0.484509 ms | 0.445794 ms | 0.040701 ms (8.397%) | 0.031591 to 0.049871 ms | | Wide row | 65.069919 ms | 65.126999 ms | 0.201249 ms (0.308%) | −0.150761 to 0.490137 ms | | NULL-heavy | 42.896721 ms | 40.379055 ms | 2.253173 ms (5.221%) | 1.770973 to 2.764231 ms | | Non-all-visible | 5.781991 ms | 5.149950 ms | 0.665734 ms (11.695%) | 0.207774 to 0.920092 ms | | Parallel | 21.293851 ms | 20.467602 ms | 1.081984 ms (5.012%) | 0.648752 to 1.629830 ms | | Single row | 0.032231 ms | 0.032087 ms | 0.000033 ms (0.102%) | −0.000523 to 0.000637 ms | Wide-row and single-row changes are unresolved around zero; they are not claimed as speedups. Their intervals are well inside the loss ceiling. One non-all-visible sample was slower (9.456 ms patched, 5.975 ms baseline). It remains in the ten samples and interval calculation; it was not discarded. Each single-row sample is one 20,000-transaction invocation, not pooled runs. ## Exact source Base: `0c5d6269614e107d1d2d669f82f63f7e232b30c9` (PostgreSQL 20devel). The controlled arms were: - One: `07e9aaabdcf506ee683d563087fa18ac601dbb0e`. - Two: `1692e1b7ae9dc127cd6877a43d9fbd950ebec9c3`. - Eight: `7648ad2af4aa3bba4cad0eab129ff3a185a18d80`. They differ only in the matching allocation and flush-count constants. After selection, the one-span patch removes dead multi-span counters and flush branches. It also corrects the source and test comments. Final tested source: `eedde37450d5be1b56c58f1e9a7649639fedea02`. Publication commit: `30bfe08c1c78e9eb177103cd545a3944fd24b6af`. Both have tree `3783d0a38f2e34b68f3b73a45af920bb493cab9f`. Full source diff SHA-256: `01a473d7e46ef248e3e4bcd996e7eb26d5bb95d51e7fa715d9eb18ba5c8d45a7`. Patch attachment SHA-256: `ba719d4b14fd8c08a38b83e17f5d89a24eb0ac72e61928316b00209a13f56622`. The simplified patch has identical compiled bitmap code and relocations. The full stripped nbtree object differs at one byte only: a vacuum error's source-line number changes from 1535 to 1517. Its instruction size is unchanged. The final controls and native tests use the simplified source. A fresh `git am` reproduced its exact tree and source diff. ## Native checks The exact final source passed PostgreSQL's native Meson suite: 357 test groups, including all 240 core regression tests, zero failures or timeouts, and 35 explicit skips. Skips are not passes. They cover disabled injection points, opt-in expensive or network tests, and platform-specific tests. Formatting with `pgindent --check --diff` passed. Twelve checks for benchmark parsing, intervals, source binding, seed copying, workload data, and the single-invocation short control passed before measurement. ## Method and limits The host is one GCP c3d-standard-8 VM, Ubuntu 24.04, AMD EPYC 9B14, Linux 6.17.0-1022-gcp, with eight logical CPUs exposed as four cores, GCC 13.3.0, and GNU ld 2.42. Builds use Meson `debugoptimized`, TAP enabled, LLVM and documentation disabled. C assertions are not enabled. No result is claimed for another platform. Each arm starts from a copy of one stopped seed database, including its ANALYZE statistics. One server and one client run at a time. Ten fixed blocks rotate and reverse arm order. Serial server/client CPU sets are 2/3. The parallel control uses server CPUs 2,3 and client CPU 0, with two actual workers required. Affinity controls guest CPUs; it does not prove physical-host isolation. Each sample checks query results and an EXPLAIN ANALYZE bitmap plan, runs 20 warmup transactions, then one logged prepared pgbench invocation. Exact transaction counts and zero failures are checked. No samples are dropped. The metric includes client and logging overhead but excludes initial connection. It does not use cached per-transaction timestamps as elapsed-time evidence. PROTOCOL.md and the supplied scripts give counts, SQL, settings, and decisions. These queries force bitmap plans. They measure an execution-path change, not a planner improvement. One span needs less than 8 KiB of buffer payload with 8 KiB pages. It is allocated once per primitive scan that enters the helper, then reused and freed. All-singleton scans keep the scalar path. Copy and allocation costs are included; their separate effects were not measured. ## Previous evidence Perfloop's [original verified Case](https://app.perfloop.ai/t/oss/case_5kyzm389gs) reported 12.1% and 13.8% gains for an earlier two-span patch and a different per-transaction median protocol. Its measured base was `ac00b0f8bdc59152e0d5b5f97c979595e9a5e2ad` and candidate was `3c031f955fc7236712f34cc1b7371af0c6b76701`. Those are historical results, not measurements of this final one-span patch. Later managed runs were blocked, incomplete, or inconclusive. An earlier eight-span run also reported a resolved loss on a scattered workload. The new comparison uses different source and a whole-run mean metric; it does not erase or reinterpret those outcomes. Its eight-span medium control passes. The first local benchmark start failed before sampling because of an install path error. The install was corrected before the single completed campaign. ## Upstream context This uses the within-call cache from Teodor Sigaev's [f5ae3ba4828e change](https://github.com/postgres/postgres/commit/f5ae3ba4828ece02bae2d16b4cbce847fbcea850). The inspected [Index Prefetching v34 B-tree patch](https://www.postgresql.org/message-id/attachment/203026/v34-0003-Add-amgetbatch-interface-and-adopt-it-in-nbtree.patch) changes the same scan loop but still passes one TID per bitmap call. The changes overlap in source, but that patch does not implement this batching. We have not measured them together. A changed scan layout needs an adjusted patch. Upstream master `7b879c485243e61a0d4cb169717a8e96e9e875c2` has no change in the three patched files relative to the tested base. Related index-scan code has changed elsewhere. This packet does not claim a current-master build or result.
reproduce.tar.gz
Description: application/gzip
