Search and inverted indexes

How full text search works. Analyzers, inverted indexes, BM25 ranking, segments and sharding, and when to pick Postgres full text or Elasticsearch.

Mid-level33 min core · 38 min full depth

Read first: Indexes

The problem it solves

An outdoor store sells 50 million products. Each listing has a title and a description, about 1 KB of text: 50 GB in all. The search box takes 2,000 queries a second at peak, and the product team wants results in under 200 ms. The first version is one line of SQL:

SELECT * FROM products WHERE description ILIKE '%trail running shoes%';

It is slow. A B-tree is sorted by the start of the value. So a pattern that starts with % cannot seek. The database reads every row, and runs a substring match on each.

Where the 50 GB lives	One full scan	Queries a second it can answer
Already in RAM, 16 cores in parallel	2 to 5 s	Under 1
Local NVMe SSD at 3 GB/s	About 17 s	Well under 1
Cloud block volume at 250 MB/s	About 3.5 min	None worth counting

The workload asks for 2,000 a second. No index on description fixes a leading wildcard.

It finds the wrong things. It misses “Running shoes for the trail” (word order) and “trail-running shoe” (punctuation, plural). And a search for “shoes” matches “horseshoes”.

It cannot rank. If 40,000 listings match, SQL has no notion of which ten are best.

A search engine does the work before the query arrives. At index time, it breaks every document into normalized words, called terms. It maps each term to the sorted list of documents that contain it. This is an inverted index. A three-word query reads three lists, instead of 50 million rows.

The price is a second copy of the data that lags the database. Analysis choices are baked in until you reindex. And it’s a distributed system to run.

How it works

Step 1: Turn text into terms

An analyzer turns text into a list of terms, for documents and for queries. The index only ever answers “which documents contain this exact term?”, so everything that makes “Running”, “runs” and “run” the same word happens here.

One analyzer at index time and at query time

Scroll or pinch to zoom, drag to pan

Color key
Service
The index

Each stage is a choice with a cost:

Stage	Example	What it buys	What it costs
Tokenize	`Trail-Running` → `Trail`, `Running`	Words regardless of punctuation	Breaks `C++`, `wi-fi`, part numbers and emails unless configured
Lowercase	`Running` → `running`	Case-insensitive matching	`US` and `us` become one term
Fold	`café` → `cafe`	Accents and diacritics stop mattering	Loses meaning in languages where the accent changes the word
Stop words	drop `the`, `of`, `for`	Smaller index, fewer huge postings lists	“The Who” and “to be or not to be” become empty queries
Stem	`running`, `runs` → `run`	Matches across word forms	Over-stemming joins unrelated words: `university` and `universe`
Synonyms	`sneakers` → `shoe`	Matches the customer’s word to the catalog’s	A list to maintain; a bad entry silently pollutes every query with it

Stemmers such as Porter and Snowball chop suffixes by rule. A lemmatizer looks words up in a dictionary (better → good). Chinese and Japanese need a dictionary tokenizer, or character grams.

Index-time and query-time analysis must produce the same form of each term. Say documents are stemmed and queries are not. The index holds run, the query asks for running, and the search silently returns less. Two asymmetries are safe, because the forms still meet:

Synonyms at query time only. Expanding sneakers to shoe in the query means the synonym list can change without rebuilding the index.
Edge n-grams at index time only. For search-as-you-type, shoes is indexed as s, sh, sho, shoe, shoes. The query sho matches one of them. If you split the query into grams too, sho matches everything starting with s.

Changing an analyzer means reindexing every document, since terms are computed at write time.

Step 2: The inverted index

A database row is a forward index: document → its words. Search needs the reverse. Give each document an integer id, analyze it, and append the id to the list of each of its terms. Ids are handed out in increasing order, so every list stays sorted for free.

Term dictionary, postings and positions

Scroll or pinch to zoom, drag to pan

Color key
Service
Kept in memory

The term dictionary holds every distinct term, sorted. Each term has a pointer to its postings, and its document frequency (df): how many documents contain it. A large index has hundreds of millions of terms.

Lucene is the library inside Elasticsearch, OpenSearch and Solr. It keeps the dictionary on disk in blocks. In memory, it holds only a finite state transducer (FST). That’s an automaton that shares common prefixes and suffixes, and maps a term’s prefix to its disk block. A lookup walks the FST, then reads one block. Prefix, wildcard, regex and fuzzy queries walk the same automaton. They visit only terms that could match.

The postings list for a term holds the sorted ids of the documents that contain it. It can optionally hold three more things:

The term frequency (tf) in each document, for ranking.
The positions, for phrase queries. ("trail running" needs run right after trail.)
Character offsets, for highlighting.

Positions are often the largest part of an index. So a keyword field such as a SKU stores ids alone.

Compression is what lets postings for a common term fit. Lucene stores the gaps between consecutive ids (delta encoding). Then it bit-packs each block of 128 gaps at the width of its largest gap (frame of reference encoding):

Representation	Ids `1003, 1007, 1012, 1013, ...`	128 ids
Plain 32-bit integers	4 bytes each	512 bytes
Gaps: `1003, 4, 5, 1, ...`	Small numbers	still 512 if unpacked
Gaps bit-packed at the block’s widest gap	4 bits each if every gap is under 16	about 64 bytes

The more common the term, the smaller its gaps: a term in most documents costs a few bits per entry. This works because ids are small integers local to one segment (Step 5), never your database’s primary keys.

Skip data sits beside each list. For every block of 128 ids, it stores the block’s last id and file offset, in several levels. So the reader jumps over whole blocks, without decompressing them. “Advance to the first id at or past X” is the basic operation every query is built from. In the code, advance stands in for skip data, with a galloping search.

InvertedIndexDemo.javainverted_index.pyPostings.csinverted_index.goinverted-index.ts

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class InvertedIndexDemo {
    // Words too common to narrow a search. Real lists are per language, and per field.
    static final Set<String> STOP_WORDS = Set.of("a", "an", "and", "the", "of", "for", "with", "to", "on", "in");
    static final Pattern TOKEN = Pattern.compile("[a-z0-9]+");

    // A toy stemmer: strip one English suffix so "running", "runs" and "run" become one term.
    // Production analyzers use Porter or Snowball rules; the idea is the same.
    static String stem(String word) {
        for (String suffix : List.of("ing", "ed", "s")) {
            if (word.endsWith(suffix) && word.length() - suffix.length() >= 3) {
                word = word.substring(0, word.length() - suffix.length());
                break;
            }
        }
        // "runn" -> "run": a doubled final consonant is left over from the suffix.
        int n = word.length();
        if (n >= 2 && word.charAt(n - 1) == word.charAt(n - 2) && "aeiouls".indexOf(word.charAt(n - 1)) < 0) {
            word = word.substring(0, n - 1);
        }
        return word;
    }

    // The same function runs at index time and at query time. If they ever differ, a document
    // indexed under "run" is never found by a query for "running".
    static List<String> analyze(String text) {
        List<String> terms = new ArrayList<>();
        Matcher m = TOKEN.matcher(text.toLowerCase());
        while (m.find()) {
            if (!STOP_WORDS.contains(m.group())) terms.add(stem(m.group()));
        }
        return terms;
    }

    // First index in list[lo, hi) whose value is >= target.
    static int lowerBound(List<Integer> list, int lo, int hi, int target) {
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (list.get(mid) < target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    // Jump forward 1, 2, 4, 8 ... entries until we pass target, then binary search the last
    // jump. This is what skip lists give a postings list on disk: skip blocks without reading them.
    static int advance(List<Integer> list, int lo, int target) {
        int step = 1, hi = lo;
        while (hi < list.size() && list.get(hi) < target) {
            lo = hi + 1;
            hi = lo + step;
            step *= 2;
        }
        return lowerBound(list, lo, Math.min(hi + 1, list.size()), target);
    }

    // Walk the short list and probe the long one. The cost follows the short list (times a log),
    // not the total length, which is why engines start from the rarest term.
    static List<Integer> intersect(List<Integer> shortList, List<Integer> longList) {
        List<Integer> out = new ArrayList<>();
        int pos = 0;
        for (int doc : shortList) {
            pos = advance(longList, pos, doc);
            if (pos == longList.size()) break;
            if (longList.get(pos) == doc) out.add(doc);
        }
        return out;
    }

    static class InvertedIndex {
        final Map<String, List<Integer>> postings = new HashMap<>(); // term -> sorted doc ids

        // Ids arrive in increasing order, so appending keeps every list sorted. Sorted lists are
        // what make intersection and delta compression cheap.
        void add(int docId, String text) {
            for (String term : new LinkedHashSet<>(analyze(text))) {
                postings.computeIfAbsent(term, k -> new ArrayList<>()).add(docId);
            }
        }

        List<Integer> searchAll(String query) {
            List<List<Integer>> lists = new ArrayList<>();
            for (String term : new LinkedHashSet<>(analyze(query))) lists.add(postings.getOrDefault(term, List.of()));
            if (lists.isEmpty()) return List.of();
            lists.sort(Comparator.comparingInt(List::size)); // rarest first: the answer can't be longer than the shortest list
            List<Integer> result = lists.get(0);
            for (List<Integer> other : lists.subList(1, lists.size())) {
                result = intersect(result, other);
                if (result.isEmpty()) break;
            }
            return result;
        }
    }

    public static void main(String[] args) {
        String[] docs = {
            "Trail running shoes with a grippy sole",
            "Road running shoes, light and fast",
            "Waterproof hiking boots for rocky trails",
            "Running socks, pack of three",
            "Cleaning kit for running shoes and boots",
        };
        InvertedIndex idx = new InvertedIndex();
        for (int i = 0; i < docs.length; i++) idx.add(i + 1, docs[i]);

        for (String term : List.of("run", "shoe", "trail")) {
            System.out.println("postings[" + term + "] = " + idx.postings.get(term));
        }
        System.out.println("\"Running Shoes\" -> " + idx.searchAll("Running Shoes"));
        System.out.println("\"trail shoes\"   -> " + idx.searchAll("trail shoes"));
        // Skip analysis on the query and nothing matches: the index holds "run", not "Running".
        System.out.println("raw \"Running\"   -> " + idx.postings.getOrDefault("Running", List.of()));
    }
}

Step 3: Boolean queries intersect postings

Every query is set operations on sorted lists:

AND is an intersection, OR a union, NOT a difference.
Start from the rarest term. An AND is no longer than its shortest list. Say trail is in 200,000 documents, run in 2 million, and shoe in 1.5 million. Walk trail, and call advance on the other two. That costs about 400,000 skip-assisted probes, instead of reading 3.7 million entries.
Phrases intersect first, then check positions in the survivors.

Filters (in_stock, category) narrow the set without changing the score. Frequent ones are cached as bitsets. Sorting and facets read doc values: a column-oriented copy of each field, keyed by doc id. Postings answer “which docs have this value”. Sorting needs “what value does this doc have”.

Go deeperRanges, and top-k without scoring every match1 min

Numeric ranges (price < 100) use a BKD tree of points instead of unioning thousands of postings lists, one per distinct price.

An OR of common terms matches millions of documents, and a user wants ten. So engines keep a heap of the best k so far. They know the highest score each term (and each block of each term) could possibly add. So they skip any document that cannot beat the current tenth place. This is WAND, and its block-max variant, in Lucene since version 8. It’s why Elasticsearch stops counting at 10,000 hits by default, and reports “10,000+”. An exact count would mean visiting every match.

Step 4: Ranking, from TF-IDF to BM25

Matching decides which documents qualify. Ranking decides the order, from three intuitions:

Term frequency. Mentioning trail five times is probably more about trails than once.
Inverse document frequency. A rare term is stronger evidence: waterproof in 2% of listings says more than shoe in 30%.
Length. A 2,000-word guide contains most words by chance. One mention in a 6-word title means more.

TF-IDF multiplies the first two: tf × log(N / df), summed over query terms. The tf part is linear, so repeating trail ten times scores ten times higher (keyword stuffing works), and it ignores length.

BM25 (“best matching”, from the Okapi system of the 1990s) fixes both and has been Lucene’s default since 2016 (Lucene 6, Elasticsearch 5). For each query term in a document:

score(term, doc) = idf × tf × (k1 + 1) / (tf + k1 × (1 − b + b × docLength / avgDocLength))

idf = ln(1 + (N − df + 0.5) / (df + 0.5))

Read it in three parts:

idf is large for rare terms, and near zero for a term in nearly every document. Lucene’s + 1 inside the log keeps it positive. The original went negative for very common terms.
tf / (tf + k1 × ...) saturates. The first occurrence adds the most, the second less, the tenth almost nothing, and no amount of repetition pushes the factor past k1 + 1. k1 sets how quickly it flattens: at 0 only presence counts, at 3 repetition keeps paying for a while. The default is 1.2.
1 − b + b × docLength / avgDocLength scales that by the document’s length, relative to the average. A document of average length gets 1. A document twice as long counts its occurrences as if they were rarer. b sets the strength: 0 ignores length, and 1 applies it fully. The default is 0.75.

A document’s score is the sum over its matching query terms. Scores only order one query’s results: 8 is not “twice as relevant” as 4, and scores from different queries do not compare.

The demo is a complete engine over eight product listings. Type a query and follow it through analysis, postings and BM25.

Search eight product listings

1 Analyze the query

2 Look up postings and intersect

3 Score with BM25

k1 1.2 term frequency saturationb 0.75 length normalization

The eight documents and their indexed terms

Things to try:

Search trail and drag k1. The sticker pack that says “trail” four times leads by about 1.5 times, not the 4 times TF-IDF would give it. At k1 = 0, only presence counts. At 3, repetition pays again.
Search trail running shoes and drag b from 0 to 1. At 0, the 16-term guide ranks first, because it repeats trail and run. With length normalization, it falls below the 5-term listing.
Search Running Shoe, then turn query stemming off. The query asks for running, the index holds run, and the AND returns nothing, with no error.
Search the. Every word is a stop word, and the query is empty.

The code compares TF-IDF and BM25 on five documents, one of them keyword stuffed:

Bm25Demo.javaexample.pyBm25Demo.csmain.goexample.ts

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Bm25Demo {
    // Documents already analyzed into terms. Doc 3 repeats "trail" to game the ranking.
    static final String[] TITLES = {
        "Trail running shoe",
        "Road running shoe",
        "Waterproof hiking boot",
        "Trail sticker pack (keyword stuffed)",
        "Complete guide to trail running",
    };
    static final List<List<String>> DOCS = List.of(
        List.of("trail run shoe grippy sole".split(" ")),
        List.of("road run shoe light fast".split(" ")),
        List.of("waterproof hike boot rocky trail".split(" ")),
        List.of("trail sticker pack trail trail trail trail trail".split(" ")),
        List.of("complete guide trail run choose shoe sock pack hydrate pace long run rocky mountain trail".split(" ")));

    // In a real engine df is just the length of the term's postings list.
    static Map<String, Integer> docFreq(List<List<String>> docs, List<String> terms) {
        Map<String, Integer> df = new HashMap<>();
        for (String t : terms) df.put(t, (int) docs.stream().filter(d -> d.contains(t)).count());
        return df;
    }

    static int count(List<String> doc, String term) {
        return Collections.frequency(doc, term);
    }

    // Classic TF-IDF for comparison: raw count times log(N / df). Linear in tf and blind to
    // length, so repeating a word ten times is worth ten times as much.
    static double[] tfIdf(List<List<String>> docs, List<String> terms) {
        int n = docs.size();
        Map<String, Integer> df = docFreq(docs, terms);
        double[] scores = new double[n];
        for (int i = 0; i < n; i++) {
            for (String t : terms) {
                if (df.get(t) > 0) scores[i] += count(docs.get(i), t) * Math.log((double) n / df.get(t));
            }
        }
        return scores;
    }

    static double[] bm25(List<List<String>> docs, List<String> terms, double k1, double b) {
        int n = docs.size();
        Map<String, Integer> df = docFreq(docs, terms);
        double avgdl = docs.stream().mapToInt(List::size).average().orElse(0);
        double[] scores = new double[n];
        for (int i = 0; i < n; i++) {
            List<String> d = docs.get(i);
            for (String t : terms) {
                int tf = count(d, t);
                if (tf == 0) continue;
                // Rare terms are stronger evidence. Lucene adds 1 inside the log so idf stays
                // positive even for a term in more than half the documents.
                double idf = Math.log(1 + (n - df.get(t) + 0.5) / (df.get(t) + 0.5));
                // Long documents contain any given word by chance more often, so tf is judged
                // against the document's length relative to the average. b = 0 ignores length.
                double norm = k1 * (1 - b + b * d.size() / avgdl);
                // tf / (tf + norm) saturates: the first occurrence counts most and later ones less
                // and less, never more than (k1 + 1). k1 sets how fast it flattens.
                scores[i] += idf * tf * (k1 + 1) / (tf + norm);
            }
        }
        return scores;
    }

    static void show(String name, double[] scores) {
        System.out.println(name);
        // Top-k: an engine keeps a small heap of the best k; sorting is fine for five documents.
        List<Integer> order = new ArrayList<>();
        for (int i = 0; i < scores.length; i++) order.add(i);
        order.sort((a, c) -> Double.compare(scores[c], scores[a]));
        for (int i : order) {
            if (scores[i] > 0) System.out.printf("  %5.2f  %s%n", scores[i], TITLES[i]);
        }
    }

    public static void main(String[] args) {
        List<String> query = List.of("trail", "shoe");
        show("TF-IDF", tfIdf(DOCS, query));
        show("BM25 (k1=1.2, b=0.75)", bm25(DOCS, query, 1.2, 0.75));
    }
}

TF-IDF ranks the stuffed listing first, with 1.34. BM25 drops it to fourth, with 0.52. It puts the short listing that matches both terms on top.

Go deeperLucene's BM25 differs from the textbook1 min

Since Lucene 8, the (k1 + 1) factor in the numerator is dropped. It multiplies every score by the same constant, so the ranking is unchanged. But dropping it keeps the per-term maximum at idf, which the top-k skipping above relies on.
Document length is stored in one byte per field, a lossy encoding. So two long documents of slightly different length can get the same stored length. Small, unexpected ties in a test corpus sometimes come from this.
Scoring is per field. A query across title and description scores each field with its own statistics, then combines them. It can take the best field, the sum, or (with cross_fields) treat the fields as one. Matching in a short title naturally outweighs matching in a long description.

Step 5: Segments, refresh and merges

A compressed, delta-encoded postings list cannot take an insert in the middle. Lucene does what an LSM tree does: it never updates a file. The index is a set of immutable segments. Each one is a complete small inverted index. A search queries every segment, and merges the results.

From a write to a searchable, durable segment

Scroll or pinch to zoom, drag to pan

Color key
Database
Service
Durable now
Searchable now

Write. A document goes into an in-memory buffer and the translog, a write-ahead log fsynced before the acknowledgement, so the write survives a crash. It is not searchable yet.
Refresh. Every second by default, the buffer becomes a new segment, opened for search. It sits in the OS page cache, not fsynced, which keeps a refresh cheap. This is near-real-time search: a write becomes visible about one refresh interval later. Bulk loads raise the interval to 30 s or turn it off for much higher throughput.
Flush. Less often, segments are fsynced in a Lucene commit and the translog is trimmed.
Merge. A refresh a second under steady writes makes 86,400 tiny segments a day per shard, and every query pays per segment. A background policy merges similar-sized segments, up to about 5 GB each.

Deletes are tombstones. Deleting a document sets a bit in its segment’s live-documents bitmap. The document stays in the postings, skipped at query time and still counted in df, until a merge rewrites the segment. An update is a delete plus an add: change a price and the whole document is reindexed. That is why fields that change every second, such as stock counts, belong in a cache beside the index.

Read-your-writes. A seller who saves a listing and searches at once may not find it. Here are the fixes, in order of preference:

Show the seller’s own edit from the database.
Index with refresh=wait_for, which returns after the next refresh.
Force a refresh. This makes a segment each time, so it’s never for a busy index.

Step 6: Shards, scatter-gather and replicas

One machine runs out of disk, memory or CPU, so the index is split into partitions called shards, in one of two ways.

By document (local index): each shard is a complete small search engine over a subset of documents, routed by hashing the id. Every query goes to every shard. Elasticsearch, OpenSearch and Solr work this way.

By term (global index): each shard holds the full postings lists for a subset of terms. A query touches only the shards that own its terms. But an AND ships lists across the network to intersect them. And one 300-term document writes to nearly every shard.

Partitioning	A query touches	A write touches	Hot spots	Wins when
By document	Every shard, in parallel	One shard	Rare; hashing spreads documents evenly	Almost always: rich queries, high write rates, simple rebalancing
By term	Only the shards of its terms	Many shards (one per term)	Shards owning `new`, `sale`, trending tags	Single-term lookups at huge scale: hashtag pages, a label in a metrics store

Document partitioning turns every query into a scatter-gather in two phases:

Query then fetch across three shards

Scroll or pinch to zoom, drag to pan

Color key
Database
Service

Query phase. Each shard returns ids and scores for its own top from + size, and the coordinator merges them into a global top k.
Fetch phase. Only the winners’ shards send documents: 10 cross the network, not 30.
Latency is the slowest shard. With 50 shards, a 1-in-100 slow response on any one shard hits about 40% of queries. Fewer shards, adaptive replica selection (route to the fastest copy, the default since Elasticsearch 7) and timeouts that return partial results keep the tail down.

Replicas are full copies of a shard on other nodes. They give availability and read throughput (three copies serve about three times the queries), not write throughput, since every copy indexes every write.

The primary shard count is fixed at creation, because routing is hash(id) mod primaries. Changing it means a split or shrink (to a multiple or factor) or a reindex. Replicas can change at any time.

Go deeperWhy scores differ slightly across shards1 min

BM25’s idf needs N and df. Each shard computes them from its own documents only. That’s cheap, and close enough when documents are routed randomly and each shard holds millions of them.

But take a small index, or routing by a key that puts similar documents together. Then a term can be rare on one shard and common on another. So equal documents get different scores, depending on where they live. The dfs_query_then_fetch search type adds a round trip that collects global term statistics first. It’s for tests and tiny indexes. At scale, the per-shard estimate is fine.

Step 7: Keeping the index in sync with the database

The search index is a derived view of the database, which stays the source of truth. The index must follow it, seconds behind, without silently drifting.

Change data capture into the index, with an alias for rebuilds

Scroll or pinch to zoom, drag to pan

Color key
Service
Database
Queue or stream
Background worker

Dual writes (the service writes the database, then the index) break in two ways. An index write that fails after the commit leaves the index wrong. And two racing updates to one product can land in the opposite order, keeping the older one forever.
Change data capture reads committed changes from the database’s log into Kafka, keyed by product id. (Debezium does this on the Postgres WAL or MySQL binlog.) An indexer applies them. Nothing that committed is lost, and updates to one product stay in order.
Transactional outbox: the service writes an event row in the same transaction, and a relay publishes it. Use it when the search document needs fields the row change does not carry.

Two habits make any pipeline safe:

Version every index write, with a number that only grows, such as the row’s log sequence number. Use external versioning, so the engine rejects anything older than what it holds. Then replays and reordering become harmless.
Reconcile on a schedule. Compare counts and per-range checksums with the database, and reindex what differs.

Reindexing with aliases. Analyzer, field and shard count changes need a full rebuild. So clients query an alias, never an index name. The steps:

Record the current Kafka offset.
Create products_v8, with replicas at 0 and refresh off while loading.
Backfill it from a database snapshot.
Replay changes from the recorded offset until it catches up.
Compare counts and known queries.
Swap the alias in one atomic call.

Rollback is swapping it back.

Relevance tuning starts after BM25. The usual layers, cheapest first:

Field boosts. A title match counts three times a description match.
Proximity. Boost documents where the query words appear close together.
Business signals. Popularity, rating and recency, so a best-seller outranks an equally relevant listing nobody buys.
Learning to rank. Rerank the top 100 to 1,000 BM25 results with a model trained on clicks and purchases. Then the expensive model sees few candidates.

Measure every change offline against a judgment list: a few hundred real queries with graded results (NDCG@10). Then A/B test click-through, conversion, and the zero-results rate. That last one is the cheapest signal of broken analysis or missing synonyms. Typo tolerance (fuzzy queries, at most 2 edits) and facet counts (“Brand (124)”, read from doc values) layer on top.

Go deeperTypo tolerance and facet counts1 min

Typo tolerance. A fuzzy query accepts terms within a Levenshtein edit distance (at most 2 in Lucene). Lucene builds an automaton that accepts every string within that distance. It walks it against the FST, visiting only nearby terms. fuzziness: AUTO allows 0 edits for 1 or 2 characters, 1 for 3 to 5, and 2 beyond. Requiring the first character or two to match cuts the cost a lot. And fuzzy matches should score below exact ones. Otherwise shoe ranks show alongside it.

Facets. The “Brand (124) · Size (38) · Under $100 (512)” sidebar is an aggregation over the matched documents, read from doc values. Across shards, a top-terms facet is approximate. Each shard sends only its own top buckets. So a brand just outside one shard’s list is undercounted. Engines report an error bound. Raising the per-shard bucket count trades memory for accuracy.

Go deeperAutocomplete and vector search, briefly2 min

Autocomplete is a different query shape: a prefix, under 50 ms, on every keystroke. There are three ways to serve it from a search engine:

Edge n-grams at index time. Flexible: it matches any word in the title. But it makes several times more terms.
A completion suggester that holds an in-memory FST of whole suggestions, with weights. Fastest, but it matches only the prefix of the suggestion.
A separate service with precomputed top suggestions per prefix. The search autocomplete problem designs this end to end.

Vector search matches by meaning, instead of by term. “Shoes for muddy hills” can find “trail runner with deep lugs”, with no word in common. Documents and queries become embeddings. An approximate nearest neighbor index (usually HNSW) finds close vectors. Elasticsearch, OpenSearch and Postgres with pgvector all support it.

It is weak where BM25 is strong: part numbers, exact names, rare words. So production systems run both, and merge the two ranked lists. They often use reciprocal rank fusion: each document scores the sum of 1 / (60 + rank) over the lists it appears in.

Options and tradeoffs

Where search lives

Option	Strengths	Limits	Wins when
PostgreSQL full text (`tsvector`, GIN index)	No second system, transactional, joins and permissions in the same query	`ts_rank` uses no corpus statistics (no idf) and reads every matching row to rank; no fuzzy or facets built in	Up to a few million documents, simple ranking, or search inside a tenant’s own data
Postgres with `pg_trgm`	Indexes `LIKE '%x%'` and similarity with trigrams; typo tolerant	No linguistic analysis or ranking; trigram indexes are large	Searching names, codes and short strings
Elasticsearch or OpenSearch	BM25, analyzers per language, facets, fuzzy, geo, vectors, scales to billions	A second system to run and sync; eventually consistent; heap and shard tuning	Search is a product feature with real traffic and ranking needs
Hosted engines (Algolia, Typesense, Meilisearch)	Typo tolerance and instant search out of the box, little to operate	Pricing per record or request; less control over ranking and analysis	A small team needs a good search box this month

In Postgres, a GIN index makes matching fast. Ranking is the cost. Sorting by ts_rank scores every matching row. So a query matching 500,000 rows reads all of them, to return 10.

How the index learns about changes

Option	Lost updates	Ordering	Lag	Wins when
Dual writes	Yes, on a failure between the two writes	Can invert under concurrency	Lowest	Prototypes, or a nightly reconcile is acceptable
CDC from the log	No	Per key, from the log	1 to 5 s	The default for a database-backed index
Transactional outbox	No	Per key, by the relay	1 to 5 s	The index document is built from an event the service designs
Periodic rebuild	Until the next run	Not an issue	Hours	Small, slow-changing catalogs; also the backstop for the others

How to partition

By document unless the workload is overwhelmingly single-term lookups (Step 6). The second decision is how many shards.

Shard count	Query cost	Rebalancing	Wins when
Few, 10 to 50 GB each	Few fan-out calls, better tail latency	Slower, each move copies tens of GB	Most indexes
Many small, under 5 GB	Overhead per shard per query; heap per shard	Fast and fine-grained	Rarely; oversharding is the common mistake
Time-based indexes (daily)	Queries hit only the days in range	Old days dropped by deleting an index	Logs and events, where data ages out

How it fails

Failure	What happens	Detect	Blast radius	Fix
Mapping explosion	Dynamic mapping turns every new JSON key into a field; cluster state grows and every node slows	Field count per index; the default 1,000-field limit rejects writes	The whole cluster’s metadata	Strict mappings; key-value data in a `flattened` field or nested key/value pairs
Deep pagination	`from=9990` makes every shard return 10,000 hits to the coordinator; past that it is rejected by default	Slow queries with large `from`; heap spikes on coordinators	Coordinators, then the cluster	`search_after` with a point in time; cap the pages users can reach
Hot shard	One shard holds a huge tenant or a routing key that everyone queries	Per-shard query and indexing rate, one node’s CPU	Every query (it waits for the slowest)	Avoid custom routing on skewed keys; split big tenants into their own index
Split brain (before ES 7)	Two halves of a partitioned cluster each elect a master and accept writes	Two masters in the logs; diverging document counts	Data lost when the halves rejoin	Set `minimum_master_nodes` to a quorum, or run 7.0+, which manages quorum itself
Stale index	The CDC connector stalls or an indexer drops errors; search shows deleted or old products	Consumer lag; a canary write timed until it is searchable	Every query, silently	Alert on lag and canary freshness; reconcile counts; rebuild behind an alias
Analyzer mismatch	A changed analyzer on new documents, or a query analyzer that differs from the index	Zero-results rate jumps after a deploy	Recall for affected queries	Analyzer changes only through a reindex; test queries in CI
Merge or heap pressure	Heavy indexing plus big aggregations; long GC pauses, nodes drop out	GC time, segment count, rejected thread pool tasks	The node, then shard relocation storms	Raise refresh interval, limit aggregation size, keep heap under half of RAM

Deep pagination gets more expensive with every page. Page 1,000 asks each of 20 shards for its top 10,000. The coordinator sorts 200,000 entries, to return 10. search_after passes the last hit’s sort values, so each shard seeks past them, and every page costs the same. A point in time keeps the view stable while the index changes.

A stale index is the failure nobody pages for, because search keeps answering. Write a canary document every minute through the real pipeline and alert when it takes over a minute to become searchable.

Go deeperSplit brain in Elasticsearch before version 71 min

Before version 7, the setting that required a majority of master-eligible nodes to elect a master (minimum_master_nodes) defaulted to 1. A network partition could produce two masters, both accepting writes, and one side’s writes vanished when the cluster healed. The fix was to set it to a quorum by hand, and many clusters forgot to update it when they added nodes. Version 7 replaced the old discovery with a coordination layer that tracks the voting configuration itself. Run three dedicated master-eligible nodes in three zones either way.

At scale

Quantity	Typical value
Refresh interval	1 s default; 30 s or off for bulk loads
Max merged segment	About 5 GB by default
Shard size	10 to 50 GB is the common guidance
JVM heap	At most half the RAM, and under about 31 GB to keep compressed pointers; the rest is page cache for segments
Result window	10,000 hits by default (`from + size`)
Index size	Often 0.5 to 1.5 times the raw JSON, depending on positions, doc values and the stored source
Indexing throughput	Thousands to tens of thousands of small documents a second per node, measured, not assumed
Query latency	Single-digit to tens of ms for a selective query on a warm index; aggregations over millions of hits take longer

Sizing the store from the opening (rough). 50 million listings at 1 KB is 50 GB of source. With positions, doc values and the stored source, plan for roughly 50 to 75 GB. That’s two or three primaries of about 25 GB. Measure one shard copy’s throughput on real queries. Say a copy handles about 400 a second. Then 2,000 a second needs five copies of each shard, and six or seven leave headroom for a lost node. Keep the segments in page cache. A search engine that reads disk on every query is a slow one.

At 10x (500 million documents, 20,000 queries a second), shards and replicas scale out, and the problems move. Reindexing takes hours, so the alias swap and replay must be routine. And fan-out across 20 or more shards makes the slowest shard the latency.

At 100x, one cluster is the wrong unit. Split by tenant, region or product line. Tier the data. A small, heavily replicated index of popular documents answers most queries. The full index is queried only when that returns too little.

What to monitor

Freshness: canary write-to-searchable time, CDC consumer lag, indexer errors.
Latency and load: p99 per query type, query and indexing rate per shard, thread pool rejections.
Quality: zero-results rate, click-through on the first page.
Health: heap and GC time, segment count, disk watermarks. (Elasticsearch stops allocating shards to a node at 85% disk, and blocks writes to its indexes at 95%.)

In the interview

Interviewer asksWe store products in Postgres. Why not search them with LIKE?

A leading wildcard cannot use a B-tree, so LIKE '%shoes%' scans every row: seconds per query on 50 GB, against 2,000 a second. It also matches substrings, misses word forms and cannot rank. For a small catalog, Postgres full text with a GIN index is enough and stays transactional. At 50 million products with ranking, facets and typo tolerance, I would add Elasticsearch fed by CDC and keep Postgres as the source of truth.

Interviewer asksHow do you keep the search index in sync with the database?

Not dual writes, which lose and reorder updates. Use CDC from the Postgres WAL into Kafka, keyed by product id. An indexer writes with external versioning on the row’s LSN, so an older change is rejected. A canary measures write-to-searchable time, and a nightly reconcile compares counts. Mapping changes go to a new index, built from a snapshot plus replay, then an atomic alias swap. A seller who must see their own edit reads it from the database.

Interviewer asksWalk me through a query across 20 shards. What limits it?

The coordinator sends it to one copy of each shard. Each shard intersects postings, scores with BM25, and returns its top from + size ids and scores. The coordinator merges them, and fetches only the global top 10 documents. Latency is the slowest of 20 responses, so the tail grows with shard count. Replicas add throughput, and let routing avoid a slow copy. Deep pages cost every shard from + size hits, so pagination uses search_after with a point in time.

Seen in

Design a hotel reservation system: a CDC-fed hotel index holds the static facts. Nightly availability lives in Redis beside it, because reindexing on every booking would churn the index.
Design Ticketmaster: event search on an Elasticsearch index fed from Postgres by CDC, so browsing (about 90% of requests) stays off the booking path.
Design search autocomplete: prefix suggestions served from a precomputed trie, with Lucene’s FST-based completion suggester as the alternative.
Design a proximity service: a text query such as “vegan ramen near me” goes to a search engine with a geo_point filter. It’s fed by the same change stream as the location index.
Design Instagram: an indexer feeds post events into a search engine sharded by term, seconds behind, to serve hashtag pages. That’s the single-term lookup where term partitioning fits.
Design a metrics and monitoring system: the same inverted index maps each label value to a sorted list of series ids, intersected per query.
Design a web crawler: the front of a web search pipeline. What it fetches is what gets analyzed and indexed.

Recap

Why. LIKE '%x%' scans every row and cannot rank. An inverted index moves the work to write time: each term points to the sorted list of documents containing it.

Analysis. Index-time and query-time analysis must produce the same term forms. Synonyms at query time and edge n-grams at index time are the safe asymmetries. Changing an analyzer means reindexing.

Structure. A term dictionary (an in-memory FST over on-disk blocks), and postings lists of doc ids, frequencies and positions. They’re delta-encoded and bit-packed in blocks of 128, with skip data.

Queries. AND intersects from the rarest list. Filters are cached bitsets. Sorting and facets read doc values.

BM25. idf × saturating tf (k1 = 1.2) × length normalization (b = 0.75). Repetition stops paying, and long documents are discounted. Scores order one query’s results, and mean nothing else.

Segments. Immutable. A refresh every 1 s makes writes searchable (near real time). The translog makes them durable. Merges compact. Deletes are tombstones, and updates are delete plus add.

Distribution. Shard by document. Query, then fetch. Latency is the slowest shard. Replicas add read throughput. Primaries are fixed at creation.

Sync and operations. CDC with versioned writes, reconcile, rebuild behind an alias. Watch a freshness canary, the zero-results rate, deep pagination, hot shards and mapping growth.

Choice. Postgres full text for a small table. Elasticsearch or OpenSearch, fed by CDC, once search is a product.

Search and inverted indexes

The problem it solves

How it works

Step 1: Turn text into terms

Step 2: The inverted index

Step 3: Boolean queries intersect postings

Step 4: Ranking, from TF-IDF to BM25

Step 5: Segments, refresh and merges

Step 6: Shards, scatter-gather and replicas

Step 7: Keeping the index in sync with the database

Step 8: Relevance, typos and facets

Options and tradeoffs

Where search lives

How the index learns about changes

How to partition

How it fails

At scale

What to monitor

In the interview

Seen in

Recap

Further reading

The designbeyondcode digest, every Saturday

Search and inverted indexes

The problem it solves

How it works

Step 1: Turn text into terms

Step 2: The inverted index

Step 3: Boolean queries intersect postings

Step 4: Ranking, from TF-IDF to BM25

Step 5: Segments, refresh and merges

Step 6: Shards, scatter-gather and replicas

Step 7: Keeping the index in sync with the database

Step 8: Relevance, typos and facets

Options and tradeoffs

Where search lives

How the index learns about changes

How to partition

How it fails

At scale

What to monitor

In the interview

Seen in

Recap

Further reading

Keep reading

The designbeyondcode digest, every Saturday