Search

Full-text search and the typeahead problem. Why a database can't do it, how an inverted index does, and how relevance is ranked.

Inverted index Tokenization TF-IDF / BM25 Elasticsearch Typeahead
đŸšĢ

Why Not LIKE '%term%'

the moment a product needs real search

The naive answer to search is WHERE body LIKE '%term%'. It fails on three counts. A leading wildcard can't use an index, so every query is a full table scan (Indexing). There's no relevance — you get matches in arbitrary order, not best-first. And there's no tokenization — searching "running" won't find "run," "Run," or "ran," because it's dumb substring matching.

The moment a product needs to search text meaningfully, it needs a structure built for it: the inverted index.

🔄

Inverted Indexes

term → the documents that contain it

A normal index maps document → its contents. An inverted index flips it: each term maps to a posting list of the documents that contain it. Now "find documents with 'search'" is one lookup returning the list, not a scan of every document.

  Documents                          Build: tokenize → normalize → index
  D1: "The fast fox"                   split into words │ lowercase, stem,
  D2: "A fast car"                                      │ drop stop-words
  D3: "The fox runs"                                    â–ŧ

  Inverted index (term → posting list):
     fast  ─â–ļ [ D1, D2 ]
     fox   ─â–ļ [ D1, D3 ]
     run   ─â–ļ [ D3 ]        ("runs" stemmed to "run")
     car   ─â–ļ [ D2 ]
     ("the", "a" dropped as stop-words)

Building it is a pipeline. Tokenize the text into terms, then normalize: lowercase, stem words to their root ("running" → "run"), and drop stop-words ("the," "a," "is") that carry no signal. The same pipeline runs on the query, so query and index meet in the same normalized form — which is exactly what makes "Running" match "ran."

🔍

The Query Side

combining posting lists

Once terms map to posting lists, queries are set operations on those lists. An AND query intersects the lists — documents that contain both terms. An OR query unions them. A phrase query ("fast fox" as an exact phrase) needs more than membership: the index must store each term's position within the document, so you can check the words appear adjacent and in order.

ℹī¸
Posting lists are kept sorted by document ID precisely so intersection and union are fast linear merges rather than nested lookups. It's the same reason sorted structures win elsewhere — order turns a search into a walk.
đŸŽ¯

Relevance

ranking matches best-first

Finding matches is half the job; ordering them is the half users feel. The intuition is TF-IDF: a term matters more in a document when it appears often there (term frequency) and rarely across the whole corpus (inverse document frequency). "The" appears everywhere, so it's worthless for ranking; a rare term is a strong signal. BM25 is the refined, saturating version of this idea and the default scoring function in modern engines.

💡
Text score is only the start. Real ranking blends signals beyond the words: recency, popularity or click-through, and personalization. The honest framing in an interview is "BM25 gives the text-relevance baseline, then I'd layer business signals — recency, popularity, personalization — on top." Naming that separation shows you know search is ranking, not just matching.
🏗

Search Infrastructure

Elasticsearch, shards, and staying in sync

Elasticsearch (and OpenSearch, both on Lucene) is the standard engine. Documents are grouped into shards so the index scales horizontally, and indexing is near-real-time: new documents become searchable after a refresh interval, so there's always a small staleness window between writing and being findable.

The real design question is keeping the search index in sync with the source-of-truth database — search is a derived copy, never the primary store.

CDC (the good way) tail the log

Capture changes off the database's write-ahead log and stream them into the search index. The DB commit is the single source of truth, and the index follows it reliably — nothing is missed because the log records every change (CDC).

Dual-write (the trap) drifts

The app writes the DB and the search index directly, in the same request. When one write succeeds and the other fails — and eventually it will — the two drift apart with no way to notice. The classic dual-write problem (Distributed Transactions).

⚠ī¸
Never make the search engine your primary store. It's a derived index optimized for retrieval, with a refresh delay and weaker durability guarantees than your database. Write to the DB, and feed the index from it via CDC. If someone proposes dual-write, the follow-up is "what happens when the second write fails?"
⌨ī¸

Typeahead / Autocomplete

a different problem: prefixes under 100ms

Autocomplete looks like search but isn't. It's prefix matching under a brutal latency budget — suggestions must appear within ~100ms of a keystroke, and every keystroke is a query. The answer is precompute-heavy and read-cheap: do the work offline so serving is a trivial lookup.

  A TRIE with precomputed top-k per node:

           (root)
            └─ s
               └─ se
                  └─ sea ── top-k: [search, seattle, season, â€Ļ]
                     └─ sear ── top-k: [search, search engine, â€Ļ]

  Type "sear" → walk to that node → return its precomputed top-k. Done.
  Suggestions are RANKED and STORED at build time, weighted by popularity.

Each node stores the top-k completions for its prefix, ranked by popularity, computed ahead of time. Serving is a walk down the trie plus returning a cached list — no ranking at request time. Fuzzy matching (tolerating typos) and freshness of trending queries are add-ons layered on top. This is the whole shape of the Typeahead case study (Typeahead).

📋

Quick Reference

DB query vs search vs typeahead
DB LIKESearch engine
StructureB-tree (unusable with leading wildcard)Inverted index
SpeedFull scanPosting-list lookup
RelevanceNoneBM25 + signals
TokenizationNone — raw substringStem, lowercase, stop-words
Full-text searchTypeahead
IndexInverted indexTrie with top-k per node
Latency budgetSub-second~100ms per keystroke
Update patternNear-real-time via CDCPrecomputed offline, read-cheap
ℹī¸
The one-liners to keep ready. LIKE can't do search: no index, no relevance, no tokenization. An inverted index maps terms to posting lists; queries are set ops on them. BM25 for text relevance, then layer recency and popularity. Keep the search index in sync via CDC, never dual-write, and never make it the source of truth. Typeahead is a separate, precompute-heavy prefix problem with a 100ms budget.