Doing Less Work, and Doing Work Faster

A frequent word can appear in thousands of engineering documents. An inverted index finds those documents without scanning every document’s text, but a ranked query may still have a large posting list to process. Can we avoid scoring most of it? And if one algorithm scores fewer documents, must it finish sooner?

Those are separate questions. A score bound can prove that an unseen document cannot enter the answer. Memory access, decoding, branches and batching determine how cheaply an implementation performs the remaining work. You will first defend a skip against an exhaustive answer, then specify the measurements needed to choose between two implementations.

On the primer’s search-system map, this lesson concerns candidate scoring and execution. Its indexes and candidates vocabulary connects the posting lists below to documents and the final answer.

We continue the synthetic engineering-document service from the identity and layout chapter: 50,000 documents, one region, 10 queries/s and 20 updates/s. The new requirement is a lexical query containing a common term with many postings. We vary query length and k when evaluating execution; the six-document example below is a small, complete query slice, not a capacity model. Reading time covers the prose; allow additional time for the exercises.

Evidence boundary: All scores, bounds and schedules in the exercises are synthetic. The algorithm and implementation discussion draws on the inspected January 14, 2026 FTS v2 articles. Their benchmark results are vendor-reported and unreplicated here. They do not establish turbopuffer v3 performance; its September 30 migration account still reports a performance regression and tuning underway.

Start with the answer and the exhaustive plan

The tenant still comes from trusted identity context. Fix one search snapshot and keep only that tenant’s live, matching documents. This chapter ranks distinct documents by total lexical score descending, then doc ID ascending. Dense distance ordering belongs to a different query contract; these lexical scores are not compared with embedding distances. The current-policy disclosure check from the previous chapter still applies before sending content to a user or external service.

An inverted index maps each query term to a sorted list of documents containing it. Each membership is a posting. A cursor records the current posting while an iterator moves through a list; advancing to a requested doc ID means finding the first posting at or beyond that ID. A lexical OR query considers the union of the query terms’ lists. A document present in several lists is scored once, with contributions from each matching term.

Real scoring needs more than membership. Term frequency counts occurrences within a document; document length helps normalize that frequency; document frequency counts documents containing the term and informs its rarity weight. The Stanford IR book’s BM25 section explains these ingredients and their tuning. Some IDF formulations can produce negative weights, so nonnegative contributions are an explicit assumption here, not a claim about every BM25 variant. We use saved contributions rather than reproduce image-only equations or implement BM25.

The query is index cache replica. Its stipulated scoring rule adds the three nonnegative contributions. An absent term contributes zero. For this numerical exercise, reduce the corpus to the six live, matching documents below, all belonging to trusted tenant A at the fixed snapshot. This smaller corpus makes an exhaustive oracle inspectable; it does not represent the full service’s common-term distribution. Group E is evaluated first, then group R. That group order is a teaching checkpoint, not a claim that textbook WAND traverses doc IDs in that order.

Saved contributions

The corresponding postings are sorted by doc ID even though the checkpoint processes E first. Each pair is doc_id:contribution.

An exhaustive baseline visits every distinct matching document, computes its complete score and sorts by the declared order. For k=3 it returns [30,40,50], with scores [11,9,6]. This exact answer is our oracle for skipping. It proves fidelity to the scoring rule, not relevance to a human question.

A top-k executor can maintain a heap, a data structure that exposes the worst retained result without sorting the whole result set after every candidate. Here the worst means lowest score, with the largest doc ID worst among equal scores. Until k results have been found, a matching document can fill an empty slot. Once the heap is full, its worst result defines a competitive boundary.

After E, the k=3 heap contains doc30 at 11, doc40 at 9 and doc50 at 6. Its score threshold T is 6. A candidate at 7 beats doc50. A candidate at 6 must also compare doc IDs; doc5 wins that tie, doc60 loses it. A threshold score alone does not encode our entire ordering.

Prove a skip before taking it

An admissible upper bound is a number that no document in the covered set can exceed under this query, scoring configuration and snapshot. It may overestimate; it must not underestimate. The bound is not an average score or a prediction of what is likely.

For group R, stipulate stored per-term maxima of 1 for index, 2 for cache and 2 for replica. Adding them gives U=5. Every document in R has total score at most 5. In this table the bound is attained by doc5, but a sum of maxima can be conservative because different documents may supply each term’s maximum.

With a full heap and valid total bound, U < T proves safety: every skipped document scores below the worst retained document. The heap’s threshold cannot fall as better candidates replace worse ones, so the same proof remains safe later in this fixed query. Here 5 < 6; skipping R preserves [30,40,50] while avoiding its three complete document scores.

The word total matters. A low bound for one term’s posting block does not prove that those documents are uncompetitive: other query terms can add score. Combine bounds for every possible contribution over the covered doc-ID range. In a real block-max algorithm, terms’ blocks need not have identical boundaries; the executor must respect the ranges over which their bounds are valid. Our E/R groups deliberately simplify that bookkeeping.

The complete decision trace is also available as a table:

Equality can sometimes be skipped with an additional valid tie proof—for example, all covered IDs are worse than the heap’s boundary ID. This chapter’s rule conservatively retains equality. Production arithmetic also needs conservative rounding: a floating-point estimate just below the true attainable score is not an admissible bound.

Guided decision: write the proof

Use the original table, k=3 and the E checkpoint. State whether the heap is full, its worst result, the remaining bound and the exact inequality that permits the skip. Compare the answer with exhaustive scoring. Then explain why a bound of 12, though valid, would not permit the same skip.

How WAND and MAXSCORE find that opportunity

Grand and Gallant’s MAXSCORE/WAND account uses sorted postings and per-term maximum contributions to explain two ways to exploit a competitive heap. Its production implementation uses block-local bounds; the small global-bound traces below explain candidate selection rather than specify its whole engine.

WAND (“weak and”) repeatedly asks which next doc ID could be competitive. Sort the active term cursors by their current doc IDs. Add their term bounds in that order until the cumulative bound reaches a competitive score; that cursor supplies a pivot ID. Cursors beyond the pivot prove their terms cannot occur at earlier IDs. Cursors before it must be advanced toward the pivot before a complete score can be computed there.

For a separate stipulated checkpoint, let index be at doc5 with bound 2, replica at doc7 with bound 5, and cache at doc8 with bound 4. The full heap threshold is 6. The cursor order and cumulative bounds are:

Doc5 cannot receive replica or cache; both cursors are already beyond it. Its best possible score is 2, so it cannot qualify. The first cumulative bound reaching 6 occurs at doc7: the pivot. Advance the index cursor to at least 7. If it lands at 7, the matching cursors can provide doc7’s exact score. If it overshoots, update the cursor ordering and pivot; do not assume a term matched. The source trace uses a score-only “exceeds” condition; under our explicit tie policy, equality also remains competitive unless doc-ID information proves otherwise.

MAXSCORE instead asks which terms must occur in any competitive document. Sort terms by increasing upper bound: index(2), cache(4), replica(5). Divide them into nonessential terms, whose combined bound cannot compete, and essential terms, at least one of which a competitive document must match. Essential lists generate candidates. Nonessential lists still contribute to their complete scores; ignoring them in scoring would change the answer.

At threshold 6, index alone is nonessential because its bound 2 is below 6. A document must match cache or replica to compete. We cannot also demote cache under our conservative tie rule: the combined index + cache bound is 2+4=6, and a tie might win. At threshold 7, the combined bound 6 is strictly below 7, so both become nonessential and replica alone generates candidates.

This cumulative condition avoids a tempting mistake. The individual cache and replica bounds, 4 and 5, are each below 6, yet a document matching both can score 9. “Every term is individually weak” does not mean “every document is weak.” MAXSCORE can also use partial scores and remaining nonessential bounds to avoid unnecessary probes; this chapter does not reproduce all of that optimization.

Block-max variants replace a term’s one global bound with local bounds. A high-scoring posting elsewhere in the corpus no longer makes every region look promising. Smaller ranges can make bounds tighter; larger ranges may save more work when skipped but include more score outliers. The FTS v2 posting-layout account describes this tradeoff for its target of roughly 256 postings per KV block. The previous chapter covers that block’s replacement and storage costs.

Change the inputs: equality, empty slots and stale bounds

Use the saved contributions and E-first schedule. Each row below is a separate query variant; changes do not accumulate. A change is one replacement of a per-term contribution. Before opening the answer, compute the exhaustive result and decide whether the supplied R bound is admissible and whether a threshold skip is safe.

Saved query variants

For equality, identify exactly who wins the tie. For unfilled, increase k before examining R and explain what “threshold” means then. For stale, calculate a repaired sum-of-term-maxima bound and show the wrong result an executor would produce if it trusted the old bound.

Stored score bounds are derived metadata. A document update, changed length normalization, a new rarity weight or a query boost can change the attainable contributions. A bound computed for an old scoring configuration cannot simply be reused. It may remain conservative, but that must be established; decreasing a score need not invalidate a still-high bound. The snapshot and configuration for postings, scoring metadata and bounds must agree with the declared answer contract. This is a validity requirement, not a description of a proprietary publication protocol.

Why more candidates can still finish sooner

Skipping removes score work but adds navigation and proof work. A plan may repeatedly reorder cursors, seek across lists and branch on different outcomes. A second plan may score more candidates while reading long contiguous sequences and performing less bookkeeping for each one. Candidate count alone cannot compare their runtime.

The FTS v2 implementation discussion says its MAXSCORE variant computes a doc-ID range from local bounds, then consumes the needed postings from one iterator in a batch before switching to the next. It contrasts this with alternating iterators that repeatedly catch up with one another. This changes the cost path:

In prose, the first path pays candidate selection, cursor navigation and scoring repeatedly. The second pays range selection, processes consecutive postings from each list, then combines their contributions and updates the heap. Both can skip; neither wins merely by carrying the name WAND or MAXSCORE.

Three CPU mechanisms explain the implementation opportunity:

• Memory locality: consecutive accesses can reuse cache lines and give hardware prefetchers a useful pattern. Switching among distant arrays can cause more misses and stalls. Contiguity creates an opportunity; the working set and actual layout still matter.
• Branch predictability: consistent loop behavior is easier to predict than irregular decisions. A mispredicted branch can discard speculative work and stall progress. Fewer branches and more predictable branches are related but different measurements.
• SIMD: single-instruction, multiple-data instructions apply an operation to several values at once. Suitable batches can make decoding and arithmetic amenable to those instructions. Batching is an execution organization; SIMD is an instruction-level technique. A batch loop can still be scalar, and not every operation in a batched query is vectorized.

Here, vectorized execution means processing batches of values. It does not mean nearest-neighbor search over embeddings. Nor do the following sizes describe one universal block:

DuckDB’s flat vectors use contiguous arrays, while constant and dictionary formats represent logical values differently and can preserve compression during execution. That documentation illustrates batching and representation choices; it does not establish a search-engine benchmark or prescribe 2048-posting blocks.

Defend an implementation choice with evidence

Loose bounds may let almost everything through, while bound navigation still costs CPU. Increasing k often lowers the competitive threshold or delays filling the heap, leaving less work to skip. Common terms, long queries, score distribution and where high scores occur can change the balance. Frequent updates add bound/layout maintenance and can change corpus statistics. Those workload changes make a fresh comparison more useful than a permanent winner.

The FTS v2 benchmark appendix uses an approximately five-million-document English Wikipedia export, AOL queries and handcrafted queries intended to resemble production, with several k values. It reports, for example, 174.4ms for v1 and 20.1ms for v2 at k=100 for pop singer songwriter born 1989 won best country song time person of year. The comparison changes storage layout and query implementation together. Those numbers are the authors’ result for that workload; they do not isolate vectorized MAXSCORE’s speedup, measure our service, or prove universal superiority over WAND.

Suppose implementation A scores fewer candidates, while B processes more postings in contiguous batches. Write a decision record before choosing:

Hold the answer contract and workload fixed for the first A/B comparison; then deliberately vary query length, common-term frequency, k and update rate. Record repetitions and result fidelity alongside latency. Decompression throughput is not complete query throughput; CPU time is not remote I/O latency; a mean is not p99. The synthetic checker for this chapter validates scores and decisions only and makes no performance claim.

Your exit artifact has two parts: a skip decision with its heap state, admissible total bound, tie rule and exhaustive comparison; and a measurement plan capable of contradicting your implementation preference. In the next chapter, candidate work changes again when eligibility and vector geometry interact.

Selected reading

• Stanford IR: Okapi BM25 resolves why term counts, document length and corpus rarity affect score. Use a verified scoring formula before implementing it.
• Vectorized MAXSCORE over WAND supplies the cursor/essential-term worked examples, batched implementation explanation and vendor benchmark methodology. Read the mechanism and appendix together.
• Designing inverted indexes in a KV-store, especially “Why N=256?”, connects skip-bound tightness to posting-block size and contiguous decoding.
• Lucene 10.3.1’s postings-format documentation makes codec blocks, skip data and scoring-impact metadata concrete within a pinned format.
• DuckDB’s Execution Format separates execution batches and their physical representations from embedding vectors and posting storage blocks.