7.7 — Search: Inverted Indexes, BM25 and Elasticsearch

A shop has a search box. It runs:

SELECT * FROM products WHERE name ILIKE '%kettle%';

Three things are wrong with it, and only one of them is speed.

It cannot use an index — a leading wildcard has no prefix to seek to (Chapter 7.3.2), so every product is read. It has no ranking — a product called "Kettle" and one called "Descaler for kettles" come back in whatever order the scan produced. And it does not understand words — searching "kettles" misses "kettle", searching "electric kettle" misses "kettle, electric", and a typo returns nothing.

Search is a different problem from lookup, and it needs a different structure.

1. The inverted index

A normal index maps row → values. An inverted index maps term → the documents containing it. The name is literal: it is the index the wrong way round.

The stored terms are not the words that were typed. Both the document and the query pass through the same analysis, which is why "kettles" finds "Kettle".

Each term's list of document ids is a posting list, kept sorted. A multi-term query walks several posting lists together and intersects them — the same merge as Chapter 4.10's merge sort, and it never touches a document that does not contain the terms.

Posting lists carry more than ids. For each document they also store how many times the term appears (needed for scoring) and, when phrase search is enabled, the positions of each occurrence — so "electric kettle" as a phrase can check that electric occurs at position n and kettle at n+1.

They are heavily compressed. Ids are stored as deltas — 1, 4, 9, 11 becomes 1, 3, 5, 2 — and small numbers are encoded in few bits. That, plus skip pointers that let an intersection jump forward instead of walking every entry, is what makes a query over billions of documents cheap.

2. Analysis: why "Kettles" matches "kettle"

The transformation from text into terms is the analysis pipeline, and it runs on documents at index time and on queries at search time, and both must use the same pipeline — otherwise the terms will not match, which is the single most common cause of "why does my search return nothing".

Character filters — strip HTML, normalise punctuation.

Tokenizer — split into tokens. Trivial for English, hard in general: languages without spaces need dictionary-based segmentation, and wi-fi, don't and C++ all need decisions.

Token filters, applied in order:

• Lowercase.
• Stop words — dropping the, a, of. Modern engines often keep them, because BM25 already gives common words almost no weight, and removing them breaks phrases like "to be or not to be".
• Stemming — reducing to a root by rules: kettles → kettl, running → run. Fast and crude, which is why the stored term is not a real word. Lemmatisation is the dictionary-based alternative: better → good, slower and more accurate.
• Synonyms — tv → television. Usually applied at query time so changing the list does not require reindexing.
• ASCII folding — café → cafe.
• N-grams — splitting into overlapping fragments, which is how substring and typo matching are supported at all.

The classic failure: indexing with one analyser and querying with another. Kettles indexed as kettl, queried as Kettles, no match, and the index looks empty.

3. Scoring: from TF-IDF to BM25

Matching gives a set. Ranking is what makes it search, and the reasoning behind the formula is more useful than the formula.

Term frequency. A document mentioning "kettle" five times is probably more about kettles than one mentioning it once. So score rises with count.

Inverse document frequency. A document containing "the" tells you nothing, because every document does. A document containing "descaler" is informative, because few do. So weight each term by how rare it is:

\text{idf}(t) = \ln\frac{N - n_t + 0.5}{n_t + 0.5}

where N is the total number of documents and n_t how many contain the term. Rare term, large value; universal term, near zero.

Multiply them and you have TF-IDF, which was the standard for decades. It has two flaws that BM25 fixes, and both are worth understanding because they are the whole difference.

Flaw one: term frequency should saturate. Ten mentions is not ten times better than one. BM25 damps it with a parameter k_1 (typically 1.2), so the contribution rises steeply at first then flattens.

Flaw two: long documents win unfairly. A 10,000-word page mentions everything more often. BM25 divides by document length relative to the average, with a parameter b (typically 0.75) controlling how strongly.

\text{score}(D,Q)=\sum_{t \in Q}\text{idf}(t)\cdot\frac{f(t,D)\cdot(k_1+1)}{f(t,D)+k_1\cdot\left(1-b+b\cdot\frac{|D|}{\text{avgdl}}\right)}

Read it as three ideas, not as algebra. Sum over the query's terms. Weight each by rarity. And each term's contribution is a saturating function of how often it appears, penalised if the document is long for its type.

BM25 is the default in Lucene, Elasticsearch, OpenSearch and Solr, and it remains a strong baseline in 2026 — modern hybrid systems combine it with vector similarity rather than replacing it, because it is extremely good at exact-term matching, which vectors are weak at.

4. When PostgreSQL's full-text search is enough

You do not need a search cluster to have real search.

ALTER TABLE products ADD COLUMN tsv tsvector
  GENERATED ALWAYS AS (
    setweight(to_tsvector('english', coalesce(name, '')), 'A') ||      -- (1)
    setweight(to_tsvector('english', coalesce(description, '')), 'B')
  ) STORED;

CREATE INDEX products_tsv_idx ON products USING gin (tsv);             -- (2)

SELECT id, name, ts_rank(tsv, q) AS rank                               -- (3)
FROM products, websearch_to_tsquery('english', 'electric kettle') q    -- (4)
WHERE tsv @@ q
ORDER BY rank DESC LIMIT 20;

(1) A generated column keeps the analysed form in sync automatically — no trigger to forget. setweight marks name matches as more important than description matches. (2) A GIN index (Chapter 7.3.2) over the terms: this is an inverted index inside PostgreSQL. (3) ts_rank scores; PostgreSQL's default ranking is simpler than BM25, which is one of the real differences. (4) websearch_to_tsquery accepts what users actually type — quoted phrases, or, -excluded — instead of requiring & and |.

Use PostgreSQL's search when the corpus is up to a few million rows, the results must be joined and filtered against live relational data, you want one system to operate, and search is a feature rather than the product. Add pg_trgm for typo tolerance and substring matching — trigram indexes also make LIKE '%kettle%' indexable, which is a useful separate trick.

Move to a dedicated engine when you need real relevance tuning, aggregations over facets, high query volume, per-field analysers, multilingual analysis, or vector search. The decision point in practice is relevance work, not size: the moment someone says "these results are in the wrong order and we need to fix it", you want the tooling.

5. Elasticsearch architecture

Elasticsearch and OpenSearch are distributed layers over Lucene, the library that implements the inverted index. Every concept below is either Lucene's or the distribution around it, and separating the two makes the whole thing easier to hold.

An index is split into shards; each shard is one Lucene index. Sharding is what allows a corpus larger than one machine, and the number of primary shards is fixed at creation — changing it requires reindexing, which is why over-sharding a small index is a common and costly early mistake. Each shard can have replicas, which serve reads and take over on failure.

A segment is an immutable file set inside a shard. New documents go to an in-memory buffer; a refresh turns the buffer into a new searchable segment. This is why Elasticsearch is near-real-time: the default refresh interval is one second, so a document is not searchable the instant it is indexed. Raising the interval during a bulk load is one of the largest available ingest speed-ups.

Segments are immutable, so an update is a delete plus an insert, exactly as in an LSM tree (Chapter 7.3.3) — the old document is marked deleted in a bitmap and removed when segments merge. Merging runs in the background, consumes I/O, and is what stops segment count from degrading query speed.

Durability comes from a translog, a write-ahead log per shard, fsynced by default every 5 seconds or per request. Same idea as Chapter 7.3.3, same trade.

A query is scatter-gather. The receiving node fans the query out to one copy of every shard, each returns its top N, and the coordinator merges them. Two consequences follow:

Deep pagination is expensive. from=10000, size=10 requires every shard to return 10,010 documents for the coordinator to sort and discard nearly all of them. With 10 shards that is 100,100 documents to answer one page. Elasticsearch refuses beyond 10,000 by default. search_after is the fix — the same keyset pagination as Chapter 9.6.2 — and scroll or point-in-time for exports.

Scores are computed per shard, so with few documents the same query can rank slightly differently depending on shard distribution, because IDF is local. It stops mattering at scale, and dfs_query_then_fetch fixes it at a cost.

Mapping: the distinction that decides everything

{ "properties": {
    "name":     { "type": "text",    "analyzer": "english" },   // (1)
    "sku":      { "type": "keyword" },                          // (2)
    "price":    { "type": "scaled_float", "scaling_factor": 100 },
    "tags":     { "type": "keyword" },
    "created":  { "type": "date" }
}}

(1) text is analysed — split into terms, stemmed, searchable by word, and not usable for exact matching, sorting or aggregation. (2) keyword is stored whole — one term, exact match only, and usable for filters, sorts, aggregations and facets.

Getting this wrong is the number one Elasticsearch mistake. A status field mapped as text cannot be aggregated meaningfully; a product name mapped as keyword cannot be searched by word. When you need both, index the field twice — name as text and name.raw as keyword, which is what the default multi-field mapping does.

Turn off dynamic mapping in production. By default, a document with a new field creates a mapping for it, guessed from the first value it sees. One bad write can map a field as long and every later string write fails, or create thousands of fields and blow up the cluster. Define the mapping explicitly.

Filters versus queries

A filter answers yes or no and is cached; a query computes a relevance score. filter for status = active, price < 5000, created > last week; must/should for the text that needs ranking. Putting exact conditions in the scoring clause wastes work and pollutes the ranking.

6. Relevance in practice

Boost the fields that matter. A term in a title should outrank one buried in a description: "fields": ["name^3", "description"].

Fuzzy matching for typos. fuzziness: AUTO allows an edit distance of one or two depending on term length (Chapter 4.31 covers edit distance). Do not apply it to short terms — it turns cat into car, bat and can.

Synonyms at query time, so updating the list does not require reindexing.

Autocomplete is a separate problem. Edge n-grams — indexing k, ke, ket, kett… — make prefix matching a term lookup, at the cost of a much larger index. Chapter 11.11 designs a full autocomplete service with the trie alternative from Chapter 4.13.4.

Vector search is complementary, not a replacement. Embeddings (Chapter 12.5) find documents that are semantically similar — "how do I stop my kettle furring up" matching a descaler page with no shared words. They are weak where BM25 is strong: exact model numbers, SKUs, rare proper nouns. Hybrid search runs both and fuses the rankings, usually with reciprocal rank fusion, and is the current default for serious systems.

Measure relevance instead of arguing about it. Click-through rate on the top result, the rate of searches with zero results, and how often users have to search twice. Chapter 11.22 uses these when designing retrieval for AI answers.

7. Operating it

A search index is not a source of truth. It is a derived view — an index you can rebuild. Treat it that way: keep the authoritative data in your database, and make reindexing a routine, tested operation rather than an emergency.

Index behind an alias. Applications query products, which is an alias pointing at products_v7. To change the mapping, build products_v8, backfill it, then atomically repoint the alias. This turns a mapping change from an outage into a deploy, and it is the single most valuable operational habit with Elasticsearch.

Bulk index, do not index per document. Use the bulk API, raise the refresh interval during the load, and set replicas to zero, then restore both.

Keep documents fetchable from the index if it saves a database round trip per result — store the fields you display. But do not let the search index become the place where data only exists.

What the interviewer will push on

"Why not just use LIKE '%term%'?" Three reasons, and only one is speed: no index can serve a leading wildcard, there is no ranking, and it matches substrings rather than words — so "kettles" misses "kettle" and a typo returns nothing. Naming ranking as a separate failure from speed is the tell.

"How does an inverted index work?" Term → sorted posting list of document ids, with term frequencies and optionally positions for phrases. Queries intersect posting lists with skip pointers instead of scanning documents. Then add that both documents and queries go through the same analysis pipeline, and that a mismatch there is the usual cause of an empty result set.

"What does BM25 add over TF-IDF?" Saturation — ten mentions is not ten times better — and length normalisation, so a long page does not win by mentioning everything. Being able to say what each of k_1 and b controls, rather than reciting the formula, is what is being checked.

"text or keyword?" text is analysed and searchable by word but cannot be aggregated or sorted; keyword is exact and can. When you need both, index the field twice as a multi-field. Then volunteer disabling dynamic mapping, because one bad document otherwise defines a field type for everything after it.

"Why is deep pagination a problem?" Scatter-gather: from=10000 makes every shard return 10,010 documents to the coordinator, which sorts and discards nearly all of them. The fix is search_after — keyset pagination — or point-in-time for exports.

"When would PostgreSQL full-text search be enough?" Up to a few million rows, when results must be joined and filtered against live relational data and search is a feature rather than the product. The move to a dedicated engine is usually triggered by relevance tuning and faceting, not by size.

One thing to volunteer: describe the alias pattern — query products, which points at products_v7, and repoint it atomically after building v8. It turns a mapping change from an outage into a deploy, and it demonstrates that you treat the search index as a rebuildable derived view rather than a database.

Recall

• An inverted index maps term → sorted posting list of documents, with frequencies and optionally positions. Queries intersect lists with skip pointers; delta encoding keeps them small.
• Analysis (tokenize, lowercase, stem, synonyms) runs on both documents and queries, and must be the same on both sides — a mismatch is the usual cause of "search returns nothing".
• BM25 fixes TF-IDF's two flaws: term frequency saturates (k_1) and long documents are normalised (b). Rarity weighting comes from IDF. It is still the default and still a strong baseline.
• PostgreSQL's tsvector + GIN is an inverted index. Good to a few million rows, when results join against live data; move on when relevance tuning and facets become the work.
• Elasticsearch = Lucene plus distribution. Shard count is fixed at creation. Segments are immutable, so updates are delete-plus-insert, cleaned by background merges; a refresh (default 1 s) makes new documents searchable — hence near-real-time.
• Queries are scatter-gather, which makes deep pagination expensive (from=10000 × shards) — use search_after.
• text is analysed (searchable, not aggregatable); keyword is exact (filter, sort, aggregate). Index both when you need both, and disable dynamic mapping in production.
• Treat the index as a rebuildable derived view: authoritative data lives in the database, applications query an alias, and a mapping change is build-then-repoint rather than an outage.

Self-test: Name the three separate failures of LIKE '%term%' · What breaks if index-time and query-time analysers differ? · What do k_1 and b control in BM25? · Why can't you aggregate on a text field? · Why is from=10000 expensive across ten shards? · What does the alias pattern buy you?

Next: 7.8.1 turns the storage question round — why every layout in this Part is wrong for analytics, and what a columnar engine does instead.