Two-Stage Processing: Fast Filter, Then Precise Ranking

A search engine holds 10 million documents, and a query for "distributed systems" must return the 10 most relevant, ranked by quality. Running a complex relevance model over all 10 million takes far too long. Two-stage processing splits the work: a fast filter cuts the data down to a small set of candidates, then an expensive, precise algorithm runs only on those.

Fast filter, then precise ranking

• Stage one favors speed over precision. An inverted index maps keywords to documents; "distributed systems" looks up both terms and intersects the lists, finding 50,000 documents in milliseconds with hash lookups and set operations and no scoring.
• Stage two favors precision. The ranker scores each candidate using term frequency, document popularity, user location and click-through history, then sorts and returns the top 10. That's expensive per document, but feasible on 50,000 instead of 10 million.

Why it scales

The filter removes orders of magnitude. Running a complex algorithm over 10 million items might take 30 seconds; filtering to 1,000 candidates in 20 ms and scoring them in 80 ms finishes in 100 ms. The cheap stage handles most of the data; the slow stage sees only a sliver.

• Stages scale independently: filtering machines with fast SSDs and lots of RAM for indexes; ranking machines with GPUs for ML models. Add filter capacity for more queries, ranking capacity when scoring is the bottleneck.
• Stage one can be approximate: a recommender uses collaborative filtering to find 500 similar users quickly (some not truly similar), and a deep model in stage two predicts what to recommend from those, correcting the filter's mistakes.

import heapq

def search(query: str, index: dict[str, set[int]], score, k: int = 10, max_candidates: int = 50_000):
    # Stage 1: cheap, recall-oriented filter (set intersection on the inverted index)
    terms = query.lower().split()
    postings = sorted((index.get(t, set()) for t in terms), key=len)
    candidates = set.intersection(*postings) if postings else set()
    candidates = list(candidates)[:max_candidates]          # cap the work for stage 2

    # Stage 2: expensive, precision-oriented scoring on the few candidates only
    return heapq.nlargest(k, candidates, key=lambda doc_id: score(doc_id, terms))

index = {"distributed": {1, 2, 3, 7}, "systems": {2, 3, 7, 9}}
popularity = {2: 0.4, 3: 0.9, 7: 0.6}
print(search("distributed systems", index, lambda d, t: popularity.get(d, 0), k=2))   # [3, 7]

Where it's used

Design considerations

• Stage one must not drop the right answers. Stage two can't recover what was filtered out, so err toward passing too many candidates (better 10,000 than missing the best result).
• Pass IDs, not documents. Shipping 50,000 full documents between stages wastes bandwidth; pass IDs (plus only the fields stage two needs) and let stage two fetch details.
• Watch the reduction ratio. If stage one emits 100,000 items and stage two can't keep up, tighten the filter; if it emits 10 and stage two is idle, loosen it for better quality. Tune both stages together.

In an interview, say plainly that ranking every document is too slow, propose index-based retrieval followed by ranking, discuss the recall vs speed trade-off of the filter, and name techniques for each stage: hash lookups, inverted indexes, Bloom filters or LSH for stage one; ML models, graph algorithms or detailed similarity for stage two.