Multi-valued range facet counts drop values that do not arrive in ascending order

LongRangeFacetCounts and DoubleRangeFacetCounts count, for each range, the documents that have at least one value in it. For a document with several values, LongRangeCounter.addMultiValued remembers the highest elementary interval it has counted for that document and returns early for any later value at or below that interval's upper end; its field comment states the assumption, "this takes advantage of the fact that values within a given doc are sorted". Nothing guarantees that order: MultiLongValues.nextValue and MultiDoubleValues.nextValue promise none, so a custom source such as the distances from the user to each of a document's locations (the use case both class javadocs name) is counted in delivery order, and Lucene's own fromDoubleField and the DoubleRangeFacetCounts(String, ...) constructor read raw-bit doubles in signed-long order, which reverses negative values: two different negative values in one document reach the counter in descending order. A document with distances 3.0 km and 0.5 km is counted under "< 5 km" but not under "< 1 km" or "< 2 km", although those ranges' drill-down queries find it; across 1,000 such documents the counts are 85, 180, 494 instead of 154, 325, 740. Counts and FacetResult.value are only ever too low, and nothing fails. Every release from 8.10.0 to 10.6.0 (10.6.0 by reading), and main, is affected.

• Range facet counts. LongRangeFacetCounts and DoubleRangeFacetCounts count, for each requested range, the documents that have at least one value in it; the result's value (FacetResult.value) is the number of documents that hit any range. Doubles are mapped to sortable longs, so both classes share one counter, LongRangeCounter.
• Elementary intervals. The counter cuts the number line at the range bounds; boundaries() holds each interval's inclusive upper end, the last one Long.MAX_VALUE (range/LongRangeCounter.java:90-92, :169-170). For "< 1 km", "< 2 km", "< 5 km": E0 below 0, E1 [0, 1), E2 [1, 2), E3 [2, 5), E4 [5, +inf). Non-overlapping ranges use ExclusiveLongRangeCounter, overlapping ones OverlappingLongRangeCounter (:52-58).
• Multi-valued sources. MultiLongValues.nextValue() and MultiDoubleValues.nextValue(): "Iterates to the next value in the current document", with no ordering (MultiLongValues.java:42-46, MultiDoubleValues.java:42-46). Custom sources are the stated purpose of #543 (9.1.0).
• Raw-bit doubles. SortedNumericDocValuesField(Double.doubleToRawLongBits(v)), the encoding fromDoubleField decodes (Double::longBitsToDouble, MultiDoubleValuesSource.java:80-83) and the DoubleRangeFacetCounts(String, ...) constructor documents ("assumes that the field was indexed with DoubleDocValuesField", range/DoubleRangeFacetCounts.java:53-56). SortedNumeric returns the longs in signed order, and for negative doubles the raw bits sort in reverse: 0xBFF0000000000000 (-1.0) is below 0xC014000000000000 (-5.0).

1. For a document with more than one value the callers call startMultiValuedDoc(), addMultiValued(v) for each value, then endMultiValuedDoc() (range/LongRangeFacetCounts.java:200-212, range/DoubleRangeFacetCounts.java:227-239, range/RangeFacetCounts.java:169-181). Only a document for which endMultiValuedDoc() returns true is added to the total (RangeFacetCounts.java:179-181, :213).
2. addMultiValued (range/LongRangeCounter.java:116-161) keeps multiValuedDocLastSeenElementaryInterval, reset to -1 per document (:66-68). If it is set and v <= boundaries[lastSeen], it returns at once (:125-130); otherwise it binary-searches only the intervals above lastSeen (:139-160). The field comment: "this takes advantage of the fact that values within a given doc are sorted" (:45-49).
3. Distances 3.0, then 0.5: 3.0 lands in E3 and lastSeen becomes 3; 0.5 is <= boundaries[3] (just below 5.0), so the method returns. E1 is never marked: "< 1 km" and "< 2 km" get 0.
4. If the first value lies above every range ({500, 5} with [0, 10), [10, 100)), lastSeen is the last interval, every later value is skipped, and the document also drops out of the total.
5. Raw-bit doubles with the sign bit set come in reverse order through fromDoubleField and through the field constructor, which maps with NumericUtils.sortableDoubleBits (range/DoubleRangeFacetCounts.java:272-275): two different negative values arrive descending, and so do -0.0 and a negative value. An out-of-order value is lost only when it falls in a lower elementary interval than one already counted (raw {-5.0, -6.0} with [-10, -2], [-2, 0], both in one interval, is counted right). Without -0.0 or NaN, a document with at most one negative value arrives ascending and is counted right. One more edge: through fromDoubleField, a NaN with the sign bit set arrives first but maps above every finite value, so the next value is skipped (executed: {NaN, 5.0} in [0, 10] counts 0, total 0).
6. Both counters lose the skipped values. The exclusive one relies on the shortcut to count each interval at most once per document ("We can do this without fear of double-counting since we know the requested ranges don't overlap", range/ExclusiveLongRangeCounter.java:122-132).
7. Counts can only go down: a value that is searched always lands in its true interval, and no interval is counted twice for one document.

One document per test: distances 3.0, 0.5 give [0, 0, 1] instead of [1, 1, 1]; longs {30, 5} with [0, 10), [10, 100) give [0, 1] instead of [1, 1]; {500, 5} gives [0, 0] and total 0 instead of [1, 0] and total 1; raw-bit {-1.0, -5.0} with [-10, -2], [-2, 0] gives [0, 1] instead of [1, 1], through fromDoubleField and through the field constructor. 1,000 documents with two random distances in [0, 10) km: [85, 180, 494], total 494, against drill-down [154, 325, 740]. Two random raw-bit temperatures in [-20, 20): [-20, -10) counts 271, drill-down 390.

• Custom sources. Both class javadocs name per-request values such as "distance from the user's location, '< 1 km', '< 2 km', etc." (range/DoubleRangeFacetCounts.java:36-39, range/LongRangeFacetCounts.java:33-37), and #543 says "This change allows users to provide custom multi-valued 'value sources' for numeric faceting". Such a source returns one value per location in whatever order it computes them; nothing asks it to sort them.
• Raw-bit doubles. The field constructor documents the raw-bit encoding (DoubleDocValuesField encodes "via Double#doubleToRawLongBits"), fromDoubleField decodes it, the MultiLongValuesSource javadoc recommends fromDoubleField(f).toMultiLongValuesSource() for double fields, and upstream's own multi-valued tests index the IEEE bits (doubleToLongBits / doubleToRawLongBits, the same bits for non-NaN values) with values in [0, 1) only. A document with two or more different negative values (western longitudes, sub-zero temperatures) reaches the counter in descending order and loses a later value that falls in a lower elementary interval; -0.0 next to a negative value does the same. fromFloatField over raw float bits behaves the same.
• Not affected (executed controls): long fields through fromLongField/fromIntField; DoubleField (sortable encoding) read with fromField(f, NumericUtils::sortableLongToDouble); raw-bit documents with at most one negative value and no -0.0 or NaN; single-valued documents; ascending custom sources.
• Default vs opt-in. Default codec, IndexWriterConfig and searcher; no setting. But each trigger needs a less common API shape: an @lucene.experimental custom source, hand-encoded raw-bit multi-valued doubles, or a decreasing decoder.
• Effect. Per-range counts and FacetResult.value are silently too low and disagree with the range's drill-down; a document whose first value lies above every range vanishes from all of them. Never too high, no error, nothing written to the index. With 1,000 documents and two random distances each, one third of the documents are missing from "< 5 km" (494 of 740).
• Likelihood. Plausible: wrong on every affected document, but these paths are uncommon, upstream tests never deliver unordered values, and no public report was found in the recorded searches, although the code has shipped since 8.10.0 (2021).
• Same assumption elsewhere. LongValueFacetCounts de-duplicates a document's values only against the previous value, so a source that returns 5, 3, 5 counts 5 twice for one document (tracked with this bug; needs its own change).

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected:<1> but was:<0>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:647)
       org.junit.Assert.assertEquals(Assert.java:633)
       org.apache.lucene.facet.range.TestRangeFacetUnsortedMultiValues.testValuesNotInAscendingOrder(TestRangeFacetUnsortedMultiValues.java:93)

• Contract. MultiLongValues.java:22-46 and MultiDoubleValues.java:22-46: "Documents may produce multiple values"; nextValue() "Iterates to the next value in the current document". No ordering, then or now. The precondition lives only in the field comment of the package-private LongRangeCounter (range/LongRangeCounter.java:40, :45-49).
• What a count means. The upstream random multi-valued tests count a document once per range if any of its values is in it ("ensure each doc can contribute at most 1 count to each range", range/TestRangeFacetCounts.java:1015, :1358) and assert that the facet count and the drill-down count both equal that (:1053, :1072, :1399, :1420).
• The same API disagrees with itself. DoubleRange/LongRange.getQuery(fastMatchQuery, Multi*ValuesSource), "Create a Query that matches documents in this range", accepts a document if any value is in the range, in any order (range/DoubleRange.java:298-302, range/LongRange.java:285-289).
• History. #127 (LUCENE-9946, 8.10.0) first searched from interval 0 with a per-document bitset; after a reviewer asked whether it took advantage of "the sortedness of SORTED_NUMERIC", revision 923d35eb0cee added the last-seen-interval search. At the time every multi-valued input was sorted. #543 (LUCENE-10245, 9.1.0) then fed unordered Multi*Values into the unchanged counter; its review, issue and dev@ thread never mention order.
• Tests. No upstream test builds a custom multi-valued source, and no multi-valued test uses negative doubles.

Strongest case (built by the devil's advocate; a reviewer from another model family rated it moderate): (a) the counter documents its precondition and the review asked for it; (b) Multi*Values copy the SortedNumericDocValues shape, and every consumer in the module assumes ascending values; (c) SortedNumericDocValuesField says doubles need NumericUtils encoding "with proper sort order", and in #11997 a committer noted that raw-bit multi-valued doubles are not ordered within a document; (d) the classes are @lucene.experimental.

Why it fails: (a) is a package-private invariant that no public API passes on; (b) is unwritten, and Lucene's own fromDoubleField and field constructor break it; (c) does not touch the custom-source trigger, and the facet API documents and decodes raw bits, while with the sortable encoding the field constructor mis-decodes negatives ({-5.0, -6.0} lands in [-2, 0] instead of [-10, -2], executed), so for that constructor neither encoding is reliable for documents with two or more negative values (the sortable encoding mis-decodes every negative value; raw bits drop a lower value that arrives second, as with {-1.0, -5.0}, while raw {-5.0, -6.0}, both in one interval, is counted right); (d) experimental is not unsupported, and custom sources are the purpose of #543. Verdict: a defect.

Option A was built and validated with gradle in a scratch worktree at a9779ef3c193; option B (the finder's patch) was re-run there; option C ran as a shadow class in independent checks; option D was not run. Any fix should also go with LFV-314's separate change in LongValueFacetCounts (merged into this bug), which the range-counter fix does not touch. By reading, the sandbox LongRangeFacetCutter (LongRangeFacetCutter.java:324-352) keeps a similar per-document lastIntervalSeen shortcut; it was not run, and none of these options touches it.

One file, range/LongRangeCounter.java: a per-document FixedBitSet of counted elementary intervals, allocated once and cleared in startMultiValuedDoc(). A value above the highest counted interval is searched from there, as today; a value inside that interval returns, as today; a value below it is searched over all intervals. Each interval is passed to processMultiValuedHit at most once per document.

final int lastSeen = multiValuedDocLastSeenElementaryInterval;
final int firstCandidateElementaryInterval;
if (lastSeen == -1 || v > boundaries[lastSeen]) {
  firstCandidateElementaryInterval = lastSeen + 1; // ascending: as today
} else if (lastSeen == 0 || v > boundaries[lastSeen - 1]) {
  return; // same interval as the last one counted
} else {
  firstCandidateElementaryInterval = 0; // out of order
}
// ... unchanged binary search from firstCandidateElementaryInterval -> idx
if (multiValuedDocCountedElementaryIntervals.getAndSet(idx) == false) {
  processMultiValuedHit(idx);
}
if (idx > lastSeen) {
  multiValuedDocLastSeenElementaryInterval = idx;
}

Trade-offs

• Fixes every caller at once: the source paths of both facet classes, the field constructor, and both counters.
• Cost: ascending input takes the same path as today plus one bitset write per counted interval and a clear per multi-valued document (intervals / 64 words); each out-of-order value pays a full binary search and one bitset write, even when its interval was already counted. Not benchmarked; not reviewed upstream.
• OverlappingLongRangeCounter already keeps its own per-document interval bitset; a maintainer may prefer to share it.
• LongRangeCounter.java is unchanged since 2021, so the patch applies to every affected branch. Open PR #16439 also edits this file (its single-valued, exclusive path); expect a small merge.

What the checks validated

• Scratch worktree at a9779ef3c193, gradle, JDK 25: the new tests fail 6 of 7 on stock and pass 7 of 7 with the fix; with TestRangeFacetCounts, 29 tests, 0 failures, assertions on and off; the randomized test passes 30 of 30 seeds (-Ptests.iters=30 -Ptests.multiplier=2).
• The whole facet module: 41 suites, 313 tests (306 upstream + 7 new), 0 failures, with assertions on (7 skipped) and off (8 skipped); :lucene:facet:check -x test (google-java-format, ecjLint, forbiddenApis) passes.
• Standalone runner with the patched class: the finder's JUnit (3 of 3), the independent reproducer's (15 of 15), the devil's advocate's probes (3 of 3) and the scale probe (facet counts equal drill-down: [154, 325, 740], total 740) pass; the patched class also passes both tests against the 10.5.2 jars.
• Edge cases, added after the fact checks (8 tests, standalone runner): raw {-0.0, -5.0} and {NaN with the sign bit set, 5.0} through fromDoubleField and the field constructor, custom longs {Long.MAX_VALUE, Long.MIN_VALUE}, {100, 10, 9} on exact range bounds, and {50, 5, 50, 5, 7} (a lower interval that comes back) with exclusive and overlapping ranges: stock main fails 7 of 8 (assertions on and off), 10.5.2 fails 7 of 8 (assertions on), and with the fix all 8 pass (assertions on and off). Not run through gradle.

Three files (RangeFacetCounts, LongRangeFacetCounts, DoubleRangeFacetCounts, +34/-24): buffer each multi-valued document's mapped values, sort them, and feed the distinct ones to the unchanged counter.

Trade-offs

Keeps the counter's precondition true, but every multi-valued document pays a buffer copy and an O(k log k) sort even when already sorted (a sortedness check could avoid it), and any new caller must remember to sort.

What the checks validated

On a9779ef3c193 the new tests and TestRangeFacetCounts pass (29 tests); on ea57360912ed the finder's repro (3 of 3) and TestRangeFacetCounts (22 of 22). Format not checked.

The simplest code, and essentially what #127 did before its review added the shortcut.

Trade-offs

Gives up the ascending fast path that the original review asked for: every value pays a full binary search.

What the checks validated

As a shadow class it turned the independent reproducer's 15 tests green and passes the history probes on 8.10.0, 9.1.0 and main.

Say that values must arrive in ascending order.

Trade-offs

No counter change, but Lucene's own fromDoubleField, fromFloatField and the field constructor break that contract for raw-bit negatives and would need fixing too, and existing custom sources would stay silently wrong. Paired with those repairs it is a coherent choice a maintainer may prefer: the #127 author relied on sorted input on purpose.

Method: SMT solving with Z3 (the semi-formal tier: a hypothesis formed while modelling, then witnessed by the tool), in a hunt unit on facet taxonomy and range counting. The finder tagged it formal; the registry records it as semi-formal because the key obligation was posed as an expected counterexample search from the code comment.

• Obligations on a model of addMultiValued: with the ascending precondition the per-document hit set equals the true set (unsatisfiable, so it always holds); without it a mismatch exists (satisfiable); raw-bit SortedNumeric order is not ascending in sortable space (satisfiable) but is when both values are non-negative (unsatisfiable), which is why the upstream random tests, all in [0, 1), pass.
• A bounded-exhaustive run of the real counters: 93,196 range sequences, 0 mismatches with ascending values, 92,376 sequences mis-count when the same documents are fed in descending order; a 24-seed randomized differential against a brute-force oracle classified every mismatch.
• Then a public-API JUnit on the stock jars, an independent reproducer, read-only reviews by a model from another family (OpenAI GPT-5.6), a devil's advocate, an adjudication, a history sweep and a security scope check.