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. Every query becomes a full table scan.
• 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, 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 a 100 GB corpus produces an index in the low tens of GB that largely lives in page cache.

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.

Analysis: the pipeline that decides what a term even is

Notice that "running" became "run" and "for" disappeared. That transform is the analyzer, and it runs identically at index time and at query time — the non-negotiable rule of search, because a query term that was analyzed differently from the document term will simply never match.

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 engines usually keep them and let IDF discount them automatically.

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.

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. Practical sizing is 10-50 GB per shard. Over-sharding is the common mistake — every query pays coordination overhead on every shard, so a 20 GB index split into 100 shards is dramatically slower than the same data in 2.
• Replicas are full copies of a shard. They provide both availability (a lost node loses no data) and read throughput (queries round-robin across copies). Writes go to the primary and replicate; read scaling is therefore cheap, write scaling requires more primaries, which requires more shards, which you cannot change without reindexing.
• 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. 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.

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. 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 roughly 50 ms end-to-end including the network, 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 at 100-150 ms — the cheapest 60% traffic reduction in the whole design.

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.