Full-text search

Why LIKE '%term%' is not search

WHERE description LIKE '%mount%' works until the table grows, then it drags, because a leading wildcard forces a scan of every row. No B-tree can help: a B-tree orders whole column values, so it can answer LIKE 'mount%' (anchored prefix) but never '%mount%', which gives it no prefix to seek on. That is the db-indexing boundary, and it is why "add an index" does not rescue substring search.

Real search flips the data around. Instead of walking documents looking for a word, you keep a structure that already knows, for every word, which documents contain it.

How an inverted index makes search fast

An inverted index maps terms to the documents that contain them. For each distinct term there is a postings list: the ids of the documents where it appears, usually with the position and how many times. Searching red shoes becomes two lookups (the postings for red, the postings for shoes) and a set operation on the results: intersect for AND, union for OR. You never touch a document that lacks the term.

The unit stored in that index is not the raw word you typed. It is a lexeme (Postgres) or token (Lucene): the normalized form after lowercasing, stemming, and dropping stop words. Which brings up the one bug this whole topic exists to prevent.

The analysis pipeline, and why both sides must agree

Before text is indexed it runs through an analyzer. Character filters clean the raw string (strip HTML, map characters), a tokenizer splits it into tokens, and token filters normalize each token (lowercase, stem running to run, drop the).

The rule that trips people: the query string goes through analysis too, and it must produce tokens that match what was indexed. Index with an English analyzer that stores run, then search for the exact token Running, and you get nothing, because Running was never stored.

Wrong "Search is case- and typo-insensitive by default, so Running finds run." Nothing is insensitive by magic. It matches only because the same normalization ran on both sides and both collapsed to run. Right use the query path that analyzes the input the same way the field was analyzed. In Elasticsearch that means a match query (analyzed), not a term query (raw); in Postgres it means building the query with to_tsquery/plainto_tsquery under the same config you used to build the tsvector.

Full-text search in Postgres

You do not need a separate engine to get tokenization, stemming, and ranked results. Postgres has tsvector (a document as sorted lexemes) and tsquery (a parsed query), matched with the @@ operator, over a GIN index.

-- store the searchable form once, keep it current automatically
ALTER TABLE products ADD COLUMN search tsvector
  GENERATED ALWAYS AS (to_tsvector('english', name || ' ' || description)) STORED;

CREATE INDEX products_search_idx ON products USING GIN (search);

-- query: same 'english' config on both sides
SELECT id, name
FROM products
WHERE search @@ plainto_tsquery('english', 'running shoes')
ORDER BY ts_rank(search, plainto_tsquery('english', 'running shoes')) DESC
LIMIT 20;

to_tsvector('english', ...) lowercases, stems (running to run), and drops English stop words. plainto_tsquery runs the same normalization on the user's text, so the two sides line up. GIN is the index type to use here: it is an inverted index over the lexemes, and the Postgres docs call it the preferred text-search index. ts_rank orders the hits, with the large caveat covered in the senior notes.

Autocomplete and typo tolerance are different features

People ask for "search like Google" and mean two unrelated mechanisms.

Autocomplete completes a prefix you are still typing: wirele should surface wireless headphones. The common approach is edge n-grams built at index time, which store w, wi, wir, wire, ... as their own tokens so a prefix is a plain term lookup. Build those at index time only. If you also run the edge n-gram analyzer on the query, the query itself shatters into prefixes and matching goes haywire.

Typo tolerance fixes a word the user actually misspelled: wierless should still find wireless. That is fuzzy matching by edit distance (how many single-character insertions, deletions, substitutions, or adjacent swaps separate two terms), not prefixing. Engines cap it low, typically two edits, because the cost grows fast. Reaching for one when you meant the other is a common mix-up worth catching before you build.

How BM25 actually scores

The default similarity in Lucene, Elasticsearch, and OpenSearch is BM25. Three forces set a document's score for a query term, and an interviewer wants you to name all three and what tunes them.

IDF (inverse document frequency) weights rarity: a term that appears in few documents carries more signal than one in most of them, so a match on defibrillator moves the score far more than a match on the. Term frequency helps, but with diminishing returns: the contribution saturates toward an asymptote, so the tenth occurrence of a word adds much less than the second. The knob is k1 (default 1.2); lower saturates sooner, higher keeps rewarding repetition. Length normalization discounts long documents so a 5000-word page does not out-score a tight product title just for containing the term more times; the knob is b (default 0.75), measured against the average field length. b=0 turns length off, b=1 applies it fully.

Wrong "Repeating a keyword ten times makes a document rank first." TF saturation is designed to defeat exactly that; past a few occurrences the gain is marginal, and length normalization pushes back on the padding. Right relevance comes mostly from matching selective (high-IDF) terms, which is why a good analyzer that keeps meaningful tokens and drops noise matters more than term counts.

The per-shard IDF gotcha

BM25 needs collection statistics (how many documents contain the term), and Elasticsearch computes them per shard by default. On a small or skewed index the same document can score differently depending on which shard it landed on, because each shard's local document frequency differs. It looks like a scoring bug and it is not. It evens out as the index grows; to force correctness now, gather global term frequencies first with dfs_query_then_fetch, which does an extra round trip before scoring. Reach for it only when relevance looks unstable on a small corpus.

Postgres ranking has no IDF

This is the sharpest tradeoff to state out loud. Postgres full-text search gives you real tokenization, stemming, phrase and boolean queries, and a GIN inverted index. What it does not give you is corpus-aware ranking. The docs are explicit that the ranking functions use no global information, so ts_rank has no IDF: it scores on in-document frequency and weights, ts_rank_cd adds proximity (cover density), and neither knows a term is rare across the collection. For many apps that is fine; when relevance quality is the product, it is the reason teams move to a BM25 engine.

A few Postgres specifics worth carrying in:

• Use GIN, not GiST, for tsvector. GIN is an exact inverted index and the documented preferred type; GiST stores a lossy fixed-length signature, produces false matches it must recheck against the heap, and is mainly interesting for cheaper updates or when you need INCLUDE.
• setweight labels lexemes A/B/C/D so a title match can outrank a body match (default weights {0.1, 0.2, 0.4, 1.0} for D/C/B/A). This is coarse boosting, not IDF.
• If you genuinely need BM25 inside Postgres, that lives in an extension (for example a pg_search/ParadeDB build), not in core ts_rank. Say that rather than pretending ts_rank is BM25.

Postgres FTS or a dedicated engine

Decide on load and features. Postgres FTS wins when search sits on data you already store there, the corpus is moderate, and "good enough" ranking plus stemming and phrases covers the need: you get one datastore, transactional writes, and no sync problem. A dedicated engine (Elasticsearch/OpenSearch) wins when you need BM25 relevance, multiple analyzers per field, typo tolerance, faceting/aggregations at query time, or query volume that you do not want competing with your OLTP traffic. The moment you introduce that second store, you inherit a new problem: keeping it current.

Keeping the index in sync

The engine's index is a derived projection of the source of truth, and the failure mode is drift. The naive plan is a dual write: the request handler writes the row to Postgres, then writes the document to the engine. Two writes to two systems are not one atomic operation. If the process dies or the engine is down between them, the row commits and the index never updates, so it drifts and stays wrong. Under concurrency there is no ordering either, so two updates can reach the index out of order and leave it stale. A database transaction cannot span Postgres and Elasticsearch, so a try/catch around both does not make it safe.

Derive the index from committed changes instead. Log-based CDC reads the database's own transaction log (the Postgres WAL or MySQL binlog), the same log used for replication, so every committed insert, update, and delete is captured in commit order; a tool like Debezium fans those events through a broker into the engine's bulk API.

If the engine is down, the pipeline retries from the log position; the index can be rebuilt by replaying. The transactional outbox is the close cousin: the handler writes the entity and an outbox row in one transaction, and CDC ships the outbox, which keeps you from capturing raw table internals. Either way, the DB stays authoritative and the index follows.

One consistency point to set expectations on: indexing is asynchronous, and even inside the engine new documents take about a second to become searchable. Elasticsearch makes writes searchable on a refresh, roughly every second by default, by opening a new Lucene segment. So search is eventually consistent regardless of the sync mechanism. Do not promise read-your-writes on the search path; if a UI needs the just-created item shown immediately, serve that one read from the source of truth.

Typo tolerance and prefixes, under the hood

Two mechanisms people conflate, worth keeping straight at the senior level.

Typo tolerance is fuzzy matching on edit (Levenshtein/Damerau) distance: the number of single-character insertions, deletions, substitutions, or adjacent transpositions between two terms. Engines default to AUTO, which allows more edits on longer terms and none on very short ones, and cap the maximum near two edits because the term expansion gets expensive fast. It fixes wierless to wireless.

Autocomplete is prefix matching, and the efficient form builds edge n-grams (w, wi, wir, ...) at index time so a prefix is a term lookup. Build them at index time only. Running the edge n-gram analyzer at query time re-fragments the query into prefixes and wrecks both recall and scoring; the query side uses a plain analyzer that matches the stored prefixes. Fuzzy and prefix solve different user problems and are often combined, but they are not the same feature and should not share one analyzer.