Start practising

SYSTEM DESIGN · BUILDING BLOCKS · 10 OF 14

Search Index: Inverted Indexes, Shards and the Indexing Pipeline

The search index as a component: why database LIKE queries fail, how an inverted index and text analysis work, how a query is matched and ranked with BM25, immutable segments and near-real-time refresh, sharding with scatter-gather, replicas, feeding the index from the database through a change stream, zero-downtime reindexing, autocomplete, failure modes and sizing.

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
1 / 15

Press play to hear the narration, or step through at your own pace.

Notes

The problem

Why not the database? A query with a leading wildcard can't use a B-tree index, so it scans fifty million rows. It doesn't know shoes and shoe are the same word, can't forgive typos, can't rank the best match first, and can't count results per brand and size quickly. You want ranked results over fifty million products in about fifty milliseconds.

Why not the database?
  • LIKE '%shoe%': B-tree index
  • useless → scan 50M rows
  • no stemming: "shoes" ≠ "shoe"
  • no typo tolerance
  • no relevance ranking
  • no facets (brand, size,
  • price buckets) at speed
  • want: ~50 ms over 50M docs

Inverted index

The core structure is the inverted index, like the index at the back of a book. For each term, store a sorted list of the documents containing it, called a postings list, often with how many times the term appears and where. Red points to documents one and three, run to one and two. To answer a query, you look up a few terms instead of scanning every document.

The inverted index
doc 1: "Red running shoes"
doc 2: "Trail running jacket"
doc 3: "Red trail shoes"

term     → postings (doc ids)
red      → [1, 3]
run      → [1, 2]
shoe     → [1, 3]
trail    → [2, 3]
jacket   → [2]
(+ term freq, positions)

Analysis

Before indexing, text goes through an analyzer. Split it into tokens, lowercase them, drop stop words, and stem them, so running becomes run and shoes becomes shoe. Add synonyms, so sneaker matches shoe. The query goes through the same analyzer. If index time and query time disagree, perfectly good documents silently stop matching. That's the most common search bug.

Text analysis
"Running Shoes, Men's!"
1 tokenize  → Running|Shoes|Men's
2 lowercase → running|shoes|men's
3 stopwords → (drop "the", "a")
4 stem      → run|shoe|men
5 synonyms  → sneaker = shoe

same analyzer at index time
and query time, or no match

Query path

A query like red shoes in size nine is analysed into terms, the postings lists are fetched and intersected, and filters like size are applied using cached bitsets. Each match is scored with BM25: a term counts more when it's rare across all documents and frequent in this one, and long documents are normalised down. A heap keeps only the top results. Then business signals like stock and sales are blended in.

Matching and ranking
  • 1 analyze query: red, shoe
  • 2 fetch postings, intersect
  • (AND) or union (OR)
  • 3 apply filters (size = 9)
  • via cached bitsets
  • 4 score with BM25: rare terms
  • and frequent-in-doc count
  • more, long docs count less
  • 5 keep top K in a heap
  • 6 business boosts (stock,
  • sales) on top

Storage

How is it stored and updated? Engines built on Lucene, like Elasticsearch and OpenSearch, write the index as immutable segments. New documents buffer in memory, and about once a second a refresh turns the buffer into a new searchable segment. That's why search is near real time: a new product appears after roughly a second, not instantly. An update marks the old document deleted and adds a new one, and background merges combine small segments.

Segments and refresh
  • index = many immutable
  • segments (Lucene)
  • new docs buffer in memory,
  • refresh every ~1 s → new
  • searchable segment
  • (near real time, not instant)
  • update = delete mark + new doc
  • background merges shrink
  • segment count, purge deletes

Sharding

To scale, split documents across shards, each with its own complete mini index. A query is scattered to every shard in parallel, each returns its local top ten, and the coordinator merges them into the global top ten. The latency is the slowest shard's latency, so more shards means more tail risk. When queries always include a tenant or region, route by it, so a query hits one shard instead of all.

Scatter-gather
  • document-partitioned: each
  • shard holds whole docs, its
  • own mini-index
  • query → all shards in
  • parallel → each returns top K
  • → coordinator merges
  • latency = slowest shard
  • route by tenant/region when
  • you can (hit 1 shard)

Replicas

Each shard has one or two replicas on other nodes. Any copy can serve a search, so replicas multiply query throughput. Writes go to the primary copy and then the replicas. If a node dies, a replica is promoted and the cluster creates a new copy elsewhere. A simple rule: more queries per second, add replicas; more data, add shards.

Replicas
  • each shard: primary + 1-2
  • replicas on other nodes
  • reads: any copy → more QPS
  • writes: primary, then replicas
  • node dies: replica promoted,
  • cluster re-replicates
  • more QPS → add replicas
  • more data → add shards

Indexing pipeline

The database stays the source of truth. Don't dual-write from the app, because one of the two writes will eventually fail and they drift. Instead, capture changes from the database's log with change data capture or an outbox, put them on Kafka, and have an indexer build one denormalised document per product, with brand, price and stock joined in, and bulk-upsert it. The index ends up a few seconds behind, and upserts by id are safely idempotent.

Keeping it in sync
  • never dual-write from the app
  • (one write fails → drift)
  • CDC (Debezium) or outbox →
  • Kafka → indexer → bulk API
  • indexer joins data into one
  • denormalised doc (product +
  • brand + price + stock)
  • lag: ~1-5 s; idempotent upserts

Reindexing

You will need to rebuild the index, for a new analyzer or field mapping. Do it beside the old one. Create version two, bulk-load it from a database snapshot, then replay the change stream from the snapshot's position so it catches up. Clients always query an alias called products. Flip the alias from version one to version two atomically, and keep version one around for a quick rollback.

Reindexing without downtime
  • new analyzer or mapping
  • = rebuild the whole index
  • 1 create products_v2
  • 2 bulk load from DB snapshot
  • 3 replay change stream since
  • the snapshot
  • 4 flip alias "products"
  • v1 → v2 (atomic)
  • 5 keep v1 for rollback

Autocomplete

Autocomplete is a special case, because it runs on every keystroke and needs answers in tens of milliseconds. Index edge n-grams, so the prefixes s h o, shoe and shoes are terms themselves, or use an in-memory prefix structure like a completion suggester. Rank by popularity, cache the hottest prefixes, and debounce input on the client. The Autocomplete design problem goes deeper.

Autocomplete
  • must answer in ~20-50 ms
  • per keystroke
  • edge n-grams: index "sho",
  • "shoe", "shoes" as terms
  • completion suggester: in-
  • memory prefix structure (FST)
  • rank by popularity, cache
  • top prefixes, debounce input
  • (see the Autocomplete problem)

Failure modes

Failure modes to name. One slow shard, maybe in a garbage collection pause, makes every query slow; use timeouts that return partial results, and hedge by asking a replica. Deep pagination is a trap: page five thousand makes every shard sort fifty thousand documents, so cap it and use cursor-style search after. Dynamic fields from user data can explode the mapping, so use strict mappings.

What goes wrong
  • one slow shard → slow query
  • → timeouts, partial results,
  • hedged requests to replicas
  • deep paging (page 5,000)
  • → each shard sorts 50k+ docs
  • → cap pages, use search_after
  • mapping explosion: dynamic
  • fields → strict mappings
  • cluster red → serve from cache

Sizing

Sizing. Fifty million products at two kilobytes each is a hundred gigabytes of source, and the index is roughly the same size again, call it a hundred fifty gigabytes. Aim for shards of ten to fifty gigabytes, so five primary shards. Then query rate: if one shard copy handles about five hundred searches a second, which you'd measure, three thousand a second needs six copies of each shard, a primary plus five replicas.

Sizing
50M products × 2 KB source
  = 100 GB; index ≈ 1-1.5x
  → ~150 GB primary
shard size target 10-50 GB
  → 5 primary shards

peak 3,000 searches/s
  one copy ~500 q/s (measure)
  → 6 copies of each shard
  = 5 primaries + 25 replicas
  ≈ 900 GB across the cluster

Say it like this

In the interview, say the database is the source of truth and the search index is derived from it through change data capture, Kafka and an indexer that writes one denormalised document per item. Mention the analyzer and BM25 with business boosts. Size shards by data and replicas by query rate, note the one-second refresh lag, and explain zero-downtime reindexing with an alias flip.

In the interview
  • DB = truth, search = derived
  • CDC → Kafka → indexer → ES
  • one denormalised doc per item
  • analyzer: stem, synonyms
  • BM25 + business boosts
  • shards by size, replicas by
  • QPS; route by tenant
  • refresh ~1 s (near real time)
  • reindex via alias flip
  • limits: deep paging, lag

Interview questions

What is an inverted index?

A map from each term to a sorted postings list of the documents that contain it, often with term frequencies and positions, so a query looks up a few terms instead of scanning every document.

Why does text analysis matter in search?

Analyzers tokenize, lowercase, remove stop words, stem and expand synonyms so that variants like shoes and shoe match; the same analysis must be applied at index and query time or matches are missed.

How are search results ranked?

Typically with BM25, which scores documents higher when query terms are rare across the corpus and frequent in the document, normalised by document length, then combined with business signals such as popularity or stock.

How do you keep a search index in sync with the database?

Treat the database as the source of truth and stream its changes through change data capture or an outbox into a queue, where an indexer builds denormalised documents and upserts them idempotently, accepting a few seconds of lag.

How does a sharded search query work?

The coordinator sends the query to every relevant shard in parallel, each shard returns its local top K with scores, and the coordinator merges them into the global top K, so overall latency is set by the slowest shard.

How do you reindex without downtime?

Build a new index alongside the old one from a snapshot, replay changes since the snapshot until it catches up, then atomically switch an alias that clients query from the old index to the new one.

Why is search near real time rather than real time?

Lucene-based engines make new documents searchable only when an in-memory buffer is refreshed into a new segment, which happens about once a second by default, trading a short delay for indexing throughput.

Why is deep pagination expensive in a search cluster?

To return page N every shard must find and sort its top N times page size results and send them to the coordinator, so cost grows with depth; cap page depth and use cursor-based search_after instead.

How do you decide shard and replica counts?

Choose the number of primary shards so each holds roughly 10 to 50 GB, and choose replicas from peak query rate divided by the measured throughput of one shard copy, plus copies for fault tolerance.