Designing a Web Search Engine: Inverted Index, Scatter-Gather, and Two-Phase Ranking

The Core Challenge of Web Search

The fundamental problem in web search is retrieving relevant documents from billions of pages in milliseconds. This is impossible with a linear scan. The architectural insight is to perform the expensive work of processing and indexing documents ahead of time, during crawling, leaving only fast, cheap operations for query time. This precomputed structure is known as the inverted index.

The Inverted Index: Flipping the Problem

Unlike a traditional document-to-word index, an inverted index maps words to the documents that contain them. For each unique word, a "postings list" stores references to all documents where it appears. When a user queries for multiple words (e.g., "database sharding"), the system performs a set intersection of the corresponding postings lists. Since these lists are typically sorted by document ID, intersections can be executed very efficiently in linear time. Postings lists also store additional signals like term frequency and position, crucial for later ranking, and are aggressively compressed to reduce I/O.

Distributed Search with Scatter-Gather

To handle the scale of the entire web, the inverted index is partitioned across thousands of servers, usually by document ID. Each server (shard) holds a complete index for its slice of documents. At query time, the system employs a scatter-gather pattern:

• Scatter: The user query is sent in parallel to all relevant shards.
• Local Processing: Each shard independently intersects its local postings lists, performs a preliminary ranking, and returns its top few candidates.
• Gather: A central coordinator collects these partial results and merges them into a final global top-N list.

This parallel processing ensures that query latency is determined by the slowest shard, not the sum of all operations. Shards are also replicated for fault tolerance and increased throughput.

Two-Phase Ranking for Relevance and Efficiency

Retrieving documents based on keywords can yield thousands of matches. Ranking all of them with a complex model is computationally prohibitive. Therefore, search engines use a two-phase ranking strategy:

1. Phase 1 (Cheap Scoring): Inside each shard, a lightweight ranking model uses readily available signals (e.g., term frequency, classic relevance formulas) to quickly filter thousands of matches down to a few hundred promising candidates.
2. Phase 2 (Expensive Scoring): After gathering, a much richer and more computationally intensive ranking model is applied only to this smaller, highly relevant set of survivors. This phase considers hundreds of signals, including query meaning, page quality, freshness, and user context. This funneling approach is common in systems where expensive operations must be applied to a large dataset, balancing accuracy with performance.