system-design

Search Systems & the Inverted Index

Why LIKE '%shoes%' is a design error, how a search engine finds one document among a billion in 10 ms, and why relevance is harder than retrieval.

Prerequisites: Indexing, Databases Overview Time to read: ~24 minutes

The problem

Users type “red running shoes” into a box. You have 50 million products. They expect results in under 200 ms, ranked by usefulness, tolerating typos, and understanding that “shoe” and “shoes” are the same thing.

Your first instinct:

SELECT * FROM products WHERE description LIKE '%running shoes%';

This is broken in five ways:

No index can help. A leading wildcard means a full table scan — 50 million rows, every query. → Indexing
It’s an exact substring match. “running shoe” (singular) finds nothing. Neither does “shoes for running.”
No ranking. A product mentioning “shoes” once and one whose title is “Running Shoes” rank identically.
No typo tolerance. “runing shoes” returns nothing, and roughly 10% of real queries have typos.
No multi-term logic. Documents matching only “red” are treated the same as documents matching all three terms.

Search is a genuinely different problem from database retrieval, and it needs a different data structure.

The inverted index

🧠 Mental model: a book’s index. A regular index maps page → words on it. An inverted index maps word → pages containing it. You want the second one, because you’re searching by word.

Forward index (what a database has):

doc1 → "red running shoes for men"
doc2 → "blue running shorts"
doc3 → "red leather shoes"

Inverted index (what a search engine has):

"red"      → [doc1, doc3]
"running"  → [doc1, doc2]
"shoes"    → [doc1, doc3]
"shorts"   → [doc2]
"leather"  → [doc3]
"men"      → [doc1]

Now “red shoes” is a set intersection: [doc1, doc3] ∩ [doc1, doc3] = [doc1, doc3]. Fast, and completely independent of total corpus size — you only touch the posting lists for the terms queried.

📐 This is why a search over a billion documents can be faster than a LIKE over a million rows. The database scans everything; the search engine touches only the two or three lists it needs.

Real posting lists store more than document IDs:

"running" → [(doc1, freq:1, positions:[1]), (doc2, freq:1, positions:[1])]

Positions enable phrase queries — “running shoes” as an exact phrase requires “shoes” to appear at position n+1 after “running”. Frequencies feed the ranking.

Building the index: the analysis pipeline

Text goes through several transformations before it becomes index terms. Getting this pipeline right matters more than any other search tuning, and it’s where most bad search experiences come from.

"Red Running SHOES for Men!"
        ↓ character filters      (strip HTML, normalize unicode)
"Red Running SHOES for Men!"
        ↓ tokenization           (split into terms)
["Red", "Running", "SHOES", "for", "Men"]
        ↓ lowercasing
["red", "running", "shoes", "for", "men"]
        ↓ stop word removal      (drop "for", "the", "a")
["red", "running", "shoes", "men"]
        ↓ stemming / lemmatization
["red", "run", "shoe", "men"]
        ↓ synonyms
["red", "run", "jog", "shoe", "sneaker", "men"]

Stemming chops to a root: “running” → “run”, “shoes” → “shoe”. Crude but fast (Porter stemmer). Lemmatization uses a dictionary to find the true base form: “better” → “good”. Slower, more accurate.

🚨 The critical rule: the same analysis must be applied at index time and at query time. If you index “shoes” as “shoe” but search for the raw “shoes”, you get nothing. This is the most common search bug, and every search engine’s “why does my query return no results” FAQ starts here.

⚖️ Stop words are a real trade-off. Removing “the”, “a”, “for” shrinks the index and speeds queries. But then you can’t search for “The Who”, “to be or not to be”, or “vitamin A”. Modern engines mostly keep stop words and handle them at ranking time instead.

Ranking: TF-IDF and BM25

Retrieval finds matches. Ranking decides which matter, and it’s the harder half.

TF-IDF combines two intuitions:

Term Frequency (TF): a document mentioning “shoes” five times is probably more about shoes than one mentioning it once.
Inverse Document Frequency (IDF): a word appearing in every document (“the”) tells you nothing. A rare word (“Vibram”) is highly informative.

score(term, doc) = TF(term, doc) × log(total_docs / docs_containing_term)

So matching a rare term is worth far more than matching a common one. That’s the whole idea.

BM25 is the modern refinement and what Elasticsearch actually uses by default. It adds two corrections that matter in practice:

TF saturation. Twenty mentions of “shoes” isn’t twenty times more relevant than one — the benefit plateaus. TF-IDF’s linear scaling lets keyword-stuffed pages win.
Document length normalization. A 10,000-word article naturally contains more terms than a 50-word product title. Without normalization, long documents dominate everything.

🎙️ “I’d use BM25 for lexical relevance — it handles term frequency saturation and document length, which plain TF-IDF gets wrong and which shows up immediately with keyword-stuffed listings.”

Beyond text relevance, real ranking blends in business signals: popularity, recency, click-through rate, conversion rate, stock availability, personalization, and paid placement. Text relevance is often only 30–50% of the final score in a commercial system, and saying so shows product awareness.

Vector search and semantic relevance

Lexical search matches words. It fails when the user’s words differ from the document’s:

Query:    "affordable laptop"
Document: "budget notebook computer"
Lexical overlap: zero. Semantic overlap: complete.

Vector (semantic) search solves this. An embedding model maps text to a high-dimensional vector where semantically similar text is nearby. Search becomes “find the nearest vectors to the query vector.”

Approximate Nearest Neighbour (ANN) algorithms make this fast — HNSW (graph-based, the common choice), IVF, product quantization. Exact nearest-neighbour search over millions of vectors is too slow; ANN trades a small amount of recall for orders of magnitude of speed.

⚖️ Vector search isn’t a replacement — it’s a complement:

	Lexical (BM25)	Vector
Exact terms, product codes, names	✅ Excellent	❌ Often poor
Synonyms and paraphrases	❌	✅
Rare/novel terms	✅	❌ (not in training data)
Explainability	✅ You can see why	❌ Opaque
Index cost	Low	High (embeddings + ANN structure)

🚨 Hybrid search is the current standard answer: run both, and fuse the results (commonly with Reciprocal Rank Fusion). Lexical catches exact matches and identifiers; vector catches intent. If a 2026 interview asks about search, proposing hybrid retrieval — and knowing why pure vector search is worse at product codes — is the strong answer.

Distributed search architecture

flowchart TB
    C[Client] --> CO[Coordinator node]
    CO --> S1[Shard 1<br/>docs 0–10M]
    CO --> S2[Shard 2<br/>docs 10–20M]
    CO --> S3[Shard 3<br/>docs 20–30M]
    S1 --> CO
    S2 --> CO
    S3 --> CO
    CO --> C

Two ways to partition, and the choice matters:

Document partitioning (used almost universally). Each shard holds a complete index for a subset of documents. A query goes to all shards; each returns its top K; the coordinator merges.

✅ Easy to add documents (write to one shard), balanced load, resilient.
❌ Every query hits every shard, so latency is bounded by the slowest — tail amplification at work.
❌ IDF is computed per-shard, so scores are slightly inconsistent across shards. Usually negligible; can be corrected with a two-phase query.

Term partitioning. Each shard holds all documents for a subset of terms. Fewer shards touched per query, but hot terms create hot shards and indexing a document requires writing to many shards. Rarely used in practice.

Replication on top gives read scaling and availability, exactly as for databases.

📐 Latency budget for a distributed search:

Coordinator → 20 shards, in parallel     ~5 ms   (bounded by slowest shard)
Each shard: index lookup + BM25 scoring  ~3 ms
Merge and re-rank top 100                ~2 ms
Fetch document bodies for top 10         ~5 ms
                                       ────────
                                        ~15 ms

Keeping the index fresh

The index is a derived data store. The database is the source of truth. Something must keep them in sync, and that something is where the bugs live.

Approach	Freshness	Complexity
Dual write (app writes both)	Immediate	🚨 The dual-write problem — they will diverge
Periodic full reindex	Hours	Simple, but heavy and stale
Event-driven (publish on change)	Seconds	Needs the outbox pattern to be reliable
CDC (read the DB replication log)	Seconds	✅ The best approach — no application changes, no missed writes

🎙️ “I’d keep search updated via CDC from the database’s replication log rather than dual-writing — dual writes silently diverge, and CDC guarantees we see every committed change. Plus a nightly full reindex as a backstop to correct any drift.”

That “plus a periodic full reindex as a backstop” clause is worth including. Derived stores drift; having a reconciliation path is a mark of operational maturity.

Near-real-time indexing. Lucene (and therefore Elasticsearch) writes to an in-memory buffer and “refreshes” to a searchable segment periodically — the default is 1 second. So there’s a small window where a written document isn’t searchable. Tune refresh_interval up (30s) for bulk indexing throughput; keep it low when freshness matters. And note this interacts with read-your-writes: a user creates a listing and immediately searches for it, finding nothing.

Features users expect

Autocomplete / typeahead — a different problem, usually solved with a trie or an FST rather than the main index. → Design Typeahead
Fuzzy matching — edit distance (Levenshtein), usually limited to 1–2 edits for performance.
Faceted search — “brand: Nike (42), size: 10 (18)”. Computed as aggregations over the result set. Expensive on high-cardinality fields.
Highlighting — showing matched terms in context. Requires positions in the index.
Pagination — 🚨 deep pagination is a real problem: page 1,000 requires every shard to return 10,000 results to the coordinator. Use search_after / cursor pagination, not from/size. → Pagination
“Did you mean?” — spelling correction from the term dictionary and query logs.

The systems

System	Character
Elasticsearch / OpenSearch	The default. Lucene-based, distributed, huge ecosystem, also used for log analytics
Apache Solr	Also Lucene. Older, strong for traditional enterprise search
Typesense / Meilisearch	Lightweight, developer-friendly, fast to set up. Great for small-to-mid catalogues
Algolia	Hosted, extremely fast, excellent relevance tooling. Expensive at scale
Postgres full-text search	🚨 Genuinely good enough for a lot of cases — `tsvector` + GIN index, no extra system to run
Vector DBs (Pinecone, Weaviate, Qdrant, pgvector)	Semantic/hybrid search

🎙️ A strong, non-obvious answer: “For a catalogue of 100,000 products with modest query volume, I’d start with Postgres full-text search. It handles stemming, ranking, and phrase queries, and it avoids running a second datastore and keeping it in sync. I’d move to Elasticsearch when we need faceting at scale, better relevance tuning, or the write volume justifies it.”

Resisting the reflex to add Elasticsearch scores well — it’s a real operational commitment.

⚖️ Trade-offs

Decision	Gain	Cost
Dedicated search engine	Real relevance, faceting, typo tolerance, scale	A second datastore to run and keep in sync
Postgres FTS	No new system; transactional consistency with your data	Weaker relevance tuning, scaling ceiling, limited faceting
More aggressive analysis (stemming, synonyms)	Higher recall	Lower precision — irrelevant results creep in
Vector search	Semantic understanding	Cost, opacity, poor at exact terms
Hybrid retrieval	Best of both	Two pipelines, fusion tuning
Frequent refresh	Fresh results	Lower indexing throughput, more segment merging

The precision/recall trade is the fundamental one in search. Aggressive stemming and synonyms find more (recall) but include more junk (precision). There’s no universally right point — it depends on whether users are looking for something specific (favour precision) or browsing options (favour recall).

In the real world

Elasticsearch’s dual life as both a search engine and a log-analytics store (the ELK stack) is worth knowing — the same inverted index that finds products also finds log lines. → Log Aggregation
Amazon’s product search is dominated by behavioural signals — purchase and click data — with text relevance as one input among many. This is the norm for commercial search: the hard part isn’t retrieval, it’s learning what people actually wanted.
Airbnb, Etsy, and Shopify have all published on migrating from pure lexical to hybrid retrieval, consistently reporting that vector search helps most with long, natural-language queries and hurts on exact identifiers — which is exactly why hybrid won.

🚨 Interview traps

Using LIKE '%term%' for search. It cannot use an index and doesn’t rank.
Not mentioning the inverted index. It’s the core data structure and the expected answer.
Forgetting index freshness. How does the search index learn about a new product? CDC or events, not dual writes.
Ignoring ranking entirely. Retrieval is the easy half.
Proposing Elasticsearch reflexively for a small catalogue. Postgres FTS may be right.
Not knowing deep pagination is expensive in a distributed search.
Treating vector search as a full replacement for lexical.

🎙️ Soundbites

“An inverted index maps terms to documents, so a query touches only the posting lists for the terms searched — that’s why corpus size barely affects latency.”
“The same analyzer must run at index time and query time, or you index ‘shoe’ and search ‘shoes’ and get nothing.”
“Search is a derived store, so I’d feed it from CDC on the database’s replication log, with a periodic full reindex as a reconciliation backstop.”
“I’d do hybrid retrieval — BM25 for exact terms and product codes, vectors for intent, fused with reciprocal rank fusion. Pure vector search is notably worse at SKUs and model numbers.”
“Text relevance is maybe 40% of the ranking here; the rest is popularity, conversion rate, and availability. Ranking is a product problem as much as a retrieval one.”

🛠️ Try it

1. Build an inverted index by hand. 20 lines of Python:

from collections import defaultdict
index = defaultdict(set)
docs = {1: "red running shoes", 2: "blue running shorts", 3: "red leather shoes"}
for doc_id, text in docs.items():
    for token in text.lower().split():
        index[token].add(doc_id)

def search(query):
    sets = [index[t] for t in query.lower().split() if t in index]
    return set.intersection(*sets) if sets else set()

print(search("red shoes"))    # {1, 3}

Then add TF-IDF scoring. Doing this once makes every search engine’s behaviour legible.

2. Use Postgres full-text search. You’ll be surprised how capable it is:

ALTER TABLE products ADD COLUMN tsv tsvector
  GENERATED ALWAYS AS (to_tsvector('english', title || ' ' || description)) STORED;
CREATE INDEX idx_tsv ON products USING GIN (tsv);
SELECT title, ts_rank(tsv, q) AS rank
FROM products, to_tsquery('english', 'running & shoes') q
WHERE tsv @@ q ORDER BY rank DESC LIMIT 10;

3. Break the analyzer. In Elasticsearch, index a field with an English analyzer and query it with a keyword (unanalyzed) query. Watch nothing match. This is the single most common search bug and seeing it deliberately is worth ten minutes.

Check yourself

1. Why can't a database index help with LIKE '%shoes%'?

A B-tree index stores values in sorted order, so it can find a *starting point* for a prefix (`LIKE 'shoe%'` is a range scan). A leading wildcard gives no starting point — "shoes" could appear at any offset in any value — so the database must examine every row. It's a full table scan regardless of the index. Trigram indexes (`pg_trgm` in Postgres) can help with substring matching, but they're a workaround; the right structure for word-based search is an inverted index.

2. Why must index-time and query-time analysis match?

Because the index stores *analyzed* terms, and the query must produce terms that can match them. If the indexer stems "shoes" to "shoe" and stores that, but the query searches the literal "shoes", there's nothing in the index equal to "shoes" and you get zero results. Same for lowercasing, synonym expansion, and stop words. The analyzers don't have to be *identical* (synonym expansion is sometimes applied only at query time, deliberately), but they must be *compatible* — and mismatches are the number one cause of "search returns nothing".

3. What does BM25 improve over TF-IDF?

Two things. **Term frequency saturation:** TF-IDF scores linearly with term count, so a page repeating "shoes" 200 times beats a genuinely relevant page — BM25 applies diminishing returns so the 20th mention adds almost nothing. **Document length normalization:** longer documents naturally contain more terms and would otherwise dominate — BM25 normalizes by length relative to the corpus average, so a 50-word product title can outrank a 10,000-word article. Both corrections address ways real corpora break TF-IDF's assumptions.

4. How do you keep a search index in sync with your database, and what's wrong with the obvious approach?

The obvious approach — the application writes to both — is the dual-write problem: the writes aren't atomic, so a failure between them leaves the index permanently wrong, silently. Better options: publish an event inside the database transaction via the **transactional outbox** and have an indexer consume it; or use **CDC** to read the database's replication log, which captures every committed change with no application involvement and no possibility of missing one. Either way, add a periodic full reindex as a reconciliation backstop, because derived stores drift.

5. When is Postgres full-text search sufficient, and when do you need Elasticsearch?

Postgres FTS is sufficient for modest corpora (up to a few million documents), moderate query volume, straightforward relevance needs, and when you value having one datastore with transactional consistency between your data and your index. You need a dedicated engine when you have: high query volume requiring independent scaling, sophisticated relevance tuning (custom scoring, boosting, learning-to-rank), faceted navigation over high-cardinality fields, typo tolerance and "did you mean", very large corpora, or a need for vector/hybrid search. The honest framing: a search engine is a real operational commitment (sync pipeline, cluster ops, reindexing), so make it earn its place.