BlockTreeOrds TermsEnum: a same-term TermState seek right after seekExact(ord) makes later seeks miss existing terms

BlockTreeOrdsPostingsFormat (module lucene-codecs, opt-in) stores term ordinals so that TermsEnum.ord() and TermsEnum.seekExact(long) work. Its seekExact(long) loads only the block that holds the target term and deliberately leaves the enum's internal positioned flag false, "because we didn't set frames for each byte leading up to current term". Its Expert seekExact(BytesRef, TermState) has a shortcut for a re-seek to the current term ("skip seek: already on target state") that does no work but sets positioned = true anyway. After seekExact(ord) and seekExact(term(), termState()) on the same enum, the next seekExact, seekCeil or next() therefore trusts parent frames that were never loaded: seekExact returns false for an existing term (assertions on and off), next() throws, and seekCeil throws on a tiny terms file or, on a larger one, returns a made-up term decoded from the terms file's header, whose postings can carry doc IDs beyond maxDoc. One document with 26 terms is enough. It has been in the code since the format was added (LUCENE-5819, first released in 4.10.0) and fails on every release run up to 10.6.0 and on main. The default codec cannot reach it (its seekExact(long) throws), and no Lucene query, merge or CheckIndex path makes the call sequence. A one-condition fix passes the test and the whole lucene/codecs test suite.

The 26 terms are stored as two blocks: a block for the prefix a with the 25 terms a00..a24, and the root block with two entries, that sub-block and the term b (default block sizes 25 and 48, OrdsBlockTreeTermsWriter.java:101, :107). An executed probe printed the enum's frames after each call. Steps 1-4 quote the probe; steps 5 and 6 are read from the code, and their exceptions and stack frames match the finder's executed 4-method test.

1. A fresh enum loads nothing. The constructor sets currentFrame = staticFrame; the root push is commented out (OrdsSegmentTermsEnum.java:93-104).
2. seekExact(0) loads only block a (:1094-1139). The reverse lookup in the terms index finds the block prefix a, so currentFrame = getFrame(0) (:1111) and pushFrame(arc, io.output, 1) (:1117) pushes and loads stack[1] (:1123-1129). stack[0], the root frame, is created with the frame constructor (OrdsSegmentTermsEnumFrame.java:105-110), which sets none of its position fields, and is never loaded. The method ends with the comment "Leave enum fully unpositioned, because we didn't set frames for each byte leading up to current term" and positioned = false (:1135-1138). Probe: positioned=false; stack[0] hasTerms=false fp=0 nextEnt=0 entCount=0; stack[1] fp=130 entCount=25.
3. seekExact(term(), termState()) takes the shortcut (:1058-1080). Its condition target.compareTo(term.get()) != 0 || !termExists (:1064) is false, because the target is the current term and it exists, so the "skip seek: already on target state" branch (:1074-1078) does nothing, and positioned = true (:1079) runs anyway. Probe: positioned=true, frames unchanged.
4. seekExact("b") trusts the stale frames. positioned && currentFrame != staticFrame (:256) holds, so it reuses them: a00 < b, so it continues from stack[0] (:326-334). The terms index has no arc for b, so it checks if (!currentFrame.hasTerms) (:420); the never-loaded root frame still has the default false, and the method returns false (:421-427). Probe: seekExact(b)=false, currentFrame.ord=0.
5. seekCeil("b") reuses the frames the same way (:530). loadBlock treats the root frame as loaded, because nextEnt is 0, not -1 (OrdsSegmentTermsEnumFrame.java:164-167); the scan finds no entry (scanToTermNonLeaf returns END, OrdsSegmentTermsEnumFrame.java:699-704) and calls next() (OrdsSegmentTermsEnum.java:701), which calls loadNextFloorBlock (:946-948). That reads a block at file pointer 0 (OrdsSegmentTermsEnumFrame.java:137-146, :157-234): the start of the terms file, its codec header. A short file ends early (EOFException); a longer one is decoded as a block of terms. This header decoding is traced from the code; the probes observed only its results (the EOFException, and the made-up term below).
6. next() after a24 re-seeks only when currentFrame == staticFrame || positioned == false (OrdsSegmentTermsEnum.java:932), so the catch-up its comment promises after a TermState seek is skipped. At the end of block a it pops to stack[0] (:961-962) and calls scanToSubBlock(130) (:964-969), which asserts fp=0 subFP=130 (OrdsSegmentTermsEnumFrame.java:557) or, with assertions off, reads an empty buffer (ArrayIndexOutOfBoundsException).

With the recommended fix, the same probe shows the TermState seek moving the enum to staticFrame, and seekExact("b") then seeks from the root: true, with the root frame loaded at fp=262 with 2 entries.

• Larger terms file: with the 26 terms plus 3,000 terms of another field (a 34,396-byte terms file), seekCeil("b") no longer throws. It returns NOT_FOUND on a 23-byte "term" made of header bytes (it contains the text OrdsBlockTreeTerms); its postings throw, or in another layout return doc IDs 13910 and 13933 in a segment with maxDoc 3000; further next() calls return 30 more byte strings cut from the terms file, then END.
• An independent exhaustive test (k00..k39 in a sub-block plus m, n0, n1 in the root block; every start ord against every target): seekExact wrong for 120 of 1,849 (start ord, target) pairs, every one a false for an existing term (all 40 sub-block ords times the 3 root-block terms); seekCeil wrong for 400 of 2,279; next() wrong for 40 of 43 start ords.
• The precise condition is an ancestor frame that the ord seek never loaded (here the root frame, the parent of the ord-sought block), which a later call then needs: a seek that has to leave the ord-sought block, or next() past its end. A follow-up inside that block does not fail (in the exhaustive test above, seekExact was wrong for exactly the pairs with a sub-block start and a root-block target). Nor does every enum history lead there: a reach probe found no failures after a single next() on a 2-level tree, but many after a fresh start, a prior seekExact(term), a prior seekExact(ord) and (on a 3-level tree) a full iteration; none without the TermState step and none with the fix.

• Who is exposed. Applications that write a field with BlockTreeOrdsPostingsFormat (chosen per field, for example through a per-field postings format; ord support is the reason to pick it) and that, on one enum, call seekExact(ord), then seekExact(sameTerm, its own termState()) with no other seek between (a redundant re-seek, for example from a "restore saved cursor" helper), then a seek that has to leave the ord-sought block or next() past its end. The ord-sought term must sit in a block below the root block. In the minimal shape, 25 terms that share the prefix a get such a block with the default sizes; in general the writer only aims at 25 to 48 entries per block and "in some cases the blocks may be smaller than the min" (OrdsBlockTreeTermsWriter.java:163-165), so the term count alone is not a threshold.
• Who is not. The default codec: its block-tree enum throws UnsupportedOperationException from seekExact(long). Lucene itself: every in-tree TermState seek (TermQuery, SynonymQuery, PhraseQuery, MultiPhraseQuery, CombinedFieldQuery, SpanTermQuery, the multi-term query wrappers, and the sandbox PhraseWildcardQuery and TermAutomatonQuery) is in code that never calls seekExact(long), FuzzyTermsEnum and FilterLeafReader only delegate both calls, and CheckIndex does seekExact(ord) then seekCeil with no TermState seek.
• Downstream (read-only survey). Elasticsearch and OpenSearch exclude the format in their test frameworks (@SuppressCodecs), and Solr does not reference it. neo4j switched its Lucene indexes to this format by default in a 2016 change (its PR #6537); a spot check of two of its current files found no trigger sequence, and whether it still uses the format was not determined.
• Effect. Deterministic: the minimal repro fails on every run (seeds DEADBEEF, C0DEFACE and 5EED1234 five times, assertions on and off), and any follow-up that needs the never-loaded root frame fails every time; a follow-up that stays inside the ord-sought block does not. seekExact is silently wrong with assertions on and off; next() fails loudly; seekCeil fails loudly only on tiny terms files and otherwise returns a made-up term whose postings can carry doc IDs beyond maxDoc. Read side only, from the code: the enum only reads, so the index files are not changed, and nothing outside the segment is read (the stale frame reads the segment's terms file; the made-up term's postings are read from the segment's postings file, at offsets decoded from header bytes).
• Scale. One document and 26 terms are enough.
• How likely. Rare: no in-tree caller makes the sequence, the downstream survey found none (for neo4j only a two-file spot check), and the recorded searches found no report of it, although it has been in the code since 4.10.0 (2014) (see "Prior reports" for the searches and their gaps).

The test sits in the format's package by convention but uses only public classes and methods. It uses a plain ByteBuffersDirectory and IndexWriterConfig, runs single-threaded, and fails the same way with seeds DEADBEEF, C0DEFACE and 5EED1234 (five iterations), assertions on and off. It is also the suggested regression test, for example as a method of TestOrdsBlockTree.

Why 25 a terms: the default minimum block size is 25, and the writer gives a prefix its own block only when it has at least that many entries, so 25 terms that share the prefix a get their own block below the root. With fewer, every term of this test sits in the root block, the ord seek loads the root itself, and nothing is stale: with 24 a terms the test passes.

Without the te.seekExact(..., te.termState()) line the same test passes, with assertions on and off.

TestOrdsTermStateSeekAfterOrdSeek > testSeekExactAfterOrdSeekAndSameTermStateSeek FAILED
    java.lang.AssertionError: existing term b: expected seekExact true, got false
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:2BBC219F910A50E9]:0)
        at org.junit.Assert.fail(Assert.java:89)
        at org.junit.Assert.assertTrue(Assert.java:42)
        at org.apache.lucene.codecs.blocktreeords.TestOrdsTermStateSeekAfterOrdSeek.testSeekExactAfterOrdSeekAndSameTermStateSeek(TestOrdsTermStateSeekAfterOrdSeek.java:52)
:lucene:codecs:test (FAILURE): 1 test, 1  failure

# the same with -Ptests.asserts=false; the standalone runner gives the same assertion on main and on 10.6.0
# without the TermState line: passes; with the recommended fix: the test passes

• Contract. seekExact(long): "Seeks to the specified term by ordinal (position) as previously returned by ord. The target ord may be before or after the current ord, and must be within bounds" (TermsEnum.java:91-95). The Expert seekExact(BytesRef, TermState): "Seeking by TermState should only be used iff the state was obtained from the same TermsEnum instance", for the same field (:97-116). "The TermsEnum is unpositioned when you first obtain it and you must first successfully call next or one of the seek methods" (:34-35): after seekExact(long) the enum is positioned in the API's sense.
• The class's own invariant. seekExact(long) leaves positioned = false "because we didn't set frames for each byte leading up to current term" (OrdsSegmentTermsEnum.java:1135-1138); the shortcut sets it to true without setting them (:1079). next()'s comment promises that when "seek(TermState) was called" and the caller then calls next(), "this method catches up all internal state so next() works properly" (:933-938). The shortcut exists for exactly this re-seek (:1074-1078).
• Lucene's own references accept it. AssertingTermsEnum marks the enum POSITIONED after seekExact(long) (AssertingLeafReader.java:384-389); through AssertingDirectoryReader no state-machine assertion fires and seekExact("b") is still false. DirectPostingsFormat returns the right answers for the same sequence. The default TermState seek in BaseTermsEnum is a plain seekExact(term) (BaseTermsEnum.java:67-72).
• Why the tests miss it. TestOrdsBlockTree never calls termState(). RandomPostingsTester takes a fresh enum for every seek and uses either an ord seek or a TermState seek, never both (RandomPostingsTester.java:1612-1628). TestTermsEnum.testRandomSeeks mixes TermState seeks (:686) with next() (:731) on one enum but has no ord seeks.
• History and precedent. The shortcut was copied from the core block-tree enum, where it is safe (no positioned flag, no ord seek); the ord seek and the unconditional positioned = true came in together with the format. LUCENE-3260 (#4333: an enum not positioned properly after a successful seek, so next() went wrong) and LUCENE-6395 (#7455: an ord-seek bug in MemoryIndex) were treated as bugs and fixed.

Strongest case (all verifiers and the adjudication looked for it): both calls are Expert, experimental performance paths; a TermState re-seek to the term the enum is already on is redundant; and seekExact(long) deliberately leaves the enum "unpositioned", so calling seekExact(term, state) there is misuse.

Why it fails: no javadoc limits either call, the only stated TermState precondition holds, and the API and the test framework's state machine treat the enum as positioned after seekExact(long). The internal flag only means "the frames are valid", and the code's own comment says it must stay false here. @lucene.experimental is about API stability, not correctness. "Nobody does this" narrows who is hit; it does not make a false for an existing term intended. All verifiers rated the intended-behaviour case weak.

Two small fixes (one changed condition; one moved statement) were built and run in a scratch worktree of 645d4fe14a20; both make the test pass. A third, larger design is listed for completeness.

Add || !positioned to the shortcut's condition in seekExact(BytesRef, TermState) (OrdsSegmentTermsEnum.java:1064). After an ord seek the enum then moves to staticFrame with the copied state, exactly as after any TermState seek; the next seek starts from the root and next() catches up. The shortcut still applies when the frames are valid. The idea is the first finder's.

--- a/lucene/codecs/src/java/org/apache/lucene/codecs/blocktreeords/OrdsSegmentTermsEnum.java
+++ b/lucene/codecs/src/java/org/apache/lucene/codecs/blocktreeords/OrdsSegmentTermsEnum.java
@@ -1061,7 +1061,7 @@ public final class OrdsSegmentTermsEnum extends BaseTermsEnum {
     // target.utf8ToString() + " " + target + " state=" + otherState);
     // }
     assert clearEOF();
-    if (target.compareTo(term.get()) != 0 || !termExists) {
+    if (target.compareTo(term.get()) != 0 || !termExists || !positioned) {
       assert otherState != null && otherState instanceof BlockTermState;
       BlockTermState blockState = (BlockTermState) otherState;
       currentFrame = staticFrame;

Trade-offs

The full TermState branch (a state copy, a copy of the term bytes and a few field writes, OrdsSegmentTermsEnum.java:1065-1073) instead of nothing, and only for a same-term TermState seek right after an ord seek: that is the only state with positioned false and termExists true. On a fresh enum and after next() returned END, termExists is false, so those cases take the full branch already. No benchmark was run.

What the checks validated

Run in a scratch worktree of 645d4fe14a20, seed DEADBEEF: the repro and TestOrdsBlockTree pass with assertions on (38 tests, 2 skipped, 0 failures) and off (38 tests, 2 skipped, 0 failures); the whole lucene/codecs test suite passes with assertions on (694 tests, 78 skipped, 0 failures; that module only). An earlier pass the same day also ran them with nightly tests on and the format check. Only OpenJDK 25.0.3 on Linux aarch64; no benchmark, no full Lucene test run.

Move positioned = true into the full TermState branch, so the shortcut keeps whatever the enum had (the independent reproducer's variant). After an ord seek the enum stays unpositioned on its valid ord-seek frame, and the next seek or next() re-seeks from the root.

Trade-offs

One moved statement plus a two-line comment. The full TermState branch is unchanged and still switches to staticFrame; only the same-term shortcut now keeps the current frame and leaves positioned as it was (false after an ord seek), so a following termState() or postings() reads the ord-seek frame, as it does today.

What the checks validated

Run the same way: the repro and TestOrdsBlockTree pass with assertions on (38 tests, 2 skipped, 0 failures) and off (38 tests, 2 skipped, 0 failures). Not run with this fix: the whole codecs suite, the format check, any benchmark.

Load the frames for each prefix of the target term during the ord seek, so the enum is fully positioned afterwards.

Trade-offs

Removes the special unpositioned state, but adds work to every ord seek: loading each block on the path from the root, where the current code loads only the block that holds the target term (OrdsSegmentTermsEnum.java:1103-1129).

Method: semi-formal, a hunt unit (codecs-module formats differential), 2026-10-26, on main ea57360912ed.

• A bounded-exhaustive translation-validation harness (reused from an earlier unit, with a new BlockTreeOrds format spec) writes every small term set with the real IndexWriter, then checks the real reader against an exact sorted-array reference operation by operation. Over 64,200 term sets (up to 3 terms, 6 block configurations) it flagged mismatches and errors; with the fix of a sibling bug (LFV-157) applied, 40 mismatches and 26 errors remained, all this bug.
• A model-based check enumerated every sequence of up to 4 TermsEnum calls (next, ord, seekExact(ord), termState, seekExact(term, saved state), seekCeil, seekExact) against a sorted-array model: 23 of 954,304 (3 terms), 40 of 2,141,490 (4 terms) and 46 of 4,193,820 (5 terms) sequences fail on stock main, 0 with the fix, every printed one (the 3-term log prints 15 of its 23) of the shape ord seek, termState, same-term TermState seek, then a seek or next. A cross-model reviewer noticed that the first version replayed TermStates captured on another enum; the model was fixed to capture them on the same enum and re-run.
• With both fixes shadowed, runs found 0 mismatches over 33,424,158 term sets (2.65e10 operations).