Lab QE2: BM25 and Scoring Internals

Background

The intensive gave you the BM25 formula and a worked numeric example. This lab makes it real three ways. First you use _explain to decompose a live document's score into its idf, tfNorm, dl/avgdl, k1, and b parts and read them off the API. Second you change the similarity — tweak k1/b, then swap to a different similarity entirely — and watch the score move in the direction the math predicts. Third you write a standalone Lucene program that computes BM25 by hand and matches _explain to the last decimal, so the formula stops being a black box. Finally you connect scoring to retrieval speed: Block-Max WAND makes top-k faster without changing the top results, and totalHitsThreshold is where the count (not the ranking) goes approximate.

Why This Matters for Contributors

Relevance bugs are the hardest class of search bug because "wrong" is subjective — until you can decompose a score. A contributor who can run _explain, read every node, and reproduce it offline can say with certainty "the score is correct, your expectation is wrong" or "the idf is off because this shard has skewed stats." That is the difference between a closed issue and a week of back-and-forth. And anyone touching the scoring or skipping code (a new Similarity, a WANDScorer change) must prove top-k is unchanged — this lab is that proof technique.

Prerequisites

• A running OpenSearch 3.x (docker run -p 9200:9200 -e discovery.type=single-node -e DISABLE_SECURITY_PLUGIN=true opensearchproject/opensearch:latest).
• curl, jq, Java 21+ (java -version).
• A Lucene core jar for the standalone program: from an apache/lucene checkout ./gradlew :lucene:core:jar, or from any OpenSearch checkout find ~/.gradle -name 'lucene-core-*.jar' | head.
• You've read the intensive BM25 section and done Lab QE1.

Note: keep number_of_shards: 1. BM25 idf uses per-shard statistics by default, so a single shard makes _explain deterministic and easy to match by hand. With multiple shards you'd need dfs_query_then_fetch (see Search Execution) for global stats.

Step-by-Step Tasks

Step 1 — Build an index with controllable lengths

H='-H content-type:application/json'
curl -s -XDELETE localhost:9200/qe2 >/dev/null
curl -s -XPUT localhost:9200/qe2 $H -d '{
  "settings": { "number_of_shards": 1, "number_of_replicas": 0 },
  "mappings": { "properties": { "body": { "type": "text", "analyzer": "standard" } } }
}' | jq .

# Doc 1: "opensearch" appears 3x in a short field.
# Doc 2: "opensearch" once in a long field (more non-matching words -> longer dl).
# Docs 3..: filler that does NOT contain "opensearch" (pads N but not n).
curl -s -XPOST 'localhost:9200/qe2/_bulk?refresh=true' $H --data-binary '
{"index":{"_id":1}}
{"body":"opensearch opensearch opensearch fast"}
{"index":{"_id":2}}
{"body":"opensearch is a distributed search and analytics suite built on lucene with many features and modules"}
{"index":{"_id":3}}
{"body":"completely unrelated filler text about gardening"}
{"index":{"_id":4}}
{"body":"more filler about cooking and recipes"}
' | jq '.errors'

Step 2 — Decompose a score with _explain

curl -s 'localhost:9200/qe2/_explain/1?pretty' $H -d '{
  "query": { "match": { "body": "opensearch" } }
}' | jq '.explanation'

The explanation is a tree. Find these nodes (descriptions vary slightly by version — read the description strings):

# Pull the raw inputs straight out of the explanation:
curl -s 'localhost:9200/qe2/_explain/1' $H -d '{"query":{"match":{"body":"opensearch"}}}' \
  | jq '[.. | objects | select(has("description")) | {d:.description, v:.value}]'

Note that doc 1 (tf=3, short dl) scores higher than doc 2 (tf=1, long dl) — both effects (more term frequency, shorter field) push the score up, exactly as the formula says. Run _explain/2 and compare.

Step 3 — Change k1/b and watch the score move

k1 and b are index settings on the BM25 similarity. Reconfigure and re-explain. (Changing similarity params requires closing/reopening the index.)

curl -s -XPOST localhost:9200/qe2/_close >/dev/null
curl -s -XPUT localhost:9200/qe2/_settings $H -d '{
  "index": { "similarity": { "default": {
    "type": "BM25", "k1": 0.5, "b": 0.0
  }}}
}' | jq .
curl -s -XPOST localhost:9200/qe2/_open >/dev/null
sleep 1

curl -s 'localhost:9200/qe2/_explain/1' $H -d '{"query":{"match":{"body":"opensearch"}}}' \
  | jq '.explanation.value'

Predict before you run:

• b = 0.0 removes length normalization entirely (1 - b + b*dl/avgdl = 1), so doc 1's length advantage over doc 2 disappears — only tf separates them.
• k1 = 0.5 saturates faster, so doc 1's tf=3 advantage shrinks versus the default k1=1.2.

Re-explain doc 2 and confirm docs 1 and 2 are now closer than in Step 2.

Step 4 — Swap to a different similarity

curl -s -XPOST localhost:9200/qe2/_close >/dev/null
curl -s -XPUT localhost:9200/qe2/_settings $H -d '{
  "index": { "similarity": { "default": {
    "type": "boolean"
  }}}
}' | jq .
curl -s -XPOST localhost:9200/qe2/_open >/dev/null
sleep 1

curl -s 'localhost:9200/qe2/_search?pretty' $H -d '{"query":{"match":{"body":"opensearch"}}}' \
  | jq '.hits.hits[] | {id:._id, score:._score}'

The boolean similarity ignores tf and idf entirely — every match gets the query boost (1.0), so docs 1 and 2 tie. This is the cleanest demonstration that BM25's score is the tf/idf/length math: remove it and ranking collapses to membership. Restore BM25 before continuing:

curl -s -XPOST localhost:9200/qe2/_close >/dev/null
curl -s -XPUT localhost:9200/qe2/_settings $H -d '{
  "index": { "similarity": { "default": { "type": "BM25", "k1": 1.2, "b": 0.75 } } } }' >/dev/null
curl -s -XPOST localhost:9200/qe2/_open >/dev/null

Step 5 — Compute BM25 by hand in standalone Lucene

This is the payoff: a tiny program that indexes the same docs, runs the same query, prints the score, and prints your hand-rolled BM25 from the raw stats — they must match.

// Bm25ByHand.java
import org.apache.lucene.analysis.standard.StandardAnalyzer;
import org.apache.lucene.document.*;
import org.apache.lucene.index.*;
import org.apache.lucene.search.*;
import org.apache.lucene.search.similarities.BM25Similarity;
import org.apache.lucene.store.*;
import org.apache.lucene.util.BytesRef;

public class Bm25ByHand {
  static final float k1 = 1.2f, b = 0.75f;

  public static void main(String[] args) throws Exception {
    Directory dir = new ByteBuffersDirectory();
    IndexWriterConfig cfg = new IndexWriterConfig(new StandardAnalyzer())
        .setSimilarity(new BM25Similarity(k1, b));
    try (IndexWriter w = new IndexWriter(dir, cfg)) {
      add(w, "opensearch opensearch opensearch fast");                       // doc 0
      add(w, "opensearch is a distributed search and analytics suite built on lucene with many features and modules"); // 1
      add(w, "completely unrelated filler text about gardening");            // 2
      add(w, "more filler about cooking and recipes");                       // 3
    }

    try (DirectoryReader r = DirectoryReader.open(dir)) {
      IndexSearcher s = new IndexSearcher(r);
      s.setSimilarity(new BM25Similarity(k1, b));
      Term t = new Term("body", "opensearch");
      Query q = new TermQuery(t);

      // ---- stats we need for BM25 ----
      int N = r.getDocCount("body");                  // docs having the field
      int n = r.docFreq(t);                           // docs containing the term
      long sumDl = r.getSumTotalTermFreq("body");     // total tokens in field
      double avgdl = (double) sumDl / N;

      TopDocs top = s.search(q, 10);
      System.out.printf("N=%d n=%d avgdl=%.4f%n", N, n, avgdl);
      double idf = Math.log(1 + (N - n + 0.5) / (n + 0.5));
      System.out.printf("idf = %.6f%n", idf);

      for (ScoreDoc sd : top.scoreDocs) {
        // per-doc tf and length
        LeafReaderContext leaf = r.leaves().get(
            ReaderUtil.subIndex(sd.doc, r.leaves()));
        int localDoc = sd.doc - leaf.docBase;
        PostingsEnum pe = leaf.reader().postings(t, PostingsEnum.FREQS);
        pe.advance(localDoc);
        int tf = pe.freq();
        // field length (dl) = number of tokens in this doc's "body"
        long dl = leaf.reader().getNormValues("body") != null
            ? decodeLen(leaf, localDoc) : tf;

        double denom = tf + k1 * (1 - b + b * dl / avgdl);
        double tfNorm = (tf * (k1 + 1)) / denom;
        double byHand = idf * tfNorm;

        System.out.printf(
          "doc=%d  lucene=%.6f  byHand=%.6f  (tf=%d dl=%d tfNorm=%.6f)%n",
          sd.doc, sd.score, byHand, tf, dl, tfNorm);
      }
    }
  }

  // Lucene stores field length lossily in norms; decode the same way BM25 reads it.
  static long decodeLen(LeafReaderContext leaf, int doc) throws Exception {
    NumericDocValues norms = leaf.reader().getNormValues("body");
    norms.advance(doc);
    return SmallFloat.byte4ToInt((byte) norms.longValue()); // approx; see note
  }

  static void add(IndexWriter w, String body) throws Exception {
    Document d = new Document();
    FieldType ft = new FieldType(TextField.TYPE_NOT_STORED);
    d.add(new Field("body", body, ft));
    w.addDocument(d);
  }
}

LUCENE=$(find ~/.gradle -name 'lucene-core-*.jar' | head -1)
ANALYZ=$(find ~/.gradle -name 'lucene-analysis-common-*.jar' | head -1)
CP="$LUCENE:$ANALYZ"
javac -cp "$CP" Bm25ByHand.java
java  -cp ".:$CP" Bm25ByHand

Note: Lucene encodes field length (dl) lossily into a single norm byte via SmallFloat, so your hand-decoded dl is the same approximation BM25 uses — that's why they match. If your byHand is off by a hair, you decoded the norm with the wrong helper; grep BM25Similarity for LENGTH_TABLE / decodeNorm and mirror it exactly: grep -n "LENGTH_TABLE\|decodeNorm\|SmallFloat" lucene/core/src/java/org/apache/lucene/search/similarities/BM25Similarity.java

Step 6 — Top-k skipping keeps results identical; counts go approximate

Block-Max WAND speeds up top-k without changing the top-k. Demonstrate the two distinct effects.

# (a) The TOP results are stable regardless of totalHitsThreshold.
for THR in 1 10000; do
  echo "track_total_hits=$THR"
  curl -s "localhost:9200/qe2/_search?pretty" $H -d "{
    \"track_total_hits\": $THR, \"size\": 2,
    \"query\": { \"match\": { \"body\": \"opensearch\" } }
  }" | jq '{total: .hits.total, ids: [.hits.hits[]._id], scores: [.hits.hits[]._score]}'
done

• With track_total_hits: 1, OpenSearch stops counting once it has more than 1 match and reports {"value":1,"relation":"gte"} — the count is approximate.
• The ids and scores of the returned top-2 are identical across both runs. That is the Block-Max WAND contract: the ranking is exact, only the total count can be early-terminated.

# (b) Profile shows the skipping machinery doing work:
curl -s 'localhost:9200/qe2/_search' $H -d '{
  "profile": true, "size": 1, "track_total_hits": 10,
  "query": { "match": { "body": "opensearch" } }
}' | jq '.profile.shards[0].searches[0].query[0].breakdown
         | {set_min_competitive_score, advance, next_doc}'

A non-zero set_min_competitive_score is the collector pushing the rising threshold θ down to the scorer — the trigger for skipping non-competitive blocks. On this tiny corpus the savings are negligible; the mechanism is the point. Tie back to the WAND/MaxScore/BMW table in the intensive.

Deliverables

• The _explain/1 tree with idf, tfNorm, dl, avgdl, k1, b identified, and the hand-computed product matching _explain's value.
• Before/after scores for the k1=0.5,b=0.0 change and the boolean similarity, each with a one-sentence prediction that came true.
• Bm25ByHand.java output showing lucene == byHand for every returned doc.
• The track_total_hits 1-vs-10000 comparison showing identical top-k ids and scores but a different hits.total.relation.

Expected Output

# Bm25ByHand (default k1=1.2 b=0.75)
N=4 n=2 avgdl=...
idf = 0.470004
doc=0  lucene=0.601...  byHand=0.601...  (tf=3 dl=4 tfNorm=1.279...)
doc=1  lucene=0.215...  byHand=0.215...  (tf=1 dl=16 tfNorm=0.458...)

# Step 6a
track_total_hits=1
{ "total": {"value":1,"relation":"gte"}, "ids":["1","2"], "scores":[0.60,0.21] }
track_total_hits=10000
{ "total": {"value":2,"relation":"eq"},  "ids":["1","2"], "scores":[0.60,0.21] }

(Exact values depend on Lucene version and norm encoding — the equality lucene == byHand and the stability of ids/scores are what matter.)

Troubleshooting

Stretch Goals

• Match _explain to Bm25ByHand exactly. Read the same doc's stats from both and assert equality to 6 decimals; if off, you've found the norm-decode subtlety — fix it and document it.
• Per-field similarity. Map two fields with different similarity (one BM25, one boolean) and show a query scoring them differently in one _explain.
• DFS the idf. Add a second shard, show scores drift, then add dfs_query_then_fetch and show them converge — connect to Search Execution.
• Force a visible BMW win. Index ~1M docs with one rare term + one common term in a should disjunction, size:10, and compare took/profile with track_total_hits:true vs default — quantify the skipping.

Coding Exercises

You decomposed scores by eye and reproduced one in a throwaway program. These exercises make the assertions permanent — JUnit/integration tests and a hardened standalone — so a future scoring change can't silently move ranking. Locate similarity classes with rg (rg -l "class BM25Similarity" ; rg -l "SimilarityTests|class.*ScoringIT" server/).

1. (warm-up) Assert the BM25 ranking on a cluster. Write an OpenSearchIntegTestCase that indexes the four qe2 docs, runs match(body: opensearch), and asserts doc 1 (tf=3, short) scores strictly higher than doc 2 (tf=1, long). A assertThat(score1, greaterThan(score2)) encodes the Step 2 observation as a regression test.

2. (core) Turn Bm25ByHand into a graded test. Convert the Step 5 program into a JUnit test (no cluster) that, for every returned doc, asserts Math.abs(luceneScore - byHand) < 1e-5. Mirror Lucene's lossy norm decode exactly (rg -n "LENGTH_TABLE|decodeNorm|SmallFloat" $(rg -l "class BM25Similarity")) so the equality holds to 5–6 decimals. This is the "match _explain exactly" stretch goal, now graded and runnable.

3. (core) Assert the direction of a k1/b change. Write a test that scores the corpus under default BM25 and under k1=0.5, b=0.0, and asserts doc 1 and doc 2 are closer together with b=0.0 (length normalization removed) — a assertThat(gapAfter, lessThan(gapBefore)). This makes the Step 3 prediction an executable claim about the math, not a hand-wave.

4. (core) A custom Similarity smoke test. Implement a trivial Similarity subclass (e.g. constant-score, or BM25 with a fixed tf cap) and write a test that wires it on a field and asserts the score behaves as designed — proving you can extend the scoring SPI, not just read it. Find the extension point with rg -n "class .*Similarity extends|SimilarityProvider" server/.../index/similarity/.

5. (advanced) Advanced challenge — prove Block-Max WAND keeps top-k exact. Build an OpenSearchIntegTestCase (or a standalone Lucene program) that indexes a larger corpus with one rare and one common term in a should disjunction, runs the query with track_total_hits: 1 and with track_total_hits: true, and asserts: (a) the returned ids and _scores of the top-k are identical across both, while (b) hits.total.relation differs (gte vs eq). Then capture profile set_min_competitive_score to show the skipping fired. This is the exact proof technique any WANDScorer/Similarity PR must supply: ranking unchanged, only the count went approximate. Deliverable: one test asserting top-k stability under early termination, cross-linked to the WAND/MaxScore/BMW table in the intensive.

Issues to Practice On

Score-decomposition is the skill that closes relevance tickets. Practice on opensearch-project/OpenSearch; the BM25/skipping internals also live in apache/lucene, so check both.

Labels drift; confirm with gh label list --repo opensearch-project/OpenSearch (look for Search:Relevance, Search).

Representative patterns. (1) "Scores differ across shards / look wrong." — usually per-shard idf; reproduce with _explain, confirm N/n per shard, and note whether dfs_query_then_fetch is needed. (2) "New similarity / scoring tweak changed unrelated rankings." — reproduce with a fixed corpus, decompose with _explain + a hand computation, and supply a top-k-stability test. Approach: reproduce → locate via rg → fix → test → PR with CHANGELOG + DCO.

Planted-bug drill. In your Bm25ByHand (or a copied BM25Similarity test subclass), drop the (k1 + 1) factor from the tfNorm numerator. Run your Step-5 equality test: byHand now diverges from Lucene — watch the assertion go red and read how far off it is for tf=3 vs tf=1 (the error grows with tf). Revert, then add an assertion comparing byHand to _explain's tfNorm node value directly, so any future formula drift is caught at the tfNorm level, not just the final product.

Etiquette: claim the issue first, reproduce before fixing, and every PR needs a test + CHANGELOG entry + DCO Signed-off-by (git commit -s). See community interaction and the prepare-a-PR lab.

Validation / Self-check

• You can read any _explain BM25 tree and name every node (idf, tfNorm, dl, avgdl, k1, b, boost, product).
• You can predict the direction a score moves when you change k1, b, or the similarity, and confirm it on the cluster.
• Your standalone program reproduces Lucene's score, and you can explain the lossy norm encoding that makes dl an approximation both sides share.
• You can state precisely what Block-Max WAND keeps exact (the top-k ranking) and what totalHitsThreshold makes approximate (the hit count).

Next: Lab QE3 — Query Cache and Optimization.