BatchEqual's upfront sort reportedly makes small-index 100k-value queries about 5x slower

perfloop-oss/roaring · INEFFICIENT ALGORITHM

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

Verdict

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

What happened: The paired measurements met the required improvement.

Hypothesis

BatchEqual finds columns whose stored value belongs to a query list. It sorts the deduplicated query before choosing a matching path. The submitter reports that this makes a 100,000-value list about five times slower on a one-column index after #532. The requested outcome removes unnecessary sorting without losing #532's large-index/small-query gain or changing results. The timing reports and attribution to sorting have not been independently checked at this checkout.

At accepted revision 0cca44e8f178ff394b7de93713b92b65f6240841 (the report's source base 0cca44e), BitSliceIndexing/bsi.go:684-724 defines BSI.BatchEqual. It filters and deduplicates values, calls sort.Slice unconditionally for surviving nonempty queries at line 709, and only then selects a path at lines 711-719. Sorting grows as O(n log n), where n is the number of distinct retained query values. The report's relevant input range is 100 to 100,000 values, with either one or 100,000 stored columns. The selector itself depends on sorted values: shouldUseParallelScan and estimateBranchCount at lines 731-764 lead to sort.Search at 753. The trie splits sorted values with sort.Search at 852 inside matchTrie, lines 834-866. The scan at lines 771-824 uses a membership map rather than ordered queries, but the current cardinality condition excludes a one-column index. Merely moving the sort below the unchanged selector is therefore not sufficient. Deduplication, membership-map construction, and bitmap matching or scanning remain costs; the removable share of total work is unknown.

The submitter reports interleaved pinned runs of a 64-plane BSI, with shuffled distinct query values including the stored value. All numbers below are reported milliseconds per operation, ordered as base bd4128b6, merged #532 at dac837d3, and master 33586ce: - One column, 100,000 values: 4.40, 22.31, 22.62, described as about 5x slower, with the same bitmap returned. - One column, 1,000 values: 0.03, 0.17, 0.18. - 100,000 columns, 100,000 values: 45.39, 86.24, 70.97. - 100,000 columns, 100 values, the #532 target shape: 38.71, 3.03, 2.22. This gain must be kept.

The reported driver is /tmp/rw/W16/zz_rw532_sort_bench_test.go, BenchmarkRW532. That driver has not been obtained here, and the three reported historical revisions are not available in the local checkout. These are attributed, unconfirmed elapsed-time reports, not Perfloop measurements or a promise of a fivefold improvement at the accepted revision. Consumer query-size distributions, cadence, configurations, and production prevalence remain unknown. This is architecture-independent algorithmic work, with no hardware-specific requirement.

The smallest useful next check is a small-index/large-shuffled-list benchmark beside the #532 benchmarks in BitSliceIndexing/bsi_benchmark_test.go:11-43 and 274-292. Start with the reported one-column/100,000-value, 64-plane shape, keep the stored value in the query, and measure complete BatchEqual calls with a CPU profile to distinguish sorting from the remaining work. Extend the comparison across all four reported shapes and check the historical report when those snapshots and the driver can be obtained. A large sorting share and reduced end-to-end time after avoiding unnecessary sorting would support the mechanism; little sorting cost or no total improvement would weaken it. The 100,000-column/100-value case is a required regression control, not evidence of savings for the small-index workload.

Keep results identical to GetValue ground truth, whose definition at BitSliceIndexing/bsi.go:137-149 treats the existence bitmap as authoritative. Existing differential coverage includes signed and sub-64-bit values, duplicates, and deserialized existence/plane divergence in BitSliceIndexing/bsi_benchmark_test.go:82-269, plus scan-path checks at BitSliceIndexing/bsi_test.go:608-649. Preserve the 64-plane clamp, bitCount := min(b.BitCount(), 64), if present on the implementation baseline; this accepted snapshot instead reads b.BitCount() at line 689. Add the requested benchmark and run go test ./... and go test -race ./BitSliceIndexing. A GetValue mismatch or loss of the required #532 gain rejects a proposed repair.

Upstream overlap is with merged https://github.com/RoaringBitmap/roaring/pull/532 at dac837d3bbc8b5113e8a313372139bf0cf4f7a23, which introduced the sorted trie. Its follow-up discussion, https://github.com/RoaringBitmap/roaring/pull/532#issuecomment-4861708077, explains why results must stay rooted in the existence bitmap, including deserialized fixture divergence. This proposal targets the upfront-sort regression while retaining that trie gain and correctness boundary, rather than reverting #532. The inspected BSI patches of open https://github.com/RoaringBitmap/roaring/pull/540 (head 4fc1c2e554ef22b6eb4b7e590d56dbe044a9fa35) and https://github.com/RoaringBitmap/roaring/pull/461 (head 64c9acf384f27c5c15ef45b391345ce5513c21af) concern CompareValue and CompareValueONeil, respectively, rather than BatchEqual sorting. No linked issue was identified in the inspected #532 material. Other discussions and uninspected files remain gaps; this is not repository-wide upstream clearance.

Change to test: Sort only on paths that need ordered values, or choose the path before sorting, so large IN-lists on small indexes avoid an upfront O(n log n) sort while preserving GetValue-equivalent results and the #532 large-index/small-query gain. Keep bitCount := min(b.BitCount(), 64) if present; add a small-index/large-shuffled-IN-list benchmark beside #532's benchmarks and run go test ./... plus go test -race ./BitSliceIndexing.

Where it lives

perfloop-oss/roaring · BitSliceIndexing/bsi.go

Evidence

BatchEqual small index · 16 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 18480648 3666027 −80% (−14792336) −15436378 to −14466265 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 3169074 3168343 −733.5 −857 to −593 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 285 282 −1.1% (−3) −3 to −3 loss ≤ 0.05 × |baseline median| PASSED

BatchEqual 781-column boundary · 16 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 28259257 4319099 −84.5% (−23892732) −25310535 to −23489428 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 4079178 3180545 −22% (−898557) −898889 to −898116 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 35991 334 −99.1% (−35657) −35658 to −35657 loss ≤ 0.05 × |baseline median| PASSED

BatchEqual 782-column boundary · 16 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 28336847 4291498 −84.7% (−24005314) −25462023 to −23341403 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 4080190 3180593 −22% (−899658) −901491 to −899214 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 36033 334 −99.1% (−35699) −35699 to −35698 loss ≤ 0.05 × |baseline median| PASSED

BatchEqual 12799-value boundary · 17 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 2487800 485757 −80.2% (−1995741) −2102178 to −1953710 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 520487 405031 −22.2% (−115413) −115700 to −115290 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 4709 95 −98% (−4614) −4614 to −4614 loss ≤ 0.05 × |baseline median| PASSED

BatchEqual large-index control · 17 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 1510033 1497221 −16137 −76173 to +64134 loss ≤ 0.05 × |baseline median| PASSED
B/op 897470 897518 +48 +40 to +57 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 946 947 +0.1% (+1) +1 to +1 loss ≤ 0.05 × |baseline median| PASSED

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

Timeline