Query-Time Cost and the Conjunctive Fast Path

A search query arrives as a handful of terms, and the system must return the best matches, fast. The latency budget for a single query is typically a few tens of milliseconds, and every one of those milliseconds is spent in a small number of identifiable places: looking up the terms in the dictionary, walking their postings lists, intersecting them, and scoring the survivors. Where the time actually goes is dominated by a single factor, the length of the longest list a query must touch.

The shape of the work

A term query resolves to one postings list, and answering it means walking that list, scoring each live document, and keeping the top K. The cost is linear in the list length, and list length is the term’s document frequency, the number of documents containing it. This is the fundamental asymmetry of search: a rare term like a product model number might have a list of a few thousand entries, while a common term like “the” or “a” has a list of nearly the whole corpus. A single common term can therefore dominate the cost of an entire query, because its list alone is larger than every other list combined.

A multi-term query adds a second operation, the intersection or union of lists. A conjunction, an AND of terms, must find documents that contain every term. The standard technique is to walk the shortest list and, for each candidate, probe the longer lists for the same document id, using a skip structure or a binary search. The cost is then the length of the shortest list times the log of the length of the others, which is why the shortest list matters so much and why the query planner sorts terms by increasing frequency before intersecting them.

Top-K pruning as a bound on work

A query rarely needs every matching document; it needs the best K, where K is small, on the order of ten to a hundred. Top-K pruning exploits this by abandoning candidates that cannot possibly make the heap. If the current K-th best score is a lower bound, any candidate whose maximum possible score is below that bound can be skipped without being fully scored. The maximum possible score is estimated from the term’s upper-bound contribution, often precomputed at index time as the best score any single document achieved for that term.

The win is largest for broad queries. A disjunction over common terms matches millions of documents, but most of them match only one of the terms weakly and cannot beat the current top K, so pruning skips them after a cheap bound check instead of a full scoring. The bound must be an over-estimate or the pruning is unsound and drops a true top-K document, so the upper bounds are computed pessimistically, and the tighter the bound the more work is pruned. This is the single biggest lever for reducing the scoring tail, and it is why index-time statistics such as per-term maximum scores are maintained even though they are never shown to a user.

Why the dictionary matters before the lists do

Before any list is walked, each term must be located in the term dictionary, the structure that maps a term string to the offset of its postings list. The dictionary is not a hash table of strings; it is a sorted structure, often a finite-state transducer or a block-compressed sorted array, because the dictionary itself must be resident and compact. A dictionary lookup costs a string comparison against a few candidate terms, and for a query with many terms, dictionary lookups plus the associated cache misses can rival the list-walking cost. This is the reason the sibling cluster on indexing treats the dictionary as a first-class structure rather than an afterthought.

The dictionary also holds the document frequency for each term, and that single integer is what the planner uses to order the lists before intersecting. Getting the frequency without touching the postings is what makes planning cheap: the frequency lives in the dictionary entry, a few bytes, not at the head of a list that might be megabytes away.

Skip pointers and the accelerated walk

A plain intersection walks the shortest list one id at a time and probes the others, but probing a long list with a random access for every candidate is wasteful when the lists are dense. Skip pointers amortize that: each list carries, every so many postings, a pointer that jumps ahead to a posting with a larger id, so a walk can leap over long runs of ids that cannot match and land near the next candidate. The skip interval is a space-versus-time choice baked in at index time. A short interval, a skip every few postings, makes intersections fast but inflates the list by the size of the pointer per skip; a long interval keeps the list compact but forces the walk to step through more postings one at a time.

The same structure serves disjunction. A union of several lists walks them in lockstep, advancing whichever list has the smallest current id and emitting each distinct id once. Skip pointers let that lockstep also leap when one list is far behind the others, which is the common case for a disjunction of one rare and several common terms: the rare term’s short list advances slowly, and the common terms’ long lists must jump ahead to keep up. Without skips, the union would scan the long lists in their entirety even though most of their documents cannot change the outcome.

Scoring is the irreducible tail

Once a candidate document is known to match, it must be scored. Scoring reads the term frequency and document length for each matched term, combines them through a model such as BM25, and inserts the result into a bounded top-K heap. The heap means the per-document scoring cost is the cost of the scoring function plus a log-K comparison; the heap itself is tiny and resident.

A second, less obvious scoring cost is the normalization lookup. BM25 divides by a function of document length, so the scorer must fetch each candidate’s length, which is not stored in the postings list but in a separate per-document field or column. A query over a million candidates therefore performs a million random length lookups, and whether those lookups hit cache is often the difference between a fast query and a slow one. Systems that store the length inline with the posting, or that fetch it in bulk for a block of candidates, are buying locality for exactly this reason.

Scoring is the part of the query that cannot be compressed away. The list walk can be accelerated with skips and the intersection can be ordered optimally, but every survivor still pays the scoring cost, and a broad query that matches a large fraction of the corpus pays it on a large fraction of the corpus. This is where the caching layers earn their keep, by short-circuiting the whole pipeline for the subset of queries that repeat.

The cost that grows with the index

Two costs scale with corpus size rather than with the query. The first is the number of segments: a query must search every segment, because a term may live in any of them, so query cost is proportional to segment count even for a rare term. This is why segment merging is a query-latency concern, not just a space concern. The second is the page cache: postings lists for a large index cannot all be resident, so a query that touches a cold term faults its list in from disk, paying a seek-plus-read that can be orders of magnitude larger than the in-memory walk. A query’s latency is often determined not by how much work it does in RAM but by how much of its data was already in RAM when it started.

A conjunctive query over a rare term is therefore fast almost regardless of the corpus, while a disjunctive query over common terms is slow almost regardless of optimization. The planner’s job is to recognize the shape of the query and route it toward the cheapest evaluation, and the rest of the system’s job is to make sure the data the query needs is already in memory.