Module P-20·34 min read

Inverted indexes, tokenisation and analysers, relevance scoring, and the exact point where Postgres full-text search stops being enough.

JJS
Written by Jatin Jain Saraf · Senior Software Engineer

Module P-20 — Search Systems

What this module covers: Why LIKE '%term%' is not slow search but the absence of search, and what an inverted index actually stores. The analysis pipeline — tokenisation, stemming, stopwords, synonyms — and why index-time and query-time analysis must agree or you get zero results with no error. Relevance as arithmetic: TF-IDF, why BM25 replaced it, and the distributed-IDF problem that makes scores shard-dependent. Postgres full-text search taken seriously, including where its ceiling actually is and the one limit that surprises people on managed hosting. The checklist for when a dedicated engine is earned. Then the part that is genuinely hard and is not a search problem at all: keeping the index consistent with the database, why dual writes are broken, and the read-your-own-writes complaint that lands the day you ship. Plus deep pagination, autocomplete latency budgets, per-tenant index strategy, and why the search engine must never be your source of truth.


The first version of every search feature is this:

sql

It works on 5,000 rows and fails on 5 million, and the two failures are different in kind.

It cannot use an index. A B-tree indexes values by their leading bytes (Module F-13), so it can answer LIKE 'data%' — a prefix — and cannot answer LIKE '%data%', because the search term may begin anywhere. Every query is a sequential scan reading and pattern-matching every row. At 5 million rows that is seconds of CPU per query, and Module P-8's noisy-neighbour arithmetic follows: one search page becomes the most expensive endpoint you own.

It has no notion of relevance, and no notion of language. A row either matches or does not, so results come back in whatever order the storage engine produced them. ILIKE '%database%' misses "databases" only in the plural-suffix case you happened to type, misses "DB", matches "databases are" inside an unrelated sentence with the same weight as a title match, and cannot tell you that a document mentioning the term nine times is more likely what the user wanted than one mentioning it once. Users experience this as "the search is broken," which is accurate — they were promised search and given substring matching.

Search is a different data structure and a different scoring problem, and both halves matter. Making substring matching fast (a trigram index will) does not make it search; it makes it fast substring matching, which still ranks nothing.

Analogy: the index at the back of a textbook. It is not a faster way of reading the book cover to cover — it is a different artefact, built in advance, that maps terms to page numbers. Nobody builds one by scanning pages at question time. And a good index does more than list pages: it merges "database" and "databases" into one entry, omits "the" entirely, cross-references "DB, see database," and puts the primary discussion first. Every one of those editorial decisions has a counterpart in the analysis pipeline below.


An Inverted Index Maps Terms to Documents, Built by an Analysis Pipeline

A forward index is what your database has: document → its contents. An inverted index is the transpose: term → the list of documents containing it, with positions and frequencies.

text

A query for "postgres database" now intersects two short posting lists instead of scanning three documents — and instead of scanning five million. That is the entire performance story, and it is the same trade as any index: you pay at write time and at storage to make reads cheap.

The interesting part is how text becomes those terms. The analysis pipeline runs in stages:

StageDoesExample
Character filterstrips or rewrites charactersHTML tags removed, &&
Tokenisersplits into tokens"don't stop"["don't", "stop"]
Lowercasecase foldingPostgrespostgres
Stopwordsdrops high-frequency, low-information wordsthe, a, is removed
Stemmingreduces to a root formindexing, indexes, indexedindex
Synonymsexpands equivalentsdbdb, database
N-grams (optional)substrings for prefix or fuzzy matchingpost, postg, postgr

Every stage is a decision with a cost:

  • Stemming is lossy and algorithmic, not semantic. Porter stemming maps universe and university to the same stem, and business to busi. It also cannot know that SAP is a company rather than tree fluid. Lemmatisation is the more accurate, more expensive alternative that uses a dictionary. Aggressive stemming raises recall and lowers precision; the choice is a product decision about which complaint you would rather field.
  • Stopwords save space and destroy phrases. Drop to and be and the query "to be or not to be" is empty. Modern engines mostly stop dropping stopwords for this reason, relying on BM25's saturation to handle common terms instead.
  • Synonyms are asymmetric. Expanding at index time bloats the index and requires reindexing to change the list; expanding at query time keeps the list editable but makes every query wider and slower. Query time is the usual right answer precisely because synonym lists are edited weekly by people who are not engineers.

The rule that causes the most confusion: index-time and query-time analysis must agree. If you index with stemming and query without it, searching indexing looks for the literal token indexing, the index contains only index, and you get zero results — with no error, no warning, and a perfectly healthy system. Teams debug this for a long time because nothing is broken; the two ends simply disagree about what a word is. This is the single most common self-inflicted search bug, and it appears in Postgres as a mismatched to_tsvector/to_tsquery configuration and in Elasticsearch as an analyzer that differs from the search_analyzer.


Relevance Is Arithmetic: TF-IDF, Then BM25

Matching gives you a set. Ranking gives you an order, and the order is what users judge. The classical intuition has two components:

  • Term frequency (TF): a document mentioning the term more is more about it.
  • Inverse document frequency (IDF): a term appearing in few documents is more discriminating. the is worthless; mitochondrial is decisive.

TF-IDF multiplies them, and it has two flaws that matter in practice. Term frequency grows linearly, so a document repeating a term 200 times scores forty times higher than one repeating it five times — but it is not forty times more relevant, and this is exactly the shape keyword-stuffing exploits. And nothing accounts for document length, so a long document accumulates matches simply by being long.

BM25 fixes both, and is the default in every Lucene-based engine for that reason:

text

The two knobs are the whole story:

  • k₁ (≈1.2) saturates term frequency. The fifth occurrence of a term adds much less than the second, and the two-hundredth adds essentially nothing. Keyword stuffing stops paying.
  • b (≈0.75) normalises by document length relative to the corpus average, so a 50-word answer that is entirely about the topic can outrank a 5,000-word page that mentions it in passing.

Two production notes about scores that catch people out.

Scores are not comparable across queries. A BM25 score of 8.4 means nothing absolute; it is only meaningful as an ordering within one result set. So a "minimum relevance" threshold hard-coded as a score is not portable across queries or corpora, and it will silently start returning nothing when your corpus grows and IDF shifts.

IDF is computed per shard. In a distributed engine, each shard knows only its own document frequencies, so the same document can score differently depending on which shard it lives on. With even distribution and a decent corpus size the effect is negligible; with few documents, skewed routing, or a test index of fifty documents it is large enough to look like a bug — and it is the standard explanation for "relevance looks wrong in staging and fine in production." Engines offer a global-frequency search type to correct it, at the cost of an extra round of coordination per query.

Above BM25 sits the layer where real relevance work happens: field boosting (a title match is worth more than a body match), freshness decay, popularity signals, and business rules ("in-stock items first"). This is why a dedicated engine's value is often less about speed than about having a place to express those rules and iterate on them.


Postgres Full-Text Search Goes Further Than People Expect

Before reaching for a cluster, know the ceiling of what you already run. Postgres has real full-text search: tsvector is an inverted index of a document, tsquery is a parsed query, and GIN indexes the mapping.

sql

That gives you stemming, stopwords, phrase queries, field weights, and ranking, inside your existing transactional database — which means the index cannot be out of sync with the data, and the entire second half of this module (the consistency problem) simply does not apply to you. That property is worth more than most teams weigh it, and it is why "start with Postgres" is genuinely good advice rather than a hedge.

Sign in to keep reading

The rest of this module is free — sign in with Google to unlock it and track your progress.

Sign in & Register

Discussion

0

Join the discussion

Loading comments...

© 2026 Jatin Jain Saraf (JJS). All rights reserved.