Cutting a ten-term BM25 OR from 74.6 ms to 20.0 ms
On a warm 10-million-document real-cloud benchmark, a ten-term BM25 OR took 74.6 ms. Five terms took 24.4 ms; three common terms took 14.3 ms. The postings were not expensive to decode. The time was going into coordinating the posting lists one candidate document at a time.
query shape maxscore windowed reduction 3 similar terms 14.3 ms 8.2 ms 43% 5 similar terms 24.4 ms 12.0 ms 51% 10 similar terms 74.6 ms 20.0 ms 73%
For faster profiling iterations, we repeated the same query family on a one-million-document in-memory tier and timed decode separately from merge and score. Decode was 3.3% of the ten-term query. Merge and score were 96.7%. Optimizing compression or I/O would not fix it.
Why MaxScore stopped skipping
Block-Max MaxScore is fast when one term has a meaningfully different upper bound. The low-scoring lists become non-essential, and whole blocks can be skipped once they cannot beat the current top-k threshold.
Common-term ORs have nearly uniform upper bounds. No term dominates, the essential set stays large, and block maxima are close to term maxima. The skip tests barely fire. MaxScore degrades into scoring almost the entire union while repeatedly finding the smallest document id across all active cursors, chasing their pointers, and touching the top-k heap.
Decode time stayed roughly flat at 0.4 to 1.0 ms as the query grew. The per-document merge grew from 5.7 ms to 10 ms to 30.5 ms. That was the part to remove.
Score one flat window at a time
The replacement processes a 4096-document range at a time. Each term walks its postings in that range and adds its BM25 contribution to a flat score array. A presence bitset records which document ids appeared. After every term has contributed, the scorer drains the set bits in document order into the existing top-k heap, then reuses the buffers for the next range.
The amount of scoring is unchanged when nothing can be skipped. What disappears is the per-document N-way cursor merge. Term-at-a-time writes are sequential and cache-friendly; the ordered drain happens once per window.
At 10 million documents, the ten-term query fell from 74.6 ms to 20.0 ms, a 73% reduction. Five terms fell from 24.4 ms to 12.0 ms; three common terms fell from 14.3 ms to 8.2 ms. A brute-force oracle confirmed that the top-k results stayed identical across term counts, negation, and k.
Dispatch by query shape
Windowing complements MaxScore. The dispatcher chooses between them from the shape of the upper bounds:
- Single-term queries keep the block-skipping path.
- Two-term ORs with a rare anchor and bounded top-k use the WAND/BMW path, where the short posting list provides a useful pivot.
- AND queries keep leapfrog intersection.
- Multi-term ORs with a dominant upper bound stay on Block-Max MaxScore, where pruning is effective.
- Multi-term ORs that pass the union-bound gates use the windowed scorer, where per-document coordination is the larger cost.
Each scorer wins on a different disjunction shape. MaxScore wins when bounds create skips; a flat window wins when the union must be scored anyway.