Impact-Ordered Postings and Early Termination

An inverted index stores postings in document identifier order, and every technique in this cluster so far has treated that order as fixed. But for ranked retrieval, identifier order is arbitrary with respect to what the query actually wants: the documents with the highest score. Impact ordering breaks the invariant and stores each term’s postings in decreasing order of the contribution that term makes to a document’s score. The engine can then stop reading a list once the remaining postings cannot affect the top-k, and the result is a query that reads a small fraction of the postings it would otherwise touch.

The cost is that identifier order is the thing that made conjunction a merge possible, and impact ordering throws it away. Everything the scheme buys in pruning it pays for in the loss of the merge, and the design of an impact-ordered engine is largely the management of that loss.

What an impact is

An impact is the per-term score contribution of a single posting. In a scoring function of the additive form score(d) = Σ over query terms of weight(term, d), each term contributes one term per document it appears in, and the impact is that term. The impact depends on the term’s frequency in the document and on the document’s length, which are both known at index time, so impacts can be precomputed and stored rather than computed during the query.

Storing impacts changes the posting layout. Each entry now carries, alongside or instead of its document identifier, a score value, and the list is sorted by that value descending. A term appearing in many documents has a long tail of documents where it appears exactly once and contributes a small, roughly uniform impact; the head of the list is the few documents where the term is prominent.

The document frequency and the document lengths become part of the impact at build time, which means the impact ordering is valid only for the scoring model it was built for. A change to the scoring function, to the length normalisation, or to the term-weighting scheme invalidates the ordering, and the index must be rebuilt to restore the early-termination guarantee. This is a sharper coupling than a document-ordered index has, where the score is computed fresh at query time and the index is agnostic to the model.

Why early termination becomes possible

In a document-ordered list, the engine does not know that the next posting is a low-impact one until it reads it, so a query that wants only the top ten documents must, in the worst case, read the entire list. In an impact-ordered list, the postings are read high-impact first, and the remaining postings are monotonically non-increasing in impact.

The engine maintains a threshold — the score of the current k-th best document. Once the next impact is below the threshold, no unseen posting can by itself push a new document into the top-k, and the list can be abandoned. The guarantee is exact for a single term: the top-k for a one-term query is found exactly by reading only the head of the list. For multiple terms the situation is harder, because a document’s total score is the sum of several impacts, and a document with a low impact on one term may still be in the top-k thanks to high impacts on others.

The two established resolutions are the WAND-style family of algorithms and the max-score family. WAND (Weak AND) processes lists in impact order, tracks the current threshold, and skips documents whose total possible score — the sum of the current impacts across all terms — cannot reach the threshold. Max-score is similar but partitions terms into those that must be scored and those that are optional, so that a document’s upper bound is computed from a subset. Both are exact when the per-term impact upper bounds are correct, and both reduce to a fraction of the postings read on head-heavy score distributions.

The early-termination guarantee is only a guarantee about which documents are read, not about which are correct. WAND and max-score are exact; the approximations come from bounding impacts more loosely than the true maximum, which trades correctness for fewer reads. The block-max index is the standard loosening: store, per block of postings, the maximum impact in the block, and skip whole blocks whose maximum cannot contribute.

The cost: merge semantics disappear

Document-ordered lists support the intersection merge, which is both the cheapest set operation and the basis of boolean search. Impact-ordered lists cannot be merged by identifier, because the identifiers are scattered in score order. A conjunction of two impact-ordered lists cannot walk two cursors in identifier order and find matches; it must fall back to one of three alternatives.

The first is to keep a document-ordered copy of the index for boolean queries and an impact-ordered copy for ranked queries, which doubles the index and is the configuration that makes the design decision explicit.

The second is to use an accumulator array in the term-at-a-time style: read the head of each impact-ordered list and accumulate scores into a per-document array, then select the top-k. This is naturally how impact ordering is consumed, because the term-at-a-time loop does not need identifier order, and it is the reason impact ordering and term-at-a-time evaluation are usually found together.

The third is to accept that boolean and ranked queries have different needs and route them to different structures, with a shared document store underneath. This is the common production shape: the ranked path uses impact ordering and early termination, the boolean path uses a document-ordered merge, and the two do not share postings.

The accumulator array reintroduces the memory cost that document-at-a-time evaluation avoids. With impacts precomputed, the array holds a partial score per document, and the array is indexed by document identifier, so it needs the dense identifier space. The scheme has traded the merge for memory, and the memory is O(N) per query.

What breaks under updates and skew

Impact ordering assumes the impact computed at index time is the impact that holds at query time. Three things break that assumption.

Document frequency and collection statistics drift as the collection grows. A term’s inverse document frequency, used in the score, changes when new documents arrive, so the stored impacts are stale. The ordering remains approximately correct while the drift is small, but the early-termination guarantee is only exact for the statistics at build time. Systems that want exactness either rebuild or store enough information to recompute.

Deletion is worse than insertion. A deleted document leaves a stale posting with a stale impact, and if it sits in the high-impact head of a list, the engine will read it and discard it on every query until the segment is merged. A document-ordered index has the same stale-posting problem, but the live-document bitmap filter is a single test; the impact-ordered index pays for the stale entry in the more expensive position, the head.

Score skew concentrates the benefit. If the scoring function produces a long flat tail of near-equal impacts — which happens with a length-normalised model over homogeneous documents — the monotone decrease is weak, the threshold is not crossed until deep into the list, and early termination saves little. The scheme’s value is maximised by a head-heavy distribution, and it is the scoring model, not the index, that determines whether that holds.

Impact ordering versus block-max

The block-max index deserves to be distinguished from impact ordering, because both enable pruning but they prune different things. Block-max keeps document order and stores a per-block maximum impact; it prunes whole blocks during a document-at-a-time merge, which preserves boolean conjunction and the merge, at the cost of storing the maxima and of being a coarser granularity than a per-posting impact. Impact ordering prunes at the per-posting level by changing the order, and loses the merge. Block-max is the conservative version of the same idea: it keeps every structure this cluster has relied on and adds one stored field per block, while impact ordering is the aggressive version that discards the order to buy finer-grained pruning.

The two compose poorly. An impact-ordered list does not have meaningful blocks in identifier space, so a block-max structure does not apply to it, and a block-max index is document-ordered, so it does not benefit from impact ordering. The choice between them is a choice about whether the engine’s ranked queries are dominated by the merge cost or by the decode cost, and it is usually made once, when the index format is fixed.

The practical consequence of impact ordering is a ranked query that reads, in the favourable case, a few percent of the postings a document-ordered index would, at the price of an O(N) accumulator array, a scoring model frozen into the index, and the loss of the merge that the rest of this cluster takes for granted.