Architecture · Chapter 19

Search

How full-text search works: inverted indexes, tokenising and stemming, BM25 ranking, shards and replicas, keeping the index in sync with CDC, and the basics of typeahead.

IntermediateInterview priority: Medium40 min
On this page
  1. The problem: "title contains shoes"
  2. The idea: an inverted index
  3. Turning text into terms
  4. Ranking: which match comes first
  5. Running a search cluster
  6. Keeping the index in sync
  7. Typeahead basics
  8. Options and when not to
  9. In the interview
  10. Quiz

The problem: "title contains shoes"

A shop with 10 million products adds a search box. The first version is one SQL query:

SELECT * FROM products WHERE title ILIKE '%running shoes%' LIMIT 20;

A LIKE query checks every row

  1. Searching a database with a query like “title contains shoes” means reading every row and checking every word. Fine for a thousand products; painfully slow for ten million.

It works in testing and falls over in production, for three reasons:

  • It scans everything. A B-tree index (the normal database index, sorted by the column's value) can find titles that start with a string, but not ones that contain it, so a leading % forces a check of all 10 million rows on every keystroke.
  • It matches badly. "Running shoes" does not find "Shoes for runners" or "running shoe". There is no notion of words, plurals or synonyms.
  • It cannot rank. It returns matches in table order; the best product might be result 4,000.

Search engines solve all three with one data structure.

The idea: an inverted index

For every word, the list of documents that contain it

  1. Search engines flip it around with an inverted index, like the index at the back of a book. For every word, it keeps the list of documents containing it.
  2. To answer “running shoes”, it just looks up two lists and finds the documents in both. That takes milliseconds, even across billions of documents.

An inverted index maps each word (a term) to the list of documents containing it, its postings list. It is "inverted" because a normal table maps document → words; this maps word → documents, like the index at the back of a book.

To answer "running shoes", the engine fetches two postings lists and intersects them. The lists are stored sorted by document ID, so intersecting them is a single merge-like walk, and lists are compressed (storing the gaps between IDs, which are small numbers) so the hot parts fit in memory. The cost depends on the length of the lists involved, not on the total number of documents, which is why a search over billions of documents can still take milliseconds.

Postings usually also store term frequency (how often the word appears in that document) and positions (where), so the engine can rank results and answer phrase queries like "trail running".

Turning text into terms

Tokenise, lowercase, stem, and drop the most common words

  1. Building the index starts with tokenizing: splitting text into words. Then normalizing: lowercase everything, so “Shoes” matches “shoes”, and stemming, so running and runs both become “run” (aggressive stemmers even fold runners into it).
  2. Very common words like “the”, “a” and “for” match almost everything, so they’re often dropped as stop words.

Before anything is indexed, text goes through an analyser: a pipeline that turns a string into terms.

StepWhat it does"Runners love Running Shoes!"
TokeniseSplit into words, drop punctuationRunners · love · Running · Shoes
NormaliseLowercase, strip accents (café → cafe)runners · love · running · shoes
StemCut words to a root with rulesrunner · love · run · shoe
Stop words (optional)Drop very common words(none here)
Synonyms (optional)Add equivalents+ sneaker

Stemmers differ in how aggressive they are. The common Porter stemmer turns "running" and "runs" into "run" but keeps "runners" as "runner" (the table shows its output); more aggressive stemmers, like the one in the figure, merge "runner" too. All of them make mistakes, such as merging words that should stay apart ("university" and "universe" both become "univers"). Lemmatisation uses a dictionary to find the true base word, which is more accurate and slower. Modern engines often keep stop words, because ranking already gives them almost no weight and dropping them breaks queries like "to be or not to be"; Elasticsearch's default analyser does not remove them.

Ranking: which match comes first

Ranking puts the most relevant match first

  1. Finding matches is half the job. Ranking puts the best first. Classic formulas like TF-IDF and BM25 reward documents that mention your words often, and words that are rare, since a rare word says more about relevance than a common one.

Finding the matching documents is half the job. Ranking orders them by a relevance score. The classic formulas reward two things:

  • Term frequency (TF): a document that mentions "trail" five times is probably more about trails than one that mentions it once.
  • Inverse document frequency (IDF): rare words matter more. Almost every product says "shoes", so matching it says little; "trail" is rarer and more telling.

BM25, the default in Elasticsearch, OpenSearch and Lucene, refines TF-IDF in two ways: extra repetitions count less and less (the 20th "trail" barely adds anything, controlled by a parameter k1 ≈ 1.2), and long documents are normalised so they don't win just by containing more words (parameter b ≈ 0.75).

Worked example: why "trail" outweighs "shoes"

BM25's IDF for a term is ln(1 + (N − n + 0.5) / (n + 0.5)), where N is the number of documents and n the number containing the term. With 10 million products:

TermProducts containing it (n)IDF
shoes500,000ln(1 + 19) ≈ 3.0
trail20,000ln(1 + 499) ≈ 6.2

A match on "trail" is worth about twice a match on "shoes". For the query "trail shoes", a product titled "Trail shoes" scores highest, a road running shoe that only matches "shoes" scores much lower, and a trail map that only matches "trail" lands in between.

Real systems go beyond BM25. A common shape is two-stage ranking: BM25 cheaply retrieves the top ~1,000 candidates, then a slower machine-learned model re-ranks them using popularity, price, recency, click-through history and personal signals. Many engines also support vector search (matching by meaning using embeddings), often combined with BM25 as "hybrid search".

Running a search cluster

Teams rarely build the index themselves. They run Elasticsearch or OpenSearch (both built on the Lucene library), or a hosted service such as Algolia. Inside each, new documents are written into small immutable segments, which are merged in the background; a new segment becomes searchable at the next refresh, by default once a second. That is why search is "near real-time": a product saved now is findable about a second later.

Shards split the data; replicas copy it; queries scatter and gather

  • Shards split the index so it can grow past one machine. A query goes to every shard (scatter), each returns its top results, and a coordinator merges them (gather). A common guideline is 10–50 GB per shard.
  • Replicas are copies of each shard. They add query throughput and survive machine failures.
  • The number of primary shards is set when the index is created; changing it means reindexing (or a split operation), so plan for growth.

100 million products × ~2 KB of searchable text ≈ 200 GB of index (index size is often close to source size, depending on settings). At ~25 GB per shard that is 8 primary shards. Peak load is 3,000 queries/s; if one shard copy handles roughly 500 queries/s for these queries (benchmark it, it varies a lot), each shard needs 6 copies: 1 primary + 5 replicas, or 48 shard copies spread over, say, 12 nodes. More data → more shards; more queries → more replicas.

Keeping the index in sync

The database stays the source of truth; the search index is a derived copy that can always be rebuilt. The hard part is copying changes reliably.

Change data capture feeds the indexer; the database stays the source of truth

ApproachHowCatch
Dual writeApp writes the database, then the search engineIf the second write fails or the app crashes between them, the two drift apart silently
Periodic batchA job reindexes changed rows every few minutesMinutes of lag; must track "changed since" reliably, and deletes are easy to miss
CDC (change data capture)A tool such as Debezium reads the database's change log (Postgres WAL, MySQL binlog) and streams every change to Kafka; an indexer applies themMore moving parts, but no change is missed and the log can be replayed
OutboxThe app writes a change event into an outbox table in the same transaction; a relay publishes itNeeds every write path to add the event, but events can carry business meaning

CDC is the usual answer for "keep search in sync with the database". Make the indexer idempotent (indexing the same version twice is harmless) and use the row's version or log position so an older change never overwrites a newer one.

Typeahead basics

Suggestions while typing ("run" → "running shoes", "running shorts") are a different problem: the input is a prefix, there is a new request on every keystroke, and the answer must arrive in under about 100 ms to feel instant.

A trie stores prefixes, with the top suggestions kept at each node

  • In a search engine, use edge n-grams (index "run" as r, ru, run) or a dedicated completion suggester, which keeps an in-memory prefix structure.
  • At larger scale, build a trie (prefix tree) offline from query logs, with the top suggestions stored at each node, so a lookup is a walk of a few letters with no sorting at query time.
  • On the client: wait ~100–150 ms after the last keystroke before calling (debounce), cancel stale requests, and cache results for short prefixes, which are the most common.

The full design is in Design search autocomplete.

Options and when not to

OptionGood atWeak atUse when
SQL LIKENo new systemFull scans; no ranking or stemmingTiny tables, admin tools
Postgres full-text (tsvector + GIN index)Real inverted index inside your database; transactional, always in syncBasic ranking; scaling and tuning are limitedUp to a few million documents, simple relevance needs
Elasticsearch / OpenSearchRich analysis, BM25, facets, aggregations, horizontal scaleAnother cluster to run; near-real-time lag; sync pipeline neededLarge catalogues, complex relevance, log search
Hosted search (Algolia, Elastic Cloud)Fast typeahead and relevance tooling with little operations workCost at volume; less controlSmall teams that need great search quickly

Do not add a search cluster for exact lookups (by ID, email or order number: a database index is right), for data that must be read-your-writes consistent (account balance), or when Postgres full-text already meets the need.

In the interview

Your turn: search for a job board

A job board has 5 million active listings and gets 2,000 searches per second. Listings are added and closed constantly; a closed listing must disappear from results within a minute. Users filter by location and salary and expect relevant results for queries like "senior python remote". Design it.

Compare with our answer

Postgres holds listings; CDC (Debezium → Kafka) feeds an indexer into Elasticsearch. Listing text uses an English analyser (stemming, synonyms such as "dev" → "developer"); location and salary are indexed as keyword and numeric fields for filters, which don't affect the score and are cached. Closing a listing is just another change event: CDC typically delivers it in seconds, well within a minute; alert on consumer lag. Sizing: 5 M × ~5 KB ≈ 25 GB, so one or two primary shards; replicas sized from a benchmark for 2,000 queries/s. Ranking: BM25 on title (boosted) and description, then re-rank by recency and freshness. Reindex with an alias swap when the analyser changes.

A strong answer mentions: database as source of truth with CDC into the index · analysers with stemming and synonyms · filters as non-scoring structured fields · a freshness target monitored through consumer lag · shard and replica sizing from data size and query rate · alias-based reindexing.

Your turn: spot the bug

A team's code: db.save(product); search.index(product); in the request handler. Every few weeks customers find products in search that were deleted days ago, and some new products never appear. What is going on, and how would you fix it?

Compare with our answer

This is a dual write. When search.index fails (timeout, cluster restarting) or the process crashes between the two calls, the database and the index diverge, and nothing ever repairs it. Deletes may also go through a different code path that forgets the index entirely. Two concurrent updates can also reach the index out of order, leaving the older version. Fix: stream changes from the database itself with CDC (or an outbox written in the same transaction), apply them with an idempotent indexer that uses the row version so older events never overwrite newer ones, and run a periodic reconciliation that compares IDs and versions.

A strong answer mentions: dual writes drift on partial failure · deletes on other code paths · out-of-order updates · CDC or outbox from the source of truth · version checks in an idempotent indexer · periodic reconciliation.

Search on one page
  • LIKE '%x%' scans every row and cannot rank. Use an inverted index: term → sorted, compressed postings list.
  • Analyser: tokenise → lowercase → stem (or lemmatise) → optional stop words and synonyms. Same analyser at index and query time.
  • Ranking: BM25 (TF with saturation, IDF, length normalisation); rare terms weigh more. Two-stage: BM25 retrieves, ML re-ranks.
  • Elasticsearch/OpenSearch on Lucene: segments, ~1 s refresh, near-real-time.
  • Shards (10–50 GB each) for data size; replicas for query throughput and failover; queries scatter and gather.
  • Database = source of truth. Sync with CDC → Kafka → idempotent, version-aware indexer. Avoid dual writes.
  • Reindex into a new index and swap an alias. Use search_after, not deep offsets.
  • Typeahead: prefixes, edge n-grams or a completion suggester; tries with top-k per node; debounce; < 100 ms.
Interactive labPractise it: the search playgroundOpens in the ByteAtlas lab. Your progress is saved in this browser.
Check what stuck

1. A product search uses WHERE title ILIKE '%shoe%' on 10 million rows and is slow, even though title has a B-tree index. Why?

2. In a 10-million-document index, "shoes" appears in 500,000 documents and "waterproof" in 30,000. How does BM25 weigh a match on each?

3. Documents are indexed with a stemming analyser, but queries are sent without analysis. What do users see?

4. A team writes to Postgres and then to Elasticsearch in each request handler. Search slowly drifts from the database. What is the most reliable fix?

5. Your index has grown to 400 GB and query volume has doubled. What should you change?

6. Users can page through search results 20 at a time, and a scraper requests page 2,000. Why is this a problem?

7. Typeahead must return suggestions within 100 ms on every keystroke for millions of users. Which approach fits best?

Score 60% or more and the lesson is marked complete.

Passing the quiz also marks it complete. Progress is saved in this browser only.