INT index sorts merge by the full 64-bit value, so out-of-int-range values leave merged segments out of order

With IndexWriterConfig#setIndexSort on a SortField (or SortedNumericSortField) of type INT, three code paths order documents. Flush (IndexSorter.IntSorter#getDocComparator) and the search-time IntComparator, which CheckIndex's index-sort test also uses, compare (int) longValue(), the low 32 bits. The merge key, IntSorter#getComparableProviders, returns the full values.longValue(). NumericDocValuesField and SortedNumericDocValuesField accept any long and IndexWriter checks only the doc-values type of index-sort fields, so a value outside the int range is accepted, and for it the merge interleaves already-sorted segments by a key that can disagree with their order: the merged segment is out of order whenever the full-long and INT orders of the documents differ across the segments being merged. Segments [a = 2^32] and [b = 1, c = 2] merge to b, c, a instead of a, b, c: CheckIndex at level 2 or higher rejects the segment and searches sorted by the index sort return wrong top hits. The merge-time cast existed from 6.2.0 to 8.1.1; LUCENE-8900 (8.2.0) dropped it. Every release from 8.2.0 to 10.6.0 and main is affected (11 releases and main executed, the rest, 10.6.0 included, by code reading or branch inference); restoring the one-line cast fixes it.

• Index sort: IndexWriterConfig#setIndexSort keeps "all (flushed and merged) segments" sorted (IndexWriterConfig.java:504). A search sorted by the index sort, or by a prefix of it, can stop collecting a segment at the first non-competitive document (TopFieldCollector.java:59, :92-111, :152-171).
• INT key: for SortField.Type.INT, a doc value counts as (int) value, its low 32 bits, sign-extended. 2^32 = 4,294,967,296 counts as 0; 3,000,000,000 counts as -1,294,967,296.
• Merge key: a merge of index-sorted segments is a k-way merge (MultiSorter). An INT sort supplies one long per document (through getComparableValues, MultiSorter.java:84), and "the natural ordering of long values" must match the sort's comparator (IndexSorter.java:57-63).

1. NumericDocValuesField and SortedNumericDocValuesField take a 64-bit long. For index-sort fields IndexWriter checks only the doc-values type (IndexingChain.java:1635), not the range, so 2^32 under an INT sort is accepted.
2. Flush sorts with values[docID] = (int) dvs.longValue() and Integer.compare (IndexSorter.java:249, :252). The search comparator reads (int) docValues.longValue() (IntComparator.java:81), and CheckIndex.testSort uses the search comparators (CheckIndex.java:1241).
3. The merge key of IntSorter#getComparableProviders is return values.longValue(); with no cast (IndexSorter.java:228). The sibling FloatSorter, also a 32-bit sorter over NUMERIC doc values, narrows with (int) at merge and at flush (:363, :382).
4. MultiSorter takes each segment's documents in their existing order and only interleaves the segments by the merge key (MultiSorter.java:35-39, :89-102, :118-136). Segment 2 is [b = 1, c = 2], segment 1 is [a = 2^32]; the keys 1 and 2 are below 4,294,967,296, so the merged segment is b, c, a. With the segments in the other order the keys already look sorted and the merge concatenates them: b, c, a again.
5. A search sorted by the index sort sees b first, finds c not competitive and skips the rest of the segment (TopFieldCollector.java:92-111), so a, the INT minimum, is never compared. This happens with any totalHitsThreshold, including Integer.MAX_VALUE.

• Who is at risk. Indexes with an INT index sort whose doc values hold a value outside [Integer.MIN_VALUE, Integer.MAX_VALUE]. Such a value is necessary but not sufficient: a merge goes wrong only when the full-long and INT orders of the documents differ across the segments being merged. That takes a type mismatch: 64-bit data in a field whose sort was declared INT. IntField always stores ints. The experimental columnar IndexWriter#addBatch with a LongColumn of NumericKind.INT reaches the same misorder.
• Opt-in. Index sorting is off by default, and in-range values are unaffected.
• Any merge. Background merges and forceMerge both go through MultiSorter.sort, which orders such a document by its full value; whenever that differs from its INT order, the merged segment is out of order. One document and two segments suffice; deterministic with assertions on and off, ascending and reverse.
• Silent at write time. No exception at addDocument, flush, merge or commit, and flush and search agree on the low 32 bits, so the index looks right until a merge.
• Persistent. The merged segment violates its declared sort until a reindex, also after a code fix. CheckIndex at level 2 or higher rejects it; level 1, the command-line default, and a CheckIndex built in code without setLevel do not run the check. Up to 8.10.x CheckIndex records the error but still reports clean=true.
• Wrong top hits. Searches sorted by the index sort, or a prefix of it, return wrong top hits with any hit-count threshold. Every hit still matches the query; document contents and deletions are intact.
• Rare. No report in about seven years; the registry rates likelihood rare.
• Not checked: whether IndexSortSortedNumericDocValuesRangeQuery, which reads (int) topValue and relies on segment order, returns a wrong hit set on such a segment. Also not checked: the skip-index path of sorted search. For a field with a doc-values skip index (NumericDocValuesField.indexedField, which also accepts any long), NumericComparator can build a competitive iterator whose INT bounds come from the int bottom value but are compared with the skipper's raw long block ranges, without narrowing; whether that skips competitive documents with out-of-range values was not run.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => org.junit.ComparisonFailure: expected:<[abc]> but was:<[bca]>
       org.junit.Assert.assertEquals(Assert.java:117)
       org.junit.Assert.assertEquals(Assert.java:146)
       org.apache.lucene.index.TestIntIndexSortMergeOrder.testMergeKeepsIntSortOrder(TestIntIndexSortMergeOrder.java:52)

• Contracts. IndexWriterConfig#setIndexSort: "Set the Sort order to use for all (flushed and merged) segments." ComparableProvider#getAsComparableLong: "Returns a long so that the natural ordering of long values matches the ordering of doc IDs for the given comparator"; for IntSorter that comparator orders by (int). MultiSorter.sort: the inputs "must already be sorted by the same sort!"
• History. LUCENE-6766 (6.2.0) compared (int) values at merge; LUCENE-7407 (7.0.0) and LUCENE-8592 (7.6.0) kept the cast. LUCENE-8900 "Simplify MultiSorter" (#9943, 8.2.0, 2019) moved case INT: under case LONG: and deleted the INT branch with its cast. Its thread says "I merged the logic for integers and longs"; nobody mentions the narrowing. There is no CHANGES entry. In the 8.2.0 jars, swapping in only the pre-change MultiSorter.java, or the changed one plus the one-line cast, makes every test pass.
• The other INT ordering paths read the low 32 bits: flush, the value comparison of IntComparator, CheckIndex, IndexSortSortedNumericDocValuesRangeQuery; and the 32-bit FLOAT sorter narrows at merge and at flush, so a FLOAT index sort over a long with high bits set merges in order. (The skip-index competitive iterator of sorted search compares raw long block ranges; it was not run.)
• Tests. TestIndexSorting uses only int-domain values for INT sorts; with the fix it passes 62 of 62.
• Precedent. Upstream treated accepted input that leaves an index-sorted segment failing CheckIndex as a bug: LUCENE-8592 (#9638, "a bad bug ... only a reindex can restore the correct sort order"), LUCENE-7581 and LUCENE-8441.

The strongest case for "caller error": SortField.Type.INT says "Sort values are Integer" and "Fields must either be not indexed, or indexed with IntPoint"; IntField cannot produce such a value; no upstream test uses one; LUCENE-8900 meant to change nothing for int-range values, where long order equals int order. "You stored longs, sort with LONG." reviewers from another model family (OpenAI GPT-5.6), reading code without running it, said not real with medium confidence on this argument alone; both agreed with the root cause. They read main at ea57360912ed, where IndexSorter.java and MultiSorter.java are identical to a9779ef3c193. A maintainer may also read the bug as missing validation of an out-of-domain INT value; a 2011 issue, #4265 (LUCENE-3192, the old search-time doc-values API), already called SortField.INT over long-valued doc values an inconsistency.

Why it fails: IndexWriter accepts the value without a check. Accepting 64-bit storage does not by itself define what an INT sort means for every value, but flush, the search comparator and CheckIndex all order it by the low 32 bits; of the paths that decide document order, only the merge disagrees. The result is not a consistent "garbage" order but a segment Lucene's own CheckIndex rejects and its own search reads wrongly; 6.2.0 to 8.1.1 produced the consistent truncated order. The cast was the original design and was removed without discussion in a simplification. The argument bears on the fix (restore the cast, or reject such values at index time) and on severity, not on whether merge contradicts flush. Verdict: not intended, a defect (the independent reproduction, the intended-behaviour check and the adjudication).

Option A was validated in a scratch worktree at a9779ef3c193 (removed afterwards); B and C were not run. Until a fix ships, users can sort 64-bit fields with Type.LONG, or keep INT-sort values in the int range.

In IntSorter#getComparableProviders return (int) values.longValue(), the same low-32-bit key that flush, IntComparator and CheckIndex use, as from 6.2.0 to 8.1.1 and as FloatSorter does. A short comment ("INT sorts compare the low 32 bits, like getDocComparator") would help the next reader.

--- a/lucene/core/src/java/org/apache/lucene/index/IndexSorter.java
+++ b/lucene/core/src/java/org/apache/lucene/index/IndexSorter.java
@@ -225,7 +225,7 @@ public interface IndexSorter {
         providers[readerIndex] =
             docID -> {
               if (values.advanceExact(docID)) {
-                return values.longValue();
+                return (int) values.longValue();
               } else {
                 return missingValue;
               }

Trade-offs

Keeps accepting out-of-range values silently, now with consistent low-32-bit semantics, so the application still does not hear about its type mistake. One narrowing per merge key; no benchmark was run. It prevents new damage only: segments already merged by 8.2.0 or later stay misordered and need a reindex; a CHANGES entry should say so, and that CheckIndex at level 2 or higher finds them.

What the checks validated

• Through gradle at a9779ef3c193: this doc's test fails 5 of 7 on stock (assertions on and off) and passes 7 of 7 with the fix (on and off).
• With the fix: 15 classes and 245 tests of the index-sort, sort and CheckIndex suites (TestIndexSorting, TestSortingCodecReader, TestCheckIndex, TestIndexSortSortedNumericDocValuesRangeQuery, the TestSort* and TestTopFieldCollector* classes and this test); the whole :lucene:core:test (8,896 tests, 0 failures, with assertions on and off); :lucene:core:check -x test (google-java-format, ecj lint, forbidden APIs) passes with the test.
• Earlier, with the same line as a shadow class: the finder's 5 tests, the independent reproducer's 8 tests, upstream TestIndexSorting (62 tests) and the audit's 13 tests pass; in the 8.2.0 jars the same one-line restore makes every test pass.

Throw IllegalArgumentException at addDocument / updateDocument (and in the columnar path) when an INT index-sort field gets a value outside the int range, next to the existing doc-values type check in IndexingChain.

Trade-offs

Loud, and closer to "Sort values are Integer". But it adds a per-value check on the indexing path of sort fields, makes applications that index such values today start failing, and does nothing for segments written by older versions, which a merge would still misorder. Best combined with the cast, not instead of it. Not run.

Order INT sorts by the full 64-bit value everywhere.

Trade-offs

For in-range values nothing visible changes (int and long order coincide), but every existing INT-sorted segment that holds an out-of-range value whose (int) order differs from its full-long order was flushed by (int), and would then fail CheckIndex and break early termination. It also changes what an INT sort means for such values at search time. Not viable as the fix. Not run.

Use SortField.Type.LONG (or SortedNumericSortField with Type.LONG) for fields that hold 64-bit values, or keep INT-sort values inside the int range. An existing index cannot change its index sort ("cannot change previous indexSort="), so switching means a reindex, which also repairs merged segments.

Trade-offs

Needs an application change and a reindex; does not repair merged segments in place.

What the checks validated

The in-range control of this doc's test merges correctly on stock main.

The hunt unit ran a bounded-exhaustive, model-based test of index sorting at flush and merge (13 sort types, document blocks, rejected documents). Writing its reference comparator meant pairing, for every IndexSorter, the flush-time DocComparator, the merge-time ComparableProvider and the search comparator. The INT row was the only one whose merge key does not narrow to (int); FLOAT and DOUBLE differ only for sign-bit NaNs, a sibling bug. The exhaustive runs did not find it themselves, because all their keys are inside the int range. A public-API JUnit on the stock main jar confirmed it.