Doc-values range queries with a skip index return wrong hits when a segment's values span more than Long.MAX_VALUE

The default codec stores a numeric doc value as (v - min) / gcd. When one segment's values span more than Long.MAX_VALUE and the segment is neither table- nor block-encoded, it uses gcd 1 and 64 bits per value, and the stored v - min of the upper values wraps to negative longs; reading one value wraps back and is right. #16160 and #16285 (10.6.0 development) changed the bulk rangeIntoBitSet of the Lucene90 doc-values producer to compare stored values with signed comparisons against shifted query bounds, saturating a shift above Long.MAX_VALUE to Long.MAX_VALUE. Wrapped values then never match, and Long.MAX_VALUE can itself be a stored value. With the opt-in doc-values skip index (NumericDocValuesField.indexedField, SortedNumericDocValuesField.indexedField), newSlowRangeQuery routes every block the skip index cannot decide through that method, so count, search(q, n) and FILTER clauses return wrong hits: 2,048 evenly spaced latitudes, [45, 90], count 0 instead of 512; 100,000 random latitudes, 0 instead of 25,157; 100,000 random 64-bit hashes, [0, Long.MAX_VALUE], 2 instead of 49,931; hand-picked values add hits. No error, and CheckIndex is clean. 10.5.2 decoded before comparing and is right; an index written by 10.5.2 returns 0 once opened with the 10.6.0 RC1 commit. kkewwei reported and fixed it publicly in open PR #16896 (2026-10-23); costin, who wrote the two introducing PRs, commented on it and suggested gating on the encoding. The study's three-part fix does that and also removes the Long.MAX_VALUE sentinel for an overflowing lower bound; it passes the test and 14 doc-values suites.

• Stored value: what the codec writes per document, (v - min) / gcd packed in a fixed number of bits per value (Lucene90DocValuesConsumer.java:553). With 64 bits per value and gcd 1 it is a plain 64-bit subtraction that can wrap.
• Encoded-domain range check: since #16160, rangeIntoBitSet maps the query bounds into the stored domain once (transformGcdBounds, Lucene90DocValuesProducer.java:550-563) and compares stored values directly, which lets a SIMD kernel run without decoding.
• Skip index: per-block min/max values (DocValuesSkipper), enabled by NumericDocValuesField.indexedField, SortedNumericDocValuesField.indexedField or DocValuesSkipIndexType.RANGE.

1. Writer. Lucene90DocValuesConsumer.java:417-422 resets gcd to 1 for values outside [MIN/2, MAX/2]; :511 uses DirectWriter.unsignedBitsRequired((max - min) / gcd), which is 64 when max - min overflows; :553 writes (v - min) / gcd. Needs more than 256 distinct values (:434-435, else table encoding) and no block split (:505-507).
2. Per-value read is right. mul * values.get(doc) + delta (Lucene90DocValuesProducer.java:1040) wraps back to v.
3. Bulk read. The dense gcd/delta override (:1066-1076) calls rangeGcdDeltaIntoBitSet (:569-583) -> transformGcdBounds (:550-563): saturatingShiftLower/Upper (:585-616) return Long.MAX_VALUE when the shifted bound would be above it (needs delta < 0, as with latitudes) and Long.MIN_VALUE when it would be below Long.MIN_VALUE (:598, :614), the lower bound is clamped to 0, and the kernels compare signed (DefaultDocValuesRangeSupport.java:39-41; PanamaDocValuesRangeSupport.java:57, 106-107). The helpers' javadoc: "Stored values are non-negative" (:588-589).
4. Both directions. A wrapped (negative) stored value never passes the lower bound (>= 0): missing hits. An overflowing lower bound becomes Long.MAX_VALUE (or ceilDiv(Long.MAX_VALUE, gcd)), and a document stored exactly there matches: extra hits.
5. Sorted numeric. hasGcdEncoding (:2019-2023) sends dense (:2095-2105, SIMD :2116) and sparse (:2226-2240) sorted-numeric fields to the same transform.
6. Queries. With a skipper, DocValuesRangeIterator.forRange builds a bulk iterator (DocValuesRangeIterator.java:49-60) whose MAYBE blocks call rangeIntoBitSet (:355-367, :447-453, sorted numeric :478-484). count collects through it at any size, search(q, n) from maxDoc >= 2048 (ConstantScoreScorerSupplier.java:81-92); nextDoc() iteration of the same query is right.

The minimal repro in numbers (executed probe on main): min = sortable(-89.956), max = sortable(+89.956), span about 9.27e18; 64 bits per value, gcd 1; 1,023 stored values are negative, including all 512 in [45, 90]; the skip index has one MAYBE block; transformGcdBounds returns [Long.MAX_VALUE, Long.MAX_VALUE]; no stored value equals it; 0 hits.

Variants (executed). In the tested latitude grids count is first wrong at 257 distinct values (256 or fewer use table encoding) and search(q, 10) first loses its hits at 2,048 docs per segment; at 5,000 docs count is 904 of 1,247 because the second 4,096-doc skip block lies fully inside [45, 90], while search(q, 10) still returns 10 hits and only count and totalHits are wrong. Values {-10, MAX - 10, MAX, 3000, ...} with [MAX - 5, MAX - 1] count 1 instead of 0. SortedNumericDocValuesField is affected single-valued (dense) and multi-valued (dense and sparse). Not affected: sparse single-valued numeric fields (per-doc default), and so sparse single-valued sorted numeric, which the producer wraps as a singleton of numeric values and the query unwraps (Lucene90DocValuesProducer.java:2002-2003, SortedNumericDocValuesRangeQuery.java:138; by reading); table- or block-encoded fields; spans below Long.MAX_VALUE; fields without a skip index at query level (direct rangeIntoBitSet callers are still wrong). At a span of exactly Long.MAX_VALUE only direct rangeIntoBitSet calls go wrong: the top stored value equals the saturated lower bound, so a range above the segment's max sets one spurious bit (study tests testDenseNumericSentinelApiOnly and testDenseNumericGcdSentinel), while the skip index prunes the block at query level.

• Default or opt-in. Default codec; the skip index is opt-in. LongField, DoubleField and plain NumericDocValuesField do not enable it. Direct callers of the public NumericDocValues#rangeIntoBitSet get wrong bits even without a skip index (executed); SortedNumericDocValues#rangeIntoBitSet runs the same transform with or without one (by reading).
• Effect. Silent wrong results, mostly missing hits (0 of 512, 0 of 25,157, 2 of 49,931), occasionally extra hits on hand-picked values. count, search(q, n) and FILTER clauses are all affected. No exception; the index is not corrupt, so CheckIndex cannot see it.
• Data shape. For a symmetric range +/-x of sortable doubles the span exceeds Long.MAX_VALUE exactly when x >= 2; ordinary latitudes and longitudes qualify. Float fields (sortable ints) cannot. Non-negative longs never span more than Long.MAX_VALUE, and epoch timestamps of realistic dates span far less (epoch nanoseconds would need values more than about 292 years apart); nothing in the code exempts timestamps.
• Scale. In the tested latitude grids, count was first wrong at 257 distinct values per segment and search(q, 10) first lost its hits at 2,048 documents; a segment also needs the wide span, the 64-bit gcd/delta encoding, a dense field if single-valued, and a skip block only partly inside the range.
• Existing indexes. The defect is in the reader: an index written by 10.5.2 counts 0 instead of 25,157 when opened with the 10.6.0 RC1 commit, with no reindex.
• Releases. 10.6.0 was released on 2026-10-29 from RC1, which has the bug. Priority high because the released 10.6.0 has it.

The data, codec and query are fixed; the seed only picks the test framework's random directory, locale and settings, which the test does not depend on (seeds 1 and 2 and 10 iterations also fail). It fails with the Panama and the scalar vector provider, and compiles unchanged against 10.5.2, where it passes. 2,048 documents is the smallest segment for which search(q, 10) goes wrong too; count alone is wrong from 257 distinct values.

cp $REPRO/TestSkipIndexedDocValuesRangeWideSpan.java $LUCENE/lucene/core/src/test/org/apache/lucene/search/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.search.TestSkipIndexedDocValuesRangeWideSpan -Ptests.seed=DEADBEEF -Ptests.asserts=true
# also with -Ptests.asserts=false

TestSkipIndexedDocValuesRangeWideSpan > testLatitudeRangeQuery FAILED
    java.lang.AssertionError: count(q); search(q, 10) returned 0 hits expected:<512> but was:<0>
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:65FF88D8F9C7AA0]:0)
        ...
        at org.apache.lucene.search.TestSkipIndexedDocValuesRangeWideSpan.testLatitudeRangeQuery(TestSkipIndexedDocValuesRangeWideSpan.java:68)
:lucene:core:test (FAILURE): 1 test, 1  failure

# the same with -Ptests.asserts=false; standalone runner on main and on the 10.6.0 RC1 commit with -ea and -da
# 10.5.2: 1 test, 0 failures (-ea, -da)
# with the recommended fix: :lucene:core:test (SUCCESS): 1 test

• Contracts. NumericDocValuesField.java:91-92 (newSlowRangeQuery), :51-58 (indexedField, "the specified 64-bit long value"); NumericDocValues.java:113-140 (rangeIntoBitSet: "the doc IDs in [fromDoc, toDoc) whose values are in [minValue, maxValue]", default per-doc advanceExact/longValue); IndexSearcher.java:491 (count).
• Regression. 10.5.2 runs the same skip-index query path but decodes first ("Per-doc evaluation for gcd/delta encoded fields", Lucene90DocValuesProducer.java:966-972 at 10.5.2) and passes.
• An unstated premise that fails at 64 bits. The writer lines that produce wrapped 64-bit stored values are unchanged in 10.0.0, 10.5.2, RC1 and main; the gcd reset dates from LUCENE-4936 (2013). The helpers assume "Stored values are non-negative" (Lucene90DocValuesProducer.java:588-589).
• The authors treat it as a bug. kkewwei filed #16896 as a fix; costin commented on it on 2026-10-28: "Stored values only go negative when bitsPerValue == 64 so keep the saturating helpers for narrower fields and use the decoded path only for 64-bit ones."
• Why tests missed it. Existing tests use small positive deltas or values from [0, domain]; 260 nearby tests pass on unpatched main.

Strongest case: the helper javadoc states its assumption ("Stored values are non-negative"), and in the #16160 review costin wrote that with the saturating helpers "the per-doc decoded fallback is provably unreachable, so I removed it" (2026-06-15, answering salvatore-campagna's question about open bounds). So spans over Long.MAX_VALUE could be read as knowingly outside the optimisation's design; the skip index is opt-in and the code new in 10.6.0.

Why it fails: that proof covered bound overflow under an unstated premise, that stored values are non-negative, which fails for 64-bit packed values. No javadoc limits users to spans of Long.MAX_VALUE, the writer produces such segments for ordinary latitudes, the same query was right in 10.5.2, and the introducing author suggested an encoding-based gate for the fix in a comment on #16896. Opt-in lowers the priority, not the bug.

Two fixes were built and run in a scratch worktree of 645d4fe14a20; a third (revert) was not built. Option A follows the encoding gate costin suggested on #16896; option B is that PR.

The study's three-part fix: (a) transformGcdBounds returns null (empty) when minValue - delta overflows upward; (b) the dense numeric gcd/delta rangeIntoBitSet runs the 10.5.2 decoded loop when bitsPerValue == 64; (c) hasGcdEncoding also requires bitsPerValue < 64, so sorted numeric uses decoded values. (b) and (c) are the gate costin suggested in a comment on #16896; (a) closes a narrower collision on gcd > 1 fields stored with fewer than 64 bits per value, where ceilDiv(Long.MAX_VALUE, gcd) can be a stored value. At query level the skip index prunes that case, so it shows only through direct rangeIntoBitSet calls.

   private static long[] transformGcdBounds(long minValue, long maxValue, long mul, long delta) {
     assert mul > 0;
+    if (delta < 0 && minValue > Long.MAX_VALUE + delta) {
+      // minValue - delta overflows: no stored value can reach the lower bound. Do not saturate to
+      // Long.MAX_VALUE here, since Long.MAX_VALUE (or ceilDiv(Long.MAX_VALUE, mul)) can itself be
+      // a stored value.
+      return null;
+    }
@@ ... @@
+                if (entry.bitsPerValue == 64) {
+                  // with 64 bits per value, the stored v - min can exceed Long.MAX_VALUE and read
+                  // back as a negative long: compare decoded values instead
+                  for (int d = fromDoc; d < toDoc; d++) {
+                    long v = mul * values.get(d) + delta;
+                    if (v >= minValue && v <= maxValue) {
+                      bitSet.set(d - offset);
+                    }
+                  }
+                  return;
+                }
                 Lucene90DocValuesProducer.rangeGcdDeltaIntoBitSet(
@@ ... @@
             && entry.table == null
+            && entry.bitsPerValue < 64 // 64-bit stored values can wrap: compare decoded values
             && (entry.gcd != 1 || entry.minValue != 0);

Trade-offs

• DirectWriter rounds 57-64 required bits up to 64 (DirectWriter.java:230-235), so every field whose stored values need more than 56 bits (with gcd 1, a span of 2^56 or more), not only spans over Long.MAX_VALUE, goes back to the 10.5.x decoded loop and loses the #16160/#16285 speedup. Narrower fields keep the encoded path, including saturated open bounds such as [Long.MIN_VALUE, t] on timestamps, #16160's stated goal. No benchmark was run.
• A variant could keep the SIMD kernel for 64-bit fields by running it on a decoding LongValues wrapper, as #16896 does (not built).

What the checks validated

• Stock + test: fails with assertions on and off; + fix: passes with assertions on and off.
• + fix: 14 suites, 738 tests (66 skipped), 0 failures, assertions on and off: TestSkipIndexedDocValuesRangeWideSpan, TestSkipBlockRangeIteratorBitSetOperations, TestDocValuesRangeIteratorIntoBitSet, TestDocValuesRangeIterator, TestSortedNumericDocValuesRangeIterator, TestDocValuesQueries, TestIndexSortSortedNumericDocValuesRangeQuery, TestIndexOrDocValuesQuery, TestBulkScorerConsistency, TestSortedSkipperScorerSupplier, the three TestLucene90DocValuesFormat* suites, TestCheckIndex; :lucene:core:check -x test passes.
• With the patched file shadowed, the study's 11 tests (false-positive sentinels, gcd 7 and 454279, sorted numeric dense, sparse and variable cardinality, 100k latitudes and hashes) pass with assertions on and off; 10 of 11 fail without it.
• Earlier, on branch_10_6 d04ee73177, the same three changes passed 5 regression tests and 3,803 package tests; removing (a) leaves the gcd = 454279 test failing. Z3 shows the transform with (a) correct for gcd == 1 at up to 63 bits per value and for gcd > 1 (a model, not the Java). Not run: the full test suite, nightly tests, benchmarks.

Removes the saturating helpers; if minValue - delta or maxValue - delta overflows, runs the kernel on decoded values, else uses exact encoded bounds (+30/-40, head ab6a77d35e94, applies cleanly to 645d4fe14a20). Built and run: the test and the same 14 suites (738 tests) pass with assertions on.

Trade-offs

Correct, but, as costin pointed out on #16896, the check is per query: common open-ended ranges such as ts <= x ([Long.MIN_VALUE, x] on a field with a positive minimum) also leave the encoded path. Its test covers the API only, not query-level count, the false-positive sentinels or sparse sorted numeric.

What the checks validated

• Test and 14 suites pass (gradle, assertions on); the candidate's standalone shadow run passes with assertions on and off.

Restores the 10.5.x per-document decoded check on branch_10_6.

Trade-offs

Simplest to reason about under release pressure, but drops the speedup for every gcd/delta field.

Method: code reading (non-formal), during the study's SIMD translation-validation survey (run 3): the whole pipeline around DocValuesRangeSupport was translated, including the bound transform transformGcdBounds and the writer's encoding. Z3 (QF_BV 64-bit and NIA) then showed that with gcd 1 a false negative exists exactly when a stored value is negative (wrapped) and hi - min overflows, and a false positive needs a stored value equal to Long.MAX_VALUE (with gcd > 1, ceilDiv(Long.MAX_VALUE, gcd)); it found the fix's two rules correct on the model. Six JUnit tests failed on main and passed on 10.5.2.

• A separate verifier wrote its own 11-case API and query matrix: 10 of 11 fail on main in both vector modes, all pass on 10.5.2 and with the fix; it showed that query-level false positives are reachable with 64 bits per value.
• A 10.6 fact sheet and an independent review reproduced it on branch_10_6 and main, checked cross-version reads and validated a port of #16896.
• This doc's test is a one-method, 2,048-document form of the verifier's latitude tests.