Lab LD2: Postings and BKD Trees

Background

This lab makes two on-disk structures concrete. Part (a) is the postings format: you index text, walk a term's PostingsEnum to read doc-ids, freqs, and positions in code, and then find the ForUtil/PForUtil decode sites that turn the 128-int FOR blocks on disk into the integers you iterated. Part (b) is the BKD tree: you index IntPoint/LongPoint values, run a range query, and use PointValues.intersect plus CheckIndex to observe the leaf structure (maxPointsInLeafNode, the prefix-compressed leaves).

You already met both at the concept level — postings in Inverted Index, BKD in Points and BKD Trees, and the byte formats in the masterclass index. Now you observe them running.

Why This Matters for Contributors

Postings iteration and BKD intersection are the retrieval primitives under almost every query: a match is postings, a range/date filter is BKD, and a numeric aggregation often reads BKD or DocValues. A contributor who can drive a PostingsEnum and a BKD intersect by hand can read a slow-query profile, reason about why a conjunction is or isn't fast (skip lists), and understand why a range over a high-cardinality field touches more leaves. These are the two structures you will profile most often in the search execution path.

Prerequisites

• JDK 17+ and a lucene-core-*.jar (+ lucene-analysis-common-*.jar for the analyzer). See Lab LD1 Prerequisites for how to find them; set export LUCENE_CP=... (include both jars).
• Read index.md (postings and BKD sections).

export LUCENE_CP="/path/to/lucene-core-9.x.x.jar:/path/to/lucene-analysis-common-9.x.x.jar"
# Have a Lucene source dir handy for the grep steps (optional but recommended):
export LUCENE_SRC="/path/to/lucene/lucene/core/src/java/org/apache/lucene"

Part (a): Postings

Step 1 — Index text with positions and walk a PostingsEnum

Postings.java indexes a few sentences and walks the PostingsEnum for one term, printing docs / freqs / positions.

import org.apache.lucene.analysis.standard.StandardAnalyzer;
import org.apache.lucene.document.*;
import org.apache.lucene.index.*;
import org.apache.lucene.store.*;
import org.apache.lucene.util.BytesRef;
import java.nio.file.*;

public class Postings {
  public static void main(String[] args) throws Exception {
    Path dir = Paths.get("ld2-postings");
    try (Directory d = FSDirectory.open(dir)) {
      IndexWriterConfig cfg = new IndexWriterConfig(new StandardAnalyzer());
      cfg.setUseCompoundFile(false);
      try (IndexWriter w = new IndexWriter(d, cfg)) {
        String[] docs = {
          "the quick brown fox jumps",
          "the lazy brown dog sleeps",
          "a quick brown fox is quick"   // 'quick' twice -> freq 2
        };
        for (String s : docs) {
          Document doc = new Document();
          // TextField default IndexOptions = DOCS_AND_FREQS_AND_POSITIONS -> writes .pos
          doc.add(new TextField("body", s, Field.Store.NO));
          w.addDocument(doc);
        }
        w.commit();
      }

      try (DirectoryReader r = DirectoryReader.open(d)) {
        for (LeafReaderContext ctx : r.leaves()) {
          Terms terms = ctx.reader().terms("body");
          if (terms == null) continue;
          TermsEnum te = terms.iterator();
          if (!te.seekExact(new BytesRef("quick"))) continue;

          System.out.println("term 'quick': docFreq=" + te.docFreq()
              + " totalTermFreq=" + te.totalTermFreq());
          // Ask for positions (implies freqs).
          PostingsEnum pe = te.postings(null, PostingsEnum.POSITIONS);
          int docID;
          while ((docID = pe.nextDoc()) != PostingsEnum.NO_MORE_DOCS) {
            int freq = pe.freq();
            StringBuilder pos = new StringBuilder();
            for (int i = 0; i < freq; i++) pos.append(pe.nextPosition()).append(' ');
            System.out.printf("  doc %d freq %d positions [%s]%n", docID, freq, pos.toString().trim());
          }

          // Demonstrate advance() / skip behaviour on a common term.
          PostingsEnum pe2 = te.postings(null, PostingsEnum.FREQS);
          int landed = pe2.advance(2);   // jump straight to doc >= 2
          System.out.println("advance(2) landed on doc " + landed
              + " (this is where the skip list helps on big lists)");
        }
      }
    }
  }
}

javac -cp "$LUCENE_CP" Postings.java
java  -cp "$LUCENE_CP:." Postings
ls -la ld2-postings/    # _0.doc _0.pos _0.tim _0.tip ...

Expected:

term 'quick': docFreq=2 totalTermFreq=3
  doc 0 freq 1 positions [1]
  doc 2 freq 2 positions [1 5]
advance(2) landed on doc 2 (this is where the skip list helps on big lists)

quick is in docs 0 and 2 (docFreq=2), appears 3 times total (totalTermFreq=3), and in doc 2 it's at positions 1 and 5 (a *quick* brown fox is *quick*). Doc-ids came back as gaps on disk (0, then +2) — the PostingsEnum decoded them for you.

Step 2 — See the FOR / PForDelta block decode

Fewer than 128 postings are written as vInts; to see the 128-int FOR blocks you need a term with many docs. But the decode site is the same code path. Find it:

# The fixed block size (128) and the postings format:
grep -rn "BLOCK_SIZE" "$LUCENE_SRC/codecs/lucene99/ForUtil.java" 2>/dev/null \
  || grep -rn "BLOCK_SIZE\s*=\s*128" "$LUCENE_SRC/codecs/"
grep -rln "class Lucene99PostingsFormat" "$LUCENE_SRC/codecs/"

# ForUtil: per-bit-width decode routines (decode1..decode32) — the FOR unpack:
grep -n "void decode\|void encode\|expandMask\|shiftLongs" "$LUCENE_SRC/codecs/lucene99/ForUtil.java" | head

# PForUtil: the exceptions/patches that make it PForDelta, not plain FOR:
grep -n "exception\|patch\|numExceptions\|class PForUtil" "$LUCENE_SRC/codecs/lucene99/PForUtil.java" | head

# Where a block of doc deltas is read during iteration:
grep -rn "refillDocs\|decodeDocDeltas\|forDeltaUtil\|readVInt" \
  "$LUCENE_SRC/codecs/lucene99/Lucene99PostingsReader.java" | head

Read the comment at the top of ForUtil.java: it explains the FOR scheme (pick the max bit width for a block, pack 128 values at that width). Then read PForUtil's exception handling — that is the "patched" part: most values share a small width; the rare outliers are stored as patches so one big value doesn't blow up the block.

Step 3 — Force a real 128-int block (stretch into reality)

Index 1000 docs all containing the term common, then inspect .doc size and run CheckIndex to confirm the postings test passes over packed blocks.

// Add to a variant program: index 1000 docs each with "common token", then:
//   docFreq for 'common' == 1000 -> ~8 full FOR blocks (1000 / 128) + a vInt tail.

# After building such an index:
du -h ld2-postings-big/_0.doc
cp -r ld2-postings-big ld2-big-copy
java -cp "$LUCENE_CP" org.apache.lucene.index.CheckIndex ld2-big-copy -verbose 2>&1 \
  | grep -i "test: terms, freq\|postings\|OK"

The postings test walking those blocks is exactly the ForUtil.decode path you grepped. With 1000 docs the .doc file is far smaller than 1000 × 4 bytes because the deltas (all +1 here) pack into ~1 bit each.

Part (b): BKD Trees

Step 4 — Index points and run a range query

Bkd.java indexes IntPoint and LongPoint values and runs a range query.

import org.apache.lucene.document.*;
import org.apache.lucene.index.*;
import org.apache.lucene.search.*;
import org.apache.lucene.store.*;
import java.nio.file.*;

public class Bkd {
  public static void main(String[] args) throws Exception {
    Path dir = Paths.get("ld2-bkd");
    try (Directory d = FSDirectory.open(dir)) {
      IndexWriterConfig cfg = new IndexWriterConfig();   // no analyzer needed for points
      cfg.setUseCompoundFile(false);
      try (IndexWriter w = new IndexWriter(d, cfg)) {
        for (int i = 0; i < 2000; i++) {
          Document doc = new Document();
          doc.add(new IntPoint("age", i % 100));               // 1-dim int point
          doc.add(new LongPoint("ts", 1_700_000_000L + i*60L)); // 1-dim long point (seconds)
          doc.add(new StoredField("id", i));
          w.addDocument(doc);
        }
        w.commit();   // BKDWriter builds the tree at flush
      }

      try (DirectoryReader r = DirectoryReader.open(d)) {
        IndexSearcher s = new IndexSearcher(r);
        Query q = IntPoint.newRangeQuery("age", 40, 49);   // inclusive range
        TopDocs hits = s.search(q, 5);
        System.out.println("age in [40,49] -> totalHits=" + hits.totalHits);

        // Per-segment BKD metadata via PointValues:
        for (LeafReaderContext ctx : r.leaves()) {
          PointValues pv = ctx.reader().getPointValues("age");
          if (pv == null) continue;
          System.out.println("BKD 'age': numDims=" + pv.getNumDimensions()
              + " bytesPerDim=" + pv.getBytesPerDimension()
              + " size=" + pv.size()
              + " docCount=" + pv.getDocCount());
          System.out.println("  min=" + IntPoint.decodeDimension(pv.getMinPackedValue(), 0)
              + " max=" + IntPoint.decodeDimension(pv.getMaxPackedValue(), 0));
        }
      }
    }
  }
}

javac -cp "$LUCENE_CP" Bkd.java
java  -cp "$LUCENE_CP:." Bkd
ls -la ld2-bkd/    # _0.kdd _0.kdi _0.kdm

Expected:

age in [40,49] -> totalHits=200
BKD 'age': numDims=1 bytesPerDim=4 size=2000 docCount=2000
  min=0 max=99

age = i % 100 over 2000 docs gives 20 docs per value, so [40,49] = 10 values × 20 = 200 hits. size=2000 (one point per doc), min/max = 0/99. The .kdd/.kdi/ .kdm files appeared.

Step 5 — Walk the tree with a custom IntersectVisitor

This is the heart of BKD querying: intersect walks the tree and your visitor's compare(minPacked, maxPacked) decides prune / collect-all / recurse per node. Add to Bkd.java:

import org.apache.lucene.index.PointValues.IntersectVisitor;
import org.apache.lucene.index.PointValues.Relation;

// Count how the tree relates to the query box [40,49], and how many leaves we touch.
final int[] inside = {0}, crosses = {0}, outside = {0}, pointsChecked = {0};
final byte[] lo = new byte[4], hi = new byte[4];
IntPoint.encodeDimension(40, lo, 0);
IntPoint.encodeDimension(49, hi, 0);

for (LeafReaderContext ctx : r.leaves()) {
  PointValues pv = ctx.reader().getPointValues("age");
  if (pv == null) continue;
  pv.intersect(new IntersectVisitor() {
    public void visit(int docID) { /* whole leaf inside -> collected without per-point check */ }
    public void visit(int docID, byte[] packed) {
      pointsChecked[0]++;   // CELL_CROSSES leaf: per-point check happens here
    }
    public Relation compare(byte[] minPacked, byte[] maxPacked) {
      int nodeMin = IntPoint.decodeDimension(minPacked, 0);
      int nodeMax = IntPoint.decodeDimension(maxPacked, 0);
      if (nodeMax < 40 || nodeMin > 49) { outside[0]++;  return Relation.CELL_OUTSIDE_QUERY; }
      if (nodeMin >= 40 && nodeMax <= 49) { inside[0]++; return Relation.CELL_INSIDE_QUERY; }
      crosses[0]++; return Relation.CELL_CROSSES_QUERY;
    }
  });
}
System.out.printf("nodes inside=%d crosses=%d outside=%d ; per-point checks=%d%n",
    inside[0], crosses[0], outside[0], pointsChecked[0]);

Run it. You will see most subtrees pruned as OUTSIDE, a few CROSSES near the range boundary (where per-point checks happen), and possibly some fully INSIDE leaves collected wholesale. That asymmetry — pruning whole subtrees by bounding box — is why a range query is much cheaper than a scan.

Step 6 — Read the BKD leaf structure with CheckIndex

cp -r ld2-bkd ld2-bkd-copy
java -cp "$LUCENE_CP" org.apache.lucene.index.CheckIndex ld2-bkd-copy -verbose 2>&1 \
  | grep -iA3 "test: points\|kdd\|leaf\|maxPointsInLeafNode\|numLeaves"

# Confirm the default leaf size in source:
grep -rn "DEFAULT_MAX_POINTS_IN_LEAF_NODE\|maxPointsInLeafNode" \
  "$LUCENE_SRC/util/bkd/BKDWriter.java" | head
# The split-on-widest-dim and median partition logic:
grep -n "split\|widest\|partition\|computePackedValueBounds" "$LUCENE_SRC/util/bkd/BKDWriter.java" | head

With 2000 points and a default maxPointsInLeafNode = 512, expect ~4 leaves and a shallow tree (depth ≈ ceil(log2(2000/512)) ≈ 2). The CheckIndex points test reports the per-field point count and validates every leaf block's checksum.

flowchart TD
    Q["IntPoint.newRangeQuery('age',40,49)"] --> Int["PointValues.intersect(visitor)"]
    Int --> Cmp["per node: compare(minPacked,maxPacked)"]
    Cmp -->|OUTSIDE| Prune["prune subtree (no decode)"]
    Cmp -->|INSIDE| All["visit(docID) for every leaf doc"]
    Cmp -->|CROSSES| Rec["recurse; at leaf, visit(docID,packed) per point"]
    All --> Hits["collected doc-ids"]
    Rec --> Hits

Deliverables

• Postings.java — walks PostingsEnum for a term, printing docs/freqs/ positions; demonstrates advance.
• A grep capture locating ForUtil.decode / PForUtil and BLOCK_SIZE = 128.
• (Optional) a 1000-doc index showing FOR blocks + CheckIndex postings test.
• Bkd.java — indexes IntPoint/LongPoint, runs a range query, prints PointValues metadata, and walks the tree with an IntersectVisitor counting inside/crosses/outside nodes.
• A CheckIndex -verbose capture of the points test + the maxPointsInLeafNode source line.

Troubleshooting

Expected Output

A PostingsEnum walk that matches the hand-computed docs/freqs/positions for quick; a located ForUtil/PForUtil decode path; a range query returning the exact arithmetic count (200); and an IntersectVisitor trace showing the tree pruning whole subtrees — proof you understand both retrieval primitives at the byte level.

Stretch Goals

• Skip-list payoff. Index 1M docs with a common term and a rare term; run a conjunction and a single-term query; compare timings. The rare term drives iteration; advance on the common term skips via the embedded skip list.
• Multi-dim BKD. Index 2-D points (IntPoint(x, y)); run a box query; watch the split alternate between dimensions (widest range each time).
• GeoPoint. Index LatLonPoint and run LatLonPoint.newBoxQuery; the same BKD machinery indexes encoded lat/lon. Observe .kdd size vs cardinality.
• Leaf size tuning. Rebuild with a custom maxPointsInLeafNode via a custom PointsFormat; observe .kdd/.kdi size and query cost trade-off.

Coding Exercises

These exercises turn the two retrieval primitives into graded code. Each is a standalone Java program or JUnit test compiled against the Lucene jars on $LUCENE_CP — no Gradle. Build on Postings.java and Bkd.java.

1. (warm-up) Assert the postings walk in a test. Wrap Step 1 in a JUnit test PostingsWalkTest that indexes the three docs and asserts quick has docFreq==2, totalTermFreq==3, and positions [1,5] in doc 2 (collect them into a List<Integer> and assertEquals). Then assert advance(2) lands exactly on doc 2. Green test = you can drive a PostingsEnum deterministically.

2. (warm-up) Hand-decode a delta gap. Write DeltaCheck that indexes a term into docs {0, 5, 9}, walks its PostingsEnum, and prints both the absolute doc-ids and the gaps (cur - prev). Assert the gaps are {0, 5, 4} — the values actually stored on disk before ForUtil packs them. This makes "doc-ids are stored as deltas" concrete in code.

3. (core) Force and verify a real 128-int FOR block. Finish the Step-3 sketch: write BigPostings that indexes 1000 docs each containing common, then asserts te.docFreq()==1000. Run CheckIndex on a copy and capture the terms/postings test as OK. Confirm the .doc file is far smaller than 1000×4 bytes (du -b), and in a comment cite the BLOCK_SIZE = 128 line you grepped in ForUtil.java. This exercises the exact ForUtil.decode path on packed blocks, not vInts.

4. (core) Count BKD leaves your visitor touched. Turn the Step-5 IntersectVisitor into a JUnit test BkdPruneTest that asserts, for age in [40,49] over the 2000 docs, that outside > 0 (whole subtrees pruned), and that inside*512 + pointsChecked >= 200 accounts for all hits. Then change the range to [0,99] (everything) and assert outside == 0. You are proving the bounding-box pruning arithmetic, not eyeballing it.

5. (core) Multi-dimension split observation. Index 2-D IntPoint("xy", x, y), run a box query, and in an IntersectVisitor decode both dimensions from minPacked/maxPacked. Assert that as you descend, the split alternates toward the widest dimension (track which dim's range shrank between a node and its child). Locate the split logic first: grep -n "split\|widestDimension\|partition" "$LUCENE_SRC/util/bkd/BKDWriter.java".

6. (advanced) Advanced challenge — a conjunction skip-list benchmark. Build SkipBench: index 1,000,000 docs where a rare term appears in ~100 docs and a common term in ~900,000. Time three queries with a warmed JIT and best-of-N: (a) common alone, (b) rare alone, (c) the rare AND common conjunction via BooleanQuery (MUST + MUST). Assert the conjunction's per-hit cost is closer to rare than common — the rare term drives iteration while advance() on common skips via the embedded skip list. Locate the skipper: grep -rn "Lucene90SkipReader\|skipper\|advanceShallow\|BlockImpactsEnum" "$LUCENE_SRC/codecs/". Deliverable: a printed table of ns/hit for the three runs plus a one-paragraph explanation tied to the class you found.

Issues to Practice On

Postings and BKD live in apache/lucene (Apache workflow: GitHub issues + PRs, a CHANGES.txt entry per change, ./gradlew check — no DCO sign-off). Find work with:

gh label list --repo apache/lucene | grep -iE "good first|core/|new feature"   # confirm the real taxonomy (labels move; check the tracker)
gh issue list --repo apache/lucene --label "good first issue" --state open
gh issue list --repo apache/lucene --search "postings OR ForUtil OR PForUtil in:title,body" --state open
gh issue list --repo apache/lucene --search "BKD OR points OR IntersectVisitor in:title,body" --state open

Representative issue patterns:

• Postings codec correctness/perf. "Skip data wrong on a boundary," "block decode off-by-one on the vInt tail." Approach: reproduce with a hand-built index, locate the read site (rg "refillDocs\|decodeDocDeltas\|Lucene99PostingsReader"), add a failing test over the boundary, fix, keep the test in CHANGES.txt.
• BKD leaf/range bugs or tuning. "Range query over-counts at the boundary," or a proposal to change DEFAULT_MAX_POINTS_IN_LEAF_NODE. Approach: write a test that asserts the exact hit count for a boundary range, locate BKDWriter/BKDReader via rg, and benchmark before/after.

Planted-bug drill. In a copy of your Bkd.java IntersectVisitor, flip the prune condition from nodeMax < 40 || nodeMin > 49 to nodeMax < 40 && nodeMin > 49 (||→&&). Re-run: nothing gets pruned as OUTSIDE, your outside counter drops to 0, and pointsChecked explodes (every point is now visited). Watch your BkdPruneTest (exercise 4) go red on the outside > 0 assertion, then fix it back and note that the assertion caught a correctness-and-performance regression at once.

Etiquette: claim the issue first, reproduce before coding, every Lucene PR needs a test + a CHANGES.txt entry (no DCO on Apache projects). See community-interaction.md.

Validation: prove you understand this

1. From your Postings run, explain quick's docFreq=2, totalTermFreq=3, and the positions [1, 5] in doc 2.
2. Describe FOR vs PForDelta for a 128-int block, why doc-ids are stored as deltas, and when the tail is written as vInts instead. Point at the ForUtil decode.
3. Explain how advance(target) uses skip data to be sublinear, and why a rare + common conjunction is fast.
4. For age = i % 100 over 2000 docs, derive why [40,49] returns 200, and what size/docCount/min/max your PointValues printed.
5. State the three Relation outcomes of compare and what each does to a subtree; from your visitor counts, say which dominated and why.
6. Given 2000 points and maxPointsInLeafNode = 512, estimate leaf count and tree depth, and explain the split-on-widest-dimension + median build.

When you can do all six, continue to Lab LD3: HNSW Vector Files on Disk.