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:

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:

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:

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:

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:

  1. 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.
  2. 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:

k1 controls saturation.
As f(q, D) grows, the score approaches an asymptote instead of growing without bound. With k1 = 1.2, going from 1 to 2 occurrences adds a lot; going from 10 to 20 adds comparatively little. Smaller k1 saturates sooner, larger k1 rewards repetition more.
b controls length normalization.
b = 0 disables it. b = 1 applies full normalization by |D| / avgdl. b = 0.75 is a strong default. Lower b for short, uniform fields such as titles; higher b for long, variable fields such as articles.

A useful way to read the formula is as a ratio:

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:
tf'(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))
This is why title^3 and body style boosts work in Elasticsearch and why separate field lengths matter.

Why BM25 endures:

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:

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
PostgreSQLtsvector/tsqueryNot native; BM25 via ParadeDBTransactional apps, small-medium corpora
MySQL InnoDBFULLTEXTTF-IDF-likeOLTP with light search
SQL ServerFull-text catalogProprietary rank.NET / enterprise apps
OracleOracle TextSCORE 0-100Enterprise / legal
SQLite FTS5FTS5 virtual tableYes, bm25()Embedded / mobile / edge
ElasticsearchLuceneYes, defaultSearch at scale, logs
OpenSearchLuceneYes, defaultSearch at scale, logs
MongoDB AtlasLuceneLucene scoringApp data plus search
RediSearchIn-memory indexYes (SCORER BM25)Low-latency / caching
ClickHouseSkip indexesNoAnalytics plus filters
BigQuerySEARCH plus indexesNoWarehouse filtering
SnowflakeCortex SearchManaged hybridWarehouse plus RAG
CassandraSecondary indexesNoPair 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:

Indexing cost

Operation Complexity Notes
Analysis (tokenize, normalize, stem)O(L) time and spacePer document.
Build the inverted indexO(T + Σ df log df)O(T log T) worst case; close to O(T) when postings arrive grouped.
Positional indexO(T) positionsPlus per-position overhead.
Forward index / doc valuesO(N * F)Only for fields and statistics you store.
Dense vectorsO(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 / proximityO(Σ df) + O(matches)Candidate gathering plus positional verification.
BM25 scoringO(Σ df(q)) worst caseEvery matching posting may be scored; pruning reduces the practical cost but not the worst case.
TF-IDF / sparse cosineO(Σ df(q))Or O(|q| + |d|) if you only visit nonzero entries.
Query likelihoodO(Σ df(q))Same posting traversal as BM25, with a log and smoothing term per posting.
Top-k selectionO(M log k)O(M) average with quickselect; full sort is O(M log M).
Fuzzy / edit distanceO(|a| * |b|)Levenshtein DP; O(min(|a|, |b|)) space. Bounded automata are roughly O(|q| * branching) per dictionary step.
Prefix / wildcardO(|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) expectedGraph 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 rerankingO(C * L^2 * d) per layerWhy C is kept to tens or low hundreds.
Learning to rankO(C * F)Feature extraction, especially text features, often dominates.
Distributed mergeO(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 valuesO(N * F)
Dense vectorsO(N * d), reduced by quantization
HNSW graphO(N * M) edges for M links per node
Per-segment overheadO(segments * V) for segment dictionaries

Rules of thumb

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:

  1. 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.
  2. 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.
  3. Tune analysis before parameters. Synonyms, stemming, stop words, language analyzers, and field boosts usually move quality more than small changes to k1 and b. A title boost of 2-3x is a common starting point.
  4. Tune BM25 conservatively. k1 around 1.2 and b around 0.75 are strong defaults. Lower b for short, uniform fields; raise it for long, variable fields. Change one thing at a time and re-measure.
  5. 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.
  6. 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.
  7. 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

12. Key takeaways

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

Comment