BatchEqual must not drop columns when a BSI carries past 64 bit planes

perfloop-oss/roaring · CORRECTNESS

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

Verdict

VERIFIED · settled 2026-11-04 · pull request opened as RoaringBitmap/roaring#586

What happened: The check fails before this change and passes with it.

Hypothesis

Batch equality can lose matching columns after an arithmetic carry grows an index beyond 64 bit planes. Callers then get a different answer from single-value reads. The frequency of these indexes and the repair's effect on normal-index speed remain unmeasured.

The submitter reports a correctness regression from upstream PR #532, merged as dac837d3bbc8, that is still present here. Their reproducer sets column 1 to -1 in a 64-plane index and calls IncrementAll(). They report that base bd4128b6cfc3 returns BitCount=65, GetValue(1)=(0,true), and BatchEqual([0])=[1], while the PR head and current code return BatchEqual([0])=[]. They also identify Add as a way to carry out of plane 63 and create a 65th plane. Their explanation is that GetValue ignores planes 64 and above, but the trie clamps p to 63 while treating plane 64's bits as part of the value, removing every column whose bit is set in plane 64.

At accepted revision 0cca44e8f178ff394b7de93713b92b65f6240841, the source differs from the report's clamp description: BatchEqual passes bitCount-1 directly to matchTrie (BitSliceIndexing/bsi.go:684-724, call at 719). matchTrie partitions uint64 query values and filters against b.bA[p] even when p is 64 (BitSliceIndexing/bsi.go:834-866). GetValue accumulates into an int64, so shifts at planes 64 and above contribute no bits (BitSliceIndexing/bsi.go:137-149). Add reaches addDigit, which appends carry planes; IncrementAll reaches the same helper through Increment (BitSliceIndexing/bsi.go:929-950 and 981-993). The accepted BSI Batch Query Verification operation already reaches this matchTrie locality through BatchEqual.

An API-only local go run probe reproduced the current mismatch. Before incrementing, the 64-plane index returned [1] for BatchEqual([-1]). After IncrementAll(), it had 65 planes, GetValue(1)=(0,true), and BatchEqual([0])=[]. Adding a separate index containing column 1 with value 1 to an index containing column 1 with value -1 produced the same mismatch. This is a local correctness observation, not a performance or production-prevalence measurement. The historical base/head executions remain unconfirmed in this run.

Upstream https://github.com/RoaringBitmap/roaring/pull/532 replaces GetValue-based membership with the trie; its merged patch and follow-up discussion address existence-bitmap authority and prefix sharing, not this extra-plane case. Current open proposals https://github.com/RoaringBitmap/roaring/pull/540 (checked head 4fc1c2e554ef22b6eb4b7e590d56dbe044a9fa35) and https://github.com/RoaringBitmap/roaring/pull/461 (checked head 64c9acf384f27c5c15ef45b391345ce5513c21af) change comparison operations in the same file, not BatchEqual's trie. Their acquired BSI implementation patches do not supply this repair; #461 describes a nonnegative-value restriction. These are open proposals, not accepted replacement decisions. The upstream comparison covers the completed current open-PR listing, these patches and discussions, and #532; no linked issue for this regression was identified in those records, and other closed work was not surveyed.

The smallest useful next check is an executable regression test of the public-API reproducer, independently asserting the 65-plane state, GetValue's wrapped zero, and inclusion of column 1 in BatchEqual([0]). The complete proof also needs the Add carry route and deterministic randomized differential tests against GetValue near both signed limits, including carried indexes. Existing randomized coverage uses values from -250 through 249 without arithmetic carries (BitSliceIndexing/bsi_benchmark_test.go:186-231). Normal indexes must retain the #532 speedup; the existing BatchEqual benchmarks provide regression controls, but neither that preservation nor a gain magnitude has been measured here.

Change to test: Make BatchEqual agree with GetValue's pre-#532 answer for indexes with more than 64 planes, for example by ignoring planes 64 and above in the trie walk, while keeping the #532 speedup on normal indexes. Add a test that fails without the fix and differential-test BatchEqual against GetValue on random values near the signed limits.

Where it lives

perfloop-oss/roaring · BitSliceIndexing/bsi.go

Evidence

The check fails before this change and passes with it: `BatchEqual includes column 1 for query zero after IncrementAll or Add carries -1 plus 1 into a 65th plane, matching GetValue returning (0, true).`

The check fails before this change and passes with it: `For a deterministic 256-column corpus near both int64 limits and across the int64 range, BatchEqual agrees with GetValue membership on the tested queries at parallelism 0, 1 and 4, before arithmetic and after IncrementAll and Add grow the index to 65 and 66 planes.`

BenchmarkBatchEqual · 16 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 58744604 58820121 +153441 −1213899 to +1238994 loss ≤ 0.05 × |baseline median| PASSED
B/op 26735585 26735585 0 −9 to +7 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 8248 8248 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED

BenchmarkBatchEqualM128 · 16 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 2068628 2090216 +10911 −93820 to +94742 loss ≤ 0.05 × |baseline median| PASSED
B/op 9343343 9343343 0 0 to +6 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 3034 3034 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED

BenchmarkBatchEqualM128Scattered · 26 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 1699805044 1712816857 +23726333 −115848498 to +80193700 loss ≤ 0.05 × |baseline median| PASSED
B/op 157460836 156913140 −1084 −2272600 to +1139156 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 23900 23765 −2.5 −552 to +280 loss ≤ 0.05 × |baseline median| PASSED

BenchmarkBatchEqualM200 · 26 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 6017399 5984196 −17462 −223707 to +160036 loss ≤ 0.05 × |baseline median| PASSED
B/op 9566337 9566338 0 −14 to +3 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 7468 7468 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED

BenchmarkBatchEqualRunOptimizedEndToEnd · 16 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 293 294.4 +1.5 −9.8 to +5.2 loss ≤ 0.05 × |baseline median| PASSED
B/op 176 176 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 8 8 0 0 to 0 loss ≤ 0.05 × |baseline median| PASSED

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

Timeline