BM25 and Modern Search Algorithms: Inside Databases at Scale
Published:
Every application eventually needs search. A product catalog, a log explorer, a documentation site, a support inbox, a code repository, or a retrieval-augmented generation (RAG) pipeline all reduce to the same question: given a query, which documents are relevant, and in what order?
The surprising part is how much of the answer still comes down to one scoring function invented in the 1990s. BM25 (Best Matching 25) remains the default ranking algorithm in Lucene, Elasticsearch, OpenSearch, SQLite's FTS5, and many other systems. It is fast, interpretable, robust, and hard to beat as a baseline.
This article is a practical tour of BM25 and the search algorithms around it, with a focus on how real databases implement search and what changes at scale. We will cover the inverted index, TF-IDF, BM25 and its variants, language models, dense retrieval and hybrid search, learning to rank, then walk through the major databases and the engineering tricks that make search work over billions of documents.
1. Search is a database problem
It helps to separate three concerns that people often blur together:
- Retrieval: find a candidate set of documents that might be relevant.
- Ranking: order those candidates by predicted relevance.
- Presentation: filter, facet, highlight, paginate, and personalize.
Databases own the data and the consistency guarantees. Search engines own the retrieval and ranking machinery. Modern systems increasingly blend the two: PostgreSQL ships full-text search, SQLite ships FTS5, MySQL and SQL Server ship FULLTEXT indexes, and search engines add aggregations, joins, and transactions.
The core trade-off is straightforward:
- Database-first search
- Pros: ACID, joins, permissions, one source of truth.
- Pros: simpler operations for small and mid-sized corpora.
- Cons: weaker relevance tooling and distributed scale.
- Search-engine-first
- Pros: excellent relevance, analyzers, facets, scale-out.
- Pros: near-real-time indexing and a rich query DSL.
- Cons: eventual consistency, duplication, operational overhead.
Most large companies end up with both: the database is the system of record, and a search engine (or a search extension inside the database) is a derived index fed by change data capture, triggers, or application writes.
2. The inverted index: the data structure behind everything
Almost every full-text system is built on an inverted index. Instead of scanning documents for query terms, it maps each term to the list of documents that contain it.
A document goes through an analysis pipeline first:
raw text
-> character filtering (HTML strip, Unicode normalization)
-> tokenization (split into words)
-> normalization (lowercase, accent folding)
-> stop-word removal (optional)
-> stemming or lemmatization (optional)
-> synonyms and shingles (optional)
The result is a stream of terms. For each term the index stores a postings list:
term "bm25" -> [ (doc 3, tf 4, positions [12, 40, 88, 91]),
(doc 9, tf 1, positions [7]),
(doc 17, tf 2, positions [3, 55]) ]
That single structure supports most of what users expect:
- Boolean
AND/OR/NOTvia postings intersection and union. - Phrase queries ("exact phrase") via positional overlap.
- Proximity queries (
bm25 NEAR ranking) via position distance. - Ranked retrieval by scoring each posting and returning the top
k. - Prefix and wildcard queries via sorted dictionaries, tries, or FSTs.
Three more structures usually sit beside the postings:
- Dictionary (term → offset into postings)
- Often a finite state transducer (FST), which is compact, ordered, and supports prefix and fuzzy traversal.
- Postings (doc IDs, term frequencies, positions)
- Compressed heavily because it dominates index size. Common encodings are delta + variable-byte, frame-of-reference, PForDelta, and Roaring bitmaps for filter-friendly fields.
- Forward index / doc values (doc → terms or per-doc statistics)
- Needed for scoring, sorting, faceting, highlighting, and machine-learned ranking features.
A useful mental model: the inverted index answers "which documents mention this term?", and the forward index answers "what is in this document?". Ranking is the process of combining many term-level answers into one score per document.
3. Boolean retrieval and TF-IDF
Boolean retrieval is the oldest model. A query like:
bm25 AND (database OR search) NOT deprecated
is evaluated purely by set operations on postings. It is precise, explainable, and still valuable in legal, compliance, and security tools where missing a document is unacceptable. Its weakness is obvious: no ranking. A document that matches every term once looks the same as one that discusses the topic in depth.
TF-IDF adds ranking with two intuitions:
- Term frequency (TF): the more often a term appears in a document, the more relevant that document probably is to the term.
- Inverse document frequency (IDF): rare terms are more informative than common ones. "The" appears everywhere; "BM25" does not.
A classic formulation is:
score(D, Q) = sum over q in Q of tf(q, D) * idf(q)
idf(q) = log( N / df(q) )
where N is the number of documents and df(q) is the number of documents
containing q.
Variants normalize the term frequency (for example by dividing by document length) and use smoothed IDF. The vector space model treats each document and query as a vector of term weights and ranks by cosine similarity:
cos(q, d) = (q . d) / (||q|| * ||d||)
TF-IDF and cosine similarity powered the first generation of web search and are still useful for similarity, clustering, and lightweight semantic matching.
But TF-IDF has two well-known problems:
- Unbounded term frequency. If a term appears 100 times, TF-IDF rewards it roughly 100 times more than a single occurrence. In practice, relevance saturates: the 100th occurrence adds almost nothing over the 5th.
- Crude length normalization. Long documents naturally contain more term occurrences. Dividing by raw length helps, but the relationship is not linear, and different fields (title vs body) deserve different treatment.
BM25 was designed to fix exactly these issues.
4. BM25: the workhorse
BM25 is a probabilistic ranking function in the family of "Best Matching" models. The version used in production is usually the Okapi BM25 formula:
score(D, Q) = sum over q in Q of
idf(q) * f(q, D) * (k1 + 1)
-------------------------------------------------------
f(q, D) + k1 * (1 - b + b * (|D| / avgdl))
where:
f(q, D) = term frequency of q in document D
|D| = length of D in tokens
avgdl = average document length in the collection
k1 = term-frequency saturation parameter (commonly 1.2 to 2.0)
b = length-normalization parameter (commonly 0.75)
Lucene and most modern engines use a smoothed IDF that stays positive:
idf(q) = ln( 1 + (N - n(q) + 0.5) / (n(q) + 0.5) )
where N is the total number of documents and n(q) is the number of documents
containing q.
This ln(1 + ...) form avoids negative scores for terms that appear in more than half the collection, which the original Robertson-Sparck Jones IDF could produce.
Intuition for the two knobs:
k1controls saturation.- As
f(q, D)grows, the score approaches an asymptote instead of growing without bound. Withk1 = 1.2, going from 1 to 2 occurrences adds a lot; going from 10 to 20 adds comparatively little. Smallerk1saturates sooner, largerk1rewards repetition more. bcontrols length normalization.b = 0disables it.b = 1applies full normalization by|D| / avgdl.b = 0.75is a strong default. Lowerbfor short, uniform fields such as titles; higherbfor long, variable fields such as articles.
A useful way to read the formula is as a ratio:
- The numerator rewards matches, weighted by IDF.
- The denominator penalizes documents that are long relative to average, and prevents unbounded growth with repetition.
- The
(k1 + 1)factor keeps scores in a familiar range without changing ranking.
BM25 is not magic. It simply encodes three things that tend to be true: rare terms matter more, repeated terms matter less and less, and long documents should not win just by being long.
Variants worth knowing
- BM25+
- Adds a positive lower bound so that even a single occurrence contributes meaningfully. Useful for short queries and short documents.
- BM25L
- Adjusts length normalization for long documents; sometimes helps on corpora with skewed length distributions.
- BM25F (fields)
- Handles multiple fields such as title, body, and anchor text. Field term frequencies are weighted and normalized, then combined before saturation:
This is whytf'(q, D) = sum over fields f of w_f * tf(q, D_f) / (1 - b_f + b_f * |D_f| / avgdl_f) score = idf(q) * tf'(q, D) * (k1 + 1) / (k1 + tf'(q, D))title^3andbodystyle boosts work in Elasticsearch and why separate field lengths matter.
Why BM25 endures:
- It needs only term statistics already present in the inverted index.
- It is cheap: one pass over matching postings per query term.
- It is robust across domains with little tuning.
- It is explainable, which matters for debugging and compliance.
- It is a strong baseline that dense models still have to beat.
5. Beyond BM25: language models, vectors, and learning to rank
BM25 is not the only classical ranking model. Several alternatives are worth understanding because they appear in databases and search engines.
Query likelihood with language models
Treat each document as a language model and score the probability that it generated the query. A common smoothed form is Dirichlet smoothing:
score(D, Q) = sum over q in Q of
log( (tf(q, D) + mu * P(q | C)) / (|D| + mu) )
where P(q | C) is the collection language model and mu controls how much we trust the document versus the collection. This family is theoretically elegant and competitive with BM25, and it underlies systems such as Indri and Lemur. Many engines expose it as an alternative similarity.
Vector space and cosine similarity
Represent documents and queries as sparse TF-IDF vectors and rank by cosine. This is still common for similarity, deduplication, and recommendation, even when full-text search uses BM25.
Dense (semantic) retrieval
Neural encoders map queries and documents into a shared vector space. A bi-encoder embeds each document once and each query at search time, then an approximate nearest neighbor (ANN) index finds close vectors. Popular ANN structures include HNSW (a navigable small-world graph) and IVF with product quantization for memory efficiency.
Dense retrieval shines when the query and document use different words: "cheap flights to Europe" can match "low-cost airfare to the EU". It is weaker on exact identifiers, rare tokens, product codes, and names, where lexical matching is precise.
Hybrid retrieval and reciprocal rank fusion
The industry default for serious search and RAG is hybrid: run BM25 and dense retrieval in parallel, then combine. Reciprocal Rank Fusion (RRF) is a simple, robust merger that uses ranks rather than raw scores:
score(d) = sum over retrievers r of 1 / (k + rank_r(d))
with k commonly set to 60. RRF avoids the score-calibration problem because BM25 scores and cosine similarities are not on the same scale.
Cross-encoder reranking
A cross-encoder reads the query and document together and produces a relevance score. It is far more accurate than a bi-encoder but too expensive to run over the whole corpus, so it is used on the top 50-200 candidates after retrieval. This retrieve-then-rerank pattern is standard in RAG.
Learning to rank (LTR)
Instead of hand-tuning a formula, collect features (BM25 per field, proximity, popularity, freshness, click signals) and train a model to order results. LambdaMART and related gradient-boosted trees are common. Elasticsearch, OpenSearch, Solr, and Vespa support LTR plugins. LTR usually sits on top of BM25 rather than replacing it: BM25 remains a strong retrieval feature.
Fuzzy, prefix, and n-gram matching
Typo tolerance uses edit distance (Levenshtein automata), often bounded to one or two edits. Prefix search uses sorted dictionaries, tries, or FSTs. N-gram indexes (character or token n-grams) support substring and CJK search at the cost of index size. Systems such as SQLite's trigram tokenizer, PostgreSQL's pg_trgm, and RediSearch's fuzzy matching all apply variations.
Query understanding
Spell correction, synonyms, stemming, query expansion (including pseudo-relevance feedback), intent classification, and entity recognition often improve results more than switching ranking formulas. Analysis choices are frequently higher-leverage than k1 and b.
6. How databases implement search
This is where theory meets operations. The same BM25 ideas show up with very different ergonomics, guarantees, and scaling models.
PostgreSQL
PostgreSQL has built-in full-text search using the tsvector and tsquery types. You convert text to a tsvector, build a GIN index (or GiST for specialized cases), and match with the @@ operator.
ALTER TABLE docs ADD COLUMN search_vector tsvector
GENERATED ALWAYS AS (
setweight(to_tsvector('english', coalesce(title, '')), 'A') ||
setweight(to_tsvector('english', coalesce(body, '')), 'B')
) STORED;
CREATE INDEX docs_search_idx ON docs USING GIN (search_vector);
SELECT id, title,
ts_rank_cd(search_vector, query) AS rank
FROM docs, websearch_to_tsquery('english', 'bm25 search') query
WHERE search_vector @@ query
ORDER BY rank DESC
LIMIT 20;
Important detail: ts_rank and ts_rank_cd are not BM25. They use term frequency and, for ts_rank_cd, cover density (proximity) with normalizing options. They are good enough for many applications but are not a drop-in BM25 implementation. For real BM25 inside Postgres, ParadeDB's pg_search extension (built on Tantivy) provides BM25 indexes.
Other useful pieces:
websearch_to_tsqueryturns user-style input into a safetsquery.pg_trgmadds trigram similarity forLIKE/ILIKEacceleration and fuzzy matching using GIN or GiST indexes.- The
rumextension improves ranked scans and positional data. - GIN "fastupdate" buffers new entries in a pending list; tune or clean it for write-heavy workloads.
- Store the
tsvectoras a generated column to avoid recomputing it.
At scale, Postgres full-text is excellent for transactional applications and small-to-medium corpora. For very large corpora, heavy faceting, or complex relevance pipelines, teams often pair Postgres with an external search engine.
MySQL (InnoDB FULLTEXT)
MySQL provides FULLTEXT indexes on InnoDB (and MyISAM) tables:
ALTER TABLE docs ADD FULLTEXT INDEX ft_docs (title, body);
SELECT id, title,
MATCH(title, body)
AGAINST ('bm25 search' IN NATURAL LANGUAGE MODE) AS score
FROM docs
WHERE MATCH(title, body)
AGAINST ('bm25 search' IN NATURAL LANGUAGE MODE)
ORDER BY score DESC
LIMIT 20;
Natural language mode returns a relevance score based on term frequency and document frequency, broadly TF-IDF-like rather than true BM25. Boolean mode supports operators such as + (required), - (excluded), ~ (negate rank), "phrase", * (wildcard), and @distance, and is often the better choice for precise control.
InnoDB implements full-text indexes with auxiliary tables (FTS_DOC_ID and FTS_*_INDEX_* tables) rather than a single opaque index. Defaults such as innodb_ft_min_token_size (usually 3) and the stopword list materially change results; plan for reindexing after changing them. For CJK languages, use the ngram parser. MySQL is single-node for this feature, so very large or high-QPS search usually moves to an external engine.
SQL Server
SQL Server uses full-text catalogs and predicates such as CONTAINS and FREETEXT, plus table-valued functions CONTAINSTABLE and FREETEXTTABLE that return a RANK column (0-1000). CONTAINS supports Boolean logic, phrases, proximity (NEAR), and ISABOUT with per-term weights. FREETEXT performs a broader meaning-based match. Language-specific word breakers, stemmers, stoplists, and thesauri are configurable.
Full-text indexes are populated asynchronously and are often placed in a separate filegroup. The feature is mature and integrates well with .NET and enterprise stacks, but distributed relevance at web scale typically still uses a dedicated search engine.
Oracle Text
Oracle Text offers CONTAINS and SCORE (0-100) with index types tuned to different jobs: CONTEXT for large documents with linguistic and theme search, CTXCAT for small text columns combined with structured predicates, and CTXRULE for document classification. It supports stemming, fuzzy matching, thesaurus expansion, and ABOUT queries for themes. It is common in enterprise, legal, and records-management systems where the data already lives in Oracle.
SQLite FTS5
SQLite's FTS5 extension turns search into a virtual table and is one of the best embedded full-text options available anywhere:
CREATE VIRTUAL TABLE docs USING fts5(
title,
body,
tokenize = 'porter unicode61'
);
SELECT title, bm25(docs) AS rank
FROM docs
WHERE docs MATCH 'bm25 OR search'
ORDER BY rank
LIMIT 20;
FTS5 really does implement BM25 through the bm25() function, and its scores are ordered so that smaller (more negative) is better, which is why the query orders ascending. It also provides highlight() and snippet() for result presentation, prefix indexes, trigram tokenization for substring search, and external-content tables so the index can mirror a normal table.
FTS5 is ideal for desktop, mobile, edge, and small-server applications. It is single-node, but it needs no separate service, which is a huge operational win for embedded products and local RAG.
Elasticsearch, OpenSearch, and Lucene
Lucene is the library underneath Elasticsearch, OpenSearch, and Solr, and it is the reference implementation of large-scale BM25. Lucene stores data in immutable segments. New documents are buffered, a refresh makes them searchable (one second by default), and background merges compact segments. Deletes are tombstones until a merge reclaims space.
BM25 has been the default similarity since the Lucene 6 / Elasticsearch 5 era, replacing the older TF-IDF default. A typical query uses multi_match with field boosts:
GET /docs/_search
{
"query": {
"multi_match": {
"query": "bm25 search",
"fields": ["title^3", "body"],
"type": "best_fields"
}
}
}
The analysis chain is where much of the real work happens: character filters, tokenizers, lowercase, stop words, stemmers, synonyms, and shingles. BM25 parameters are configurable per field via a similarity definition.
Distributed relevance has a subtle wrinkle. By default, each shard computes IDF from its own documents, so the same document can score differently depending on shard layout. dfs_query_then_fetch performs a preliminary round trip to gather global term statistics; it improves consistency at the cost of latency. Many teams tune shard routing and accept minor drift instead.
Scale features include dynamic pruning (WAND and Block-Max WAND), search_after for deep pagination, index sorting, aliases and rollover, index lifecycle management, tiered hot-warm-cold storage, and searchable snapshots. Shard sizing is a real design decision: too many small shards waste resources, while very large shards make recovery and rebalancing slow.
MongoDB Atlas Search
MongoDB's older $text indexes provide basic term matching, but Atlas Search is the modern option: an Apache Lucene-based engine exposed as the $search aggregation stage. It supports analyzers, text, phrase, autocomplete, and compound queries, returns a searchScore, and integrates with Atlas Vector Search for hybrid retrieval. You get Lucene-style relevance without running a separate cluster, at the cost of relying on the managed service.
RediSearch
RediSearch (bundled into recent Redis distributions) builds an in-memory inverted index and exposes FT.CREATE and FT.SEARCH. It supports BM25 and TF-IDF scoring via the SCORER option, plus vector fields (FLAT and HNSW) and hybrid queries. It is excellent for low-latency search over data that already fits in memory, such as autocomplete, session data, and caches. Memory cost and cluster sharding are the main constraints.
ClickHouse
ClickHouse approaches text from the analytics side. Token and n-gram bloom filter skip indexes (tokenbf_v1, ngrambf_v1) and functions such as hasToken accelerate filtering over huge datasets. Recent versions add experimental full-text indexing, but these are not a replacement for a BM25 relevance engine. The common pattern is to prefilter in ClickHouse and rank elsewhere, or to use ClickHouse for log analytics where time and attribute filters do most of the work.
Cloud warehouses: BigQuery, Snowflake, Databricks
Warehouse search features are optimized for filtering and exploration rather than relevance ranking. BigQuery provides the SEARCH operator and search indexes to accelerate token and phrase matching; Snowflake provides CONTAINS and managed Cortex Search, which blends keyword and vector retrieval for RAG. None of these exposes a tunable BM25 formula, and that is usually fine: analytics queries tend to be highly selective on structured columns, with text as an additional filter.
Cassandra and ScyllaDB
Wide-column stores generally do not implement BM25. Cassandra has secondary indexes and historically SASI, but these are not a relevance engine, and SASI is no longer recommended for new work. The standard pattern is to stream changes via CDC into Elasticsearch or OpenSearch and serve search there. ScyllaDB has been adding vector search, but full-text relevance still usually lives in a dedicated system.
Vector databases and hybrid engines
pgvector adds HNSW and IVFFlat indexes to PostgreSQL, making it possible to keep relational data, full-text search, and embeddings in one database. Qdrant, Weaviate, and Milvus focus on ANN search and increasingly support sparse vectors (BM25-like or learned sparse representations) and hybrid fusion. Vespa goes further, combining BM25, dense retrieval, and multi-phase ranking expressions in one engine. The practical lesson: dense retrieval complements lexical search rather than replacing it, and hybrid is the default for production RAG.
Comparison at a glance
| Engine | Native full-text | BM25? | Best fit |
|---|---|---|---|
| PostgreSQL | tsvector/tsquery | Not native; BM25 via ParadeDB | Transactional apps, small-medium corpora |
| MySQL InnoDB | FULLTEXT | TF-IDF-like | OLTP with light search |
| SQL Server | Full-text catalog | Proprietary rank | .NET / enterprise apps |
| Oracle | Oracle Text | SCORE 0-100 | Enterprise / legal |
| SQLite FTS5 | FTS5 virtual table | Yes, bm25() | Embedded / mobile / edge |
| Elasticsearch | Lucene | Yes, default | Search at scale, logs |
| OpenSearch | Lucene | Yes, default | Search at scale, logs |
| MongoDB Atlas | Lucene | Lucene scoring | App data plus search |
| RediSearch | In-memory index | Yes (SCORER BM25) | Low-latency / caching |
| ClickHouse | Skip indexes | No | Analytics plus filters |
| BigQuery | SEARCH plus indexes | No | Warehouse filtering |
| Snowflake | Cortex Search | Managed hybrid | Warehouse plus RAG |
| Cassandra | Secondary indexes | No | Pair with external search |
7. Scale: what changes with a billion documents
At small scale, ranking quality dominates. At large scale, engineering dominates: index layout, memory, latency, and cost decide what is possible.
Sharding and replication
Documents are partitioned across primary shards, and each shard has replicas for availability and query throughput. The query fans out to all shards, each returns its top k, and a coordinating node merges the results. Replication scales reads; sharding scales corpus size and write throughput.
Local versus global IDF
Because each shard sees only its own documents, term statistics differ. A term that is rare globally can look common on one shard, flipping the ranking. Options include collecting global statistics (dfs_query_then_fetch), routing related documents together, or accepting the drift. The larger the corpus and the more skewed the sharding, the more this matters.
Segments, refreshes, and merges
Lucene-based engines write immutable segments. Indexing creates new segments, a refresh makes them searchable, and merges combine small segments into larger ones while removing deleted documents. Refresh interval is a direct latency-versus-throughput knob. Aggressive refreshes make data visible sooner but create many small segments and more merge work. Merging is background I/O that competes with queries, so bulk loads often use larger refresh intervals and then force a merge.
Postings compression and caching
Postings lists dominate index size. Delta encoding plus variable-byte or PForDelta compresses doc IDs and frequencies well. Roaring bitmaps speed up filter-heavy queries. The operating system page cache does a lot of the real work, which is why search nodes want plenty of RAM relative to the hot index working set. Query caches and filter caches help repeated traffic, not one-off long-tail queries.
Top-k pruning
Ranking every matching document is wasteful when only the top 10 or 100 are shown. Dynamic pruning algorithms such as WAND, Block-Max WAND, and MaxScore use upper bounds on term contributions to skip documents that cannot reach the current top-k threshold. These techniques are essential for long queries and large corpora. Search engines expose them indirectly through top-k and timeout settings; you rarely tune them directly, but you benefit from them constantly.
Deep pagination
Sorting a huge result set and returning page 10,000 is expensive. Many engines cap from + size (Elasticsearch defaults to 10,000). The scalable patterns are search_after with a stable sort, point-in-time snapshots, or cursor-based pagination. Product UIs rarely need deep pagination; they need better ranking so users never go that deep.
Write amplification and index maintenance
Every insert, update, and delete touches multiple structures. Full-text index maintenance can be much heavier than row storage. Bulk indexing, batching, and tuning refresh and translog durability are normal operational levers. Changing analyzers usually requires a full reindex, so treat the analysis configuration as a schema decision, not an afterthought.
Multi-tenancy and cost
Large systems often use one index per tenant or routing by tenant to keep queries local and relevance clean. Tiered storage moves older indices to cheaper hardware or searchable snapshots. The biggest cost lever is usually not the ranking algorithm but how much data you keep hot, how many replicas you run, and how large your shards are.
Latency budgets
A typical interactive search budget is 100-300 ms end to end. That budget is split across query parsing, fan-out, per-shard scoring, merging, reranking, and network. Cross-encoder reranking and LLM calls are usually asynchronous or limited to a small candidate set for this reason. Measure p95 and p99, not averages; tail latency is what users feel.
8. Time and space complexity
Search is fast because it avoids scanning the whole corpus, but the exact cost depends on how many postings a query touches, how many candidates survive pruning, and how much work happens after retrieval. The variables below appear throughout this section:
N= number of documentsV= vocabulary size (distinct terms)T= total number of tokens in the collectionL= average document length in tokensQ= number of terms in the querydf(q)= number of documents containing termqk= number of results returnedd= embedding dimensionC= number of reranking candidatesS= number of shardsF= number of stored fields or per-document statistics
Indexing cost
| Operation | Complexity | Notes |
|---|---|---|
| Analysis (tokenize, normalize, stem) | O(L) time and space | Per document. |
| Build the inverted index | O(T + Σ df log df) | O(T log T) worst case; close to O(T) when postings arrive grouped. |
| Positional index | O(T) positions | Plus per-position overhead. |
| Forward index / doc values | O(N * F) | Only for fields and statistics you store. |
| Dense vectors | O(N * d) | Commonly four bytes per value before quantization. |
Query-time complexity
| Operation | Complexity | Notes |
|---|---|---|
| Boolean AND (intersection) | O(df(p1) + df(p2)) | Linear merge; roughly O(min(df) * log(max(df) / min(df))) with galloping and skip pointers. |
| Boolean OR (union) | O(Σ df) | Sum over every query term. |
| Phrase / proximity | O(Σ df) + O(matches) | Candidate gathering plus positional verification. |
| BM25 scoring | O(Σ df(q)) worst case | Every matching posting may be scored; pruning reduces the practical cost but not the worst case. |
| TF-IDF / sparse cosine | O(Σ df(q)) | Or O(|q| + |d|) if you only visit nonzero entries. |
| Query likelihood | O(Σ df(q)) | Same posting traversal as BM25, with a log and smoothing term per posting. |
| Top-k selection | O(M log k) | O(M) average with quickselect; full sort is O(M log M). |
| Fuzzy / edit distance | O(|a| * |b|) | Levenshtein DP; O(min(|a|, |b|)) space. Bounded automata are roughly O(|q| * branching) per dictionary step. |
| Prefix / wildcard | O(|prefix|) + O(output) | Trie or FST walk plus match enumeration. |
| Dense retrieval (exact) | O(N * d) | Fine for thousands of documents; too slow for millions. |
| Dense retrieval (HNSW) | O(log N) expected | Graph hops per query; O(N * d) vectors plus O(N * M) edges. |
| Dense retrieval (IVF) | O(nprobe * (N / nlist) * d) | nprobe controls the recall-versus-latency trade-off. |
| Cross-encoder reranking | O(C * L^2 * d) per layer | Why C is kept to tens or low hundreds. |
| Learning to rank | O(C * F) | Feature extraction, especially text features, often dominates. |
| Distributed merge | O(S * k log k) | Plus O(S * k) network traffic; deep pagination makes this worse. |
| Hybrid fusion (RRF) | O(R * k log(R * k)) | Or O(R * k) with a heap. |
Space complexity at a glance
| Structure | Approximate space |
|---|---|
| Inverted index (non-positional) | O(T) postings, O(V) dictionary entries |
| Inverted index (positional) | O(T) postings plus one entry per position |
| Forward index / doc values | O(N * F) |
| Dense vectors | O(N * d), reduced by quantization |
| HNSW graph | O(N * M) edges for M links per node |
| Per-segment overhead | O(segments * V) for segment dictionaries |
Rules of thumb
- Query cost scales with the number of postings touched, not with
N. That is the entire point of an inverted index. - Rare terms are cheap; very common terms are expensive. Removing or down-weighting stop words is both a relevance and a performance decision.
- Top-k pruning turns many real queries from "score every match" into "score a small fraction of matches".
- Reranking and LLM calls should run on tens to hundreds of candidates, not thousands.
- ANN indexes trade recall and memory for speed. Measure
recall@kalongside latency, or you may be optimizing the wrong thing.
9. How industries use search
The same primitives recur across very different products. A few patterns are worth calling out.
E-commerce and marketplaces
Product search combines BM25 or BM25F over title, description, brand, and category with business signals: stock, margin, popularity, ratings, and personalization. Query understanding (spell correction, synonyms, unit and size normalization, intent detection) is critical. Facets and filters handle the structured side. Most systems use a fast lexical retriever plus a learning-to-rank or function-score layer for the final order.
Observability and logging
Tools such as Elasticsearch, OpenSearch, Loki, and Splunk are optimized for high ingest and time-bounded queries. Relevance is usually secondary to filters, aggregations, and fast scans. Index-per-day plus lifecycle policies keep costs manageable. BM25 still helps when engineers search free text in logs, but field filters and structured queries do most of the work.
Documentation and enterprise search
Hosted engines such as Algolia, Typesense, and Meilisearch focus on developer experience: typo tolerance, prefix search, faceting, and instant results. Enterprise suites emphasize permissions, connectors, and compliance. BM25-style lexical matching remains the backbone, often with semantic reranking for natural-language questions.
Code search
Code search is its own problem: symbol indexes, trigram indexes for regex and substring matching, and language-aware parsing matter more than BM25. GitHub, Sourcegraph, and similar tools combine structural indexes with text search. BM25 is useful for comments and documentation but is not the primary mechanism for matching identifiers.
RAG and AI assistants
Retrieval-augmented generation depends on retrieval quality. The standard architecture is hybrid: BM25 for exact terms, identifiers, and rare tokens; dense vectors for paraphrase and semantics; reciprocal rank fusion to merge; then a cross-encoder or LLM-based reranker on the top candidates. Chunking strategy, metadata filters, and freshness often matter more than the choice of embedding model. BM25 is the reliable floor that keeps RAG from missing exact matches.
Security and SIEM
Security search is precision-heavy and time-scoped. Boolean logic, indicators of compromise, and exact string matching dominate. Scale comes from event volume, not corpus diversity. Systems favor fast filtering and correlation over sophisticated relevance, though keyword scoring still helps analysts triage.
Legal and e-discovery
Recall and defensibility matter more than speed. Boolean and proximity queries, stemming control, and auditable ranking are important. Oracle Text and specialized e-discovery platforms are common. Explainability is a feature, not a nice-to-have.
10. Tuning and evaluation
Search quality is an empirical discipline. A sensible workflow:
- Build an evaluation set. Collect 50-500 real queries with known relevant documents. Measure Precision@k, Recall@k, MRR, MAP, and nDCG@k. Public benchmarks such as BEIR, MS MARCO, and TREC Deep Learning are useful for sanity checks, but your own traffic is what matters.
- Start with BM25. It is fast, cheap, and a strong zero-shot baseline. BEIR famously showed that BM25 remains competitive across many out-of-domain tasks. Do not skip the baseline; you need it to prove that a more complex system is actually better.
- Tune analysis before parameters. Synonyms, stemming, stop words, language analyzers, and field boosts usually move quality more than small changes to
k1andb. A title boost of 2-3x is a common starting point. - Tune BM25 conservatively.
k1around 1.2 andbaround 0.75 are strong defaults. Lowerbfor short, uniform fields; raise it for long, variable fields. Change one thing at a time and re-measure. - Add semantics with evidence. Add dense retrieval when queries and documents use different vocabulary. Use hybrid fusion rather than replacing lexical search. Add a reranker when the top-k ordering is the bottleneck and latency allows it.
- Evaluate online. Offline metrics do not capture user intent, freshness, or business value. Use click logs, A/B tests, and interleaving. Watch for position bias and feedback loops when training on clicks.
- Monitor production. Track latency percentiles, zero-result rate, click-through rate, and query distribution. Slow logs and query profiling reveal expensive patterns. Search quality regressions are often caused by data and analysis changes rather than ranking code.
11. A practical decision guide
- Need ACID, joins, and moderate search in one system? Use PostgreSQL full-text search, add
pg_trgmfor fuzzy matching, and consider ParadeDBpg_searchif you need true BM25. - Building an embedded, desktop, mobile, or edge app? Use SQLite FTS5. It has real BM25, needs no server, and is extremely reliable.
- Need large-scale relevance, faceting, and log search? Use Elasticsearch or OpenSearch, size shards carefully, and lean on analysis, boosts, and hybrid retrieval.
- Need very low latency over in-memory data? Use RediSearch with BM25 scoring and vector fields.
- Already on MongoDB? Use Atlas Search for Lucene-based relevance and Atlas Vector Search for hybrid retrieval.
- Building RAG? Default to hybrid BM25 plus dense retrieval, fuse with RRF, then rerank the top candidates. Keep BM25 as the exact-match safety net.
- Doing analytics over huge text datasets? Prefilter in ClickHouse or a warehouse, then rank in a dedicated engine if relevance matters.
- Want a managed developer-friendly search experience? Consider Algolia, Typesense, Meilisearch, or a cloud search service.
12. Key takeaways
- The inverted index is the foundation; analysis determines what is even searchable, and ranking determines what wins.
- TF-IDF introduced the right intuitions but over-rewards repetition and handles length crudely.
- BM25 fixes both with term-frequency saturation (
k1) and length normalization (b), and remains the default for good reasons. - Databases increasingly ship full-text search. PostgreSQL, MySQL, SQL Server, Oracle, and SQLite each implement it differently; only some expose true BM25.
- Lucene-based engines remain the reference for relevance at scale, with segment-based indexing, compressed postings, dynamic pruning, and mature distributed features.
- Dense retrieval and hybrid search are now standard for semantic and RAG workloads, but lexical search is still the reliable baseline.
- At scale, sharding, IDF locality, refresh and merge behavior, postings compression, top-k pruning, and cost management matter as much as the scoring formula.
- Measure before optimizing. Start with BM25, build an evaluation set, tune analysis first, and add complexity only when the data proves it helps.
Search has been "solved" many times and keeps being reinvented because the problem keeps growing. BM25 survived that churn not because it is perfect, but because it is a well-understood, efficient, and surprisingly strong foundation. Understanding it, and understanding how your database implements it, is one of the highest-leverage skills in modern application engineering.
References and further reading
- Manning, Raghavan, and Schütze. Introduction to Information Retrieval. Cambridge University Press, 2008.
- Robertson and Zaragoza. The Probabilistic Relevance Framework: BM25 and Beyond. Foundations and Trends in Information Retrieval, 2009.
- Thakur et al. BEIR: A Heterogeneous Benchmark for Zero-shot Evaluation of Information Retrieval Models. NeurIPS 2021. arxiv.org/abs/2104.08663
- Cormack, Clarke, and Buettcher. Reciprocal Rank Fusion Outperforms Condorcet and Individual Rank Learning Methods. SIGIR 2009.
- Broder et al. Efficient Query Evaluation using a Two-Level Retrieval Process. CIKM 2003. (WAND)
- Ding and Suel. Faster Top-k Document Retrieval Using Block-Max Indexes. SIGIR 2011.
- Lucene BM25Similarity documentation: lucene.apache.org/core
- Elasticsearch reference: elastic.co/guide
- PostgreSQL full-text search: postgresql.org/docs/current/textsearch.html
- MySQL full-text search: dev.mysql.com/doc/refman/8.0/en/fulltext-search.html
- SQLite FTS5: sqlite.org/fts5.html
- ParadeDB pg_search: github.com/paradedb/paradedb
- pgvector: github.com/pgvector/pgvector
- Microsoft MS MARCO: microsoft.github.io/msmarco