How do you return the top K results without scoring and sorting every match?

The 30 second answer

Keep a min-heap of size K while iterating matches: compare each score with the smallest in the heap and replace it if larger. That costs n log K instead of n log n and needs memory only for K. Search engines go further and skip documents that cannot beat the current Kth score, using per-block maximum scores, so many matches are never fully scored.

Heap. For n candidates and K results, a min-heap ordered by score keeps the best K seen so far. Each new candidate is compared with the heap's minimum, so the work is O(n log K) and memory O(K). Break ties on a stable key, such as document ID, so pagination is deterministic. The topK method in the BM25 snippet above does exactly this.

Skipping work. Introduction to Information Retrieval describes techniques that avoid scoring every match: champion lists of the strongest documents per term, impact-ordered postings, and tiered indexes. Lucene implements the modern version: a collector can call setMinCompetitiveScore to tell the scorer it "may safely ignore all documents whose score is less than the given minScore", and the postings format stores per-block maximum impacts so whole blocks can be skipped. This is why Elasticsearch does not count every hit exactly by default; track_total_hits controls it.

Distributed top K. Each shard returns its own top K and the coordinating node merges them, so a page from + size asks every shard for from + size hits. Deep pagination multiplies that cost; Elasticsearch caps it with index.max_result_window and recommends search_after for deep paging, which Zalando's 2025 post also names as a guardrail.

Second stage. In a two-stage ranker, the first stage returns a few hundred candidates and a heavier model re-ranks only those, which keeps the expensive part bounded. Zalando's 2024 ranking-platform paper reports offline results for the top 500 candidates passed to the ranker.

Sources (5)