Search & the Inverted Index

Sooner or later every product needs a search box: find the product, the post, the document that contains these words. The obvious approach, asking the database for every row that contains the text, works with a thousand rows and collapses at a hundred million. Search needs a different data structure, built for exactly this question, and it is one of the most elegant ideas in this course.

A SQL query such as `LIKE '%term%'` has to look inside every row for the substring. Cost grows with the size of the table, and a normal database index cannot help, because the text could match anywhere inside the value. At a hundred million rows each search reads a hundred million rows.

When you want to find where a textbook discusses replication, you do not read the whole book. You open the index at the back, find the word, and read off the page numbers. The book is arranged page to words, but the index is the other way round: word to pages. That reversal is the whole idea.

• -The pages of the book are the documents.
• -The word you look up is a term.
• -The list of page numbers beside it is the posting list for that term.
• -The index at the back, as a whole, is the inverted index: it maps each word to the documents containing it.

Take three tiny documents: 1 is distributed systems scale, 2 is distributed databases, and 3 is systems design. Going through each document and recording where every word appears gives this inverted index: distributed maps to documents 1 and 2, systems to 1 and 3, scale to 1, databases to 2, design to 3. To answer the query distributed systems, look up the two posting lists, [1, 2] and [1, 3], and keep the documents that are in both. The answer is document 1, found without reading a single document. The sketch below does exactly that:

The cost of a query now depends on the length of the posting lists involved, not on the size of the whole collection, which is why search engines can answer in milliseconds over billions of documents.

Real engines clean the text first, so that searches match what people mean. They lowercase everything, split it into words, drop very common words (such as the and of) that match everything, and reduce words to a root so that running, runs and ran match run. The same preparation is applied to the query, otherwise the words would not line up.

The card below describes the search index component as it appears in the lab:

Finding the matching documents is only half of the job. A query can match thousands, and users read the first few. So search engines also score each match for relevance. The intuition behind the classic measure, TF-IDF, is two ideas multiplied together. A word matters more in a document if it appears often there (term frequency), and matters more if it is rare across all documents (inverse document frequency). The word the appears everywhere and tells you nothing; the word inverted appears in few documents, so finding it in one is a strong signal. BM25, the modern default, refines the same idea. This is why designing a search engine is really two problems: find the candidates quickly, and rank them well.

A search index is not your primary database. The standard design keeps the database as the source of truth and feeds a separate search system (Elasticsearch and OpenSearch are common) through an asynchronous pipeline, so search queries never touch the production database. The diagram shows the flow:

• -Results can lag: a new document is searchable after the pipeline has processed it, usually seconds later. This is eventual consistency, and it is normally acceptable for search.
• -Never treat the search index as the only copy of your data: it can be rebuilt from the database, and sometimes has to be, when the text preparation rules change.
• -At scale the index is split into shards by document and each query is sent to every shard, then the best results are merged. Replicas add read capacity and survive a failure.