Scaling Data · lesson 6 of 7 · about 30 min
How full-text search works: the inverted index that turns a scan into a lookup, analysis that decides what counts as the same word, BM25 ranking you can tune, what splitting an index across shards does to relevance, why new documents appear after a refresh, and why page one thousand is a cluster-killer. Tap any for a plain-language card.
Full-text search
The catalogue below is a real inverted index of 300 seeded product descriptions. Type a query, switch between AND and OR, and see the actual postings lists. The slider extrapolates the work to a large collection: a scan reads every document, while the index reads only the lists for your terms.
Try “gaming keyboard” with AND and with OR, then move the collection size up to a billion documents.
AND over 2 terms matches 50 of 300 documents, for example #7: “pixel ergonomic wireless headphones for travel”. At 1,000,000,000 documents a scan would read all of them; the index reads about 850,000,000 postings, only the lists for wireles and headphone.
A real inverted index built in the browser from seeded descriptions, using a lower-casing, stop-word and light-stemming analyzer. The extrapolation scales the measured share of postings to the chosen collection size.
Analysis
The same analyzer must be applied to documents and queries, or terms will not line up. Real analyzers also handle accents, synonyms, languages without spaces and compound words, which is where search engineering effort really goes. Toggle the options and watch the tokens, the index size and the number of matches for the query “headphone”.
Switch stemming off and the query “headphone” finds nothing. Switch lower-casing off and capitalised words split into separate terms.
With these settings the sentence becomes 3 tokens. The index holds 37 distinct terms and 1,666 postings; a search for “headphone” matches 101 documents and “Headphones” matches 101. Stemming folds singular and plural together.
The catalogue is 300 seeded descriptions. The stemmer is a light suffix stripper (-ing, -ed, -s), enough to show the effect; production engines use language-specific analyzers.
Ranking
This is a real BM25 and TF-IDF implementation over 300 seeded product descriptions. Pick a query, change the model and the two parameters, and watch the order shift.
Set b to 0 (no length normalisation) and long descriptions rise; set k1 to 0 and only the presence of a term matters, not how often.
| # | Score | Description |
|---|---|---|
| 1 | 2.31 | acme wireless wireless headphones for gaming headphones and backpack |
| 2 | 2.31 | atlas wireless wireless headphones for office headphones and watch |
| 3 | 2.31 | nova wireless wireless headphones for studying headphones and watch |
| 4 | 2.31 | orbit wireless wireless headphones for running headphones and monitor |
| 5 | 2.13 | acme wireless wireless headphones for travel |
| 6 | 2.13 | atlas wireless wireless headphones for travel |
205 of 300 documents match “wireless headphones”. BM25 (k1 = 1.2, b = 0.75) puts #12 first with a score of 2.31: it contains the rare terms and is not padded with other words.
Scores are real: idf = ln(1 + (N − df + 0.5) ÷ (df + 0.5)); BM25 term score = idf × tf(k1+1) ÷ (tf + k1(1 − b + b·len/avg)).
Search at scale
There is a subtler problem. BM25's idf depends on how rare a term is in the collection, but each shard only knows its own counts. If documents are grouped by category, a word like “speaker” is common on the shard holding speakers and rare elsewhere, so the same term gets different weights on different shards, and merging the scores compares apples to oranges. With random placement the local statistics are close to the global ones. Engines address it by sharing global statistics (a distributed-frequency step, at the cost of an extra round trip) or by living with the error. Below, the merged top 5 is compared with the true global top 5.
Choose the query “gaming keyboard” with category placement and 4 shards: the merged top 5 disagrees with the global ranking.
With category-based placement across 8 shards the merged top 5 for “waterproof speaker hiking” matches 40% of the true global top 5. Each shard computed idf from its own slice, so scores from different shards are not on the same scale.
Real BM25 on 300 seeded documents, split across shards; each shard ranks with its own idf and returns its top 5; the coordinator merges by score.
Freshness
Many small segments are expensive: every query must search each one and combine the results. So a background process merges segments into bigger ones, dropping deleted documents, spending disk and CPU to keep the count low. Refreshing more often makes data fresher and creates more segments to merge; a longer interval is cheaper and staler. Bulk loads often turn refresh off entirely and enable it afterwards.
Compare a 1-second refresh with a 30-second one for an hour of indexing: freshness against segment churn.
Refreshing every 1 s makes a new document searchable after 0.5 s on average (1 s at most). Over 60 minutes that writes 3,600 segments, which merging brings down to about 9, at a cost of roughly 1,995 seconds of merge work.
A simplified tiered-merge model: every group of merge-factor equal-size segments is merged into one; each merged segment costs 0.5 s of work per input segment (an illustrative constant).
Which structure?
Exact keys and ranges want a B-tree, words inside text want an inverted index, prefixes want a trie, and tiny data wants nothing. Each answer is worth 20 XP.
Ask: exact value, range, word inside text, or prefix? and how much data?
Find the user whose email is exactly alice@example.com.
Tip: press 1 to 4 to answer, Enter for the next one.
Who lives by this
Four published search systems.
the engine under Elasticsearch and Solr
Lucene, created by Doug Cutting, is a Java library that builds inverted indexes out of immutable segments and merges them in the background. Elasticsearch, Solr and OpenSearch are distributed servers built around it, which is why their refresh, segment and BM25 behaviour all trace back to Lucene.
refresh_interval and max_result_window
Elasticsearch makes new documents searchable at the next refresh, one second by default, and limits from + size to 10,000 hits per search by default because deep offset paging makes every shard sort and ship that many hits; search_after is the recommended way to go deeper.
incremental indexing
Google announced Caffeine as a new indexing system that updates the web index continuously in small increments rather than rebuilding it in large batches, so fresh pages become searchable much sooner.
real-time inverted index
Twitter's Earlybird is a real-time search engine built on Lucene that keeps recent tweets in an in-memory inverted index so that a tweet becomes searchable within seconds of being posted, while older tweets live in compact, immutable on-disk segments.
Interview angle
Six questions, each worth 20 XP. 'Design search for X' is one of the commonest interview prompts.
Say inverted index, analysis, BM25 ranking, sharding with scatter-gather, and near-real-time refresh.
What is an inverted index?
Tip: press 1 to 3 to answer, Enter for the next one.
Break it
The alternative is (search_after): remember the sort key of the last hit you returned, and ask each shard for the next size hits after it. Every page then costs the same however deep you are. Users rarely need page 1,000 anyway; better filters and ranking serve them better than infinite pagination.
At 50 shards, page 1,000 with 10 per page makes the cluster sort and ship half a million hits. A cursor makes it 500.
Page 1,000 at 10 per page means each of 50 shards sorts its top 10,000 hits and the coordinator merges 500,000 of them to return 10. A cursor-based request would touch 500: 1,000 times less.
Hits handled = shards × (offset + size) for offset paging versus shards × size for a cursor.
Where to go next