Build a distributed search engine (Elasticsearch / OpenSearch style) (12 scenes)
Scene 08

BM25 — TF saturation × IDF × length norm

BM25 sums per-term IDF × saturating-TF / length-norm — rare terms outweigh common ones, the 100th match barely beats the 10th, and long docs are penalized.

Previously

Phase 1 of every search asked each shard to RANK its local matches. The function each shard runs is BM25 — and its three constants (k1, b, IDF) decide whose match wins.

Scene 09

BM25 — TF saturation × IDF × length-norm

  1. Watch
  2. Try it
  3. Predict
  4. Capture
QUERYdistributed systemsscore = Σ IDF(q) · tf·(k1+1) / (tf + k1·(1 − b + b·|D|/avgdl))PER-DOC SCORE BREAKDOWN · rankedIDFTF (sat)len-normDistributed Systemsbook-21.81.12.9Designing Data-Intensive …book-31.80.91.8The Cat in the Hatbook-10.0Lucene in Actionbook-40.0The Old Man and the Seabook-50.0TUNABLESk1 (TF saturation)1.20b (length norm)0.75default 1.2 / 0.75N=5 · df(distributed)=2 · df(systems)=2 · avgdl≈62
IDF(distributed) ≈ ln((5 − 2 + 0.5)/(2 + 0.5) + 1) ≈ 0.85
Book 2 wins: short doc (length-norm boost) + both terms in title.
What to watch for

Score the query 'distributed systems' against the five-book catalog. IDF is computed across the corpus (rare terms win); TF saturates so the 100th match barely beats the 10th; length-norm pushes long docs down. Books 1, 4, and 5 don't contain either query term — they sit at score 0.

Implementation

Highlighted lines are the ones running in the diagram right now.

BM25.score
sum per-term: idf x saturating_tf
def score(doc, query):
    s = 0.0
    for term in query.terms:
        tf = doc.term_freq(term)
        if tf == 0: continue
        df = corpus.doc_freq(term)
        s += idf(term, N=corpus.size, df=df)
             * saturating_tf(tf, k1, b,
                 doc_len=doc.length, avgdl=corpus.avgdl)
    return s
BM25.idf
rarity weight — ln((N - df + 0.5)/(df + 0.5) + 1)
def idf(term, N, df):
    return ln((N - df + 0.5) / (df + 0.5) + 1)
BM25.saturating_tf
k1 caps repeats; b scales length penalty
def saturating_tf(tf, k1, b, doc_len, avgdl):
    len_norm = (1 - b) + b * (doc_len / avgdl)
    return tf * (k1 + 1) / (tf + k1 * len_norm)

Where this sits in Build a distributed search engine (Elasticsearch / OpenSearch style)

Scene 08 of 12. BM25 ranks each match by IDF × saturating-TF / length-norm — and the saturation knob k1 is exactly what stops a keyword-stuffed doc from winning the page.

Up next. BM25 needs IDF, and IDF asks 'how many docs in the corpus contain this term?'. Each shard knows only its own corpus — so the same document scores differently depending on where it lives.

All 12 scenes in Build a distributed search engine (Elasticsearch / OpenSearch style) · Every curriculum

Designs that use this

Built with Arqly
Every scene in Build a distributed search engine (Elasticsearch / OpenSearch style) builds on the one before it.All 12 Build a distributed search engine (Elasticsearch / OpenSearch style) scenes