Search & Inverted Indexes

The index, inverted

A B-tree maps a value to its rows, sorted by the whole value: title = 'System Design' is fast, body LIKE '%quorum%' is a scan. It seeks to a prefix, never to a word inside a 4 KB text field — ten million documents, ten million rows read.

An inverted index reverses the natural direction, document → its terms:

quorum → [17, 402, 9931, 20114, ...]   (12,000 doc ids)
merkle → [402, 9931]

Each list is a posting list: sorted document ids with term frequencies and, for phrase queries, the positions of each occurrence — "read repair" keeps only documents where a repair position is one past a read. Positions cost 2–3× the index size.

quorum AND merkle is a merge of two sorted lists with skip pointers: work proportional to the shorter list, not the corpus. The index is keyed by what the user typed, so the query is a lookup, not a scan.

The analysis pipeline

Text becomes terms through an ordered pipeline; every stage is a lossy decision:

Stop-word removal is a megabyte-era legacy; BM25 discounts common terms anyway, so keep them.

Ranking: TF-IDF, then BM25

TF-IDF scores tf × log(N/df): reward terms frequent here, discount terms common everywhere. Two errors. Term frequency is linear — a page mentioning coffee 50 times is not 50× more relevant than one mentioning it once. Long documents win by accident: more words, more of everything.

BM25 fixes both. Term frequency contributes tf × (k1+1) / (tf + k1), which saturates: at k1 = 1.2 the first occurrence buys ~45% of all a term can contribute, the tenth ~89%, the fiftieth ~98%. Length is normalised against the corpus average with b = 0.75, so a 5,000-word page works harder than a 300-word one.

Relevance is a product decision, not a formula. BM25 only knows words. Real ranking layers business signals on top: recency, popularity, personalisation, title boosts — none of it tunable by eye. Mine click logs, measure NDCG@10, A/B it.

Segments are an LSM-tree

Lucene buffers new documents in memory, then flushes them to an immutable segment: a miniature index with its own dictionary and posting lists. Segments are never modified — deletes flip a bit in a tombstone bitmap, updates are delete plus reinsert, and background merges combine small segments into large ones, dropping deletions.

That is storage-engines's LSM-tree exactly: immutable runs, tombstone deletes, background compaction, reads that consult every run.

Merges are IO amplification: rewriting a 5 GB segment reads and writes 5 GB while queries want the same disk. And there is no read-your-writes — a screen that saves then searches must read the primary store.

Shards, replicas, and scatter-gather

An index is split into shards (partitioning), each a complete Lucene index over its slice of documents, plus replicas. This is the local secondary index made concrete: partitioning is by document, so no shard knows the global answer.

Every query is a scatter-gather: the coordinator asks one copy of every shard, each returns its top size ids and scores, and the merged global top 10 is fetched.

p99 is the slowest shard, not the average one. If a shard is fast 99% of the time, a 10-shard query is fast 0.99¹⁰ ≈ 90% of the time: fan-out amplifies the tail tenfold. Shards are extra chances to be slow, not free parallelism — hence over-sharding, the most common Elasticsearch misconfiguration. Aim for 10–50 GB per shard.

Deep pagination

Ask for results 10,000–10,010, ranked globally, across 10 shards. No shard knows which of its documents fall in that window without seeing everyone else's scores, so every shard must return its own top 10,010. The coordinator sorts 100,100 hits and discards 100,090.

Cost is (from + size) × shards, growing with both offset and shard count. Elasticsearch caps it at index.max_result_window: 10000, and the cap is a feature. Use a cursor instead: search_after passes the sort values of the last hit, so each shard returns only size rows beyond it — constant cost per page.

Operating a derived index

Search is never the source of truth. It is a derived view — the polyglot-persistence case: a second store bought for one access pattern, paid for with a sync pipeline.

• Rebuildable. You must be able to drop it and rebuild from the primary store, and know how long that takes — every analyser change needs it anyway.
• CDC or an outbox, never dual writes. Writing to the database and then the index in application code fails partially: the row commits, the index call times out, and nothing reconciles them.
• Idempotent indexing (idempotency) — key documents by primary key so a replay overwrites rather than duplicates, and version them so a late replay cannot resurrect an old document.
• Alias swaps for zero-downtime reindex, and alarm on lag between commit and searchability. Lag is the metric users feel.

Postgres or a dedicated engine?

Postgres full-text goes further than most teams assume: tsvector with a GIN index, websearch_to_tsquery, unaccent, weighted fields, pg_trgm for typos, ParadeDB for real BM25. Move to a dedicated engine for relevance tuning, faceting at scale, or a corpus that outgrows one machine.

What to take away

• An inverted index maps term → posting list, turning a scan into a sorted-list merge.
• The same analyser must run at index and query time, or queries silently match nothing.
• BM25 beats TF-IDF: term frequency saturates and document length is normalised.
• Lucene segments are an LSM-tree — immutable writes, background merges, near-real-time reads.
• Scatter-gather means p99 is the slowest shard; deep pages cost (from+size) × shards.
• Search is a derived index: rebuildable, fed by CDC or an outbox, never by dual writes.