Chapter 24 of 33

Search Systems & Inverted Indexes

Type "fast charging phone" on an e-commerce site and, in a fraction of a second, it shows the most relevant products out of crores of listings. It even finds items whose titles say "phones" instead of "phone", and puts the best matches first. How?

A normal database query cannot do this efficiently. Search systems use a special data structure called an inverted index, plus a ranking formula that decides which result is "most relevant". In this chapter we build an inverted index from scratch, rank results with TF-IDF and BM25, and then see how engines like Elasticsearch, OpenSearch and Apache Solr (all built on the Apache Lucene library) scale this across many machines. Ideas from Database Sharding & Partitioning and Database Replication will come back here.

An inverted index is a data structure that maps each term (word) to the list of documents that contain it, often with extra details such as how many times and at which positions the term appears. It is called "inverted" because it reverses the usual document → words mapping into word → documents.


Why Not Just Use SQL LIKE?

The obvious first attempt:

SELECT * FROM products WHERE title LIKE '%charging%';

This has several problems:

  • Full table scan. A B+ tree index (see the DBMS tutorial) is sorted by the start of the string, so it cannot help with a pattern that starts with %. The database must read every row. With 10 crore products, that is far too slow for each keystroke.

  • No understanding of words. '%phone%' also matches "earphone" and "microphone"; searching "phones" does not match "phone".

  • No ranking. Rows either match or they don't. There is no notion of "this product is a better match".

  • Multi-word queries become a messy chain of ANDs and ORs, each causing its own scan.

(Some databases do include full-text search features, such as PostgreSQL's tsvector with GIN indexes or MySQL's FULLTEXT indexes. Inside, they use the same inverted-index idea described here. Dedicated search engines go further with ranking, distribution and features like typo tolerance.)


Building an Inverted Index

Take four product titles:

Doc 1: Redmi phone with 5G and fast charging
Doc 2: Samsung phone case with stand
Doc 3: Fast charging cable for Samsung and Redmi phones
Doc 4: Wireless earphones with fast pairing

Step 1: Text Analysis

Before indexing, each document goes through an analyzer, a pipeline that turns raw text into clean terms:

  1. Tokenisation: split text into words ("Fast", "charging", "cable", ...).

  2. Normalisation: lowercase everything, maybe remove accents ("Fast" → "fast").

  3. Stop-word removal (optional): drop very common words like "the", "and", "with" that carry little meaning.

  4. Stemming or lemmatisation: reduce words to a base form ("phones" → "phone", "charging" → "charg" with an aggressive stemmer like Porter's, or "charge" with a lemmatiser).

The same analyzer must be applied to the search query, so that the query "Phones" also becomes the term "phone" and matches the index.

Step 2: Map Terms to Documents

For each term, record which documents contain it. This list is called a posting list.

Forward index (what we start with)        Inverted index (what we build)
Doc 1 → redmi, phone, 5g, fast, charging    fast     → [1, 3, 4]
Doc 2 → samsung, phone, case, stand         phone    → [1, 2, 3]
Doc 3 → fast, charging, cable, samsung,     charging → [1, 3]
        redmi, phone                        samsung  → [2, 3]
Doc 4 → wireless, earphone, fast, pairing   earphone → [4]
                                            ...

Notice "earphone" is its own term. Searching "phone" does not match "earphones", which is exactly what we want and what LIKE '%phone%' got wrong.

Step 3: Answer Queries by Combining Posting Lists

A query "samsung AND phone" becomes the intersection of two posting lists:

samsung → [2, 3]
phone   → [1, 2, 3]
AND     → [2, 3]

Posting lists are stored sorted by document ID, so two lists of lengths m and n can be intersected in O(m + n) time by walking through both with two pointers, like the merge step of merge sort. A good trick is to start with the shortest list, because the result can never be longer than it. OR is a union of lists, and NOT is a difference.

The key point: the cost depends on the length of the posting lists for the query terms, not on the total number of documents. That is why search stays fast even with billions of documents.

Positions for Phrase Queries

To answer the phrase query "fast charging" (the words next to each other, in order), the index also stores positions:

fast     → doc1: [pos 4], doc3: [pos 1], doc4: [pos 3]
charging → doc1: [pos 5], doc3: [pos 2]

Phrase match where position(charging) = position(fast) + 1 → docs 1 and 3

(Positions counted after stop-word removal, starting at 1.) This is called a positional index.


Ranking: Which Result Comes First?

Finding matching documents is only half the job. With thousands of matches, the order matters most. Classic ranking uses two intuitions:

  • Term frequency (TF): a document that mentions the query term more often is probably more about it.

  • Inverse document frequency (IDF): a term that appears in very few documents is more informative. "phone" appears in many product titles; "5g" in fewer, so matching "5g" says more.

TF-IDF

tf-idf(t, d) = tf(t, d) × log(N / df(t))

tf(t, d) = number of times term t occurs in document d
N        = total number of documents
df(t)    = number of documents containing t

Worked example (N = 1,000 documents, natural log):

Term "phone":  df = 400 → idf = ln(1000/400) = ln 2.5  ≈ 0.92
Term "5g":     df = 20  → idf = ln(1000/20)  = ln 50   ≈ 3.91

A doc with "phone" once and "5g" once:  1 × 0.92 + 1 × 3.91 = 4.83
A doc with "phone" three times only:    3 × 0.916           ≈ 2.75

The rarer word "5g" carries more weight, so the first document ranks higher.

BM25: The Modern Default

TF-IDF has two weaknesses. Repeating a word 50 times raises the score linearly (easy to spam), and long documents naturally contain more words, so they win unfairly. BM25 (Okapi BM25) fixes both and has been the default similarity in Lucene-based engines, including Elasticsearch since version 5.0.

score(d, q) = Σ over terms t in q of
              IDF(t) × tf × (k1 + 1) / ( tf + k1 × (1 − b + b × |d| / avgdl) )

IDF(t) = ln(1 + (N − n + 0.5) / (n + 0.5))      (n = docs containing t)
|d|    = length of document d (in terms); avgdl = average length
k1     = 1.2  (how quickly extra occurrences stop helping)
b      = 0.75 (how strongly long documents are penalised)
  • Saturation: as tf grows, the score approaches IDF × (k1 + 1) and stops increasing. The 10th occurrence of a word adds very little.

  • Length normalisation: a document longer than average gets a bigger denominator, so the same tf scores lower.


A Mini Search Engine in Python

This program builds an inverted index with term frequencies, supports AND queries, and ranks results with BM25 (same formula and constants as above).

import math
import re
from collections import defaultdict

STOP_WORDS = {"a", "an", "the", "is", "of", "and", "to", "in", "for", "with"}


def analyze(text):
    """Text -> list of terms: lowercase, split, drop stop words, crude stemming."""
    terms = []
    for word in re.findall(r"[a-z0-9]+", text.lower()):
        if word in STOP_WORDS:
            continue
        if len(word) > 3 and word.endswith("s") and not word.endswith("ss"):
            word = word[:-1]              # "phones" -> "phone" (toy stemmer)
        terms.append(word)
    return terms


class SearchIndex:
    def __init__(self):
        self.postings = defaultdict(dict)   # term -> {doc_id: term_frequency}
        self.doc_len = {}                   # doc_id -> number of terms
        self.docs = {}

    def add(self, doc_id, text):
        self.docs[doc_id] = text
        terms = analyze(text)
        self.doc_len[doc_id] = len(terms)
        for t in terms:
            self.postings[t][doc_id] = self.postings[t].get(doc_id, 0) + 1

    def boolean_and(self, query):
        lists = [set(self.postings.get(t, {})) for t in analyze(query)]
        if not lists:
            return []
        lists.sort(key=len)                 # intersect smallest list first
        result = lists[0]
        for s in lists[1:]:
            result &= s
        return sorted(result)

    def bm25(self, query, k1=1.2, b=0.75):
        N = len(self.docs)
        avgdl = sum(self.doc_len.values()) / N
        scores = defaultdict(float)
        for t in analyze(query):
            plist = self.postings.get(t, {})
            n = len(plist)                  # document frequency
            if n == 0:
                continue
            idf = math.log(1 + (N - n + 0.5) / (n + 0.5))
            for doc_id, tf in plist.items():
                norm = k1 * (1 - b + b * self.doc_len[doc_id] / avgdl)
                scores[doc_id] += idf * tf * (k1 + 1) / (tf + norm)
        return sorted(scores.items(), key=lambda x: -x[1])


docs = {
    1: "Redmi phone with 5G and fast charging",
    2: "Samsung phone case with stand",
    3: "Fast charging cable for Samsung and Redmi phones",
    4: "Wireless earphones with fast pairing",
}

idx = SearchIndex()
for d, text in docs.items():
    idx.add(d, text)

print("Inverted index (term -> {doc: tf}):")
for term in sorted(idx.postings):
    print(f"  {term:<9} {dict(sorted(idx.postings[term].items()))}")

print("\nAND query 'samsung phone':", idx.boolean_and("samsung phone"))
print("\nBM25 ranking for 'fast charging phone':")
for doc_id, score in idx.bm25("fast charging phone"):
    print(f"  doc {doc_id}  score={score:.3f}  {docs[doc_id]}")

Output:

Inverted index (term -> {doc: tf}):
  5g        {1: 1}
  cable     {3: 1}
  case      {2: 1}
  charging  {1: 1, 3: 1}
  earphone  {4: 1}
  fast      {1: 1, 3: 1, 4: 1}
  pairing   {4: 1}
  phone     {1: 1, 2: 1, 3: 1}
  redmi     {1: 1, 3: 1}
  samsung   {2: 1, 3: 1}
  stand     {2: 1}
  wireless  {4: 1}

AND query 'samsung phone': [2, 3]

BM25 ranking for 'fast charging phone':
  doc 1  score=1.377  Redmi phone with 5G and fast charging
  doc 3  score=1.270  Fast charging cable for Samsung and Redmi phones
  doc 4  score=0.381  Wireless earphones with fast pairing
  doc 2  score=0.381  Samsung phone case with stand

Doc 1 and Doc 3 match all three terms, but Doc 1 is shorter (5 terms vs 6), so BM25's length normalisation ranks it first. Let's verify Doc 2's score by hand. It matches only "phone" (tf = 1, |d| = 4). Document lengths are 5, 4, 6, 4, so avgdl = 19/4 = 4.75. "phone" is in n = 3 of N = 4 documents.

IDF  = ln(1 + (4 − 3 + 0.5) / (3 + 0.5)) = ln(1.4286) ≈ 0.3567
norm = 1.2 × (1 − 0.75 + 0.75 × 4 / 4.75) = 1.2 × 0.8816 ≈ 1.0579
part = 1 × 2.2 / (1 + 1.0579)             = 2.2 / 2.0579 ≈ 1.0690
score = 0.3567 × 1.0690 ≈ 0.381  ✓

Notice the toy stemmer's special rule for "ss": without it, "wireless" would become "wireles". Real stemmers (Porter, Snowball) contain many such rules, and choosing the analyzer is one of the most important decisions in a search system.


Scaling Search: The Architecture of a Search Engine

One machine cannot hold an index for billions of documents or answer thousands of queries per second. Engines like Elasticsearch and OpenSearch distribute the index:

  • Index: a logical collection of documents (like a table), e.g. products.

  • Shard: the index is split into shards, each a complete Lucene index for a subset of documents. Documents are assigned to shards by hashing their ID (document-based partitioning).

  • Replica: each primary shard has copies on other nodes for fault tolerance and to serve more read traffic.

                      Query: "fast charging phone"
                                 │
                       ┌─────────▼─────────┐
                       │ Coordinating node │
                       └──┬──────┬──────┬──┘      scatter
                          ▼      ▼      ▼
                     ┌───────┐┌───────┐┌───────┐
                     │Shard 0││Shard 1││Shard 2│  each returns its top-10
                     └───┬───┘└───┬───┘└───┬───┘
                         └────────┼────────┘      gather
                                  ▼
                 merge 30 candidates → global top-10
                 then fetch the full documents for those 10

This scatter-gather pattern (Elasticsearch calls it query then fetch) is why a search is only as fast as its slowest shard. Too many small shards add overhead to every query; too few large shards are slow to move and recover. Since Elasticsearch 7.0, a new index gets 1 primary shard by default, and you choose more based on data size.

Why Search Is "Near Real-Time"

Lucene writes new documents into small, immutable segments. A new document becomes searchable only after a refresh opens a new segment, which in Elasticsearch happens every 1 second by default (for indices that are actively being searched). So a product added now appears in search results about a second later, not instantly. That is near real-time search. In the background, small segments are merged into bigger ones; deletions are only marks until a merge removes them.

Immutable segments are a smart design: they can be cached aggressively, need no locks for reading, and compress well.


Keeping the Search Index in Sync with the Database

The search engine is usually not the source of truth. The main database (say, MySQL) holds the real product data, and the search index is a derived copy, optimised for searching.

Option A: dual write (fragile)
App ──write──→ MySQL
    └─write──→ Search index      ← if this fails, they silently diverge

Option B: change data capture (preferred)
App ──write──→ MySQL ──binlog──→ CDC tool ──→ Kafka ──→ Indexer ──→ Search index

With change data capture (CDC), every committed database change is read from the database's log and pushed through a queue (see Message Queues & Pub/Sub) to an indexer. The index is eventually consistent with the database: usually a few seconds behind, but because the log records every committed change and the pipeline retries, updates are not silently lost the way a failed dual write loses them. (Indexers should be idempotent, since a change may be delivered more than once.) For a full rebuild (for example after changing the analyzer), you re-index into a new index and switch an alias to it with zero downtime.


Extra Features You Will Be Asked About

Feature

How it is usually built

Autocomplete / typeahead

Edge n-grams in the index ("phone" is also indexed as "ph", "pho", "phon", so the typed prefix "pho" finds it), or a trie of popular queries ranked by frequency, often served from memory or cache

Typo tolerance ("samsng")

Fuzzy queries that match terms within a small edit (Levenshtein) distance, typically 1 or 2

Synonyms ("mobile" = "phone")

A synonym filter in the analyzer

Filters and facets (brand, price range)

Structured fields indexed separately; aggregations count matches per brand or price bucket

Personalised / business ranking

Combine text relevance with signals like popularity, rating and stock, often with a learning-to-rank model

Semantic search

Vector embeddings with approximate nearest neighbour search, often combined with BM25 ("hybrid search")


Common Mistakes

  • Using the search engine as the primary database. Search engines are built for fast retrieval, not transactions; keep the source of truth in a proper database.

  • Different analyzers at index time and query time, so query terms never match indexed terms.

  • Expecting instant visibility. A document indexed now may not be searchable until the next refresh.

  • Calling it "inverted" because it is sorted backwards. It is inverted because it maps word → documents instead of document → words.

  • Over-sharding: hundreds of tiny shards make every query slow because of scatter-gather overhead.

  • Using dual writes to keep DB and index in sync, which leads to silent mismatches.


Interview Questions

Q1. What is an inverted index and why is it fast?

It maps each term to a sorted list of documents containing it. A query only reads the posting lists of its own terms and merges them, so the work depends on how many documents contain those terms, not on the total number of documents.

Q2. How do you intersect two posting lists efficiently?

Keep them sorted by document ID and walk both with two pointers, advancing the one with the smaller ID and emitting matches: O(m + n). Start with the shortest list when there are several terms.

Q3. What problems of TF-IDF does BM25 fix?

Term frequency saturation (repeating a word gives diminishing returns, controlled by k1) and document length normalisation (long documents are not unfairly favoured, controlled by b).

Q4. In a collection of 10,000 documents, a term appears in 100 of them. What is its IDF using ln(N/df)?

ln(10,000 / 100) = ln 100 ≈ 4.61.

Q5. Why is Elasticsearch called near real-time?

New documents become searchable only after a refresh opens a new Lucene segment, which happens every second by default, so there is a small delay between indexing and visibility.

Q6. How would you keep a product search index consistent with MySQL?

Use change data capture: read the MySQL binlog, publish changes to a queue such as Kafka, and have an indexer apply them to the search index. Accept eventual consistency, and rebuild via a new index plus alias switch when the mapping changes.


Summary

  • LIKE '%word%' scans every row, has no idea of words, and cannot rank results.

  • An inverted index maps term → posting list of documents (with frequencies and positions).

  • Text goes through an analyzer (tokenise, lowercase, stop words, stem); the query uses the same analyzer.

  • Boolean queries are posting-list intersections and unions; phrase queries use positions.

  • Ranking: TF-IDF rewards frequent and rare terms; BM25 adds saturation and length normalisation and is the modern default.

  • Search engines shard the index and use scatter-gather; Lucene's immutable segments make search near real-time.

  • Keep the database as the source of truth and feed the index with CDC.

Analyze the words, invert the index, intersect the lists, and let BM25 sort the winners.