Search: inverted indexes and Elasticsearch

Full-text search finds the documents that contain some words and ranks them by relevance. It's built on an inverted index: a map from each word to the documents containing it.

Why it matters

Users type words, not IDs, and they expect the best matches first, even with typos. Normal database indexes can't do that efficiently.

The idea

A SQL query like LIKE '%shoe%' scans every row. A search engine builds an inverted index in advance ('shoe' → documents 3, 17, 42), so lookups are fast. It also handles word forms (running → run), typos, and ranking (for example BM25). Search engines like Elasticsearch are usually a second store, filled from the main database.

The index at the back of a cookbook that lists, for each ingredient, every recipe page that uses it.

A cookbook index is exact. Search must also guess what the user meant — misspellings, synonyms, word forms — and rank thousands of matches, which is a whole field of its own.

How it works

  1. Indexing: each document's text is split into words, lowercased, and reduced to stems ('Running Shoes' → 'run', 'shoe').
  2. For each word, the engine adds the document's ID to that word's posting list.
  3. A search for 'red shoes' looks up the lists for 'red' and 'shoe' and intersects them, giving the documents that contain both.
  4. Each match gets a score: words that are rare overall but frequent in this document score higher (TF-IDF or BM25), and business signals like popularity can be added.
  5. The top results are returned. The index is split across many shards, which are searched in parallel.

Example

An online shop writes products to PostgreSQL, streams every change to Elasticsearch, and serves the search box from Elasticsearch.

Key points

Common mistakes

Not true: A new document can be found by search the instant it is saved.
In fact: The search index is updated a moment after the main database, so new or changed items take a short time to appear.

Not true: LIKE '%word%' is a fast way to search text in a large table.
In fact: A pattern that starts with % cannot use a normal index, so every row is scanned. An inverted index maps each word straight to the documents that contain it.

In the interview

For text search I'd use a search engine like Elasticsearch, built on inverted indexes and fed from the main database through change events. The database stays the source of truth; search can lag by a second or two.

Part of Unit 3: Data: databases, storage and scaling data in the free System Design course.