# 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.