These are the notes for System Design episode 22. A customer types "tea" into ChaiNow's search box and gets... Steamed Momos. You'll see why checking every dish is both slow and wrong, invent the inverted index (the idea inside every search engine), teach it that "CHAI!" is still "chai" with analysis (tokenizing, lowercasing, stemming), answer two-word searches with AND and OR as list intersection and union, put the best result first with TF-IDF and then BM25 (Elasticsearch's default), and split an index that outgrows one machine into shards. Every demo is plain Python and runs as-is; outputs are real (Python 3.13). The menu is made up, timings change from run to run and machine to machine, and the "remove a final s" stemmer is a toy (real engines use language-aware stemmers).
The problems
| Problem | What it teaches |
|---|---|
| Check every dish | Full-text search, why a scan (or SQL LIKE '%tea%') is slow and matches letters, not words |
| Find it instantly | The inverted index, posting lists, forward vs inverted |
| "CHAI!" isn't "chai" | Analysis: tokenization, normalization, stemming, the same analyzer for documents and queries |
| Two words | AND = intersection, OR = union of posting lists |
| Which result first? | Relevance and ranking: tf, idf, TF-IDF, BM25 (k1, b) |
| Words in the right order | Positions in posting lists, phrase search |
| Too big for one machine | Sharding the index by document, scatter-gather, merging the top results, replicas |
Problem 1: check every dish
ChaiNow lists 1 million dishes from thousands of cafes, and at lunchtime 1,000 people search every second. The obvious way: go through every dish and keep it if the query appears anywhere in the name. That is also what SQL's WHERE name LIKE '%tea%' does.
import time
# 1 million dishes on ChaiNow: 16 names from many cafes
MENU = ["Ginger Tea", "Masala Chai", "Steamed Momos", "Iced Tea",
"Paneer Tikka", "Butter Naan", "Steamed Idli", "Masala Dosa",
"Kulhad Chai", "Green Tea", "Cold Coffee", "Masala Maggi",
"Veg Samosa", "Lemon Soda", "Aloo Paratha", "Filter Coffee"]
dishes = [f"{MENU[i % 16]} #{i}" for i in range(1_000_000)]
def search(query): # the obvious way: check every dish
return [d for d in dishes if query.lower() in d.lower()]
start = time.perf_counter()
found = search("tea")
ms = (time.perf_counter() - start) * 1000
print(f"'tea': {len(found):,} matches in {ms:.0f} ms")
print(found[:4])
Output (the time varies by run and machine: about 120 ms in the video, 89-164 ms in test runs, 169 ms on a busy machine here):
'tea': 312,500 matches in 169 ms
['Ginger Tea #0', 'Steamed Momos #2', 'Iced Tea #3', 'Steamed Idli #6']
Two failures:
- Slow. Every search reads every dish. At about 100 ms a search and 1,000 searches a second, that's about 100 seconds of work every second.
- Wrong. "Steamed" contains the letters t-e-a. We searched for letters, not words: 312,500 matches, but only 187,500 are real teas (next demo).
A normal database index (a B-tree, episode 10) can't help either: it sorts whole values, so it finds names that start with "tea", not names with "tea" somewhere in the middle. Searching for words inside text is called full-text search.
Problem 2: the inverted index
Need "photosynthesis" in a 300-page biology textbook? You don't read every page; you turn to the index at the back: "Photosynthesis: 12, 45". That index was written once, when the book was printed, not every time someone reads it. Then a search is one lookup.
In code: for every word, a list of the ids of the dishes that contain it.
import time
MENU = ["Ginger Tea", "Masala Chai", "Steamed Momos", "Iced Tea",
"Paneer Tikka", "Butter Naan", "Steamed Idli", "Masala Dosa",
"Kulhad Chai", "Green Tea", "Cold Coffee", "Masala Maggi",
"Veg Samosa", "Lemon Soda", "Aloo Paratha", "Filter Coffee"]
dishes = [f"{MENU[i % 16]} #{i}" for i in range(1_000_000)]
# build ONCE: every word -> the ids of the dishes that contain it
index = {}
start = time.perf_counter()
for dish_id, name in enumerate(dishes):
for word in name.lower().split()[:-1]: # skip the "#123" part
index.setdefault(word, []).append(dish_id)
print(f"built: {len(index)} words in {time.perf_counter() - start:.1f} s")
def search(query): # one dictionary lookup
return index.get(query.lower(), [])
start = time.perf_counter()
found = search("tea")
us = (time.perf_counter() - start) * 1_000_000
print(f"'tea': {len(found):,} matches in {us:.0f} microseconds")
print([dishes[i] for i in found[:4]])
Output (times vary by run and machine; the build takes under a second, the lookup a few microseconds):
built: 25 words in 0.7 s
'tea': 187,500 matches in 4 microseconds
['Ginger Tea #0', 'Iced Tea #3', 'Green Tea #9', 'Ginger Tea #16']
setdefault(word, [])creates an empty list the first time a word appears, then.appendadds the dish id.- The build costs about 0.7 s, once. A million dishes have only 25 different words.
- A search is one dictionary lookup: a few microseconds instead of about 100 ms, thousands of times faster.
- The results are only real teas (Ginger Tea, Iced Tea, Green Tea): no momos, because "steamed" is its own word.
Elasticsearch: The Definitive Guide puts it exactly like this: "An inverted index consists of a list of all the unique words that appear in any document, and for each word, a list of the documents in which it appears." It is inverted because it flips dish → words into word → dishes. When dishes are added, changed or removed, the index is updated too.
Forward vs inverted index
| Forward index | Inverted index | |
|---|---|---|
| Maps | document → its words | word (term) → the documents that contain it |
| Example | dish 3 → "iced", "tea" | "tea" → 0, 3, 9, 16, ... |
| Good at | "What words are in dish 3?" (showing a document) | "Which dishes contain tea?" (search) |
| Search cost | Read every document | One lookup per query word |
| Built | It's just how the data is stored | Once, up front; updated when documents change |
| Each entry's list | The document's words | A posting list (the sorted document ids, often with counts and positions) |
The trade-off is the one you've seen with caches and database indexes: pay once when writing, so every read is fast. The cost is extra storage and extra work on every write.
Problem 3: "CHAI!" is not "chai"
Cafes type names their way ("Masala CHAI!", "Ginger-Tea") and customers search their way ("chai", "Teas"). The index only matches words that are exactly equal.
import re
dishes = ["Masala CHAI!", "Ginger-Tea", "Iced teas", "Kulhad chai, hot"]
def build(split_words):
index = {}
for dish_id, name in enumerate(dishes):
for word in split_words(name):
index.setdefault(word, set()).add(dish_id)
return index
def naive(text): # just split on spaces
return text.lower().split()
def analyze(text): # tokenize + normalize
words = re.findall(r"[a-z]+", text.lower()) # letters only
return [w[:-1] if w.endswith("s") else w for w in words] # teas -> tea
for name, fn in [("naive", naive), ("analyzed", analyze)]:
index = build(fn)
for query in ["chai", "Teas"]:
word = fn(query)[0] # the query gets the SAME treatment
print(f"{name:<9} {query!r:<7}", sorted(dishes[i] for i in index.get(word, [])))
Output:
naive 'chai' []
naive 'Teas' ['Iced teas']
analyzed 'chai' ['Kulhad chai, hot', 'Masala CHAI!']
analyzed 'Teas' ['Ginger-Tea', 'Iced teas']
- Naive: the index holds
chai!andchai,(punctuation glued on) andginger-tea(one word), so "chai" finds nothing and "Teas" finds only "Iced teas". - Analyzed:
re.findall(r"[a-z]+", ...)keeps only runs of letters, so punctuation and hyphens split words; removing a finalsturnsteasintotea. Now "chai" finds both chais and "Teas" finds both teas.
The steps have names:
- Tokenization: splitting text into words (tokens, or terms once stored in the index).
- Normalization: making tokens comparable: lowercasing, removing accents, and stemming (cutting a word to its root:
teas→tea,foxes→fox). - Analysis: the whole pipeline; the code that does it is an analyzer.
The Definitive Guide's example documents are "The quick brown fox jumped over the lazy dog" and "Quick brown foxes leap over lazy dogs in summer": "Quick" can be lowercased to "quick", and "foxes" can be stemmed to its root form. "This process of tokenization and normalization is called analysis." And the key rule: "both the indexed text and the query string must be normalized into the same form." That is why the loop above runs the query through fn too.
Our s-remover is a toy: it turns "bus" into "bu" and does nothing for "leaves" vs "leaf". Real engines use language-aware stemmers (or dictionary-based lemmatizers), and analyzers often add more steps, such as dropping stop words ("the", "a") or mapping synonyms.
Problem 4: two words, AND and OR
The customer types "masala chai". Think of two lists at school, the cricket team and the choir:
- In the cricket team AND the choir: names on both lists, the intersection. Fewer, more exact results.
- In the cricket team OR the choir: names on either list, the union. More results.
Posting lists work exactly the same way. And even then many dishes may match, so we need a score to decide which goes first.
import math
dishes = ["masala chai", "masala dosa", "masala chai with extra masala",
"kulhad chai", "ginger chai", "masala maggi", "chai and samosa"]
index = {}
for dish_id, name in enumerate(dishes):
for word in name.split():
index.setdefault(word, set()).add(dish_id)
query = ["masala", "chai"]
both = index["masala"] & index["chai"] # AND: in both lists
either = index["masala"] | index["chai"] # OR: in any list
print("AND:", len(both), "dishes OR:", len(either), "dishes")
def score(dish_id): # rare words count more (idf),
words = dishes[dish_id].split() # repeated words count more (tf)
return sum(words.count(w) * math.log(len(dishes) / len(index[w]))
for w in query)
for dish_id in sorted(either, key=score, reverse=True)[:4]:
print(f"{score(dish_id):.2f} {dishes[dish_id]}")
Output:
AND: 2 dishes OR: 7 dishes
1.46 masala chai with extra masala
0.90 masala chai
0.56 masala dosa
0.56 masala maggi
&on two Python sets is the intersection (AND),|is the union (OR). Real engines keep posting lists sorted by document id and intersect them by walking both lists at once, like merging, starting with the shortest list.- tf (term frequency): how many times the word appears in this dish. More often → counts more.
- df (document frequency): in how many dishes the word appears. idf (inverse document frequency) = log(all dishes / dishes with the word): a rarer word scores higher. Here "masala" is in 4 of 7 dishes (idf = log(7/4) ≈ 0.56) and "chai" in 5 of 7 (log(7/5) ≈ 0.34).
- The score is the sum of tf × idf over the query words: TF-IDF. "masala chai" = 0.56 + 0.34 = 0.90; "masala chai with extra masala" = 2 × 0.56 + 0.34 = 1.46.
The weakness is visible: the dish that says "masala" twice beats plain "masala chai". A cafe could stuff "masala" ten times into a name and jump to the top, because in raw TF-IDF the score grows linearly with every repeat.
TF-IDF vs BM25
BM25 ("Best Matching 25") is the formula real engines use instead. The Elasticsearch reference lists "BM25 similarity (default)", with k1 ("The default value is 1.2") and b ("The default value is 0.75").
For a query Q with terms q₁ … qₙ and a document D:
score(D, Q) = Σ over each query term q of IDF(q) × f(q, D) × (k1 + 1) / ( f(q, D) + k1 × (1 − b + b × |D| / avgdl) )
f(q, D): the term's frequency (tf) in this document.|D|: the document's length in terms;avgdl: the average document length in the collection.IDF(q): still "rare words count more". Lucene (the library inside Elasticsearch) usesIDF(q) = ln(1 + (N − n + 0.5) / (n + 0.5)), where N is the number of documents and n the number that contain q.- k1 controls term-frequency saturation: each repeat adds less than the one before, and one term's tf part can never exceed
k1 + 1(2.2 by default). With k1 = 0, tf is ignored completely; a bigger k1 lets repeats count longer. - b controls length normalization: a match in a long text counts a bit less than in a short one. b = 0 ignores length; b = 1 normalizes fully.
How much repeating a word helps (the tf part of one term's score, before multiplying by idf):
# how much does repeating a word help? (the tf part of one term's score)
k1, b = 1.2, 0.75 # Elasticsearch's defaults
def bm25_tf(tf, doc_len, avg_len):
norm = 1 - b + b * doc_len / avg_len
return tf * (k1 + 1) / (tf + k1 * norm)
print("tf TF-IDF BM25 (avg length) BM25 (3x avg length)")
for tf in [1, 2, 3, 5, 10, 100]:
print(f"{tf:>3} {tf:>6} {bm25_tf(tf, 6, 6):>17.2f} {bm25_tf(tf, 18, 6):>20.2f}")
Output:
tf TF-IDF BM25 (avg length) BM25 (3x avg length)
1 1 1.00 0.55
2 2 1.38 0.88
3 3 1.57 1.10
5 5 1.77 1.38
10 10 1.96 1.69
100 100 2.17 2.14
| TF-IDF (as in the demo) | BM25 | |
|---|---|---|
| Rare words | Count more (idf) | Count more (idf, a smoothed version) |
| Repeats | Every repeat adds the same: 100 repeats = 100x | Saturate: approach k1 + 1 = 2.2 |
| Document length | Ignored | A match in a long text counts less (b) |
| Tunable | No | k1 (default 1.2), b (default 0.75) |
| Keyword stuffing | Pays off without limit | Pays off less and less |
| Used by | Textbooks, simple systems | Elasticsearch's and Lucene's default |
BM25 limits stuffing; it doesn't make it worthless (see the mini project). Real search systems add more signals on top, such as popularity, ratings, distance or freshness.
Problem 5: words in the right order (phrase search)
Search masala chai with AND and you also get "chai with masala peanuts": both words are there, but not as a phrase. The fix is to store where each word appears, its position (0 = first word), inside the posting list: word -> {dish_id: [positions]}. A phrase match needs the second word at the first word's position plus one.
dishes = ["masala chai", "chai with masala peanuts", "kulhad masala chai"]
# store WHERE each word appears: word -> {dish_id: [positions]}
index = {}
for dish_id, name in enumerate(dishes):
for pos, word in enumerate(name.split()):
index.setdefault(word, {}).setdefault(dish_id, []).append(pos)
print("masala:", index["masala"])
print("chai: ", index["chai"])
def phrase(a, b): # b must come right after a
hits = []
for dish_id in index[a].keys() & index[b].keys(): # AND first
if any(p + 1 in index[b][dish_id] for p in index[a][dish_id]):
hits.append(dishes[dish_id])
return sorted(hits)
both = index["masala"].keys() & index["chai"].keys()
print("AND: ", sorted(dishes[i] for i in both))
print("phrase:", phrase("masala", "chai"))
Output:
masala: {0: [0], 1: [2], 2: [1]}
chai: {0: [1], 1: [0], 2: [2]}
AND: ['chai with masala peanuts', 'kulhad masala chai', 'masala chai']
phrase: ['kulhad masala chai', 'masala chai']
Positions are what make a search in quotes ("masala chai") work. They cost extra space in the index, which is why search engines let you choose per field whether to keep them.
Problem 6: too big for one machine
With 100 million dishes and many words each, the index outgrows one machine. So we shard it, like the database in episode 12:
- Split the dishes across machines (shard by document). Each shard builds the inverted index for its own dishes only.
- A word's matches can be on any shard, so the query goes to every shard at once (scatter).
- Each shard ranks its own matches and returns only its top 10.
- A coordinator merges those lists and shows the best 10 overall (gather).
- Replicas of each shard (episode 11) keep search up when a machine dies, and share the read load.
# scatter-gather: every shard indexes its own dishes; ask all, merge the top
import heapq
shards = [ # (score, dish) results each shard found
[(2.9, "Masala Chai #4"), (2.1, "Masala Chai Large #12"), (0.8, "Masala Dosa #20")],
[(3.4, "Special Masala Chai #7"), (1.2, "Masala Maggi #31")],
[(2.5, "Masala Chai Kulhad #50"), (2.4, "Masala Chai #66"), (0.9, "Chai #71")],
]
def top_k(results, k): # each shard returns only its own best k
return heapq.nlargest(k, results)
K = 3
gathered = [hit for shard in shards for hit in top_k(shard, K)]
for score, dish in heapq.nlargest(K, gathered): # merge: the best k overall
print(f"{score:.1f} {dish}")
Output:
3.4 Special Masala Chai #7
2.9 Masala Chai #4
2.5 Masala Chai Kulhad #50
The best result overall came from shard 2, so asking only one shard would have missed it. (Scores here are made up; in a real cluster each shard computes idf from its own documents, so scores can differ slightly between shards.) The slowest shard sets the response time.
The whole chain
- Check every dish: about 100 ms a search, and "tea" finds Steamed Momos (letters, not words).
- Inverted index: word → dish ids, built once; a search takes microseconds, only real teas.
- Analysis: tokenize, lowercase, stem, the same for documents and queries: "chai" goes from 0 to 2 results.
- AND = intersection, OR = union of posting lists: 2 vs 7 dishes; positions in the postings give phrase search.
- Rank: TF-IDF, where repeats win without limit → BM25 (k1 = 1.2, b = 0.75), where repeats saturate.
- Shard the index by document; ask every shard, merge the top results; replicas for availability.
Common mistakes (and the real outputs)
| Mistake | Code | Output | Fix |
|---|---|---|---|
| Substring search over every row | if query in name for every dish (or LIKE '%tea%') |
'tea': 312,500 matches and 'Steamed Momos #2', about 100 ms |
An inverted index of words |
| Splitting on spaces only | index on text.lower().split() |
naive 'chai' [] |
Analyze: letters only, lowercase, stem |
| Analyzing the dishes but not the query | analyze(dish) but query.lower() |
'teas' [] (the index holds tea) |
Run the query through the same analyzer |
| Ranking by raw TF-IDF | words.count(w) * idf |
1.41 masala masala masala ties with a real dish (Practice 3) |
BM25: repeats saturate, long texts normalized |
| Asking only one shard | query shard 1 only | misses 3.4 Special Masala Chai #7 |
Scatter to every shard, merge the top k |
The third mistake, run for real:
import re
def analyze(text):
words = re.findall(r"[a-z]+", text.lower())
return [w[:-1] if w.endswith("s") else w for w in words]
dishes = ["Ginger-Tea", "Iced teas"]
index = {}
for dish_id, name in enumerate(dishes):
for word in analyze(name): # dishes ARE analyzed
index.setdefault(word, set()).add(dish_id)
query = "Teas"
wrong = query.lower() # the query is NOT
right = analyze(query)[0]
print(repr(wrong), sorted(index.get(wrong, [])))
print(repr(right), sorted(index.get(right, [])))
Output:
'teas' []
'tea' [0, 1]
Mini project: a tiny search engine with BM25
Twenty dish descriptions, one analyzer for documents and queries, an inverted index that stores each term's frequency per document, AND/OR queries, and BM25 ranking with Elasticsearch's defaults.
# Mini project: a tiny search engine over 20 dish descriptions
import math, re
DISHES = [
"Masala Chai: strong tea boiled with milk and spices",
"Ginger Tea, fresh ginger and black tea",
"Iced Tea with lemon, served cold",
"Green Tea, light and hot",
"Kulhad Chai served in a clay cup",
"Masala Dosa: crispy rice crepe with potato masala",
"Masala Maggi with vegetables",
"Paneer Tikka, grilled paneer cubes",
"Butter Naan from the tandoor",
"Steamed Momos (6 pcs) with red chutney",
"Steamed Idli with sambar and chutney",
"Cold Coffee with ice cream",
"Filter Coffee, South Indian style",
"Veg Samosa, crispy and spicy",
"Lemon Soda, sweet or salty",
"Aloo Paratha with butter and curd",
"Chai and Samosa combo",
"Elaichi Chai with cardamom",
"Masala masala masala chai masala!!", # a keyword-stuffed name
"Cutting Chai, half a glass of strong tea",
]
def analyze(text): # tokenize, lowercase, toy stemmer
words = re.findall(r"[a-z]+", text.lower())
return [w[:-1] if w.endswith("s") else w for w in words]
# build the inverted index once: term -> {doc_id: term frequency}
index, lengths = {}, []
for doc_id, text in enumerate(DISHES):
terms = analyze(text)
lengths.append(len(terms))
for t in terms:
index.setdefault(t, {})
index[t][doc_id] = index[t].get(doc_id, 0) + 1
N, avgdl = len(DISHES), sum(lengths) / len(DISHES)
def bm25(doc_id, terms, k1=1.2, b=0.75): # Elasticsearch's defaults
score = 0.0
for t in terms:
postings = index.get(t, {})
if doc_id not in postings:
continue
df, tf = len(postings), postings[doc_id]
idf = math.log(1 + (N - df + 0.5) / (df + 0.5))
norm = 1 - b + b * lengths[doc_id] / avgdl
score += idf * tf * (k1 + 1) / (tf + k1 * norm)
return score
def search(query, mode="AND", top=3):
terms = analyze(query) # the SAME analyzer as the documents
lists = [set(index.get(t, {})) for t in terms]
if not lists:
return []
hits = set.intersection(*lists) if mode == "AND" else set.union(*lists)
ranked = sorted(hits, key=lambda d: (-bm25(d, terms), d))
return [(f"{bm25(d, terms):.2f}", DISHES[d]) for d in ranked[:top]]
print(f"{N} dishes, {len(index)} terms, avg length {avgdl:.1f}")
for query, mode in [("masala chai", "AND"), ("masala chai", "OR"),
("Strong TEAS", "AND"), ("chutney", "AND"), ("pizza", "OR")]:
print(f"\n{query!r} {mode}:")
for score, text in search(query, mode) or [("-", "no results")]:
print(f" {score:>5} {text}")
Output:
20 dishes, 71 terms, avg length 5.8
'masala chai' AND:
3.91 Masala masala masala chai masala!!
2.20 Masala Chai: strong tea boiled with milk and spices
'masala chai' OR:
3.91 Masala masala masala chai masala!!
2.20 Masala Chai: strong tea boiled with milk and spices
1.91 Masala Dosa: crispy rice crepe with potato masala
'Strong TEAS' AND:
2.99 Cutting Chai, half a glass of strong tea
2.82 Masala Chai: strong tea boiled with milk and spices
'chutney' AND:
2.09 Steamed Momos (6 pcs) with red chutney
2.09 Steamed Idli with sambar and chutney
'pizza' OR:
- no results
What to notice:
- "Strong TEAS" finds "strong tea" because the query went through the same analyzer (uppercase and plural removed).
- AND returns only the 2 dishes with both words; OR adds Masala Dosa (it has "masala" twice, but no "chai").
- The stuffed name still wins: it is short (5 terms, below the 5.8 average) and its 4 repeats still add something. But BM25 gives it 3.91, not the runaway score raw TF-IDF would (4 repeats would count 4x). Saturation limits stuffing; real engines also use other signals (ratings, orders, spam rules).
- Ties are broken by document id, so the output is stable.
Extend it: add phrase search (store each term's positions in the posting list and check they are next to each other), a synonym map (chai → also tea), and split DISHES into 2 shards that each return their top 3 for a merge.
Practice
- Homework: in the INDEX demo, search "chai" and "coffee" instead of "tea". How many matches?
- Homework: in the ANALYZE demo, add the dish "Momos (6 pcs)" and search "momos" and "pcs". What changes, and what happens to the "6"?
- Homework: in the RANK demo, add a dish called "masala masala masala". Where does it land?
- Homework: should a search for "chai" also find "tea"? How would you do it?
- "masala" appears in 10 of 1,000 dishes and "chai" in 400. Using idf = log(N / df) (natural log), which word matters more, and by how much?
- Why must the query use exactly the same analyzer as the documents? What breaks if the dishes are stemmed and the query isn't?
- A search cluster has 5 shards. A user asks for the top 10. How many results does the coordinator receive at most, and why can't each shard return just 2?
Solutions and hints
1. Replace the last five lines with a loop:
for q in ["chai", "coffee"]:
found = search(q)
print(f"{q!r}: {len(found):,} matches", [dishes[i] for i in found[:3]])
built: 25 words in 0.8 s
'chai': 125,000 matches ['Masala Chai #1', 'Kulhad Chai #8', 'Masala Chai #17']
'coffee': 125,000 matches ['Cold Coffee #10', 'Filter Coffee #15', 'Cold Coffee #26']
Each is 2 of the 16 names, so 2/16 of a million = 125,000. (The build time varies by run.)
2. Use dishes = [..., "Kulhad chai, hot", "Momos (6 pcs)"] and for query in ["chai", "Teas", "momos", "pcs"]:
naive 'chai' []
naive 'Teas' ['Iced teas']
naive 'momos' ['Momos (6 pcs)']
naive 'pcs' []
analyzed 'chai' ['Kulhad chai, hot', 'Masala CHAI!']
analyzed 'Teas' ['Ginger-Tea', 'Iced teas']
analyzed 'momos' ['Momos (6 pcs)']
analyzed 'pcs' ['Momos (6 pcs)']
Naive stores pcs) with the bracket, so "pcs" misses. Analyzed, both sides become momo and pc (the toy stemmer cuts them, but the same way on both sides, so they still match). The 6 disappears completely, because the analyzer keeps letters only: a search for "6" would find nothing. A real analyzer keeps digits.
3. Add "masala masala masala" to the end of the dishes list:
AND: 2 dishes OR: 8 dishes
1.41 masala chai with extra masala
1.41 masala masala masala
0.94 masala chai
0.47 masala dosa
With 8 dishes, "masala" is in 5 and "chai" in 5, so both have idf = log(8/5) ≈ 0.47. The stuffed dish (3 × 0.47) ties for first place and beats plain "masala chai" (0.94), even though it isn't a dish anyone wants. That's raw TF-IDF's weakness; BM25 would cap each repeat.
4. Use synonyms in the analyzer: map chai to chai + tea (at index time, by adding both terms to the posting lists, or at query time, by searching chai OR tea). Query-time synonyms are easier to change without rebuilding the index. But it's a product choice: someone searching "masala chai" may not want "iced tea" ranked high, so synonyms often get a lower weight than the exact word.
5. masala: log(1000/10) = log(100) ≈ 4.61. chai: log(1000/400) = log(2.5) ≈ 0.92. A "masala" match is worth about 5x more, because it is rarer and says more about the dish.
6. The index only matches equal terms. If dishes are stored as tea and the query is teas, they never meet: 'teas' [] (see Common mistakes). The Definitive Guide: "both the indexed text and the query string must be normalized into the same form."
7. Each shard returns its own top 10, so up to 5 × 10 = 50 results. A shard can't return only 2, because all 10 best results overall might be on that one shard; only the top 10 from each shard guarantees the true overall top 10.
Quick quiz
index = {
"masala": {1, 2, 3, 6},
"chai": {1, 3, 4, 5, 7},
}
# How many dishes match
# "masala" AND "chai"?
- A. 1
- B. 2
- C. 7
- D. 9
Answer
B. AND is the intersection: {1, 3}, so 2 dishes. OR would be the union: {1, 2, 3, 4, 5, 6, 7}, 7 dishes. (9 is what you get by adding the list lengths, counting dishes 1 and 3 twice.)
Interview questions
- What is an inverted index, and why is it called "inverted"? (Term → posting list of documents; it flips the forward document → terms mapping.)
- Why not
LIKE '%term%'in a SQL database? (A full scan on every query, matches substrings not words, no ranking; a B-tree index can't help with a leading wildcard.) - What is analysis? Why must the same analyzer run at index and query time? (Tokenize + normalize: lowercase, stem, stop words, synonyms; otherwise terms never match.)
- How do you run an AND query over two posting lists efficiently? (Keep lists sorted by doc id; walk them together, start with the shortest; skip pointers.)
- Explain TF-IDF. What is its weakness? (tf × idf; repeats grow the score linearly and long documents are favoured.)
- How does BM25 improve on it? What do k1 and b do? (tf saturation controlled by k1, length normalization controlled by b; Elasticsearch defaults 1.2 and 0.75.)
- How do you scale search to billions of documents? (Shard by document, scatter-gather, each shard returns its top k, merge; replicas for availability and read throughput.)
- Why shard by document rather than by term? (By term, a hot word's list overloads one machine and multi-word queries need several shards to exchange huge lists; by document, every shard does a small, equal share and only top k results travel.)
- How do new or changed documents get into the index? (Update the index on every write, or in small batches; search engines usually make new documents visible after a short delay, so search is eventually consistent with the main database.)
- How would you design ChaiNow's search? (Main database as the source of truth, changes streamed to a search engine like Elasticsearch, an analyzer per language, BM25 plus ratings/distance for ranking, sharded and replicated.)
Glossary
| Term | Meaning |
|---|---|
| Full-text search | Finding documents by the words inside their text, not by an exact field value |
| Search engine | A system that indexes documents and answers ranked text queries (e.g. Elasticsearch) |
| Document | One searchable item: here, a dish name or description |
| Corpus / collection | All the documents being searched |
| Query | What the user searches for, e.g. "masala chai" |
| Scan (full scan) | Reading every document to answer one query |
LIKE |
SQL's pattern match; LIKE '%tea%' matches any value containing "tea", usually by scanning every row |
| B-tree index | A normal database index of sorted values (episode 10); can't help with "contains a word in the middle" |
| Term / token | A single word unit after splitting text; called a term once it is stored in the index |
| Tokenization | Splitting text into tokens (e.g. on spaces and punctuation) |
| Normalization | Making tokens comparable: lowercasing, removing accents and punctuation, stemming |
| Stemming | Cutting a word to its root form: teas → tea, foxes → fox |
| Stemmer | The code that stems; real ones know the language's rules |
| Lemmatization | Mapping a word to its dictionary form (e.g. ran → run), a smarter cousin of stemming |
| Stop words | Very common words ("the", "a") an analyzer may drop |
| Synonyms | Different words treated as the same term (e.g. chai and tea) |
| Analysis | The whole tokenization + normalization process |
| Analyzer | The code or configuration that performs analysis, used for both documents and queries |
| Inverted index | A map from each term to the list of documents that contain it |
| Forward index | A map from each document to its terms (the normal way data is stored) |
| Posting list | One term's list of document ids (often with counts and positions) |
| Posting | One entry in a posting list: a document id (plus its tf, positions) |
| Intersection | Items in both lists; how AND is answered |
| Union | Items in either list; how OR is answered |
| AND query | Matches documents containing all the query terms |
| OR query | Matches documents containing any of the query terms |
| Phrase query | Matches the terms next to each other, in order; needs positions in the postings |
| Relevance | How well a document matches what the user wanted |
| Ranking | Ordering the matches by a relevance score, best first |
| Score | The number a ranking formula gives each matching document |
| tf (term frequency) | How many times a term appears in one document |
| df (document frequency) | How many documents contain a term |
| idf (inverse document frequency) | A weight that is high for rare terms, e.g. log(N / df) |
| N | The number of documents in the collection |
| TF-IDF | Scoring a document by the sum of tf × idf over the query terms |
| Keyword stuffing | Repeating a word in a text to game the ranking |
| BM25 | "Best Matching 25", a ranking formula with tf saturation and length normalization; Elasticsearch's default |
| k1 | BM25 setting for tf saturation: how fast repeats stop adding (Elasticsearch default 1.2) |
| b | BM25 setting for length normalization: 0 = ignore length, 1 = full (Elasticsearch default 0.75) |
| Saturation | Each extra repeat adding less and less, up to a limit (k1 + 1 in BM25) |
| Document length normalization | Counting a match in a long text a bit less than in a short one |
| avgdl | The average document length in the collection, used by BM25 |
| Similarity | Elasticsearch's name for the scoring formula (BM25 by default) |
| Elasticsearch | A popular distributed search engine built on Lucene |
| Lucene | The open-source Java search library inside Elasticsearch |
| Shard | One piece of a split index, each holding some of the documents (episode 12) |
| Shard by document | Each shard gets whole documents and indexes only those |
| Replica | A copy of a shard on another machine, for availability and more read capacity (episode 11) |
| Scatter-gather | Sending a query to every shard (scatter), then collecting and merging their answers (gather) |
| Coordinator | The node that scatters the query and merges the shards' results |
| Top k | The k best results; each shard returns its own top k and the coordinator merges them |
| Eventual consistency | A newly saved document becomes searchable a little later, not instantly |
Summary
- Checking every document (or
LIKE '%tea%') is slow (reads every row) and wrong (matches letters, not words). - An inverted index maps each term to its posting list; built once, a search is one lookup: microseconds instead of milliseconds.
- Analysis (tokenize, lowercase, stem) makes messy words match, and must be the same for documents and queries.
- AND = intersection, OR = union of posting lists.
- Ranking: TF-IDF (rare words and repeats count more) lets repeats win without limit; BM25 saturates repeats (k1 = 1.2) and normalizes for length (b = 0.75), and is Elasticsearch's default.
- A big index is sharded by document; every shard is asked, each returns its top k, the results are merged, and replicas keep search up.
Next episode: every dish and every order needs an ID, but with many servers creating orders at once, two of them can hand out the same number: unique IDs at scale.
Sources: Elasticsearch: The Definitive Guide, "Inverted Index" (the definition, the quick brown fox example documents, "This process of tokenization and normalization is called analysis", "both the indexed text and the query string must be normalized into the same form"); Elasticsearch reference, similarity settings ("BM25 similarity (default)"; k1 "The default value is 1.2"; b "The default value is 0.75").