The Inverted Index and Postings

The inverted index is the structure that makes full-text search fast, and it is the thing most people mean when they say "Lucene." Flip a normal document store on its head — instead of "document → its words," store "word → the documents that contain it." That inverted mapping, term to postings list, is what turns match: "quick brown fox" from a scan of every document into three cheap lookups and a merge. This chapter is the inside of an OpenSearch match or term query: the terms dictionary, the FST that indexes it, the postings, and the iterators a TermQuery drives.

This is the Lucene layer beneath Query DSL and QueryBuilders: that chapter showed MatchQueryBuilder analyzing text into TermQuery objects; here you learn what those TermQuery objects do when they execute.

After this chapter you can: explain terms → postings and the on-disk layout; describe the BlockTree terms dictionary and the FST that indexes it; drive a TermsEnum + PostingsEnum in your head; explain positions/offsets/payloads and the IndexOptions that control them; and trace a TermQuery end to end.

Terms and postings

For each indexed field, Lucene builds a sorted dictionary of terms (the distinct tokens produced by analysis — see Mapping and Analysis). Each term points to a postings list: the sorted list of document IDs that contain it, plus optional per-occurrence data (how often, where, with what payload).

Field "body":
  "brown" -> docs [2, 5, 9]      freqs [1, 2, 1]   positions [...]
  "fox"   -> docs [2, 9, 17]     ...
  "quick" -> docs [2, 5]         ...

A query for body:fox is now: find "fox" in the dictionary, open its postings, iterate doc IDs. A phrase query for "quick brown" intersects the postings of both terms and checks that "brown" appears at position+1 after "quick". Scoring multiplies in term frequency, document length norms, and the collection-level inverse document frequency — but the retrieval is pure postings iteration.

On disk these live in the postings sub-format's files (see Segments and Codecs):

The BlockTree terms dictionary, backed by an FST

A field can have millions of distinct terms; you cannot binary-search a flat file of them cheaply. Lucene's default PostingsFormat uses a BlockTree terms dictionary: terms are sorted and grouped into blocks sharing a common prefix, and an in-memory index over the block prefixes points into the on-disk blocks. That index is a finite-state transducer (FST).

An FST is a compressed automaton mapping a byte sequence (a term prefix) to an output (a file pointer / metadata). It is like a trie that shares both prefixes and suffixes, stored as a tiny, cache-friendly byte array. The FST holds just enough of the dictionary (prefixes of block boundaries) to seek you to the right on-disk block; the block is then scanned linearly. So a term lookup is: walk the FST to find the block, read the block, scan to the term.

flowchart TD
    Q["seek 'brown'"] --> FST["FST index (.tip, in RAM)"]
    FST -->|"file pointer for 'br...' block"| Block["terms block (.tim, on disk)"]
    Block -->|scan to 'brown'| Meta["term metadata: doc count, postings file pointers"]
    Meta --> Doc[".doc postings"]
    Meta --> Pos[".pos positions"]

# The terms dictionary + FST live here:
grep -rln "BlockTree" lucene/core/src/java/org/apache/lucene/codecs/
ls lucene/core/src/java/org/apache/lucene/codecs/lucene*/   # *PostingsFormat
find lucene/core/src/java/org/apache/lucene -path "*util/fst/FST.java"
grep -rn "class FST\b\|class FSTCompiler\|Outputs" \
  lucene/core/src/java/org/apache/lucene/util/fst/

Note: The FST is the reason Lucene's term seeks are fast and small. It's also reused far beyond the terms dict — synonym filters, the suggest/completion components, and more all build FSTs. Reading FST.java once is one of the highest-return hours you can spend in the Lucene codebase.

Terms, TermsEnum, PostingsEnum

At read time the API mirrors the structure exactly:

The canonical access pattern — read it, then write it from memory:

LeafReader leaf = ...;                       // one segment
Terms terms = leaf.terms("body");            // field's terms, or null
TermsEnum te = terms.iterator();
if (te.seekExact(new BytesRef("fox"))) {     // found the term?
    PostingsEnum pe = te.postings(null, PostingsEnum.FREQS);
    int docID;
    while ((docID = pe.nextDoc()) != DocIdSetIterator.NO_MORE_DOCS) {
        int freq = pe.freq();                // term freq in this doc
        // with PostingsEnum.POSITIONS you could also pe.nextPosition()
    }
}

grep -rn "abstract class Terms\b\|abstract class TermsEnum\|abstract class PostingsEnum" \
  lucene/core/src/java/org/apache/lucene/index/
grep -rn "seekExact\|seekCeil\|postings(" \
  lucene/core/src/java/org/apache/lucene/index/TermsEnum.java

Note PostingsEnum is a DocIdSetIterator: nextDoc() / advance(target) / NO_MORE_DOCS. Every query in Lucene ultimately produces a DocIdSetIterator; postings are just the most fundamental source of one. That shared interface is what lets Lucene intersect a term, a range (BKD), and a filter (a bitset) in a single conjunction.

Positions, offsets, payloads — and IndexOptions

How much per-occurrence data a field stores is governed by IndexOptions, set at index time per field. More options = richer queries but bigger postings.

• Positions are token positions ("brown" is the 2nd token), needed to verify a phrase like "quick brown" truly appears adjacent.
• Offsets are character start/end in the original text, used by highlighters to underline the matched span without re-analyzing.
• Payloads are arbitrary bytes attached to a token occurrence (e.g. a part-of-speech tag, a per-term boost) — read via PostingsEnum.getPayload().

grep -rn "enum IndexOptions" lucene/core/src/java/org/apache/lucene/index/IndexOptions.java
# How OpenSearch field types pick index options:
grep -rn "IndexOptions\|setIndexOptions\|indexOptions" \
  server/src/main/java/org/opensearch/index/mapper/TextFieldMapper.java \
  server/src/main/java/org/opensearch/index/mapper/KeywordFieldMapper.java

A keyword field is typically DOCS (you only ask "does this doc equal this term"); a text field is DOCS_AND_FREQS_AND_POSITIONS (you score and run phrase queries). That difference is set in the OpenSearch field mappers and flows straight into the postings files Lucene writes.

Skip lists

A postings list can be enormous (a common term may appear in millions of docs). Conjunctive queries don't read all of it — a phrase query intersecting fox and quick repeatedly calls advance(target) to skip ahead to the next candidate doc. To make advance sublinear, the postings format embeds a multi-level skip list: periodic checkpoints that let the iterator jump over blocks of doc IDs without decoding them.

flowchart LR
    A["advance(1000)"] --> SkipL2["skip level 2: jump near 1000"]
    SkipL2 --> SkipL1["skip level 1: refine"]
    SkipL1 --> Block["decode the block containing 1000"]
    Block --> Doc["land on first doc >= 1000"]

grep -rn "Skip\|skipper\|class .*Skip" \
  lucene/core/src/java/org/apache/lucene/codecs/lucene*/ | head

This is why conjunctions over a rare term + a common term are fast: the rare term's postings drive the iteration, and each advance on the common term skips huge stretches of its postings via the skip list. Understanding this is the key to reasoning about query cost in search execution.

How a TermQuery walks all of this

Put it together. An OpenSearch term/match query becomes a Lucene TermQuery (after analysis splits text into terms). Execution:

flowchart TD
    TQ["TermQuery(body:fox)"] --> W["createWeight() -> TermWeight"]
    W --> PerSeg["for each segment (LeafReaderContext)"]
    PerSeg --> Terms["leaf.terms('body')"]
    Terms --> TE["TermsEnum.seekExact('fox')  (walks FST -> block)"]
    TE -->|found| Scorer["TermScorer over PostingsEnum"]
    TE -->|not found| Empty["no scorer for this segment"]
    Scorer --> Iter["nextDoc()/advance(): iterate postings + score (BM25)"]
    Iter --> Collect["LeafCollector collects + scores top docs"]

grep -rn "class TermQuery\|class TermWeight\|class TermScorer" \
  lucene/core/src/java/org/apache/lucene/search/

1. TermQuery.createWeight builds a Weight (per-query, captures statistics for scoring).
2. For each segment, the weight's scorer(leafContext) seeks the term via TermsEnum (FST → block → metadata) and, if found, wraps the PostingsEnum in a TermScorer.
3. The IndexSearcher drives each segment's scorer with a Collector, iterating postings (nextDoc/advance, using skip lists for conjunctions) and computing BM25 scores from freq + norms + IDF.

This is the same retrieval machinery OpenSearch's search execution layer coordinates across shards; the per-segment work is exactly the above. A match with multiple terms is a BooleanQuery of TermQuerys; a phrase is a PhraseQuery that also reads positions; a prefix/wildcard is a MultiTermQuery that enumerates many terms via the TermsEnum.

Reading exercise

# 1. The read API.
grep -rn "abstract class Terms\b\|class TermsEnum\|class PostingsEnum" \
  lucene/core/src/java/org/apache/lucene/index/

# 2. The FST + BlockTree.
find lucene/core/src/java/org/apache/lucene -path "*util/fst/FST.java"
grep -rln "BlockTree" lucene/core/src/java/org/apache/lucene/codecs/

# 3. IndexOptions and where OpenSearch sets them.
grep -rn "enum IndexOptions" lucene/core/src/java/org/apache/lucene/index/IndexOptions.java
grep -rn "setIndexOptions\|IndexOptions" \
  server/src/main/java/org/opensearch/index/mapper/TextFieldMapper.java

# 4. The query.
grep -rn "class TermQuery\|class TermScorer\|class TermWeight" \
  lucene/core/src/java/org/apache/lucene/search/

# 5. Inspect real terms with Luke (or the explain API):
#    ./gradlew :lucene:luke:run    -> Documents/Terms tab
curl -s 'localhost:9200/my-index/_search?pretty' -H 'Content-Type: application/json' -d'
{ "explain": true, "query": { "match": { "body": "fox" } } }' | head -40

Answer:

1. Explain "inverted index" by contrasting forward vs inverted storage, and say what a postings list contains.
2. What is the BlockTree terms dictionary, and what role does the FST play? Why not just binary-search a flat term file?
3. Write the Terms → TermsEnum → PostingsEnum access pattern from memory and name the method that seeks a term and the one that iterates docs.
4. List the IndexOptions levels and say which OpenSearch field types (text vs keyword) use which, and why.
5. What problem do skip lists solve, and why do they make a rare-term + common- term conjunction fast?
6. Trace a TermQuery from createWeight to scored docs, naming TermWeight/TermScorer/PostingsEnum and where the FST seek happens.

Common bugs and symptoms

Validation: prove you understand this

1. Draw the inverted index for three short documents and show the postings (with freqs and positions) for two terms.
2. Explain the BlockTree + FST: what the FST stores, what the on-disk block stores, and the two-step seek between them.
3. Hand-trace TermsEnum.seekExact + PostingsEnum.nextDoc for a term across a two-segment reader.
4. Map each IndexOptions level to a query capability it unlocks and a file it adds, and assign text/keyword to the right level.
5. Explain a multi-level skip list and why it makes advance(target) sublinear.
6. Trace match: {body: "fox"} from MatchQueryBuilder (OpenSearch) through TermQuery/TermScorer (Lucene) to collected hits, naming every layer.