IndexedDISI returns its jump-table entry count as a short, so a sparse field whose last document is at doc id 2,147,352,576 or above loses its jump table (8.0.0+)

IndexedDISI records which documents of a segment have a sparse doc-values, norms or vector field, in blocks of 65,536 doc ids. Since 8.0 it also writes a jump table after the blocks, one entry per block up to the last one with a document plus one for the end marker (no table when every document is in block 0), so that advance() can jump straight to a far block. writeBitSet returns the number of entries as a short, under the comment "As there are at most 32k blocks, the count is a short". Legal doc ids fill blocks 0 to 32,767, so up to 32,769 entries are written. When the field's last document is at doc id 2,147,352,576 or above, the count is 32,768 or 32,769 and the cast returns -32,768 or -32,767. The default doc-values, norms and vector writers store that value; their readers take a count of 0 or less as "no jump table" and advance()/advanceExact() walk the block headers one by one. The documents and values returned stay correct; about 256 KiB of table per affected field per segment is written and never read. Every release from 8.0.0 to 10.6.0 and main is affected.

1. One entry per block up to the last doc's block, plus one. In writeBitSet (:192-236) each block with documents calls addJumps(..., lastBlock, block + 1) and sets lastBlock = block + 1 (:215-216); after the loop one more entry is added for the NO_MORE_DOCS block (:231), and the method returns flushBlockJumps(jumps, lastBlock + 1, out) (:235). Empty blocks before the last one get entries too (they point at the next non-empty block). So, for a field whose last doc is past block 0, the count is the last doc's block + 2 (if every doc is in block 0 that is 2, and flushBlockJumps writes no table and returns 0, :255-259).
2. The count is narrowed to a short.

// As there are at most 32k blocks, the count is a short          // :264
// The jumpTableOffset will be at lastPos - (blockCount * Long.BYTES)
return (short) blockCount;                                         // :266

1. The default codecs store it. Lucene90DocValuesConsumer.writeDISI (:166-174), Lucene90NormsConsumer (:116-119) and lucene95/OrdToDocDISIReaderConfiguration.writeStoredMeta (:89-93, used by the vector formats) write it with meta.writeShort(jumpTableEntryCount).
2. The readers take it as "no table". Lucene90DocValuesProducer (:388, :420), Lucene90NormsProducer (:223) and OrdToDocDISIReaderConfiguration.fromStoredMeta (:129) read it back with readShort(). createBlockSlice treats a count below 0 as no table bytes (:375), and createJumpTable returns null for a count of 0 or less (:392-393).
3. advance walks. advanceBlock uses the table only when jumpTable != null (:498); otherwise it takes the "Fallback to iteration of blocks" (:512-516): seek to the end of the current block, read the next block header, repeat. A DENSE block also has its 256-byte rank table read (:549-550).

IndexWriter.MAX_DOCS - 1 = 2,147,483,518 (index/IndexWriter.java:208) is in block 32,767, so no legal doc id goes further. Only sparse fields are affected: a field that every document has, or none has, stores -1 and no IndexedDISI (Lucene90DocValuesConsumer.java:461-470, and the same in the norms and vector writers).

The table bytes on disk are valid; only the stored count is wrong. Reading the same bytes with the count taken as an unsigned 16-bit value restores the jumps and gives the same results. A Z3 model of the layout proves that a wrapped count always reads back negative and that every last doc id below 2,147,352,576 keeps a correct count; that a negative count then switches the table off, so it is never misread, follows from the code (:375, :392-393).

• Who is hit. The default codec, doc values and norms from 8.0.0, sparse vectors from 9.2.0. No setting turns the jump table on or off: it is written for every sparse field whose last document is at doc id 65,536 or above (block 1 or later). Only doc values were run end to end; norms and vectors store and read the count the same way (by reading). For vectors, iteration, exact search and merging go through IndexedDISI; ordinary HNSW graph search works on ordinals and may not touch it (not checked).
• How such a segment arises. The default TieredMergePolicy caps merged segments at 5 GiB (TieredMergePolicy.java:77), under about 2.5 bytes per document for 2^31 documents, so in practice it takes a forceMerge of a near-full index to very few segments, or a raised cap. Such segments are supported: Lucene's @Monster test TestIndexWriterMaxDocs.testExactlyAtTrueLimit indexes MAX_DOCS documents and calls forceMerge(1).
• Cost. The walk only moves forward, so each iterator pays at most one extra pass over the non-empty blocks it passes, in its lifetime, not per call (but each query, segment, sort or facet makes its own iterators): up to 32,768 header reads (a document in every block 0 to 32,767), plus the rank table of each DENSE block, and one extra header read for a field with two documents. Measured medians, in memory on a loaded shared host, so order of magnitude only, no table against the table: one far advance from a fresh iterator 477 us against 48 us (one doc per block) and 1.9 ms against 69 us (4,096 docs per block); about 1,000 sorted advanceExact calls 512 us against 95 us, and 2.0 ms against 0.38 ms. For scale, a full scan of the dense field took 852 ms.
• Space. About 256 KiB of table per affected field per segment is written and never read.
• Visibility. None: nothing fails or warns. In effect the segment falls back to the pre-8.0 block walk: a 7.x baseline with the same doc set takes the same 32,767-seek walk.

One document in block 32,766 is the smallest input that wraps: the writer still emits entries for the empty blocks 0 to 32,765, so the count is 32,766 + 1 + 1 = 32,768 (12 bytes of blocks, then 32,768 x 8 = 262,144 bytes of table). A last document one block earlier gives 32,767, which fits. The test holds the result in no short variable, so it compiles unchanged against an int return type.

As the regression test: the same test; it fails without the fix and passes with the recommended fix. It checks the writer's count; that readers then use the table was checked separately while validating the fix.

The consequence, not part of the repro: with one document in every block 0 to 32,766, advance(2147352576) on a fresh iterator reads 32,767 block headers, on the raw IndexedDISI and through Lucene90DocValuesFormat (a sparse NUMERIC field of a segment with maxDoc = IndexWriter.MAX_DOCS, written and read through the format's consumer and producer; no index of 2^31 documents was built). Through the format, advanceExact(2147352576) also takes 32,767 seeks and returns the right value (an independent reproducer's codec test on ea57360912ed, and the diagram probe on 645d4fe14a20).

# gradle, main 645d4fe14a20, seed DEADBEEF
TestIndexedDISIJumpTableCount > testJumpTableEntryCount FAILED
    java.lang.AssertionError: expected the 32768 jump-table entries written (blocks 0..32767), actual the short cast expected:<32768> but was:<-32768>
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:AD89756848C50AE2]:0)
        at org.junit.Assert.fail(Assert.java:89)
        at org.junit.Assert.failNotEquals(Assert.java:835)
        at org.junit.Assert.assertEquals(Assert.java:647)
        at org.apache.lucene.codecs.lucene90.TestIndexedDISIJumpTableCount.testJumpTableEntryCount(TestIndexedDISIJumpTableCount.java:32)

# the hunt's consequence tests (main 645d4fe14a20, gradle, count held in an int; same on ea57360912ed)
testAdvanceUsesTheJumpTable: advance to the last block took 32767 block seeks (count=-32768)
testDocValuesFieldIgnoresItsJumpTable: advance to the last block took 32767 block seeks

• Contract. @return the number of jump-table entries following the blocks, -1 for no entries (IndexedDISI.java:188-189, also on the 2-argument overload at :167). The constructors say the count "must match the number returned by" writeBitSet (:288-289, :318-319).
• The code's own invariant is false. "As there are at most 32k blocks, the count is a short" (:264); doc ids up to MAX_DOCS - 1 fill blocks 0 to 32,767, and the writer adds the NO_MORE_DOCS entry: up to 32,769.
• Purpose. Class javadoc: "To avoid O(n) lookup time complexity ... lookup tables are used"; the table "allows for direct jumping to the block, as opposed to iteration from the current position and forward one block at a time" (:56-62). CHANGES.txt:6877: "LUCENE-8585: Index-time jump-tables for DocValues, for O(1) advance when retrieving doc values."
• No misuse. The wrapped value comes from Lucene's own default writers.
• No test or discussion covers it. TestIndexedDISI uses small doc-id ranges; the Test2B*DocValues monster tests give every document a value, which is stored without IndexedDISI. In the LUCENE-8585 review (lucene-solr#525) the only remark on the line moved the count to the meta file; its width was never discussed.

Strongest case (an intended-behaviour checker and a works-as-designed review by another model family): IndexedDISI is @lucene.internal (:94), so the @return javadoc is an internal contract; DocIdSetIterator promises correct results, not O(1) cost; Lucene90DocValuesFormat documents both modes, skipping "either done on an iterative basis or by using the jump-table" (Lucene90DocValuesFormat.java:65-66); the fallback is safe; and the trigger is extreme.

Why it fails: these limit severity, not validity. The iterative mode is a general path that happens to absorb an arithmetic slip (the reviewer: "an arithmetic oversight accommodated by a general fallback", rating the intended argument moderate); nothing says that a valid segment may lose its table; the code comment shows the count was meant to always fit; and the trigger is legal: Lucene's own monster tests build segments of that size. Verdict: a defect, with low priority because of the scale it needs.

One option was validated through gradle; the hunt validated a read-side-only variant by shadowing the class.

writeBitSet (both overloads) and flushBlockJumps return int; the comment and the @return javadoc say the count can be up to 32,769. A package-private helper decodes a stored count in createBlockSlice, createJumpTable and the constructor the public one delegates to: -1 and 0 still mean no table, -32,768 and -32,767 become 32,768 and 32,769 (today's writers store no other negative value; a corrupt or foreign value from -32,766 to -2 would decode to 32,770 to 65,534, so the fix relies on the checksummed metadata, or could also check the decoded count against the DISI length). The writers store (short) jumpTableEntryCount: Lucene90DocValuesConsumer, Lucene90NormsConsumer, OrdToDocDISIReaderConfiguration, and two test-only writers in backward-codecs that assigned the result to a short. +33/-18 lines in 6 files.

static int decodeJumpTableEntryCount(int jumpTableEntryCount) {
  return jumpTableEntryCount < -1 ? jumpTableEntryCount & 0xFFFF : jumpTableEntryCount;
}

Trade-offs

• No format change: the 16 bits on disk are the same as today, so segments already written in the 9.0+ formats get their table back once read by the fixed code.
• The return type of a public @lucene.internal method changes: binary incompatible for outside callers, and those that assign it to a short need a cast.
• The backward-codecs lucene80 copy, which reads 8.x-format segments, keeps the old behaviour; the same helper there would fix it too (not validated).

What the checks validated

• Gradle in a scratch worktree of 645d4fe14a20: without the fix the repro fails, and so do the hunt's three tests (the count check plus two consequence tests; 32,767 block seeks); with the fix all four pass, with assertions on and off (-Ptests.asserts=false): writeBitSet returns 32,768, and advance() and a sparse doc-values field written and read through Lucene90DocValuesFormat use the jump table again (at most 2 seeks).
• The closest suites pass: every class in codecs.lucene90 (TestIndexedDISI, TestLucene90DocValuesFormat and its MergeInstance and VariableSkipInterval variants, TestLucene90NormsFormat and its MergeInstance variant, and the rest), codecs.lucene95 and codecs.lucene99 (vector formats), TestDocValues, TestNorms and TestCheckIndex: 28 classes, 1,049 tests, 0 failures, 87 skipped. In backward-codecs, TestLucene92HnswVectorsFormat and TestLucene94HnswVectorsFormat, whose test writers changed: 116 tests, 0 failures, 6 skipped.
• ./gradlew :lucene:core:check -x test (google-java-format, ecj lint, forbidden APIs) and the backward-codecs format and ecj checks pass with the repro test in place. The full test suite was not run.
• Limits: the executed checks cover the 32,768-entry case (last doc in block 32,766) on the raw IndexedDISI and a sparse doc-values field. The 32,769-entry case (a real block 32,767, which shares its block number with the end block), norms and vectors were checked by reading the code only; no executed test covers 32,769 entries.

The same decode helper in IndexedDISI's readers; writeBitSet keeps returning short, so its @return javadoc would also have to say the value is an unsigned 16-bit count (that change is not in the hunt's sketch).

Trade-offs

Smallest change, no signature change, restores the table for existing and new segments. But the method keeps returning -32,768, so its documented contract has to change, and the minimal repro keeps failing.

What the checks validated

Hunt, main ea57360912ed, class shadowed: the two consequence tests pass (2 run, 0 failed) and TestIndexedDISI passes (15 run, 0 failed, 3 skipped).

Write and read the count with writeInt/readInt.

Trade-offs

Needs a new format version and back-compatible reading in three formats, for a value that already fits in 16 bits unsigned. Not tried.

Method: formal (the solver's own counterexample). A hunt unit modelled the IndexedDISI layout in Z3 4.12.2 bit-vector arithmetic (38 obligations) over doc ids below IndexWriter.MAX_DOCS.

• The obligation "the jump-table entry count survives the short return value" was SAT; z3 Optimize gave the smallest failing last doc id, 2,147,352,576 (= 32766 << 16, 32,768 entries, returned -32,768).
• Two more obligations proved (unsat) that every smaller last doc id keeps a correct count and that a lost count always reads back negative; by the code (:375, :392-393) a negative count disables the table, so it is never misread.
• The unit's bounded-exhaustive test on the stock jar flagged the same count mismatch on every set with more than 32,767 entries, and no read mismatch.
• A deterministic JUnit on the stock main jars then reproduced it through the public API, and through Lucene90DocValuesFormat on a SegmentInfo with maxDoc = IndexWriter.MAX_DOCS, so no 2^31 documents were indexed.