Phrase queries and faceting

Why do phrases and facets break early termination, and what do engines do instead?

Phrase and proximity

The bag-of-words model deliberately discarded order. Phrase queries ("red kurta" as a phrase, not as two separate words) want it back, so positions must be stored: one entry per occurrence rather than one per document. The price of order is therefore proportional to total corpus tokens, not to document count. Typically it is a several-fold multiple on index size, concentrated exactly in the common terms whose lists were already the largest.

Worse, joint-position predicates are not decomposable across terms. Whether two terms are adjacent is a property of their positions together. No per-term upper bound tells you anything useful about it. So the skipping mechanism from the previous section stops working the moment proximity enters the scoring function.

The universal resolution: two stages

Use a decomposable, skippable first pass to produce a few hundred candidates. Then evaluate the expensive positional predicate only on those. This is filter-and-refine (the organizing pattern of this mechanism, appearing here for the first time in text). It is also the honest origin of multi-stage retrieval as an architecture rather than an optimization.

The alternative: precompute pairs

Index adjacent token pairs or shingles (short runs of consecutive tokens) as first-class terms. That converts a proximity question into a membership question. The cost is vocabulary explosion: the number of distinct bigrams is far larger than the number of distinct terms, and the postings for each are short, which pushes per-term fixed costs up.

The boundary of multi-stage systems

State this clearly, because it recurs in vector search and in every reranking pipeline:

The stages trade cost against quality only within the candidate set. Outside it, the loss is permanent.

One line: order is information you threw away, and you pay for it either in positions per token or in a second pass over candidates.

Faceting and aggregation over postings

Faceting asks: of the documents that matched, how many carry each value of some field? ("Kurtas (12,400), Shirts (8,300)...") That question runs in the opposite direction from the index. The inverted index maps term to documents. Faceting needs document to its values.

There is no clever way around this. The engine stores a second structure, a per-document column of field values, and that structure is an ordinary columnar column living beside the inverted index. Faceting is the point at which a search engine becomes a column store. The cost is that the data is materialized twice, in two orientations, with two write paths and two merge paths.

This is the first instance of something general:

Inverted and forward index here; base table and secondary index in a relational database; forward and reverse adjacency in a graph. A mapping and its inverse are different data structures, and materializing one does not materialize the other. Highlighting and snippets add a third copy: they are the reason the original text is also stored.

Faceting defeats early termination

This is sharper and usually goes unsaid. Top-k pruning works because you only need ten documents. A count needs every matching document. A query that returns ten results and three facet breakdowns pays O(k) for the results and O(matches) for the facets, so the facets dominate by orders of magnitude. The pruning that makes search cheap is structurally unavailable to the aggregation that sits next to it on the same page. (This is Amara's second oddity: about 40 times slower with counts.)

The escapes, as you would now predict

Approximate the counts with sketches. Note that approximate counts are two-sided error. That is acceptable only because facet counts are advisory.
Precompute aggregates for common facet fields.
Sample the match set and extrapolate.
Restrict faceting to low-cardinality fields (few distinct values), where the forward column is small and dense enough to be nearly free.

Top-N facet values computed independently per shard do not compose. A value ranked eleventh on every shard can be first globally. Example: on each of three shards, brand X has 100 listings and one other brand (a different one per shard) has 110. X ranks second on every shard, but its global total of 300 beats any other brand's total of 110. If each shard reports only its top 1, brand X is never reported. This is the same non-composition as percentiles. The fix is the same: either an extra coordination round to fetch exact counts for the candidate values, or accept a bounded-error answer.

One line: the inverted index cannot answer questions about the matched set, only about the matching terms. So faceting is a second, forward copy, and it cancels the pruning that made search cheap.