Search Systems

Inverted indexes, analyzers, BM25 and hybrid ranking, sharded clusters, and syncing with CDC.

Search boxes are everywhere: products, posts, messages, places, people. A relational database can't do this well at scale — WHERE body LIKE '%term%' scans every row and can't rank results — so most designs add a dedicated search system such as Elasticsearch or OpenSearch, fed from the primary database. This page covers what that system is and how it fits in; Building Full-Text Search goes deeper.

The inverted index

The core data structure. Instead of mapping a document to its words, it maps each term to the documents that contain it:

"distributed" -> [doc 3, doc 8, doc 21]
"systems"     -> [doc 3, doc 21, doc 40]

A query for "distributed systems" intersects the two lists: doc 3 and doc 21. Lookups take milliseconds even across billions of documents.

Analysis: turning text into terms

Before indexing, text goes through an analyzer, and queries go through the same one so they match:

Tokenize: split into words.
Normalize: lowercase, strip accents.
Remove stop words such as "the" and "a" (optional).
Stem or lemmatize: "running", "runs" → "run".

N-gram or edge n-gram tokens support partial matches and prefix search, at the cost of a bigger index. For instant autocomplete, a dedicated structure is usually better — see Design Typeahead.

Ranking

Matching is half the job; ordering the results is the other half.

BM25: the standard text relevance score. Rare terms count more than common ones, and repeated matches have diminishing returns.
Business signals: recency, popularity, ratings, distance, personalization. Usually combined with BM25 in a scoring function.
Semantic search: embed documents and queries as vectors and find nearest neighbors (HNSW indexes). Hybrid search combines keyword and vector results, and is the usual setup behind retrieval for LLM apps.

How a search cluster scales

The index is split into shards, each a self-contained index, spread across nodes. A query goes to every shard (scatter), and the results are merged (gather).
Each shard has replicas, which add read capacity and survive node failures.
Indexing is near real time: new documents become searchable after a refresh, typically about a second.

Keeping it in sync

The search index is a derived copy, not the source of truth. The database is. Ways to keep them aligned:

Dual writes from the app: simple, but a crash between the two writes leaves them out of sync.
Change data capture (CDC): stream the database's change log (for example, via Debezium into Kafka) to an indexer. The standard answer: reliable, ordered, and replayable.
Periodic rebuild from the database to repair drift and apply mapping changes.

app = service "App Servers" @0,1
db = store "Postgres\n(source of truth)" @1,0
cdc = queue "CDC → Kafka" @2,0
idx = service "Indexer" @3,0
es = store "Elasticsearch" @3,1
search = service "Search Service" @1,1
app -> db : writes
db -> cdc : change log
cdc -> idx
idx -> es : upsert docs
app -> search : queries
search -> es

[!WARNING] Don't make search the source of truth Search engines are tuned for queries, not for durable, transactional writes. Keep the canonical data in a database and treat the index as something you can always rebuild.

[!INTERVIEW] Cover the pipeline, not just the box "Posts live in Postgres. A CDC stream feeds Kafka, and an indexer writes to Elasticsearch, sharded by post ID. Search queries hit Elasticsearch, ranked by BM25 plus recency, and results are typically visible within a couple of seconds of posting."