Search systems (surface)

Why the obvious query can never work

Every search feature starts as SELECT * FROM items WHERE title LIKE '%running shoes%'. It works on 10,000 rows in a laptop demo and fails on every axis at scale, for reasons that are worth being able to state precisely rather than waving at.

• The leading wildcard defeats the index. A B-tree orders by prefix, so it can answer "starts with run" but has no way to jump to rows containing run somewhere in the middle, so with a plain B-tree every such query becomes a full table scan. (Postgres's pg_trgm extension can index infix LIKE with a trigram GIN index, which fixes this one point, but not ranking or linguistic matching.)
• Scans do not fit the latency budget. 50 million rows at 2 KB each is 100 GB. Even reading purely from page cache at several GB/s that is tens of seconds, and it burns the CPU and I/O of the database your writes depend on.
• It is literal. "running shoes" does not match "shoes for running", "Running Shoe", or "sneakers". No stemming, no reordering, no synonyms.
• There is no ranking at all. LIKE returns a set, not an order. With 40,000 matches you have no principled way to pick the 10 to show, and the ordering is the entire product.

Postgres full-text search (tsvector plus a GIN index) fixes the first three and part of the fourth (its ts_rank ranks from per-document information; the Postgres docs note the ranking functions use no global information, so it is not corpus-aware BM25), and is genuinely the right answer up to a few million documents with modest query volume. Say so — reaching for Elasticsearch on day one is over-engineering and a good interviewer will say as much. But both roads lead to the same data structure, so understand it properly.

The inverted index, built from three documents

A normal index maps document → contents. An inverted index maps term → the documents containing it, which is the direction a query actually needs. Each entry in the map is a postings list: the sorted document IDs for that term, usually with positions and term frequencies alongside.

The performance property is the whole point: query cost scales with the length of the postings lists for the query's terms, not with corpus size. Adding fifty million documents that contain neither red nor run costs those queries nothing. And because the lists are sorted integer sequences, they compress viciously well (delta encoding plus variable-byte or bitpacking), so the index is often a fraction of the raw corpus size and can largely live in page cache (how much smaller depends on what you store: positions, stored fields and doc values change it a lot, so treat any ratio as a planning figure and measure).

Postings usually store more than IDs. Term frequency per document powers scoring; term positions power phrase queries, so "red shoes" as an exact phrase can check that red at position i is followed by shoe at position i+1 rather than merely co-occurring in the document.

Dry run: scoring the query "red running" with TF-IDF over the three documents above

idf(red) = idf(run) = ln(3/2) ≈ 0.405, since each appears in 2 of the 3 documents. idf(shoe) = ln(3/3) = 0 — "shoe" appears in every document, so it contributes exactly nothing to any score, which is the arithmetic behind the figure's claim that it "carries almost no signal." Boolean intersection returns only D1; TF-IDF instead ranks D1 highest but still surfaces D2 and D3 as partial matches, which is the entire reason a ranking stage exists on top of retrieval.

Analysis: the pipeline that decides what a term even is

Notice that "running" became "run" and "for" disappeared (this example uses a classic stop-word list). That transform is the analyzer, and it must produce compatible terms at index time and at query time — the non-negotiable rule of search, because a query term that was analyzed incompatibly with the document term will simply never match. Usually that means the same analyzer; Elasticsearch also lets a field have a separate search_analyzer, which is exactly how edge n-gram autocomplete works: the index side emits n-grams, the query side does not.

Three things to know about these stages, because each has a real failure mode. Tokenization is language-specific: whitespace splitting is useless for Chinese and Japanese, which need dictionary-based segmentation, and it mangles identifiers like C++ or wi-fi. Stemming is a lossy heuristic — Porter stemming maps "university" and "universe" both to "univers", and "operating" to "oper"; lemmatization is the dictionary-based, slower, more accurate alternative. Stop words are no longer a clear win: they were a compression trick from when index size dominated, and dropping them breaks phrase queries like "to be or not to be" and "The Who". Modern setups usually keep them and let IDF discount them automatically: Elasticsearch's standard analyzer, for instance, has stop words off by default.

Relevance: TF-IDF, then BM25, then reality

Once you have the matching set you must order it. The classical intuition is TF-IDF, built from two opposing forces:

• Term frequency. A document mentioning "kayak" eight times is more about kayaks than one mentioning it once.
• Inverse document frequency. A term appearing in nearly every document (shoe in our three-doc corpus, or the in any corpus) discriminates nothing, so its weight collapses toward zero. Rare terms carry the signal.

A document's score for a query is the sum, over the query's terms, of term-frequency times inverse-document-frequency. BM25 is the modern default and fixes two concrete defects in that formula, both worth naming:

• Term frequency saturates. Under raw TF-IDF a page repeating "kayak" 500 times scores 500× a page mentioning it once, which is both wrong and trivially game-able. BM25 applies diminishing returns via a tunable parameter (k1, typically ~1.2), so going from 1 to 5 occurrences matters a lot and 50 to 500 matters almost nothing.
• Length normalization. A long document naturally contains more terms and would otherwise win everything. BM25 divides by document length relative to the corpus average, with a parameter b (typically 0.75) controlling how hard that penalty bites.

You do not need the closed form on a whiteboard. Saying "BM25 — TF-IDF with saturating term frequency and length normalization, and it's the default in Lucene" demonstrates exactly the right depth for a system design round. If someone pushes further, the honest frontier is that BM25 is a lexical score, and modern stacks add a vector/embedding retrieval arm to catch semantic matches BM25 misses, then fuse the two result sets. The vector side is approximate nearest-neighbour search (HNSW graphs are the common index), and a simple, robust fusion is reciprocal rank fusion: each document scores the sum of 1 / (k + rank) across the lists, with k = 60 by default in Elasticsearch, so no score normalisation is needed.

Two more terms that come up: spell correction ("did you mean", usually edit distance against the vocabulary, or a model trained on query logs) and learning to rank (a trained model, often gradient-boosted trees, that reorders the few hundred candidates using many features). And how do you know any of it is good? Offline, humans or click logs label results and you report NDCG@10 or MRR; online, you A/B test click-through and reformulation rate.

Textual relevance is not business relevance

BM25 answers "which document is most about these words." Nobody actually wants that. A news search wants recent things; a marketplace wants items that are in stock and convert; a music app wants the song people are streaming this week. Pure lexical relevance would happily rank a perfectly matching, sold-out, three-year-old listing first.

Real systems therefore run two stages, and the separation is the architectural point:

The reason to split is pure economics: you cannot run a gradient-boosted model or a cross-encoder over ten million documents inside a 200 ms budget, but you can absolutely run it over 300. Blending is usually multiplicative or a weighted sum over normalized signals — a common shape being final = bm25_norm × recency_decay × log(1 + popularity), where recency decay is an exponential with a half-life chosen per vertical (hours for news, months for products).

Elasticsearch in practice: shards, replicas, near-real-time

Elasticsearch and OpenSearch are distributed wrappers around Lucene, and the three operational concepts you need are all visible in how a document becomes searchable.

• Shards partition the index. Each shard is an independent Lucene index; a query fans out to every shard, each returns its local top-k, and a coordinating node merges them. Elastic's sizing guidance is 10-50 GB per shard and under about 200 million documents. Over-sharding is the common mistake — each shard's search runs on a CPU thread, every query pays coordination overhead on every shard, and a 20 GB index split into 100 shards is dramatically slower than the same data in 2. Fan-out also amplifies tail latency: the query finishes when the slowest shard does, so if each of 100 shards is slow on 1% of requests, about 63% of queries (1 − 0.99^100) hit at least one slow shard. Note the shape: this is a document-partitioned (local) secondary index, where each shard indexes whole documents and every query scatters to all shards; a term-partitioned index would send a query only to the shards owning its terms but makes writes touch many shards (the trade-off is laid out in Designing Data-Intensive Applications). Because each shard scores with its own statistics, tiny or skewed shards can distort IDF; dfs_query_then_fetch collects global term statistics first, at the cost of an extra round trip.
• Replicas are full copies of a shard. They provide both availability (a lost node loses no data) and read throughput (queries are spread across copies). Writes go to the primary and replicate; read scaling is therefore cheap, write scaling requires more primaries, which requires more shards. The primary-shard count of an existing index cannot be edited in place, but the split API creates a new index with a multiple of the shard count from a read-only source without a full reindex, and time-based data uses rollover to start each new index with a fresh shard count.
• Near-real-time. Lucene segments are immutable. A new document goes to an in-memory buffer and is not searchable until a refresh creates a new segment — by default every 1 second (with one wrinkle: if you have not set refresh_interval explicitly, a shard that has had no search for 30 seconds, index.search.idle.after, stops refreshing in the background until the next search arrives, and that search triggers the refresh). That one second is not a bug you can configure away for free: refreshing more often produces more tiny segments and more merge pressure. For bulk loads the standard move is to disable refresh entirely, index, then refresh once.

Immutable segments also explain deletes and updates. A delete just marks a tombstone; an update is a delete plus an insert. Space is only reclaimed when background merges rewrite segments together, so a heavily-updated index carries dead weight and periodic merge I/O spikes. This is why Elasticsearch is a poor primary datastore for frequently-mutating rows and a great one for append-heavy documents. (Segments that are written immutably and merged in the background are the same idea as a log-structured merge tree.) One more practical limit: from + size paging stops at 10,000 hits by default; deep pagination uses search_after with a point in time, so "jump to page 5,000" is not a feature you promise.

Search is a secondary index, fed asynchronously

This is the architectural claim that matters most in an interview, and the one candidates most often get backwards. Your search cluster is not your source of truth. It is a derived, denormalized, rebuildable projection of data that lives authoritatively somewhere else.

Three consequences follow, and each is an interview point on its own:

• No read-your-writes. A user edits a listing and immediately searches for it; the change is committed but not yet indexed. Fixes, in increasing order of effort: tell the UI it may take a moment; read the just-written record from the primary and splice it into the results; or make the write path wait for an index acknowledgement, which trades latency for consistency and is rarely worth it.
• Never dual-write. The tempting implementation is "write to Postgres, then write to Elasticsearch" in the same request handler. It fails the instant the second write errors or the process dies between them, and it leaves permanent, silent divergence. Use the transactional outbox (write the row and an outbox event in one transaction, a relay publishes the event) or change data capture from the database's replication log. Either way there is exactly one atomic commit.
• It is disposable, and that is the point. Because the index is derived, you can always rebuild it from source. This is what makes the alias-swap reindex safe, and it means a corrupted search cluster is an availability incident, not a data-loss incident. Recovery is a choice: restoring a snapshot is usually the faster way back for a large index, and a reindex from source is the fallback (and the only way to apply a mapping or analyzer change). It also means search should degrade gracefully — if the cluster is down, fall back to a database prefix lookup or a "search is temporarily unavailable" state rather than failing the whole page.

Autocomplete is a different problem with a different index

Autocomplete fires on every keystroke, so its budget is tight (roughly 50 ms server-side is a common target, a planning figure rather than a standard), and it must handle a 2-character prefix matching millions of entries. Running a full BM25 query per keystroke is both too slow and semantically wrong — "shoe" typed as "sho" is not a term.

The crucial insight is that suggestions should be ranked by what people search for, not by what exists in the catalogue. Build the suggestion index from query logs weighted by frequency and click-through, which also means it is small, offline-rebuildable, and can be pushed entirely into memory. And debounce on the client (wait 100-150 ms after the last keystroke, a typical starting value) — typically the cheapest large traffic reduction in the whole design; measure your own savings. At very large scale the suggestion service is usually sharded by prefix, with the top-k completions per prefix cached.

Recognizing it in an unseen problem

• The prompt says "search", "find", "filter by keyword", "typeahead", or describes users looking for something by name or description rather than fetching it by ID.
• A naive design puts LIKE '%term%' on the primary database and never mentions ranking — the two failures to call out immediately are the full scan and the absence of any ordering.
• Distinguish it from a database indexing question: a B-tree answers "give me the rows where x = y" exactly; search answers "give me the best rows for this fuzzy human intent, in order." Ranking is the tell.
• Distinguish it from a recommendation question: search has an explicit query string, recommendations do not. They share the two-stage retrieve-then-rank architecture, which is a good connection to draw.
• Any time you introduce a search cluster, immediately say how it gets fed and what the staleness window means for the user — the async secondary-index point is worth more than any detail about BM25.
• Pitfall: forgetting permissions and filters belong in the index. Post-filtering ranked results silently returns empty pages to exactly the users with the narrowest access.