Document-at-a-Time and Term-at-a-Time Evaluation

Ranked retrieval has to turn a conjunction or disjunction of postings lists into a list of documents ordered by score. There are two ways to organise that computation, and they differ in what quantity the loop indexes over: documents, or terms. The distinction is less about correctness — both orders produce the same score for every document — and more about which resource dominates the cost, and which structures can prune the work early.

The two orders have different natural homes. Conjunctive boolean search, where the answer is a set rather than a ranking, is inherently document-oriented because a merge walks documents. Ranked search over many terms, where scores accumulate across terms, can go either way, and the choice interacts with how scores are computed and how early termination is applied.

The two loops

Document-at-a-time (DAAT) walks all postings lists simultaneously, keeping a cursor per term, and at each step advances to the next document that appears in any list. For every document it visits, it adds the contribution of each term that contains that document, producing a complete score in one pass, then decides whether the document belongs in the current top-k heap. The score is assembled incrementally but is final the moment the document is passed, because no later step revisits it.

Term-at-a-time (TAAT) walks one list at a time. For the first term, it reads every posting and adds that term’s contribution into an accumulator array indexed by document identifier. Then it moves to the next term and adds that term’s contributions into the same array. After all terms, the accumulator array holds every document’s total score, and the top-k is a selection pass over the array.

The accumulator array is the whole difference. DAAT needs only a running score and a small heap, so its memory is O(k) plus cursor state. TAAT needs an array with one cell per document in the collection, initialised to zero before each query, so its memory is O(N). For a collection of tens of millions of documents, that is hundreds of megabytes of working set that is touched on every query, most of it uselessly.

Why TAAT existed

TAAT is the order that comes out of the simple, pre-ranking formula. In the classic tf-idf or BM25 shape, a document’s score is a sum over query terms of per-term weights, and a sum is naturally computed term by term: for each term, walk its list, add into a running total. The postings lists can be read in arbitrary order, they are read sequentially in the order stored, and the accumulator array is a perfectly random-access structure for the writes. The sequential read is cache-friendly, which is TAAT’s one genuine performance strength.

The cost of initialising the accumulator array to zero is avoidable with a generation trick: keep a parallel array of per-query timestamps, and treat a cell as zero when its timestamp is not the current query’s. This removes the O(N) clear but not the O(N) array footprint, nor the scattered writes, nor the final selection pass over N cells.

The scattered writes are the deeper problem. Adding a term’s contribution to document d writes a random location in a large array, which for a list of millions of postings is millions of cache misses. The sequential read is paid for twice, because the array is too large to stay resident and every write may be a miss. DAAT does not have this problem because its working state is a single score and a heap of size k.

Where DAAT wins and loses

DAAT’s advantages compound. Its memory is O(k) rather than O(N), its score is final when the document is visited, which enables early termination, and it needs no separate selection pass. The heap keeps the k best scores seen so far, and once k is filled, the heap minimum is a threshold: any document whose partial score cannot exceed the threshold can be abandoned before all its terms are read. That pruning is not available to TAAT, which does not know a document’s partial score across terms until the last term has been processed.

DAAT’s cost is the merge. With t query terms, each document visit touches all t cursors, even those that do not contain the document, and a disjunctive query over a common term and a rare term degenerates into a walk of the common term’s long list. TAAT walks each list once, which is O(total postings), independent of the other terms’ lengths, and it pays no merge overhead per document. For short queries over lists of comparable length, the difference is small; for long queries, or queries mixing frequent and rare terms, the merge cost of DAAT grows with t per document, and TAAT’s independent per-term walks look better.

There is a third cost to DAAT that is easy to miss: to advance a cursor, the decoder must often skip to an arbitrary document identifier, which is exactly the random access that compressed lists make expensive. A format with fine-grained skip pointers — small blocks, or byte-aligned codes with dense skips — favours DAAT, while a format optimised for pure sequential decode favours TAAT. The compression scheme and the evaluation order are not independent decisions; they are one decision made in two places, which is why the skip structure discussion and this one are entangled.

Max-score and other ways to decide early

Both orders can be pruned, but the pruning mechanisms differ.

TAAT’s standard optimisation is to process terms in decreasing order of their maximum possible contribution, and to maintain a running ceiling. Once the ceiling of the remaining terms, added to the best score so far, cannot beat the current k-th score, processing stops. The accumulator then holds exact scores only for documents that have met every processed term; documents first seen in a skipped term would have a partial score, which is the source of the scheme’s approximate mode. Bounding the error requires tracking which terms each document has seen, or accepting that the result is a heuristic top-k.

DAAT’s standard optimisation is block-max pruning. If the index stores, per block of postings, the maximum term weight in that block, then during the merge the evaluator can skip an entire block of a term when the block’s maximum, summed over all terms, cannot exceed the heap threshold. This turns DAAT’s per-document threshold into a per-block threshold and can skip most of the postings in a ranked query over a head-heavy scoring function. The block maxima are the reason several index formats carry them even though they cost storage; they exist to serve DAAT.

The early-termination discussion continues in impact-ordered early termination, which changes the postings order itself rather than the traversal over a fixed order.

Choosing, and the failure cases

The practical split is not absolute. Long queries with many rare terms are naturally TAAT, because the merge cost of DAAT grows with t while TAAT’s independent walks do not, and because a large t makes the accumulator’s memory cost relatively small. Short conjunctive queries with selective terms are naturally DAAT, because the merge is cheap, the heap pruning is strong, and the accumulator would be pure waste.

The failure cases are where each order’s weakness is maximised. TAAT fails when the accumulator array does not fit in cache: the scattered writes become a latency-bound loop whose cost scales with the collection size rather than with the result size. DAAT fails when one term is much more frequent than the others: the merge walks the frequent term’s entire list, producing nothing for the rare terms to intersect with, and the per-document cursor work is pure overhead. The standard mitigation for the second case is to make the most selective term drive the merge and gallop the others into it, the technique named in postings lists as sorted arrays.

The two orders also place different demands on the document identifier space. TAAT’s accumulator array is indexed by document identifier, so it requires identifiers to be a compact, dense range; any scheme that scatters identifiers across a sparse space inflates the array. DAAT only needs identifiers to be comparable and ordered, so it is indifferent to density. This is a genuine constraint on collection design when TAAT is the evaluation order, and one that disappears if the engine can rebuild to DAAT later.