Index-sort merges misplace a NaN whose sign bit is set, so FLOAT/DOUBLE-sorted segments break their own sort

With IndexWriterConfig#setIndexSort on a SortField of type FLOAT or DOUBLE (values from FloatDocValuesField / DoubleDocValuesField), flush sorts documents with Float.compare / Double.compare, which put every NaN after +Infinity. Merges order documents by the keys of IndexSorter.FloatSorter/DoubleSorter.getComparableProviders, which since #13320 (9.11.0) are NumericUtils.sortableFloatBits / sortableDoubleBits of the raw stored bits. The doc-values fields store raw bits, so a NaN keeps its sign bit, and a NaN with the sign bit set gets a key below -Infinity. The merge interleaves already-sorted segments by a key that disagrees with their order, so the merged segment can end up in neither order: descending segments {3, 1, NaN} and {2, 0.5} merge to [2.0, 0.5, NaN, 3.0, 1.0]. CheckIndex's index-sort test (level 2 or higher) rejects the segment, and searches sorted by the index sort that terminate early return wrong top hits, also for queries that do not match the NaN document. The same for DOUBLE. Every release from 9.11.0 through 10.6.0 (10.6.0 by reading) and main; restoring the NaN canonicalization that #13320 removed fixes it.

• Index sort: IndexWriterConfig#setIndexSort keeps every segment physically sorted, "for all (flushed and merged) segments" (IndexWriterConfig.java:504). A search sorted by the index sort, or by a prefix of it, stops collecting a segment at the first document that cannot compete (TopFieldCollector.java:56-71, :91-112, :151-170).
• Sign-bit NaN: a NaN whose sign bit is set, raw bits 0xffc00000 (float) or 0xfff8000000000000 (double). Float.compare treats it like every other NaN: greater than +Infinity. Run-time negation of a NaN, Math.copySign(Float.NaN, -1f) and binary decoding produce it; text parsing does not.

1. FloatDocValuesField stores Float.floatToRawIntBits(value) (FloatDocValuesField.java:21, :40); DoubleDocValuesField stores doubleToRawLongBits (:21, :39). The sign bit survives.
2. Flush: IndexSorter.FloatSorter.getDocComparator uses Float.compare (IndexSorter.java:385; Double.compare at :449). The search comparator and CheckIndex.testSort use the same order.
3. Merge: MultiSorter.sort calls getComparableValues (MultiSorter.java:84), whose default adapts getComparableProviders (IndexSorter.java:147-150). FloatSorter.getComparableProviders returns NumericUtils.sortableFloatBits(valueBits) of the raw bits (:364; double sortableDoubleBits at :428).
4. sortableFloatBits(bits) is bits ^ (bits >> 31) & 0x7fffffff, with no NaN handling (NumericUtils.java:88-91). For 0xffc00000 it gives 0x803fffff (-2,143,289,345), below -Infinity's 0x807fffff (-2,139,095,041). A positive NaN (any payload) stays above +Infinity, so only sign-bit NaNs are misplaced; positive NaNs with different payloads get different keys, which Float.compare treats as equal, so that breaks no order. floatToSortableInt, the key before #13320, canonicalizes through floatToIntBits first (:70-72).
5. MultiSorter is a k-way merge whose inputs "must already be sorted by the same sort!" (MultiSorter.java:35-39); it only interleaves, taking each input's documents in their existing order (:118-136). Segment 1 arrives as [NaN, 3.0, 1.0], but the merge sees its head as the smallest key, so in a descending merge it takes 2.0 and 0.5 first: [2.0, 0.5, NaN, 3.0, 1.0]. Ascending, {1, NaN} + {0.5, 2, 3} give [0.5, 1.0, NaN, 2.0, 3.0].
6. Early termination trusts the order: for top 1 of a query without the NaN document, doc 0 (2.0) fills the queue, doc 1 (0.5) cannot compete, and 3.0 is never looked at. Here the hit count stays exact (4 hits); above the searcher's default 1,000-hit threshold, an early-terminated search reports a lower bound, with or without this bug.
7. CheckIndex.testSort ("This segment claims its documents are sorted according to the incoming sort ... let's make sure", CheckIndex.java:1219-1222) rejects the segment, but only at level 2 or higher (:1114, :1148). Level 1, the command-line default (:4673, :4748), reports the index clean, and a CheckIndex created in code without setLevel runs at level 0 (:499), which skips the test too.

• Who is exposed. Applications with an index sort on SortField.Type.FLOAT or DOUBLE (values from FloatDocValuesField / DoubleDocValuesField) that index a NaN with the sign bit set. Index sorting is opt-in; codec, merge policy and searcher are the defaults otherwise. A merge that involves the document (forceMerge or an ordinary background merge) can misorder the merged segment, depending on the segments' contents.
• How a sign-bit NaN arises (executed on JDK 25, aarch64): run-time negation -x of a NaN, in the interpreter (-Xint), with C1 and C2 (-Xcomp) and after warm-up (0xffc00000 / 0xfff8000000000000), for example an application that indexes -value to reverse an order; Math.copySign(Float.NaN, -1f); binary decoding that keeps bits, such as ByteBuffer.getFloat. Not a trigger: Float.parseFloat("-NaN") and Double.parseDouble("-NaN") (canonical NaN), the compile-time constant -Float.NaN (folded to 0x7fc00000), and on aarch64 0f/0f, inf - inf, sqrt(-1) and NaN * -1f.
• x86 (not executed). Intel documents that the default NaN of SSE arithmetic ("QNaN floating-point indefinite") has the sign bit set, so computed NaNs there may trigger it. No x86 host was used.
• Not affected. SortedNumericSortField over FloatField / DoubleField, which store floatToSortableInt / doubleToSortableLong and so canonicalize NaN at index time; INT, LONG, STRING and SORTED_SET sorts; the canonical NaN.
• Scale. 5 documents in 2 segments; deterministic (this doc's test failed in all 10 iterations). A bounded-exhaustive check of two flushed segments of 1-2 documents over {missing, sign-bit NaN, NaN, -Inf, -1, -0.0, 0.0, 1, +Inf} found 13,652 FLOAT and 13,620 DOUBLE order violations in 48,600 merges each and 4,976 wrong top-1 hits each; 0 without the sign-bit NaN and 0 with the fix. So 13,652 of the 17,496 FLOAT merges that contain a sign-bit NaN break the order, not all of them (a rate over the enumeration, not over real data). With three 400-document segments and one sign-bit NaN, all 20 early-terminated searches tried (4 queries, k from 1 to 200) differed from the full sort in a descending sort; in an ascending sort all 20 matched, although CheckIndex still rejected the merged segment.
• What you see. No error at merge or search time. Searches sorted by the index sort (or a prefix of it) can return wrong top hits, also for queries that do not match the NaN document; hit counts are not made wrong. CheckIndex at level 2 or higher condemns the merged segment; level 1, the command-line default, reports it clean. "Corrupt" here means a segment that breaks its declared sort: document contents, deletions and blocks are intact.
• It persists. A second forceMerge(1) with 500 more documents still fails CheckIndex level 2 (executed, stock code). A merge keeps each input's documents in their existing order, so two documents out of order inside a merged segment stay out of order in every later merge, with or without the fix, unless one is deleted (code reading; not executed with the fix). A code fix stops new damage only: segments already merged by 9.11.0-10.6.0 (10.6.0 by reading) need a reindex or a re-sort. CheckIndex -exorcise would drop the whole segment (1,500 of 1,500 documents in a probe).
• Downstream (read, not tested): Elasticsearch and OpenSearch reject non-finite float/double values at parse time and Elasticsearch index sorts use SortedNumericSortField; Solr's point fields write doc values through floatToIntBits / doubleToLongBits. No affected path was found there.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected:<[NaN, 3.0, 2.0, 1.0, 0.5]> but was:<[2.0, 0.5, NaN, 3.0, 1.0]>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:120)
       org.junit.Assert.assertEquals(Assert.java:146)
       org.apache.lucene.index.TestIndexSortMergeSignedNaN.testMergedSegmentFollowsIndexSort(TestIndexSortMergeSignedNaN.java:58)

• Contracts. IndexWriterConfig#setIndexSort: "Set the Sort order to use for all (flushed and merged) segments." (IndexWriterConfig.java:504). IndexSorter.ComparableProvider#getAsComparableLong: "Returns a long so that the natural ordering of long values matches the ordering of doc IDs for the given comparator" (IndexSorter.java:57-62). MultiSorter.sort: "The documents for each incoming leaf reader must already be sorted by the same sort!" (MultiSorter.java:35-39). NumericUtils.floatToSortableInt, the merge key before #13320: "The sort order (including Float#NaN) is defined by Float#compareTo; NaN is greater than positive infinity." (NumericUtils.java:61-66; double at :37-43). CheckIndex.testSort, Lucene's own integrity check, rejects the merged segment.
• Lucene decided this order. LUCENE-3582 (#4656, 2011) fixed the same kind of defect in NumericUtils: raw bits made sign-bit NaNs sort before -Infinity; the fix canonicalized through floatToIntBits / doubleToLongBits and added TestNumericUtils cases with sign-bit NaNs (0xff800001, 0xffffffff, 0xfff0000000000001L, 0xffffffffffffffffL) that must sort above +Infinity; they are still on main (TestNumericUtils.java:280-302, :343-365). LUCENE-4937 (#6001, 2013) moved the comparators to Float.compare / Double.compare ("Fix incorrect sorting of float/double values (+/-0, NaN)").
• History. #13320 "Remove unnecessary bit conversion for IndexSorter" (by @bugmakerrrrrr, merged by @jpountz on 2024-05-14) (its title presents the conversion as unnecessary) replaced floatToSortableInt(Float.intBitsToFloat(bits)) with sortableFloatBits(bits) and the double equivalent; the two differ exactly for non-canonical NaNs. The PR has the empty description template, no reviews, no test change and no CHANGES entry; nobody discussed NaN.
• Upstream tests. No test indexes a NaN as an index-sort value; TestIndexSorting draws floats and doubles in [0, 1) (TestIndexSorting.java:2481-2557). With the fix the whole core suite passes, so no test pins the current behaviour.
• Trigger legality. Public API only. FloatDocValuesField / DoubleDocValuesField accept any value and document that they store raw bits; neither setIndexSort nor SortField restricts NaN. Where Lucene does not support NaN, it says so or rejects it: scores are documented as invalid and asserted, and FloatRange / DoubleRange and XYDocValuesField throw.
• Precedent. LUCENE-8592 (#9638, 2018): the merge order differed from the index sort for MIN_VALUE with a reverse sort; upstream treated it as index corruption, with a CHANGES note that CheckIndex detects affected indices.

The strongest case for "intended or unsupported" (built by the devil's advocate and by a reviewer from another model family, OpenAI GPT-5.6, with a works-as-designed lens): IEEE 754 NaN is unordered and Java says NaN has no sign, so the order of exotic NaN bit patterns is unspecified; SortField.Type.FLOAT only says "lower values are at the front"; the doc-values fields store raw bits on purpose, so ordering raw bits is consistent; a committer merged #13320; in the LUCENE-3582 thread one participant said Lucene does not really support NaN as a value; and the recorded searches found no public report in the more than two years since 9.11.0 (tagged 2024-06-06).

Why it fails: Lucene does specify the order (flush, search and CheckIndex all use Float.compare; the floatToSortableInt javadoc puts NaN after +Infinity; LUCENE-4937 made it a bug fix), and LUCENE-3582's tests cover sign-bit NaNs specifically; the LUCENE-3582 fix was committed despite that remark. The merge contract is to match the comparator, not the bits, and the repro's merged output follows no order at all, misordering ordinary values too. #13320's title presents the conversion as unnecessary, and the PR never considers NaN. A plain -x produces the value. What still weighs on the other side: no javadoc says in so many words that NaN is a supported index-sort value, and a maintainer could say that applications should sanitize raw binary floats (the doc's cross-model fact check, OpenAI GPT-5.6, rates that case moderate, "NaN is not a supported sort value" weak as an account of today's code but moderate as a future policy, and the -x case weak); neither explains why flush, search and CheckIndex use one order and the merge another. The likely maintainer reply is "real but rare, low priority, restore the canonicalization", not "by design"; no source supports by design. The GPT-5.6 reviewer rated the intended case weak; the devil's advocate found no argument that outweighs the contracts.

Option A was validated in a scratch worktree at ea57360912ed (removed afterwards); B and C were not run. Until a fix ships, users can canonicalize NaN before indexing (the workaround; the test's canonical-NaN control shows it merges correctly).

In FloatSorter / DoubleSorter.getComparableProviders, encode through floatToSortableInt / doubleToSortableLong, which go through floatToIntBits / doubleToLongBits and so map every NaN to the canonical NaN above +Infinity. This restores the 9.10.0 merge keys.

-              return NumericUtils.sortableFloatBits(valueBits);
+              // canonicalize NaN like Float.compare (used at flush time) does
+              return NumericUtils.floatToSortableInt(Float.intBitsToFloat(valueBits));
...
-              return NumericUtils.sortableDoubleBits(valueBits);
+              // canonicalize NaN like Double.compare (used at flush time) does
+              return NumericUtils.doubleToSortableLong(Double.longBitsToDouble(valueBits));

Trade-offs

One NaN canonicalization per merge key (the intBitsToFloat round trip is a reinterpretation). No benchmark was run. It changes only the key used while merging: stored values keep their raw bits, as the doc-values fields document. It prevents new damage only: segments already merged by 9.11.0-10.6.0 (10.6.0 by reading) stay misordered and need a reindex or a re-sort; a CHANGES entry should say so, and that CheckIndex at level 2 or higher finds them.

What the checks validated

• Through gradle at ea57360912ed: this doc's test fails 4 of 5 on stock (assertions on and off) and passes 5 of 5 with the fix (on and off).
• With the fix: TestIndexSorting (62 tests), TestSortingCodecReader (3), TestNumericUtils (24), TestCheckIndex (9), the TestSort* and TestTopFieldCollector* classes and this test: 15 classes, 241 tests, 0 failures; the whole :lucene:core:test: 8,870 tests, 0 failures, with assertions on (322 skipped) and off (325 skipped); :lucene:core:check -x test (checkGoogleJavaFormat, ecjLint, forbiddenApis) successful. The suite runs used the test before a formatting-only edit; the repro and check runs used the final file.
• Earlier steps: the finder's repro, the independent reproducer's 9 tests, the reviewers' tests, the security probe and the bounded-exhaustive check (0 violations in 48,600 merges each for FLOAT and DOUBLE) pass with the same patch as a shadow class.

Store floatToIntBits / doubleToLongBits in FloatDocValuesField / DoubleDocValuesField.

Trade-offs

Changes their documented raw-bits storage for every user, does nothing for values written by older versions or by other producers of NUMERIC doc values, and leaves the merge key inconsistent with its contract. Not recommended on its own. Not run.

Make getDocComparator order by sortableFloatBits of the raw bits.

Trade-offs

Flush and merge would agree, but the search comparator and CheckIndex.testSort use Float.compare, so early termination would still return wrong hits. Not viable. Not run.

Canonicalize before indexing: if (Float.isNaN(v)) v = Float.NaN; (and Double.NaN for doubles). Reindex indexes that already hold sign-bit NaNs.

Trade-offs

Needs a change in every application that can produce such values; does not repair merged segments.

What the checks validated

The test's canonical-NaN control merges correctly on stock main (5 runs: it passes every time).

Method: code reading (a hunt unit, sorted search and index-sort early termination, 2026-10-26), while setting up a bounded-exhaustive check of the contract that early termination presumes: every segment really is in index-sort order.

• The finder compared, for every IndexSorter that SortField uses, the flush-time getDocComparator with the merge-time getComparableProviders, and saw that the FLOAT/DOUBLE merge keys (sortableFloatBits / sortableDoubleBits of raw bits) differ from Float.compare / Double.compare only for NaNs with the sign bit set.
• It confirmed this with a public-API JUnit on the stock main jars, CheckIndex at level 3 and a release bisection (9.10.0 passes, 9.11.0 fails).
• A bounded-exhaustive merge-order check written afterwards (two flushed segments of 1-2 documents over {missing, sign-bit NaN, NaN, -Inf, -1, -0.0, 0.0, 1, +Inf}, every FLOAT/DOUBLE SortField variant, order checked with the search comparator as CheckIndex does) showed that the sign-bit NaN is the only value in that domain that breaks the order; INT, LONG, sorted-numeric FLOAT/DOUBLE, STRING and SORTED_SET gave 0 violations.
• Then: a refute review by an independent reviewer from another model family (OpenAI GPT-5.6, with its own executed test), an independent reproducer, a GPT-5.6 "works as designed" review with local re-runs, a devil's advocate with a reachability probe, an adjudication with fresh-seed re-runs, a per-release history sweep, a prior-report search, a security assessment and probe, and this doc's own test and fix validation. No model checker or prover was involved.