Q59 — How does a search index work — why can't you use a database LIKE query at scale?

What does a LIKE query actually do?

When you run SELECT * FROM products WHERE description LIKE '%wireless headphones%', the database must scan every row in the table, load the description column for each row, and check whether the string "wireless headphones" appears anywhere in it. There is no index that helps — a B-tree index is built on sorted key prefixes, and %wireless% with a leading wildcard means the string can appear anywhere, so no prefix ordering applies. The database has no choice but to read every row.

At 1 million products, this is slow but tolerable. At 100 million products, it's unacceptable — it takes seconds, or minutes, and the database must do it for every search query. The larger the table, the worse it gets, linearly. It also blocks other queries while holding locks on the scanned rows.

LIKE is a brute-force string scan. Full-text search is a fundamentally different approach that pre-processes the data at write time so that reads are instant at any scale.

What is an inverted index?

The core data structure of every search engine — Elasticsearch, Lucene, Solr — is the inverted index. The name tells you what it does: it inverts the document-to-word mapping into a word-to-document mapping.

In a normal database, you start with a document (row) and look at its words. An inverted index starts with a word and tells you which documents contain it.

At index time, every document is processed:

1. Tokenization: split the text into tokens (words). "Wireless Bluetooth Headphones" → ["wireless", "bluetooth", "headphones"]
2. Normalization: lowercase, strip punctuation. "Headphones!" → "headphones"
3. Stemming/lemmatization: reduce words to their root form. "running" → "run", "headphones" → "headphone"
4. Stop word removal: remove extremely common words with low search value ("the", "a", "is")

The resulting tokens are stored in the inverted index: a mapping from each token to the list of document IDs that contain it, along with the position of the token within each document and its frequency.

"wireless"    → [doc_3, doc_7, doc_12, doc_41, ...]
"bluetooth"   → [doc_3, doc_8, doc_12, doc_19, ...]
"headphone"   → [doc_3, doc_12, doc_55, ...]

How does a search query use the inverted index?

Query: "wireless bluetooth headphones"

1. Tokenize and normalize the query: ["wireless", "bluetooth", "headphone"]
2. Look up each token in the inverted index — an O(1) hash lookup
3. Intersect the posting lists: documents that appear in all three lists: [doc_3, doc_12, ...]
4. Score each result by relevance (how many times each term appears, how rare the term is, where in the document it appears)
5. Return the top N results sorted by score

The lookup is near-instantaneous regardless of the total number of documents — because the work of finding which documents match was done at write time (indexing), not read time (querying). Queries become a set intersection problem on precomputed lists, not a full table scan.

This is the same fundamental insight as a B-tree database index — move work from read time to write time. But the inverted index is specifically designed for unstructured text queries, while a B-tree is designed for ordered key lookups.

What makes search engines more than just inverted indexes?

Relevance scoring (TF-IDF and BM25): not all matching documents are equally relevant. A document where "wireless" appears 15 times is more relevant than one where it appears once. But a very common word ("the" appears in every document) is less informative than a rare word ("planar-magnetic" appears in few). TF-IDF (Term Frequency × Inverse Document Frequency) quantifies this: relevance is proportional to term frequency in the document and inversely proportional to how common the term is across all documents. BM25 is a refined version of TF-IDF and is the default scoring function in Elasticsearch and Lucene.

Phrase queries: searching for "wireless headphones" as a phrase (consecutive words) requires knowing the position of each token within the document, not just that it's present. This is why positions are stored in the posting lists alongside document IDs. A phrase query intersects the document lists and then checks whether the tokens appear adjacent in position.

Fuzzy matching: searching for "headpohnes" (typo) should still return headphone results. Search engines use edit-distance algorithms (Levenshtein distance) to find tokens within N edits of the query token. This is why search works despite typos.

Faceted search: filtering on structured attributes alongside text matching. "wireless headphones under $100 with 4+ star reviews" combines a full-text query with structured filters. Search engines store field values alongside the inverted index and apply structured filters as post-processing on the matched set.

Analyzers per field: the title field might use a different tokenizer than the description field. A product SKU field shouldn't be tokenized at all (it's a keyword). Search engines let you configure per-field analysis pipelines.

How does Elasticsearch organize data at scale?

Elasticsearch is built on top of Apache Lucene (the inverted index library) and adds distribution and scalability.

An Elasticsearch index is split into shards — each shard is a self-contained Lucene index. A 10-shard index has 10 independent inverted indexes. Documents are routed to shards (typically by document ID hash), so the data is distributed across shards.

When a query arrives, it's broadcast to all shards in parallel (scatter-gather). Each shard independently searches its portion of the inverted index and returns its top N results. The coordinator merges and re-ranks results from all shards and returns the final top N. This parallelism is why Elasticsearch can search billions of documents in milliseconds — the work is distributed across many shards running simultaneously.

Each shard is also replicated (primary shard + replica shards). Reads can go to replicas, providing horizontal read scaling and fault tolerance.

What are the trade-offs of a search index vs a relational database?

Writes are expensive: building and updating an inverted index is significantly more work than a B-tree insert. Lucene segments (the underlying storage units) are immutable — you write new documents into new segments and periodically merge segments. Updates to documents require deleting the old document (soft delete) and inserting the new one. High write throughput requires careful tuning.

Near-real-time, not real-time: Lucene makes new documents searchable by refreshing the search reader (opening new segment readers). By default, Elasticsearch refreshes every second. A document written at time T is searchable at time T+1 second, not instantly.

Not a primary store: search indexes are optimized for reads, not for durability guarantees comparable to a relational database. The standard pattern is to use a relational DB or document store as the primary store and sync data into Elasticsearch for search. The search index is a derived, queryable view of the primary data.

No transactions: you can't atomically update multiple documents in a search index the way you can in a relational DB. Each document is independently indexed.

The mental model

LIKE query at scale:
  Full table scan → read every row → O(N) per query
  N = 100M rows → seconds per query → unusable for user-facing search

Inverted index (the solution):
  At write time: tokenize → normalize → stem → build word→[doc_id] mapping
  At query time: look up each query token → intersect posting lists → score → return top N
  Work is done at write time → query is O(1) hash lookup + list intersection

Inverted index structure:
  "wireless"  → [(doc_3, pos:0, freq:2), (doc_7, pos:5, freq:1), ...]
  "bluetooth" → [(doc_3, pos:1, freq:1), (doc_8, pos:0, freq:3), ...]

Scoring (BM25):
  Relevant = appears often in this doc (TF) + appears rarely across all docs (IDF)
  Rare terms in a document = high signal of relevance

Beyond basic inverted index:
  Phrase queries: position-aware intersection
  Fuzzy matching: edit-distance for typo tolerance
  Faceted search: text + structured filters combined
  Per-field analyzers: different tokenization per field

Elasticsearch at scale:
  Index → N shards (each = Lucene index) → distributed across nodes
  Query: scatter to all shards → each searches locally → gather + merge results
  Parallelism across shards → billions of docs → millisecond queries

Trade-offs vs relational DB:
  ✅ Full-text search, relevance ranking, typo tolerance, phrase search
  ⚠️  Writes are heavier (segment writes + merges)
  ⚠️  Near-real-time (default 1s refresh lag, not instant)
  ⚠️  Not primary store — sync from DB → Elasticsearch
  ⚠️  No transactions

Pattern: relational DB = source of truth → CDC/outbox → sync to Elasticsearch = search layer

The LIKE query was never designed for search — it's a pattern-matching operator added to SQL. A search index inverts the problem: instead of scanning documents for words, scan words for documents. That inversion is what makes sub-second search over billions of documents possible.