Search Internals#

Q: What is an inverted index?

An inverted index maps every term to the list of documents that contain it. Lookups become a fast intersection of posting lists instead of scanning every document.

Q: How do BM25 and TF-IDF differ?

TF-IDF weights terms by raw frequency and inverse document frequency. BM25 adds saturation so repeating a term has diminishing returns and corrects for document length, giving better real-world ranking.

Q: How does Elasticsearch keep search fresh?

Documents are buffered in memory and refreshed into searchable Lucene segments roughly every second. Background merges combine small segments into larger ones for query efficiency.

Q: When should I use hybrid search?

When users mix keyword queries with semantic intent. BM25 catches exact matches and rare terms while a vector index finds paraphrases and synonyms, then a reranker fuses both lists.

Q: How do you shard a search index?

Hash documents by id across primary shards for write balance, replicate each shard for read scale and failover, and route queries to all shards then merge top-K results at the coordinator.

Problem statement (interviewer prompt)

Design the indexing and ranking pipeline for a product search of 100M items. Combine BM25 over an inverted index with vector / ANN over embeddings. Cover sharding, freshness (real-time updates), and a hybrid reranker.

flowchart LR
  Doc[Doc / Item]
  Tok[Tokeniser]
  IDX[Inverted Index]
  Q[Query]
  Score[BM25 / TF-IDF<br/>or vector cosine]
  Top[Top-k]
  Doc --> Tok --> IDX
  Q --> IDX
  IDX --> Score --> Top

  classDef p fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
  classDef s fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
  class Doc,Q,Top p;
  class Tok,IDX,Score s;

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class Doc,Tok,Q,Score,Top service;
    class IDX datastore;

Two families of search: lexical (tokens → inverted index → BM25 / TF-IDF) and vector (embed → ANN index → cosine similarity). Modern systems combine both ("hybrid search").

Inverted index#

flowchart TB
  subgraph Build[Index build]
    Docs[Documents]
    Tok[Tokenise + normalise<br/>lowercase, stop, stem]
    Post[Per-term postings list<br/>doc_id, positions, tf]
    Seg[(Immutable segment)]
    Merge[Background merge]
  end
  subgraph Query[Query path]
    QP[Parse query]
    QT[Per-term postings fetch]
    Intersect[AND / OR / phrase / proximity]
    Score[BM25 score per doc]
    Topk[Top-k heap]
  end
  Docs --> Tok --> Post --> Seg --> Merge
  QP --> QT --> Intersect --> Score --> Topk
  Seg --> QT

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class Docs,Tok,Post,Merge,QP,QT,Intersect,Score,Topk service;
    class Seg datastore;

A posting for term cat:

cat → [(doc_3, freq=2, pos=[10,42]), (doc_7, freq=1, pos=[3]), ...]

BM25#

The de-facto ranker. For a query Q with terms q_i and a doc D:

score(D, Q) = Σ IDF(q_i) · (tf · (k_1 + 1)) / (tf + k_1 · (1 - b + b · |D| / avgdl))

Knobs: k_1 (term frequency saturation, ~1.2), b (length normalisation, ~0.75).

TF-IDF (predecessor)#

Term frequency × inverse document frequency.
Doesn't saturate; long docs win unfairly. BM25 fixes both.

Phrase / proximity#

Use position lists to detect "data center" as adjacent tokens.
Skip lists in the postings make intersection O(min(p1, p2)).

Sharding the index#

Shard by doc id range: each shard has all terms for its docs (sub-set of docs). Queries fan out to all shards.
Shard by term: each shard owns a subset of terms - cheaper for some queries but skewed (rare terms vs common).
Most production systems shard by doc id.

Vector / semantic search#

flowchart TB
  T[Text / image]
  E[Embedding model<br/>BERT / CLIP / SBERT]
  V[Vector - 512 to 4096 dim]
  IDX[(ANN index<br/>HNSW / IVF-PQ / ScaNN)]
  Q[Query embedding]
  KNN[k-NN search]
  T --> E --> V --> IDX
  Q --> IDX
  IDX --> KNN

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class T,V,KNN service;
    class IDX datastore;
    class E,Q compute;

ANN structures#

HNSW - small-world graph; fast recall, RAM-hungry. Most popular.
IVF + PQ - coarse cluster + product-quantised residuals. Memory-efficient.
ScaNN - Google's hybrid; great quality / latency.
DiskANN - SSD-backed for billion-scale.

Hybrid search#

Lexical (BM25) returns top 200.
Vector returns top 200.
Reciprocal-rank fusion or learned-to-rank reranks. Both signals matter - pure vector misses brand names; pure lexical misses synonyms.

Real-time freshness#

Lucene/ES uses immutable segments + soft commits (visible within seconds).
Trade-off: smaller segments = faster freshness, more merge overhead.

Caches in front of search#

Query cache (whole-query top-k).
Filter cache (e.g. "language=en" bitsets).
Field-data cache (sort + aggregations).

Where this shows up#

Search engine (tier 8) - direct application.
Recommendation system - ANN over user/item embeddings.
Autocomplete - trie + ranker = lightweight inverted index.
Spam / abuse detection - vector similarity for near-dup content.

Glossary & fundamentals#

Concepts referenced in this design. Each row links to its canonical page; the tag column shows whether it is a high-level (HLD) or low-level (LLD) concept.

Tag	Concept	What it is	Page
`HLD`	Sharding	horizontal partitioning across nodes	database-sharding
`HLD`	Search internals	inverted index, BM25, embeddings, ANN	search-internals
`LLD`	Data structures & complexity	Big-O, common DS, latency numbers	data-structures-complexity
`LLD`	Immutability	immutable types, persistent collections	immutability

Quick reference#

Lucene segment lifecycle#

In-memory buffer → flush → immutable segment.
Many small segments → merge into fewer larger ones.
Deletes are tombstones; freed at merge.

Tokenisation pitfalls#

CJK languages need n-gram or ICU analysers, not whitespace.
URLs / code / log lines need keyword analysers (no stemming).
Synonyms expanded at index time (precise) or query time (flexible) - both have trade-offs.

Embedding model choice (2024+)#

General text: OpenAI text-embedding-3, Cohere embed-multilingual, BGE.
Code: voyage-code-2.
Images / video: CLIP, OpenCLIP.
Pick a dim that fits memory: 512-d × 1B vectors × 4 bytes = 2 TB.

Latency budget (typical search)#

p99 budget: 100-300 ms.
Allocate: parse 5 ms, candidate fan-out 30 ms, score 30 ms, hydrate 20 ms, ranker 50 ms.

When you don't need a search engine#

Single table, < 100k rows - Postgres full-text (tsvector) is fine.
Strict exact-match: indexed columns + B-tree.

Refs#

"Lucene in Action" (still relevant).
Elasticsearch internals docs.
"Pretrained Transformers as Universal Computation Engines" (modern embeddings).
Faiss / HNSWlib / ScaNN repos.
"BM25 explained" - Trey Grainger talk.

FAQ#

What is an inverted index?#