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.)
| Method | Time |
|---|---|
body LIKE '%w15000%' (parallel scan of the table) | 156 ms |
to_tsvector(body) @@ query, computed for every row | 6,174 ms |
The same query with a GIN index on a stored tsvector | 0.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:
- Tokenisation: split into words. Easy in English, harder in languages without spaces, and full of special cases (e-mail addresses, version numbers, hyphens).
- Normalisation: lowercase, remove accents when appropriate.
- Stop words: drop very common words ("the", "of"). They make posting lists huge and carry little meaning, but removing them makes phrase searches like "to be or not to be" impossible; many modern engines keep them and rely on compression and ranking.
- Stemming or lemmatisation: reduce "indexes", "indexing" and "indexed" to one form. This raises recall (finds more) and lowers precision (some matches are wrong). It is language-specific.
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.
- Term frequency (tf): a document that mentions the term more often is probably more about it.
- Inverse document frequency (idf): a term that occurs in few documents is more informative than one that occurs in most. A match on "postgres" counts for more than a match on "the".
- Length normalisation: a term appearing three times in a 20-word document says more than three times in a 20,000-word one.
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:
- A judged test collection. Take real queries (sampled from your query logs, covering the frequent ones, the middle and the long tail, in each language you support), and for each one have people judge how relevant the top results are, on a small scale (for example 0 to 3) with written guidelines. Several judges per query, and a measure of how much they agree, tell you how reliable the labels are. Public collections (TREC, MS MARCO, BEIR) are useful to compare methods in general, but they are not your documents or your users.
- Metrics with a purpose. Precision at k (how many of the first k are relevant), recall (how many of the relevant ones were found), mean reciprocal rank (how far down the first good result is; right for "find the one page" tasks) and nDCG (which rewards putting the most relevant results first and handles graded judgments). Pick the metric that matches how people use the search, and report it per query group, because an average over all queries hides a regression in a segment.
- Enough queries, and a significance check. A difference of a few points on 20 queries is noise. A few hundred judged queries, a paired comparison of the old and the new ranking per query, and a confidence interval are the minimum for a decision.
- Offline, then online. Offline judgments are cheap and repeatable and catch regressions (keep a "golden" set that every change must pass). Online tests (A/B tests on clicks, reformulations, abandonment, time to the first useful click, conversion) show real behaviour but are biased by position (people click the first result), so interpret clicks with care.
- Look at failures. Read the queries with zero results, the ones users rephrase straight away, and the ones where the top result was skipped. They show problems (missing synonyms, wrong language, stemming errors) that no average reveals.
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 list | Raw 4-byte ids | Delta + variable-byte | Share |
|---|---|---|---|
| a very common term (500,000 documents) | 2,000,000 bytes | 500,000 bytes | 25% |
| a common term (50,000 documents) | 200,000 bytes | 50,062 bytes | 25% |
| a rare term (500 documents) | 2,000 bytes | 963 bytes | 48% |
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:
| Query | Matches | Plan and time |
|---|---|---|
| a rare word | 69 | bitmap index scan, 0.245 ms |
search & database (both common) | 85,072 | bitmap index scan, 125 ms |
the & of (in almost every row) | most rows | the planner chose a sequential scan, 79 ms |
three common words with ORDER BY ts_rank ... LIMIT 10 | about 47,000 | parallel 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
- Prefix search ("auto" matching "automatic") works naturally on a sorted term dictionary: all terms with the prefix form one range. Search-as-you-type is built on prefix ranges or on indexing edge n-grams.
- Fuzzy matching finds terms within an edit distance. Comparing the query with every term would be slow, so engines use automata over the dictionary or character n-grams: split each term into overlapping groups of three characters and look for terms that share many. In my test, "postgress" matched postgres (similarity 0.73), "elastisearch" matched elasticsearch (0.69) and the British/American spelling "normalization" matched normalisation (0.65), all far above the next best candidate (0.0). Postgres offers this in the
pg_trgmextension. - Synonyms and query expansion are decided per domain ("NYC" and "New York") and need care; see the next subsection.
Synonyms
A synonym list lets a search for "laptop" find "notebook computer". It looks simple and has several traps:
- Where to apply them. Applied at query time (the query is expanded to "laptop OR notebook"), a change takes effect at once without a rebuild, and the index stays small. The cost is that multi-word synonyms are hard for the query parser (the phrase "new york" has to match as a unit), scoring can be skewed (the more synonyms a query has, the more matches), and the expansion happens on every query. Applied at index time (each document is also indexed under the alternatives), queries are simple and fast, but every change to the list needs the affected documents to be reindexed, and the index is larger. Many teams use query-time synonyms for lists that change often and index-time for stable ones; whichever you choose, the analysis chain at both ends has to be consistent with it.
- Direction. "Postgres" may stand for "PostgreSQL", but a search for "database" should not be limited to Postgres. Use one-way rules (a specific term expands to the general one, or the reverse, deliberately) and equivalence rules only where the terms are truly interchangeable.
- Interaction with stemming, stop words and case. Synonyms are matched on analysed terms, so a rule written for "indexes" may never fire after stemming reduces it to "index", and a rule for a stop word may never see it.
- Context. "Apple" and "java" mean different things in different domains, and a synonym that helps one query hurts another. Curated, domain-specific lists, reviewed against the evaluation set, beat a generic thesaurus; learned or embedding-based expansion needs the same checks.
- Maintenance. Keep the list in version control, with a reason for each rule, and measure every change on the judged queries. Queries that return nothing are the best source of new rules.
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.
- Know the language of each document and each query. Store it with the document when it is known (a
languagefield), detect it when it is not (short texts and mixed texts are where detection fails), and decide what to do with queries whose language you cannot tell (search several chains, or use the user's interface language). - Index patterns. One field per language (
title_en,title_pt,title_de, each with its own analyser) gives the best analysis and is simple to query when you know the language. A multi-field indexes the same text under several analysers (for example a stemmed one and an exact one). A separate index per language is cleaner for large corpora and per-language tuning. In Postgres, atsvectoris built with a text search configuration (english,portuguese,germanand so on), so store the configuration used with each row and use the same one in the query; building every vector with one fixed configuration is a common mistake. - Languages differ in what a "word" is. German compounds (Datenbankindex) need decompounding to match "Index"; Chinese, Japanese and Thai have no spaces and need a dictionary-based or n-gram tokeniser; Arabic and Hebrew need morphological handling; Turkish has its dotted and dotless i. Accent folding is helpful in one language (searching "cafe" for "café") and harmful in another where the accent separates words (Portuguese pais and país, Spanish año and ano). Unicode normalisation (NFC/NFKC) and consistent case folding avoid invisible mismatches.
- Mixed-language content (a Portuguese page with English technical terms, code identifiers) is normal. Index code and identifiers with a chain that does not stem, and allow a query to match both fields.
- Cross-language search (a query in one language finding documents in another) needs translation or multilingual embeddings, and is a different feature from the above.
- Evaluate each language separately. An average over all queries can be good while one language is bad; keep judged queries per language.
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
- A segment never changes after it is written. That makes it simple to cache, to read concurrently without locks, and to compress well.
- A refresh makes recent documents searchable (about one second by default in Elasticsearch, hence "near-real-time" and not real-time). A commit makes them durable; the transaction log covers the gap.
- A delete only marks the document; an update is a delete plus a new document. The space returns when segments are merged in the background.
- A query searches all segments and merges the results, so many small segments slow it down; the merge policy keeps their number in check, at the cost of background I/O.
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:
- Latency is set by the slowest shard, so tail latency matters (see observability on percentiles).
- Scores are local: idf is computed per shard unless the engine is told to collect global statistics, so very small shards or unbalanced ones can produce slightly different rankings. Deep paging (page 1,000) forces every shard to produce 1,000 times the page size; prefer "search after" cursors to offsets, as in pagination for APIs.
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
- Dual writes (the application writes to the database and then to the index) fail in between: the database commit succeeds and the index call fails, or the other way round. Use an outbox table or change data capture so that the event is committed in the same transaction as the data; the pattern is discussed in message queues and delivery guarantees.
- Make the indexer idempotent, index documents by their primary id and a version, so that redelivery and reordering of events cannot bring back an old version.
- Expect lag and design for it: a record saved a second ago may not be searchable yet (see consistency). For "read your own write", show the new item from the database directly. Lag has several parts that add up: the time until the change event is published (an outbox poller's interval), the queue wait, the indexer's batching, the engine's refresh interval (about one second by default in Elasticsearch, and often raised to 30 seconds or more during bulk loads for throughput), and replica lag if searches go to replicas. Measure it end to end: write a heartbeat document or stamp each document with its commit time, and track how long until it can be found, at the 50th, 95th and 99th percentiles. Then decide what the product promises, and alert when the lag exceeds it.
- Removals matter more than additions. If a document is deleted, unpublished, or a user loses access, the search index must stop returning it. A late addition is an annoyance; a late removal can leak data. Treat deletes and permission changes as high priority (a separate fast path), and re-check access against the database when you load the full records, so that a stale index entry cannot expose anything.
- Expect indexing failures and handle each kind on purpose. A bulk request can partly succeed (the engine returns an error for individual items, even when the HTTP status is 200), so check every item. Transient failures (a timeout, overload, a node restarting) should be retried with backoff and jitter (see resilience patterns); permanent ones (a mapping conflict, a document that is too large, a field of the wrong type) will fail every time, so after a few attempts move the event to a dead-letter queue with the reason, alert on it, and keep going, so that one bad document does not block the stream behind it. Use the record's version as an external version where the engine supports it, so a retried or reordered older event cannot overwrite a newer one. Apply backpressure when the engine is saturated (smaller batches, slower consumption) and not an unbounded retry loop.
- Reconcile. Even with all this, the index and the database drift apart (a lost event, a bug, a restore of one side). Run a periodic reconciliation: compare counts, ids and a checksum or version per record between the database and the index, report the difference as a metric, and repair it by reindexing the missing or stale documents. The ability to rebuild the whole index (next point) is the last line of defence.
- Be able to rebuild. Mappings and analysers change; plan to reindex into a new index and switch an alias to it, with the old one kept until the new is verified. This is why the database, not the index, must hold the truth.
- Authorisation is a search problem too: filter results by what the user may see, in the query (as a filter on a tenant or permission field), not afterwards, or the counts, facets and paging will leak and be wrong. See multi-tenant systems.
8. Postgres or a dedicated engine?
| Postgres full-text search | Dedicated engine (Elasticsearch, OpenSearch, Solr, Typesense, Meilisearch) | |
|---|---|---|
| Consistency with your data | transactional; one system | eventually consistent copy |
| Operations | nothing new | another cluster to run, monitor, upgrade and secure |
| Ranking | ts_rank (a basic scheme), no BM25 in core (extensions add BM25 and other schemes) | BM25 and many tunable signals, hybrid with vectors |
| Language and analysis | good set of built-in configurations | very rich analyser ecosystem, synonyms, suggesters |
| Features | no built-in facets, weak fuzzy search (pg_trgm helps) | facets, highlighting, fuzzy, did-you-mean, geo, aggregations |
| Scale | one 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:
| Factor | Points towards Postgres | Points towards a dedicated engine |
|---|---|---|
| Corpus size and document size | the index and the hot part of the table fit in memory | the index is much larger than RAM, or documents are large (many pages of text) |
| Query cost | selective 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 concurrency | tens of searches per second beside the normal load | hundreds or thousands, which would compete with the transactional workload for CPU, memory and I/O |
| Write pattern | moderate updates; the search column changes rarely | a 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) |
| Freshness | must be searchable the instant the transaction commits | a second or so of lag is acceptable |
| Relevance needs | "contains these words, newest first" is enough | tuned ranking, field boosts, synonyms, typo tolerance, learning to rank, hybrid with vectors |
| Languages | one or two, covered by the built-in configurations | many, with decompounding or CJK tokenisers, or custom analysers |
| Team and operations | no one to run another cluster | someone owns the cluster, or a managed service is acceptable |
| Consistency and permissions | search results must always agree with the database and its access rules | the 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
- Using
LIKE '%term%'for search on a table that will grow. - Calling
to_tsvectorinside theWHEREclause with no matching expression index, or forgetting to store the vector and index it. - Analysing documents and queries with different chains.
- Aggressive stemming or stop-word removal that breaks names, codes and phrase queries.
- Evaluating relevance by eye on a handful of queries, or treating a synthetic demo as proof that one ranking is better.
- One analyser for every language, accent folding that merges different words, and synonym lists that nobody tests.
- Ignoring index lag, partial bulk failures and late deletes, or having no way to reconcile the index with the database.
- Treating the search index as the source of truth, or dual-writing without an outbox.
- Letting users page deep with offsets.
- Filtering by permissions after the search.
- Putting the search load on the primary database without limits, and the opposite: building a cluster for 50,000 documents.
10. Things to mention in an interview
- Why a B-tree cannot do "contains a word", and the inverted index as term to sorted posting list with positions.
- AND as an intersection of sorted lists (rarest first), OR as a union, a phrase as a position check.
- tf, idf and length normalisation; BM25's saturation; the idea that ranking is a pipeline with many signals, evaluated with judgments.
- Index compression with deltas and variable-byte coding; immutable segments with background merges; near-real-time refresh.
- Sharding for scale, scatter-gather, and the cost of deep paging.
- The index as a derived view: the outbox pattern, idempotent indexing, reindexing with an alias, and permissions in the query.
- Starting with Postgres full-text search and moving to a dedicated engine for specific, named reasons that depend on the workload (corpus and query cost, concurrency, update rate, freshness, relevance and language needs, operations).
- How to know a ranking is better: judged queries, nDCG and other metrics, enough queries, offline and online tests, and per-language evaluation; and why a demo on eight documents is not evidence.
- Synonyms (query time against index time, direction, interaction with stemming), multilingual analysis (per-language chains, compounds, CJK, accents) and the lag and failure modes of indexing (partial bulk failures, dead letters, deletes, reconciliation).
Quick recap
- The inverted index maps terms to sorted posting lists with positions; a query combines lists and never reads the text. In the test a GIN lookup took 0.245 ms against 156 ms for
LIKEand 6,174 ms for an unindexedto_tsvector. - The analysis chain (tokenise, normalise, stop words, stem) must be the same at indexing and query time, and it is specific to each language.
- Relevance is shown by judged queries and metrics on your own data, not by demos; the timings and ranking examples in this guide use synthetic data to show mechanisms.
- BM25 improves on TF-IDF with saturation and length normalisation; ranking costs work for every match, not for every returned result.
- Posting lists shrink to about a quarter with delta and variable-byte coding.
- Engines write immutable segments and merge them in the background; they scale by sharding with scatter-gather.
- The search index is a derived copy: feed it through an outbox, make indexing idempotent, expect lag and indexing failures (handle partial bulk errors with retries and a dead-letter queue, propagate deletes fast), reconcile it with the database, and be able to rebuild.
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
- Christopher Manning, Prabhakar Raghavan and Hinrich Schütze, Introduction to Information Retrieval (Cambridge University Press), the chapters on the inverted index, index compression, scoring and evaluation.
- Stephen Robertson and Hugo Zaragoza, The Probabilistic Relevance Framework: BM25 and Beyond (Foundations and Trends in Information Retrieval, 2009).
- PostgreSQL documentation, Full Text Search, GIN indexes and pg_trgm.
- Apache Lucene documentation, scoring and the BM25 similarity, and the Elasticsearch guide on near-real-time search, segments and merging.
- Ellen Voorhees and Donna Harman (eds.), TREC: Experiment and Evaluation in Information Retrieval (MIT Press, 2005), and Nandan Thakur et al., BEIR: A Heterogeneous Benchmark for Zero-shot Evaluation of Information Retrieval Models (2021), on test collections and evaluation; Kalervo Järvelin and Jaana Kekäläinen, Cumulated gain-based evaluation of IR techniques (ACM TOIS, 2002), for nDCG.
- Elasticsearch documentation on synonym token filters, language analyzers, the refresh interval and the bulk API (per-item errors); PostgreSQL documentation on text search configurations and GIN fast update.
- Daniel Lemire and others on SIMD-based integer compression for posting lists (for example Decoding billions of integers per second through vectorization, 2015).
Practise this topic: Databases