Stop words and champion lists
A scoring function cannot rescue a document that was removed before scoring began. We can reduce search work by omitting common words or retaining only selected candidates for each term, but each shortcut discards information. The useful question is which queries lose an answer when that information disappears.
We'll compare removing words with capping candidates, then follow how each changes the results.
Removing words from the representation
The BM25 lesson kept every analyzed token and let document frequency influence its weight. Another approach removes selected words entirely. A configured list of words to omit is a stop-word list. Commonness may motivate the choice, but the actual removal is a product and language policy rather than a consequence of the score formula.Our experiment chooses exactly a, and and to. They are test inputs, not a recommended English stop list. The unchanged corpus retains them; the replay creates a separate pruned copy so later lessons continue to use the same source texts and statistics.
Deleting tokens can change more than whether a term is searchable. If the remaining tokens are packed together, their positions change. The original d5 text includes keys to rows. A packed pruned representation contains keys rows, so a request for that exact adjacent phrase can match even though the original document did not contain it.
The posting-list lesson's phrase helper checks adjacent analyzed tokens. In this experiment the stop policy is applied to both document and query text. That lets keys to rows continue to match after both sides lose to, while the distinct literal request keys rows also becomes a match. Preserving the original position gaps would avoid that particular adjacency error, though queries requiring a removed word would still need a representation that retained it.
Which common words are expendable?
Inspect both how widely a term occurs (df / N) and how often it repeats. Define the averaging population: total occurrences divided by all documents differs from the average among matching documents. These are diagnostics, not a universal rule for deleting terms.
In a database-only catalog, database may occur almost everywhere yet still matter in an exact title. A required word, negation or direction can be essential even when it has little ranking weight. Review representative title and phrase queries before choosing a stop list. Lower weighting retains evidence that deletion removes.
A configured language list is only a starting policy. Elasticsearch's stop filter allows explicit words, language lists and case handling. Its trailing-token option also matters for completion: removing the word currently being typed can change the offered suggestions. Our experiment does not emulate that analyzer; it deliberately repacks tokens to expose the phrase error.
Keeping selected candidates
There is another way to reduce work without deleting a word: retain a small preselected list of documents for it. Such a retained subset is called a champion list. The subset is chosen before the full query is known. It can be built for any term, not only common words; list sizes can differ by term.
Our chosen cap is one document per term. Build each list by scoring that single term with our BM25 variant and retaining the highest result, using identifier order for ties. At query time, take the union of the retained lists, then apply the full requested matching condition to those candidates. This is a candidate restriction, not a complete implementation of arbitrary top-result search.
For database, the equal-length single-term tie retains d2 ahead of d5. For index, the shorter document d8 wins over d5. The combined query database index therefore begins with only d2 and d8 available, even though d5 contains both terms. A document that is second for each individual term can be the best combined answer.
The two retained single-term winners contain different words. Requiring both after the cap cannot recover d5:
The losses in one capture
The Python replay performs both transformations from the original corpus. original and pruned label separately analyzed document sets. The champion portion prints complete either-term candidates, retained candidates and the result after requiring both query terms.
python3 public/course-assets/system-design/m16-search.py pruningstop words: ['a', 'and', 'to']
token occurrences: 50 -> 43
phrase keys to rows: original= ['d5'] pruned= ['d5']
phrase keys rows: original= [] pruned= ['d5']
champions database/index: {'database': ['d2'], 'index': ['d8']}
full OR candidates: ['d2', 'd5', 'd8'] capped candidates: ['d2', 'd8']
full AND: ['d5'] capped then AND: [] missed: ['d5']Fifty token occurrences become forty-three under the selected stop policy. That is a count of retained occurrences, not measured index bytes or a latency improvement. The byte layout of a real posting list could include dictionaries, offsets, positions and compression, each with its own cost.
The champion restriction removes d5, so the required-term check returns nothing. Running the scorer over the retained documents cannot repair that result because the missing identifier never reaches it. Keeping a complete index behind the shortcut would allow a fallback, but that means the complete representation and its maintenance cost still exist.
The policy boundary
For this corpus, retain every token and the complete posting lists. Their counts are small, and the counterexamples give a concrete cost for removing information. If a measured workload later makes common-term traversal expensive, first consider a query-specific policy that preserves required phrases and filters. That lets a broad browsing request accept a shortcut without silently changing exact phrase semantics.
Choose the shortcut from the kind of answer the caller expects:
| Query contract | Default | Reason |
|---|---|---|
| Required words or exact phrase | Complete retained representation | Omitted evidence can change eligibility |
| Broad exploration with complete fallback | Try bounded candidates, then complete search | Recover misses at additional work |
| Explicitly approximate suggestions | Evaluated candidate cap | The product accepts evaluated coverage loss |
Choosing query-specific pruning adds branches that need tests. A rule that ignores to in a broad topic query must not also erase it from an exact title request. Keeping a separate phrase-capable representation is another option, with the cost of another field or index. Choose that complexity only when the query contract and measurements justify it.
Evidence before an approximation
The missed d5 is an exact matching failure, which requires no user judgment to detect. Whether dropping a broader result harms the reader is a different question. Search evaluation will label documents against particular information needs and compare what the result list preserves.
Champion lists also need a publication boundary. Recomputing them after documents change can alter who survives the cap; an outdated champion entry may refer to a removed or now-inaccessible document. Index synchronization owns that version and deletion work. A preselected list never replaces the access check before exposure.
The next lesson changes another part of the path: it interprets the caller's words before retrieval. Query understanding makes those transformations visible so that a broader answer can be traced to a chosen rule rather than mistaken for a match to the original request.
Under the Hood: Optimization Strategies for Massive Corpora
When searching over billions of documents, postings lists for common words contain hundreds of millions of entries. Search engines employ two contrasting strategies to maximize query throughput without sacrificing accuracy: Stop Word Handling and Champion Lists.
Champion Lists (Fancy Lists) Architecture
Under the Hood: The Evolution of Stop Words
- Historical Approach (Aggressive Removal): Early search engines stripped all stop words ("the", "to", "and", "or") during indexing to save disk space. The Failure: Queries like "To be or not to be" or "The Who" returned zero results or completely corrupted semantics.
- Modern Approach (Common-Grams & WAND): Modern engines retain all words in the index. Frequent word pairs can be indexed as single tokens (common-grams such as "to_be"), positional indexes answer phrase queries containing common words, and common terms are pruned during query evaluation using dynamic pruning algorithms like WAND (Weak AND) and Block-Max WAND.
Worked example: the cost of "the"
In a 1 billion document English web corpus, "the" appears in the large majority of documents. Even at about one byte per compressed posting, walking its list means reading hundreds of megabytes for one query term, yet its IDF is close to zero, so it barely changes the ranking. Meanwhile "raft" might appear in 200,000 documents: a fraction of a megabyte.
Three ways to handle the query the raft paper:
| Approach | Work | Risk |
|---|---|---|
| Drop "the" at index time | Minimal | Phrase and name queries such as "The Who" become impossible |
| Keep it, evaluate naively | Scans the huge list | Latency spikes on every query containing common words |
| Keep it, dynamic pruning such as WAND or Block-Max WAND | Skips most of the list because its maximum possible score contribution is tiny | Exact top K preserved; more complex implementation |
| Common grams, index "the_who" as one token | Short list for the phrase | Larger index; must choose which pairs to index |
How WAND skips work, in one paragraph
Each term stores an upper bound on its score contribution. Suppose the current 10th best score is 9.0, and the upper bounds are raft 7.0, paper 3.5, the 0.1. A document containing only "the" and "paper" can score at most 3.6, below 9.0, so it cannot enter the top 10. WAND jumps directly to the next document that contains raft, skipping millions of "the" postings. Block-Max WAND stores bounds per block of 128 postings, making the skips even tighter. Lucene has used block-max WAND for top-K disjunctions since version 8.
Champion list sizing
Choose r, the champion list length per term, larger than K. With r = 1,000 and K = 20, most two-term queries find enough candidates in the union of champion lists; queries that do not fall back to full postings. Larger r means more RAM and better recall; the right value comes from measuring recall at K on a query log against full evaluation.