Searching the Index, and Index Design Factors

In one line: the query mechanics are simple. The interesting question is what happens when a term matches millions of documents — which is the normal case, not the exception.

Searching for a multi-word query

For the query search engine, the relevant mappings are:

Both terms appear in documents 1, 2, and 3:

• search: Document 1 (pos 6), Document 2 (pos 4), Document 3 (pos 5).
• engine: Document 1 (pos 9), Document 2 (pos 5), Document 3 (pos 8).

search  -> {1, 2, 3}
engine  -> {1, 2, 3}
          -----------
intersection = {1, 2, 3}   <- all three documents match both terms

Intersection order matters enormously at real scale

With three documents, order is irrelevant. With real posting lists it is the difference between a fast query and a slow one.

Suppose search matches 50 million documents and engine matches 80 million, but a third term elasticsearch matches 200,000. Intersecting from the smallest list first bounds the whole operation at 200,000 comparisons; starting with the largest does far more work to reach the same answer.

That is why an index stores document frequency per term — it lets the query planner order the intersection cheaply. It is the same instinct as a database query planner choosing join order by selectivity, and it is a good detail to volunteer.

Posting lists are also kept sorted by document ID precisely so intersection is a linear merge rather than a set-hash, and so skip lists can jump ahead over non-matching stretches.

Using positions to promote a phrase match

The intersection says all three documents contain both terms. Positions say something stronger:

Doc 1: search=6, engine=9   -> 3 apart, not adjacent
Doc 2: search=4, engine=5   -> ADJACENT: contains the phrase "search engine"
Doc 3: search=5, engine=8   -> 3 apart, not adjacent

So document 2 is the only true phrase match, and a ranker should place it first even though all three matched the boolean query.

This is proximity search, one of the capabilities Lesson 3 listed, and it is why positions are stored despite their cost. Terms appearing near each other is strong evidence of relevance; terms scattered across a long document is much weaker.

When a term matches millions of documents

As a single term can appear in millions of documents, the result list for a query can be extensive.

"Would this technique work when too many documents are found against a single term?"

It probably wouldn't work to return all the documents found. Instead, we should sort them by relevance to the search query. The top results should be returned to the user rather than all the documents.

This is where retrieval ends and ranking begins — and ranking is the harder half

The inverted index solves retrieval: which documents match. At web scale that answer is often millions of documents, which is useless as a response.

So the real system has a second stage the index does not provide: ranking. And its quality is what users actually experience — nobody has ever praised a search engine for its recall. They praise it for the first result being right.

Three things follow, and they shape the rest of the design:

Ranking needs signals beyond the index. Term frequency is a start, but relevance also depends on document popularity, freshness, link structure, user context, and click behaviour. The index stores frequency and position; the ranker consults much more.

Only the top-K matter. You never materialize millions of results — each node returns its best few, and Lesson 8's merger combines and sorts those. This is what makes parallel search tractable: each partition returns a small list, not its full match set.

Lesson 2's response size makes it concrete: 80 suggestions at 50 bytes. Out of potentially millions of matches, 80 are returned.

In an interview, saying "retrieval is the easy half; ranking and top-K selection are where the system actually lives" is a strong signal.

Ordering the intersection by list length is the cheapest optimization available and the one people forget: the intersection is bounded above by the shortest posting list, so starting there means every subsequent comparison runs against a smaller candidate set.

Factors of index design

Storage means RAM, and that is what forces distribution

Read the first factor carefully: "RAM and disk space required to store the index for low-latency access."

Lesson 5 makes the consequence explicit — "efficient query processing requires keeping a large portion of the inverted index in memory." An index on disk means a disk seek per term lookup, which destroys the millisecond budget.

So the real constraint is not "can we store the index" but "can we hold it in RAM" — and RAM per machine is small and expensive relative to disk. That single constraint is what makes this a distributed system. Not durability, not throughput: the index does not fit in one machine's memory.

Once you see that, Lesson 7's partitioning is not an optimization; it is the only option.

Resilience is the factor unique to search — and it is adversarial

The other four factors appear in every storage system. Resistance to manipulation does not, and it is worth pausing on.

Search rankings have direct commercial value, so there is a permanent, well-funded incentive to game them. That makes search the rare system with a genuinely adversarial input: keyword stuffing, link farms, cloaking, generated content.

Two design consequences follow:

Ranking signals must be hard to fabricate. Term frequency is trivially gamed — repeat a word a thousand times. That is precisely why PageRank used inbound links (costly to manufacture) rather than on-page text, and why modern rankers lean on behavioural signals that require real users.

The ranking algorithm must stay secret and must keep changing. A published, static ranking function is a specification for how to defeat it.

No other building block in this course has an opponent. Naming that in an interview shows you understand search as a product rather than only as a data structure.

Interview signal by level

Next: what happens when you try to do all this on one machine.