SyntaxPilot
Courses/System Design/Lesson 22

System Design · Lesson 22 of 40 · 10 min

Search: the inverted index

queued

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 .append adds 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! and chai, (punctuation glued on) and ginger-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 final s turns teas into tea. 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) uses IDF(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.

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:

  1. Split the dishes across machines (shard by document). Each shard builds the inverted index for its own dishes only.
  2. A word's matches can be on any shard, so the query goes to every shard at once (scatter).
  3. Each shard ranks its own matches and returns only its top 10.
  4. A coordinator merges those lists and shows the best 10 overall (gather).
  5. 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

  1. Check every dish: about 100 ms a search, and "tea" finds Steamed Momos (letters, not words).
  2. Inverted index: word → dish ids, built once; a search takes microseconds, only real teas.
  3. Analysis: tokenize, lowercase, stem, the same for documents and queries: "chai" goes from 0 to 2 results.
  4. AND = intersection, OR = union of posting lists: 2 vs 7 dishes; positions in the postings give phrase search.
  5. Rank: TF-IDF, where repeats win without limit → BM25 (k1 = 1.2, b = 0.75), where repeats saturate.
  6. 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

  1. Homework: in the INDEX demo, search "chai" and "coffee" instead of "tea". How many matches?
  2. Homework: in the ANALYZE demo, add the dish "Momos (6 pcs)" and search "momos" and "pcs". What changes, and what happens to the "6"?
  3. Homework: in the RANK demo, add a dish called "masala masala masala". Where does it land?
  4. Homework: should a search for "chai" also find "tea"? How would you do it?
  5. "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?
  6. Why must the query use exactly the same analyzer as the documents? What breaks if the dishes are stemmed and the query isn't?
  7. 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").