Batch B-tree leaf-page TIDs into TIDBitmap

perfloop/postgres · POOR DATA LOCALITY

https://perfloop.ai/t/oss/case_5kyzm389gs

Verdict

VERIFIED · settled 2026-09-13

Hypothesis

B-tree already accumulates the matches for one leaf page in a bounded saved array, but its bitmap producer sends each heap TID through a separate call. That resets TIDBitmap's current-block cache before the next item, forcing a repeat page-entry decision even when adjacent index-order TIDs name the same heap block. A local compact TID batch can expose the existing bulk API without an executor or Table-AM redesign. Current source is authoritative about this structure; it does not prove cache misses, CPU share, or a production win. The proof target is interleaved baseline-versus-patch trials at 2M and 10M rows with perf instructions and cache counters plus inclusive bitmap-build profiling; retire it if same-block adjacency or bitmap-build share is not material, both target workloads do not clear the dual 10% threshold, or exactness/control checks fail. The active #6176 heap-page batching work is prior art but its inspected v4 does not touch this B-tree/TIDBitmap seam.

This anchor crosses index_getbitmap dispatches IndexAmRoutine.amgetbitmap; bthandler assigns that field to btgetbitmap at nbtree.c:165., an index-invisible edge the agent declared; the static analysis could not confirm the edge, so confidence rests on the benchmark and verdict, not the code index.

Change to test: In btgetbitmap, add a fixed ItemPointerData[MaxTIDsPerBTreePage] scratch buffer, compact the current saved B-tree leaf-page heapTid span into it, and invoke the existing tbm_add_tuples once per span.

Where it lives

perfloop/postgres · src/backend/executor/nodeBitmapHeapscan.c

Evidence

10M-row grouped-key scalar-array bitmap query, 3M matches, 150 prepared transactions; raw median pgbench field-3 latency in milliseconds per transaction from validated transaction logs; server CPU 2, client CPU 3 · 10 sample pairs

metric baseline candidate paired median change confidence range required result
median-latency-ms 186.3 163.2 −12.1% (−22.56) −23.59 to −21.75 < −9.316 PASSED

2M-row grouped-key equality bitmap query, 200k matches, 2000 prepared transactions; raw median pgbench field-3 latency in milliseconds per transaction from validated transaction logs; server CPU 2, client CPU 3 · 10 sample pairs

metric baseline candidate paired median change confidence range required result
median-latency-ms 12.03 10.37 −13.8% (−1.661) −1.737 to −1.527 < −0.6014 PASSED

500k-row paired bitmap controls: selective, wide-row, NULL-heavy, non-all-visible, parallel, short-query; raw median pgbench field-3 latency in milliseconds per transaction from validated transaction logs; serial and short controls server CPUs 2-3/client CPU 3, parallel server CPUs 2-3/client CPU 0 · 10 sample pairs

metric baseline candidate paired median change confidence range required result
median-latency-ms/selective 0.4355 0.4055 −7% (−0.0305) −0.033 to −0.027 ≤ 0.002 PASSED
median-latency-ms/wide-row 5.845 5.329 −9.2% (−0.539) −0.57 to −0.466 ≤ 0.002 PASSED
median-latency-ms/null-heavy 36.36 34.8 −4.6% (−1.671) −2.488 to −1.01 ≤ 0.002 PASSED
median-latency-ms/non-all-visible 5.005 4.575 −8.4% (−0.422) −0.494 to −0.382 ≤ 0.002 PASSED
median-latency-ms/parallel 21.31 19.75 −6.3% (−1.337) −2.176 to −0.859 ≤ 0.002 PASSED
median-latency-ms/short-query 0.054 0.054 0 0 to 0 ≤ 0.002 PASSED

Checks: 1 of 1 passed. Verification: no defect found.

Timeline