CS Fundamentals Trainer · Guides

Search and full-text indexing

The inverted index, analysis, BM25 ranking, posting list compression, segments and merging, sharded search, keeping an index in step with the database, and when Postgres full-text search is enough.

32 min read

A user types "postgres index tuning" and expects the best ten pages out of millions in a few milliseconds. A LIKE '%word%' query cannot do that, because it has to read every row. Search works because someone did the reading in advance and kept the result in a structure built for the question: the inverted index. This guide explains that structure, how queries and ranking use it, why search engines are built from immutable segments, and how to run it in Postgres or in a dedicated engine. I ran the numbers in Postgres 16 and in small Python scripts (code in the appendix).

1. Why a normal index is not enough

A B-tree index (database indexes) is sorted by the whole value, so it answers "equals this", "starts with this" and "between these". It cannot answer "contains the word index somewhere in this paragraph", because the position of a word inside the text says nothing about where the row sorts.

I generated 200,000 synthetic documents of 30 to 70 words each (61 MB), drawn from a vocabulary of 20,000 words with the uneven frequencies of natural language, and searched for a rare word that occurs in 68 of them. (The corpus is artificial: it has no grammar, no topics, no repeated phrases and no real document-length distribution, so the timings show how the structures behave and how they scale, and are not what your corpus will give. Real text has more skewed term distributions, longer documents and clustering, all of which change index size and query cost.)

MethodTime
body LIKE '%w15000%' (parallel scan of the table)156 ms
to_tsvector(body) @@ query, computed for every row6,174 ms
The same query with a GIN index on a stored tsvector0.245 ms

The scan reads everything and its cost grows with the data; the index looks at the word and goes straight to the 69 rows that contain it. The middle row is a warning: using full-text functions without an index is far worse than a plain LIKE, because the text is analysed again for every row.

2. The inverted index

An inverted index is a dictionary from each term to the list of documents that contain it (a posting list), usually with the positions of the term inside each document. "Inverted" because the natural direction is document to words, and this goes from words to documents.

Building it has three steps: analyse the text into terms (tokenise, lowercase, remove stop words, perhaps stem), then collect the postings, then sort them by term. Step through a tiny example, once with AND semantics and once with OR:

Interactive animation: inverted index

With AND, the query quick dog takes the posting list for quick (D1 and D3), the one for dog (D2 and D3) and intersects them: one match, D3. With OR it takes the union: three matches. In both cases only the short lists were read, never the text of the documents. Posting lists are kept sorted by document id, so an intersection is a merge of two sorted lists, and skip pointers let it jump over long runs of non-matching ids. Starting with the rarest term makes the intersection cheaper.

Diagram: From documents to results

The analysis chain must match

The text is analysed at indexing time and the query at search time, and they must use the same chain; otherwise a query for "Running" looks for a term that was indexed as "run". Typical steps:

Choose them per field and per language. A field with product codes or user names usually needs no stemming at all.

Positions and phrases

To match the phrase "inverted index" the engine needs to know that the two words are adjacent, so the postings store positions. In my test corpus, the words inverted and index both appear in documents D2 and D7; the phrase inverted index matches both, while index inverted matches none, which is a check of the positions, not just of the words. Positions make the index larger and phrase queries slower, so engines keep them only when the field is configured for it.

3. Ranking: which result comes first

Finding the matches is the easy part; most queries match thousands of documents, and users read the first few. A relevance score orders them.

TF-IDF multiplies the first two. Its flaw is that tf grows without limit: a page that repeats a word fifty times beats a good page. BM25, the default in Lucene, Elasticsearch, OpenSearch and others, fixes this with a saturating term frequency (the tenth occurrence adds much less than the second) and with length normalisation controlled by two parameters, usually k1 of about 1.2 and b of 0.75.

I tested both on eight tiny documents with the query "search index". Document D6 is the word search repeated ten times. This is a demonstration of a mechanism, built to show what saturation does, with the spam document planted: it says nothing about which formula returns more relevant results on real queries, and eight invented documents cannot say it. With plain TF-IDF it scores 6.93 and the next document 1.19, a landslide for the spam. With BM25 it scores 1.39 against 1.27: it still comes first here, since it is the only document that matches search so heavily, but the gap shrank from 5.8 times to 1.1 times, so a single further signal (such as a title match or a freshness boost) is enough to reorder them. Saturation reduces keyword stuffing; it does not remove it.

BM25 is a good baseline and, with a little tuning, hard to beat on keyword search. Real systems add more signals on top: matches in the title count more than matches in the body (field boosts), popularity or click data, freshness, and more recently semantic ranking with vector embeddings, usually combined with BM25 ("hybrid search") because embeddings are good at meaning and bad at exact identifiers. Evaluate any change with a set of example queries and judgments (precision and recall at k, nDCG), not by looking at five queries. The next section says what that means in practice.

Evidence of relevance: what to measure, and what the demos do not show

The two ranking numbers above come from a constructed example. Evidence that a ranking is better comes from a different kind of test:

The same applies to the performance numbers in this guide: measure on a sample of your documents and queries, with your concurrency and update rate.

4. Making the index small and fast

Posting lists dominate the size of the index, and fortunately they compress well. Because the document ids are sorted, store the gaps between them (delta encoding) and write each gap in as few bytes as it needs (variable-byte coding). In a test with 1,000,000 documents:

Posting listRaw 4-byte idsDelta + variable-byteShare
a very common term (500,000 documents)2,000,000 bytes500,000 bytes25%
a common term (50,000 documents)200,000 bytes50,062 bytes25%
a rare term (500 documents)2,000 bytes963 bytes48%

Dense lists have small gaps (one byte each); sparse lists have larger gaps and compress less. Production engines use faster bit-packed formats (Lucene uses frame-of-reference blocks), but the idea is the same. Compression is also a speed optimisation: less data to read from disk and memory, and so less cache pressure (see the memory hierarchy).

In Postgres, the GIN index over my 200,000 documents took 29 MB, against 61 MB for the original text. That is a good ratio, but note the costs: filling the tsvector column with one UPDATE rewrote every row, and the table's heap measured 223 MB afterwards (the old row versions stay until the space is reused or the table is rewritten), and a GIN index makes writes slower, which is the price of every index.

When the index does not help

The index is fast for selective terms. For terms that occur in a large share of the documents, the work is proportional to the number of matches, not to the size of the answer you return. On the same 200,000 documents:

QueryMatchesPlan and time
a rare word69bitmap index scan, 0.245 ms
search & database (both common)85,072bitmap index scan, 125 ms
the & of (in almost every row)most rowsthe planner chose a sequential scan, 79 ms
three common words with ORDER BY ts_rank ... LIMIT 10about 47,000parallel scan, 89 ms

Two lessons. First, a frequent term is cheap in a dedicated engine's compressed lists but still costs time in proportion to the matches, which is why stop words and AND queries starting from the rarest term matter. Second, ranking costs work for every match, not for the ten you return: the database must score about 47,000 documents to find the best 10. Engines avoid some of that with early termination techniques (such as block-max WAND), and applications avoid it by narrowing the candidates first with filters, or by limiting how deep a user can page.

5. Typing mistakes and prefixes

Synonyms

A synonym list lets a search for "laptop" find "notebook computer". It looks simple and has several traps:

Languages and multilingual content

An analysis chain is per language. Stemming, stop words, tokenisation and accent handling all depend on it, and a chain for English applied to German, Portuguese or Japanese damages recall and precision.

6. Search engines: segments, merging and near-real-time

A dedicated engine such as Lucene (the library inside Elasticsearch, OpenSearch and Solr) does not update one big index in place. It writes the index in immutable segments:

Diagram: Writes create segments; merges compact them

This is the same shape as the log-structured storage used by many databases, and it has the same trade-off: fast writes and reads of old data, background work to keep it tidy.

Scaling out

An index is split into shards, each a complete index of its own subset of documents (by hash of the document id, see replication, partitioning and sharding and consistent hashing), and every shard has replicas for availability and to spread the read load. A query goes to one copy of every shard (scatter), each returns its local top results, and a coordinating node merges them (gather). Two consequences:

7. Keeping the search index in step with the database

The search engine is almost never the system of record. The source of truth is your database, and the index is a derived copy built for queries. Keeping the two aligned is the real engineering problem.

Diagram: A search index is a derived view of the primary database

8. Postgres or a dedicated engine?

Postgres full-text searchDedicated engine (Elasticsearch, OpenSearch, Solr, Typesense, Meilisearch)
Consistency with your datatransactional; one systemeventually consistent copy
Operationsnothing newanother cluster to run, monitor, upgrade and secure
Rankingts_rank (a basic scheme), no BM25 in core (extensions add BM25 and other schemes)BM25 and many tunable signals, hybrid with vectors
Language and analysisgood set of built-in configurationsvery rich analyser ecosystem, synonyms, suggesters
Featuresno built-in facets, weak fuzzy search (pg_trgm helps)facets, highlighting, fuzzy, did-you-mean, geo, aggregations
Scaleone node, or sharded manually; "millions of documents" is a rough figure that depends on the workload (see below)built to be distributed across many nodes

A sensible default: start with the database's own full-text search. It is transactional, there is nothing to synchronise, and for a modest corpus with simple relevance needs it is enough. Move to a dedicated engine when you need relevance tuning, facets, typo tolerance, search-as-you-type, very large corpora or heavy search traffic that you do not want to put on the primary database.

"Modest" and "heavy" depend on the workload, so decide with these questions, and with a test on your own data:

FactorPoints towards PostgresPoints towards a dedicated engine
Corpus size and document sizethe index and the hot part of the table fit in memorythe index is much larger than RAM, or documents are large (many pages of text)
Query costselective queries, simple filters (the rare word took 0.25 ms)many matches that must all be ranked (about 47,000 matches took 89 ms in my test, per query), several facets, deep aggregations
Query concurrencytens of searches per second beside the normal loadhundreds or thousands, which would compete with the transactional workload for CPU, memory and I/O
Write patternmoderate updates; the search column changes rarelya constant stream of updates (GIN indexes batch their insertions in a pending list and can fall behind; every update rewrites the row and its index entries)
Freshnessmust be searchable the instant the transaction commitsa second or so of lag is acceptable
Relevance needs"contains these words, newest first" is enoughtuned ranking, field boosts, synonyms, typo tolerance, learning to rank, hybrid with vectors
Languagesone or two, covered by the built-in configurationsmany, with decompounding or CJK tokenisers, or custom analysers
Team and operationsno one to run another clustersomeone owns the cluster, or a managed service is acceptable
Consistency and permissionssearch results must always agree with the database and its access rulesthe copy can lag, and you can enforce permissions in the query

Extensions and variants blur the line (BM25 and vector search inside Postgres, search features in other databases), so check what your version offers before deciding. A reasonable plan is to start in Postgres, measure query latency percentiles, indexing cost and result quality on your own data, define the threshold at which you would move, and keep the search behind an interface so that the switch is a project and not a rewrite.

9. Common mistakes

10. Things to mention in an interview

Quick recap

Appendix: the experiment code

The experiments here are demonstrations on synthetic data (a generated vocabulary with a skewed distribution, eight invented documents for the ranking comparison). They show how the structures behave and how costs scale; they are not benchmarks of Postgres or of any search engine, and they are not evidence about relevance on real text. The timings come from one small virtual machine and will differ on yours.

The first script writes 200,000 synthetic documents (words drawn from a 20,000-word vocabulary with a skewed distribution, so a few words are very common and most are rare); it is not real text, but it has the shape that matters for the posting lists. The SQL script loads them into Postgres 16, runs the queries and prints the plans with EXPLAIN (ANALYZE). Timings come from a small virtual machine and vary from run to run; the row counts and the plan shapes are the stable part. The third script is a self-contained mini search engine in Python: analysis, an inverted index with positions, TF-IDF and BM25 scoring, phrase matching, posting list compression and trigram similarity.

Generating the test corpus (synthetic documents)

import random, bisect
rnd = random.Random(11)
V = 20000
words = [f"w{i}" for i in range(V)]
# readable words for the demo queries
words[0:6] = ["the", "of", "index", "search", "database", "postgres"]
w = [1/(i+1) for i in range(V)]; tot = sum(w); cum = []; a = 0
for x in w: a += x/tot; cum.append(a)
pick = lambda: words[bisect.bisect_left(cum, rnd.random())]
with open("docs.tsv", "w") as f:
    for i in range(200000):
        n = rnd.randint(30, 70)
        f.write(f"{i}\t{' '.join(pick() for _ in range(n))}\n")

Postgres full-text search with and without a GIN index

\timing off
\set QUIET on
drop table if exists docs; create table docs(id int primary key, body text);
\copy docs from 'docs.tsv'
select pg_size_pretty(pg_total_relation_size('docs')) as table_size;
-- word frequencies of the demo terms
select count(*) filter (where body like '% search %') as search_docs,
       count(*) filter (where body like '% w15000 %') as rare_docs from docs;
\timing on
explain (analyze, costs off, timing off) select count(*) from docs where body like '%w15000%';
explain (analyze, costs off, timing off) select count(*) from docs where to_tsvector('simple', body) @@ to_tsquery('simple','w15000');
\timing off
alter table docs add column tsv tsvector;
update docs set tsv = to_tsvector('simple', body);
create index docs_gin on docs using gin(tsv);
vacuum analyze docs;
select pg_size_pretty(pg_relation_size('docs_gin')) as gin_size, pg_size_pretty(pg_relation_size('docs')) as heap_size;
\timing on
explain (analyze, costs off, timing off) select count(*) from docs where tsv @@ to_tsquery('simple','w15000');
explain (analyze, costs off, timing off) select count(*) from docs where tsv @@ to_tsquery('simple','search & database');
explain (analyze, costs off, timing off) select count(*) from docs where tsv @@ to_tsquery('simple','the & of');
explain (analyze, costs off, timing off) select id from docs where tsv @@ to_tsquery('simple','search & database & postgres') order by ts_rank(tsv, to_tsquery('simple','search & database & postgres')) desc limit 10;

BM25, phrases, posting list compression and trigrams

import math, re
from collections import defaultdict, Counter

DOCS = {
 "D1": "postgres full text search uses a gin index over tsvector columns",
 "D2": "an inverted index maps each term to the list of documents that contain the term",
 "D3": "search engines rank results with bm25 which refines tf idf with length normalisation",
 "D4": "the quick brown fox jumps over the lazy dog",
 "D5": "a database index speeds up queries but slows down writes because the index must be updated",
 "D6": "search search search search search search search search search search",
 "D7": "elasticsearch and lucene store an inverted index in immutable segments that are merged in the background",
 "D8": "caching and indexing are different ideas but search systems use both a cache and an index",
}
def tokens(s): return re.findall(r"[a-z0-9]+", s.lower())
STOP = {"a","an","the","of","and","to","in","is","are","that","with","over","each","but","because","must","be","up","down","both","use","uses","which","ideas"}

def build(docs, stop=STOP):
    index = defaultdict(dict)                  # term -> {doc: [positions]}
    length = {}
    for d, text in docs.items():
        toks = tokens(text); length[d] = len(toks)
        for pos, t in enumerate(toks):
            if t not in stop: index[t].setdefault(d, []).append(pos)
    return index, length

index, length = build(DOCS)
N = len(DOCS); avg = sum(length.values()) / N

def idf(t): n = len(index.get(t, {})); return math.log(1 + (N - n + 0.5) / (n + 0.5))   # BM25 idf (Lucene variant, never negative)
def tfidf(q):
    s = Counter()
    for t in tokens(q):
        for d, pos in index.get(t, {}).items(): s[d] += len(pos) * idf(t)
    return s
def bm25(q, k1=1.2, b=0.75):
    s = Counter()
    for t in tokens(q):
        for d, pos in index.get(t, {}).items():
            tf = len(pos); s[d] += idf(t) * tf * (k1 + 1) / (tf + k1 * (1 - b + b * length[d] / avg))
    return s
q = "search index"
print("query:", q)
for name, f in (("tf-idf", tfidf), ("bm25", bm25)):
    print(f"  {name:6}", [(d, round(v, 2)) for d, v in f(q).most_common(4)])

# phrase queries need positions
def phrase(words):
    docs = set(index[words[0]]) if words[0] in index else set()
    for w in words[1:]: docs &= set(index.get(w, {}))
    return sorted(d for d in docs if any(all(p + i in set(index[w][d]) for i, w in enumerate(words)) for p in index[words[0]][d]))
print("both words 'inverted' and 'index':", sorted(set(index["inverted"]) & set(index["index"])))
print("phrase 'inverted index':", phrase(["inverted", "index"]), "  phrase 'index inverted':", phrase(["index", "inverted"]))

# ---- posting list compression: delta + variable-byte
import random, bisect
def varint(n):
    out = bytearray()
    while True:
        b = n & 0x7F; n >>= 7
        if n: out.append(b | 0x80)
        else: out.append(b); return bytes(out)
def compress(ids): 
    prev, out = 0, bytearray()
    for i in ids: out += varint(i - prev); prev = i
    return bytes(out)
rnd = random.Random(4); N_DOCS = 1_000_000
for name, n in (("very common term", 500_000), ("common", 50_000), ("rare", 500)):
    ids = sorted(rnd.sample(range(N_DOCS), n))
    print(f"posting list of {n:>7} docs out of {N_DOCS}: raw 4-byte ints {4*n:>8} bytes, delta+varint {len(compress(ids)):>7} bytes ({len(compress(ids))/(4*n)*100:.0f}%)")

# ---- fuzzy matching with character trigrams
def trigrams(w): w = f"  {w} "; return {w[i:i+3] for i in range(len(w) - 2)}
vocab = ["postgres", "elasticsearch", "lucene", "inverted", "normalisation", "database", "indexing", "segments"]
def similar(q): 
    a = trigrams(q); return sorted(((len(a & trigrams(v)) / len(a | trigrams(v)), v) for v in vocab), reverse=True)[:2]
for typo in ("postgress", "elastisearch", "normalization"): print(f"  '{typo}' ->", [(v, round(s, 2)) for s, v in similar(typo)])

Sources

Practise this topic: Databases

More guides