Lab LD1: The FST Terms Dictionary

Background

You read in the masterclass index and the Inverted Index chapter that the terms dictionary's index — the .tip file — is an FST (finite-state transducer): a near-minimal automaton mapping term prefixes to file pointers into the on-disk term blocks in .tim. That is abstract until you build one. In this lab you do three things:

1. Build an FST directly with Lucene's org.apache.lucene.util.fst API — a tiny program mapping a handful of terms to long outputs — then traverse it arc by arc and print its structure and size.
2. Build a real Lucene index and inspect its actual .tim/.tip terms dict with CheckIndex -verbose and a TermsEnum walk in code.
3. Connect the two: explain exactly how seekExact descends the FST to a block and scans it.

Why This Matters for Contributors

The FST is one of the most-reused structures in Lucene — terms index, synonym filters, the suggest/completion components, and the MultiTermQuery intersection all build or walk FSTs. A contributor who has built one by hand can read FST.java, FSTCompiler.java, and BlockTreeTermsWriter.java without flailing, can reason about why a leading wildcard is slow (it matches a huge slice of the FST), and can debug "term seek is slow / terms dict is huge" issues from the structure up. This is the single highest-return data structure to internalize.

Prerequisites

• A JDK 17+ (java, javac) on PATH.
• A Lucene lucene-core-*.jar. Get one from an OpenSearch checkout's gradle cache or download it; locate it with:

# In an OpenSearch checkout, the bundled Lucene jar:
find ~/.gradle /opt /usr -name "lucene-core-*.jar" 2>/dev/null | head
# Or from a Lucene checkout after ./gradlew assemble:
find . -name "lucene-core-*.jar" 2>/dev/null | head
export LUCENE_CP="/path/to/lucene-core-9.x.x.jar"   # set this for the rest of the lab

• Read index.md (the terms-dict + FST sections) and skim inverted-index-and-postings.md.

Note: Exact class/method names vary by Lucene version (the FST API was refactored around the FSTCompiler/FST.FSTMetadata split). If a symbol below doesn't resolve, grep the jar's source or the lucene/core/src/java/org/apache/lucene/util/fst/ directory to find the real name — the shape of the API is stable.

Step-by-Step Tasks

Step 1 — Build an FST by hand

Create BuildFst.java. It maps six sorted terms to long outputs using PositiveIntOutputs (the outputs we use are the kind the terms index uses: a non-negative long, summed along the arc path).

import org.apache.lucene.util.BytesRef;
import org.apache.lucene.util.IntsRefBuilder;
import org.apache.lucene.util.fst.FST;
import org.apache.lucene.util.fst.FSTCompiler;
import org.apache.lucene.util.fst.PositiveIntOutputs;
import org.apache.lucene.util.fst.Util;

public class BuildFst {
  public static void main(String[] args) throws Exception {
    // Outputs are non-negative longs that sum along the path (like file pointers).
    PositiveIntOutputs outputs = PositiveIntOutputs.getSingleton();

    // Newer Lucene: FSTCompiler.Builder(...).build(); older: new Builder<>(...).
    FSTCompiler<Long> compiler =
        new FSTCompiler.Builder<>(FST.INPUT_TYPE.BYTE1, outputs).build();

    // Terms MUST be added in sorted (UTF-8 byte) order. Pretend these are block
    // file pointers in .tim.
    String[] terms = {"brown", "dog", "fox", "lazy", "quick", "the"};
    long[] ptr     = {  100,    140,   175,   210,    250,     300 };

    IntsRefBuilder scratch = new IntsRefBuilder();
    for (int i = 0; i < terms.length; i++) {
      BytesRef term = new BytesRef(terms[i]);
      compiler.add(Util.toIntsRef(term, scratch), ptr[i]);
    }

    FST<Long> fst = FST.fromFSTReader(compiler.compile(), compiler.getFSTReader());
    // (older API: FST<Long> fst = compiler.compile();)

    // How big is the whole automaton, in bytes? This is what lives in .tip / RAM.
    System.out.println("FST ram bytes used: " + fst.ramBytesUsed());

    // Exact lookups: walk the FST, get the output (== our pointer).
    for (String t : new String[] {"fox", "the", "cat" /* miss */}) {
      Long out = Util.get(fst, new BytesRef(t));
      System.out.println("get(" + t + ") = " + out);
    }
  }
}

Compile and run:

javac -cp "$LUCENE_CP" BuildFst.java
java  -cp "$LUCENE_CP:." BuildFst

Expected (numbers approximate; the point is exact outputs and a null miss):

FST ram bytes used: 200
get(fox) = 175
get(the) = 300
get(cat) = null

cat returns null — the FST is exact over its key set; it never invents a key. Each found output is exactly the pointer we stored.

Step 2 — Traverse the FST arc by arc

Now print the structure: starting at the root arc, follow the first target arc and its siblings to see how brown/dog/… diverge and where outputs sit. Add this to a new WalkFst.java (reuse the build code, then walk):

import org.apache.lucene.util.fst.FST;
// ... (build the FST<Long> exactly as in Step 1, into a variable `fst`) ...

FST.Arc<Long> arc = new FST.Arc<>();
FST.BytesReader reader = fst.getBytesReader();

// Root arc.
fst.getFirstArc(arc);
System.out.println("root: output=" + arc.output());

// Enumerate the arcs leaving the root (the first byte of every term).
fst.readFirstRealTargetArc(arc.target(), arc, reader);
while (true) {
  char label = (char) arc.label();
  System.out.printf("  arc label='%c' (0x%02x) output=%s final=%b%n",
      label, arc.label(), arc.output(), arc.isFinal());
  if (arc.isLast()) break;
  fst.readNextRealArc(arc, reader);
}

Compile/run the same way. You will see the distinct first bytes of your terms (b,d,f,l,q,t) as arcs leaving the root, each carrying the pushed part of the output. Outputs are pushed toward the root, so the shared prefix of two pointers can sit on a shared arc. Walk deeper (follow arc.target() again) to watch brown continue b→r→o→w→n and reach a final arc whose accumulated output is 100.

Note: readFirstRealTargetArc / readNextRealArc are the low-level traversal primitives BlockTreeTermsReader uses. If your version renamed them, grep: grep -rn "readFirstTargetArc\|readNextArc\|readFirstRealTargetArc" $LUCENE_SRC/util/fst/FST.java.

Step 3 — Build a real index with a terms dict

Now produce real .tim/.tip files. IndexAndDump.java indexes the two documents from the worked example in index.md and walks the resulting terms dict.

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 IndexAndDump {
  public static void main(String[] args) throws Exception {
    Path dir = Paths.get("ld1-index");
    try (Directory d = FSDirectory.open(dir)) {
      IndexWriterConfig cfg = new IndexWriterConfig(new StandardAnalyzer());
      cfg.setUseCompoundFile(false);          // keep files un-packed so we can find .tim/.tip
      try (IndexWriter w = new IndexWriter(d, cfg)) {
        for (String body : new String[] {"the quick brown fox", "the lazy brown dog"}) {
          Document doc = new Document();
          doc.add(new TextField("body", body, Field.Store.NO));
          w.addDocument(doc);
        }
        w.commit();
      }

      // Walk the terms dictionary of field "body".
      try (DirectoryReader r = DirectoryReader.open(d)) {
        for (LeafReaderContext ctx : r.leaves()) {
          Terms terms = ctx.reader().terms("body");
          if (terms == null) continue;
          System.out.println("field 'body': sumDocFreq=" + terms.getSumDocFreq()
              + " sumTotalTermFreq=" + terms.getSumTotalTermFreq()
              + " size=" + terms.size());
          TermsEnum te = terms.iterator();
          BytesRef t;
          while ((t = te.next()) != null) {
            System.out.printf("  term=%-7s docFreq=%d totalTermFreq=%d%n",
                t.utf8ToString(), te.docFreq(), te.totalTermFreq());
          }

          // Now a targeted seek: this is what descends the FST then scans a block.
          TermsEnum seeker = terms.iterator();
          boolean found = seeker.seekExact(new BytesRef("brown"));
          System.out.println("seekExact('brown') -> " + found
              + " docFreq=" + (found ? seeker.docFreq() : -1));
          // Walk its postings (the file pointers the FST seek resolved to).
          if (found) {
            PostingsEnum pe = seeker.postings(null, PostingsEnum.FREQS);
            int id;
            while ((id = pe.nextDoc()) != PostingsEnum.NO_MORE_DOCS) {
              System.out.println("    doc " + id + " freq " + pe.freq());
            }
          }
        }
      }
    }
  }
}

javac -cp "$LUCENE_CP" IndexAndDump.java
java  -cp "$LUCENE_CP:." IndexAndDump
ls -la ld1-index/        # look for _0.tim _0.tip _0.tmd _0.doc _0.pos

Expected:

field 'body': sumDocFreq=8 sumTotalTermFreq=8 size=6
  term=brown   docFreq=2 totalTermFreq=2
  term=dog     docFreq=1 totalTermFreq=1
  term=fox     docFreq=1 totalTermFreq=1
  term=lazy    docFreq=1 totalTermFreq=1
  term=quick   docFreq=1 totalTermFreq=1
  term=the     docFreq=2 totalTermFreq=2
seekExact('brown') -> true docFreq=2
    doc 0 freq 1
    doc 1 freq 1

Six terms, sorted, exactly as predicted in the worked example. brown and the have docFreq=2; the rest are 1.

Step 4 — Inspect .tim/.tip with CheckIndex and xxd

# CheckIndex prints the terms-dict test, per field. Run on a COPY to be safe.
cp -r ld1-index ld1-copy
java -cp "$LUCENE_CP" org.apache.lucene.index.CheckIndex ld1-copy -verbose 2>&1 \
  | grep -A4 -i "test: terms\|field \"body\"\|blocks"

# See the CodecUtil header of the terms index (.tip) — CODEC_MAGIC + codec name:
xxd -l 48 ld1-index/_0.tip
#   3fd7 6c17 ...  Lucene90BlockTree...   <- magic 3FD76C17 then the format name

# Relative sizes: with 6 terms the FST is tiny; with a big field .tip stays small
# while .tim/.doc grow. Prove it later with a large index.
du -h ld1-index/_0.tim ld1-index/_0.tip ld1-index/_0.tmd ld1-index/_0.doc

Look in the CheckIndex output for the terms test reporting the field, the number of terms, and (with a bigger index) the BlockTree block count and depth.

Step 5 — Explain the descent (write it down)

In your own words, in a comment block or notes, complete this trace for seekExact("brown"):

1. TermsEnum.seekExact walks the FST in .tip consuming bytes b,r,o,w,n, accumulating the output → the file pointer of the floor block in .tim.
2. It seeks .tim to that pointer, reads the block header (prefix length, term count), and linearly scans the block's prefix-suffix term entries.
3. On the match it reads the term metadata: docFreq, totalTermFreq, and the docStartFP/posStartFP file pointers into .doc/.pos.
4. postings(...) opens a PostingsEnum at docStartFP; nextDoc() decodes the doc-id deltas (here, vInts — fewer than 128 postings).

That is the entire hot path of a term/match query, per segment.

Deliverables

• BuildFst.java — builds and queries an FST; prints ramBytesUsed and exact outputs incl. a null miss.
• WalkFst.java — enumerates root arcs and follows one term's path to a final arc.
• IndexAndDump.java — a real index; the six-term dump + a seekExact + PostingsEnum walk.
• A du/xxd/CheckIndex capture of .tim/.tip with the CODEC_MAGIC header identified.
• The written Step-5 descent trace.

Troubleshooting

Expected Output

A working FST you can query exactly, an arc-by-arc dump showing the automaton's branching, a real six-term terms dictionary that matches the worked example, and a CODEC_MAGIC-confirmed .tip file on disk — plus a clear mental model of the FST→block descent.

Stretch Goals

• Scale it. Index 100k random words; print terms.size() and du -h _0.tip vs _0.tim. Observe the FST (.tip) stays tiny while the block file (.tim) grows — that asymmetry is the whole design.
• Visualize the FST. Use Util.toDot(fst, writer) to emit Graphviz; render with dot -Tpng. You will see the shared suffixes (merged states).
• MultiTermQuery. Add a PrefixQuery("body","b") and confirm via explain that it enumerates brown (and only b… terms) — the FST/automaton intersection.
• Compare to Luke. Open ld1-index in Luke (./gradlew :lucene:luke:run) and walk the same terms in the Terms tab; confirm the docFreqs match your dump.

Coding Exercises

These exercises turn the trace-and-observe work above into code you can grade. Each is a standalone Java program (or JUnit class) compiled against the Lucene jars on $LUCENE_CP — no Gradle, no checkout required. Build on the BuildFst/WalkFst/ IndexAndDump programs you already have.

1. (warm-up) Assert exact FST semantics in a JUnit test. Wrap your BuildFst logic in a JUnit 5 (or junit:junit 4) test FstExactTest that builds the six-term FST and asserts, with assertEquals, that Util.get(fst, new BytesRef("fox")) returns 175L and that Util.get(fst, new BytesRef("cat")) is null. Add a parameterized case for every key. Verify: javac -cp "$LUCENE_CP:$JUNIT_CP" FstExactTest.java && java -cp ... org.junit.runner... (or the JUnit 5 console launcher) is green. This proves "exact over its key set."

2. (warm-up) Count arcs and states. Extend WalkFst into a method int countArcs(FST<Long> fst) that does a depth-first traversal using readFirstRealTargetArc/readNextRealArc (the same primitives you grepped) and returns the total arc count. Print it next to fst.ramBytesUsed(). Then index the same six terms with a trailing shared suffix (e.g. add running,jumping) and show the arc count grows sub-linearly because suffixes merge.

3. (core) Build the FST that the terms index actually builds. Replace the toy long outputs with the real output type the terms index uses. Locate it: grep -rn "PositiveIntOutputs\|ByteSequenceOutputs\|Outputs<" "$LUCENE_SRC/codecs/.../*TermsWriter.java" (the BlockTree writer — verify the exact class on your branch). Write FstFromTerms that walks a real index's TermsEnum, feeds each term + its .tim block file pointer into an FSTCompiler, and asserts that Util.get on your hand-built FST returns the same pointer the codec stored. You are reconstructing the .tip.

4. (core) Prove the prefix-pushing. Write a test that builds a two-term FST ({"app": 1000, "apple": 1000}) and asserts that the shared output sits on the shared arc path, not duplicated on both finals — read arc.output() along a→p→p and assert it already carries the common prefix. This is the single property that makes outputs compress. Reference the Util.toDot stretch goal to visualize it, but the assertion is the deliverable.

5. (advanced) Advanced challenge — a PrefixQuery enumeration harness. Build a small program PrefixEnum that, given an index field and a prefix, uses Terms.intersect(CompiledAutomaton, null) (the FST↔automaton intersection that PrefixQuery/MultiTermQuery use) to enumerate exactly the matching terms. Locate the call site first: grep -rn "intersect\|CompiledAutomaton\|TermsEnum intersect" "$LUCENE_SRC/index/Terms.java" "$LUCENE_SRC/search/PrefixQuery.java". Then write a JUnit test that indexes {"brown","brisk","brave","green"}, runs your harness with prefix "br", and asserts it returns exactly {brave,brisk,brown} in sorted order and never touches green. Bonus: add a counter inside an instrumented build to confirm a leading wildcard (*own) forces a full-FST walk while br* does not — the structural reason leading wildcards are slow.

Issues to Practice On

The terms dictionary and FST live in apache/lucene (Apache workflow: GitHub issues + PRs, a CHANGES.txt entry per change, ./gradlew check/tidy — no DCO sign-off, unlike OpenSearch). Browse and claim issues with:

gh label list --repo apache/lucene | grep -iE "good first|core/.*|new feature"   # see the real taxonomy first (labels move; confirm on the tracker)
gh issue list --repo apache/lucene --label "good first issue" --state open
gh issue list --repo apache/lucene --search "FST in:title,body" --state open
gh issue list --repo apache/lucene --search "BlockTree OR terms dictionary in:title,body" --state open

Representative issue patterns for this subsystem:

• FST memory / build-time regressions. "FST uses more RAM than expected" or "term dictionary build slowed down." Approach: reproduce with a synthetic index, locate the writer via rg "class FSTCompiler\|class BlockTreeTermsWriter", add a micro-measurement (ramBytesUsed, arc count) as a test, then bisect.
• Off-by-one / boundary bugs in seekCeil/seekExact. Approach: write a failing BaseTermsEnumTestCase-style test that seeks a term on a block boundary, locate the scan in BlockTreeTermsReader/SegmentTermsEnumFrame (rg "seekExact\|scanToTerm"), fix, keep the test.

Planted-bug drill. In a copy of your BuildFst, change the input order so two terms are out of UTF-8 byte order (e.g. swap "the" before "quick"). Run it: you should get IllegalArgumentException: input is not sorted. Now harden your code: catch that, and add a JUnit test assertThrows(IllegalArgumentException.class, ...) that would have caught an unsorted feed — exactly the invariant the codec relies on. Then plant a subtler one: in your FstFromTerms (exercise 3), store ptr - 1 instead of ptr and watch your Util.get-equals-codec-pointer assertion go red; revert and note which assertion guarded you.

Etiquette: claim an issue (comment to take it) before working, reproduce first, and every Lucene PR needs a test + a CHANGES.txt entry under the right release section (no DCO on Apache projects). See community-interaction.md.

Validation: prove you understand this

1. State the two trie-vs-FST differences that make an FST small, and where the outputs live on the arcs.
2. From your BuildFst run, explain why get("cat") is null and get("fox") is exactly your stored pointer — what "exact over its key set" means.
3. Using your IndexAndDump output, list the six terms in order and their docFreqs, and say why brown and the are 2.
4. Trace seekExact("brown") from the .tip FST to the .doc postings, naming .tim, the floor block, the term metadata, and PostingsEnum.
5. Identify the CODEC_MAGIC bytes in your xxd of _0.tip and name the format string that follows them.
6. Predict (and then measure in the stretch goal) how .tip vs .tim sizes diverge as term count grows, and explain why.

When you can do all six, continue to Lab LD2: Postings and BKD Trees, which walks the PostingsEnum the FST seek lands you on and then builds the numeric BKD tree.