Float taxonomy facets: one NaN-valued label makes getTopChildren return a lower-valued label in place of a higher one

Float taxonomy facets (TaxonomyFacetFloatAssociations, fed by FloatAssociationFacetField weights or a DoubleValuesSource) pick the top child labels with TopOrdAndFloatQueue, whose comparator tests value < other, then value > other, then the ordinal (TopOrdAndFloatQueue.java:36-45). Both tests are false for NaN, so a NaN-valued label ties with every value, the order is no longer transitive, and the heap keeps the wrong labels: with a=5, b=NaN, c=10, getTopChildren(1) returns [a (5.0)] and getTopChildren(2) returns [b (NaN), c (10.0)]. The NaN can come from data with no NaN in it (a 0/0 ratio expression, sqrt of a negative, +Inf and -Inf in one label). It is a 9.11.0 regression from #12966, which let every label with a count into the queue (before, only value > 0), and it is still on main and in 10.6.0. A Float.compare-based comparator that keeps equal values tied fixes it without changing the order of any non-NaN values.

1. Values reach the queue unchecked: FloatAssociationFacetField encodes any float (FloatAssociationFacetField.java:33-40), and TaxonomyFacetFloatAssociations casts a DoubleValues value to float (:151) or reads the stored one (:191) and folds it with SUM (+) or MAX (Math.max), both of which propagate NaN (AssociationAggregationFunction.java:40-66).
2. TaxonomyFacets.getTopChildrenForPath (:467-503) puts every child with count > 0 (sparse :482, dense :495) through insertIntoQueue (:421-431) into PriorityQueue.insertWithOverflow, which replaces the current worst entry when lessThan(top, element) (PriorityQueue.java:231-243). getTopChildren, getAllDims and getTopDims all use it.
3. TopOrdAndFloatQueue.OrdAndFloat#lessThan (TopOrdAndFloatQueue.java:36-45): if (value < other) return true; if (value > other) return false; return ord > other.ord;. For NaN both tests are false, so only the ordinal decides.
4. Hand trace for top-1. The taxonomy has 5 ordinals, so counting is dense and the children are visited newest first: c, b, a. c enters the empty queue. lessThan(c, b): 4 > 3, so b replaces c. lessThan(b, a): 3 > 2, so a replaces b. Result [a (5.0)]. For top-2, c and b fill the queue and a loses to c by value: [b (NaN), c (10.0)].
5. Large taxonomies can vary from call to call. Counting uses a hash table only when a FacetsCollector is given, the taxonomy has 1024 or more ordinals and the hits number fewer than maxDoc / 10 (integer division; TaxonomyFacets.java:103-123, :132), and the child walk iterates it (:479). Every iterator starts at a newly seeded slot and step (IntIntHashMap.java:106, :463, :480-482), so each call can visit a, b, c in another order; for top-1 with b=NaN, 2 of the 6 orders end at a.
6. The same change that let NaN in (#12966) ranks the dims of getTopDims with the NaN-safe Float.compare (FloatTaxonomyFacets.java:48), but kept < / > for the child labels. getAllDims sorts dims with its own NaN-unsafe comparator (TaxonomyFacets.java:580-590, the sibling LFV-820).

• Weights -3, NaN, 7: top-1 [low (-3.0)].
• Plain FacetField labels with the weight DivFloatFunction(LongFieldSource("clicks"), LongFieldSource("impressions")), clicks / impressions 5/100, 0/0, 50/100: top-1 [low (0.05)] instead of high (0.5); with 0/10 instead of 0/0 the result is right.
• Finite double weights through DoubleValuesSource.fromDoubleField: a 5.0, b 1e39 and -1e39, c 10.0. The float casts give +Inf and -Inf, b sums to NaN, and top-1 is [a (5.0)]; with 1e30 and -1e30 (sum 0) the result is right.
• Sparse counting (1100 filler labels, a query matching 3 of 1103 documents): 14 to 19 of 60 identical getTopChildren(1) calls on one Facets object return [a (5.0)] in the tie-break runs (12 to 15 in the fact check's re-runs), the rest c or b; with b=7, 0 of 60.
• MAX with 5, NaN, 10: [a (5.0)]. MAX over 6 labels, NaN from a double doc value (the review's own JUnit, on main a9779ef3c193, 10.5.2 and 9.12.3; re-run on 645d4fe14a20 by the fact check): top-2 [L2 (20.0), L0 (2.0)] while L5 (10.0) and L4 (9.0) outrank L0.
• getTopDims(1, 1) on the a=5, b=NaN, c=10 index: the dim's child list is [a (5.0)].
• Not every visiting order misorders: 8,524 of 97,184 sweep checks with a NaN input fail, 0 of 119,424 without (+-Inf and -0.0 alone are safe).

• Who is hit. Users of TaxonomyFacetFloatAssociations (an opt-in, @lucene.experimental API) fed by FloatAssociationFacetField weights or a DoubleValuesSource (an expression, a function query, a double doc-values field), with SUM or MAX, through getTopChildren, getAllDims or getTopDims (all three executed). Default IndexWriterConfig, codec, taxonomy writer and FacetsConfig. getTopDims ranks the dims NaN-safely, but its child lists come from this queue; getAllDims gets its child lists from getTopChildren and also sorts the dims with its own NaN-unsafe comparator (the sibling LFV-820).
• When. Once one child label aggregates to NaN. That takes a NaN weight (accepted without a check), a NaN double doc value, a weight that computes 0/0 (a ratio for a document with no denominator), sqrt or ln of a negative value, or finite double weights of opposite sign beyond the float range in one label. Then only some visiting orders misorder.
  • Dense counting (fewer than 1024 taxonomy ordinals, no FacetsCollector, or at least maxDoc / 10 hits): the order comes from the ordinals, and in the tested dense cases the same query on the same index gave the same wrong top-k on every run.
  • Sparse counting (a FacetsCollector, 1024 or more ordinals and fewer than maxDoc / 10 hits, integer division): the visiting order can change from call to call, so identical calls can disagree (12 to 19 of 60 wrong in the runs).
  • Other queries over the same labels may or may not be affected, depending on which labels they match and on k.
• What goes wrong. Silently: a lower finite label is shown in place of a higher one (5 for 10, -3 for 7), top-k lists for different k contradict each other, and on the sparse path repeated calls can disagree. No exception, with assertions on or off.
• Not affected. getAllChildren, the aggregated values, which documents match, drill-down, and the index.
• How likely. Rare: typical scores, prices or ratings do not normally give NaN; ratio or square-root weights over sparse data can.

The test indexes 3 documents, each with one FloatAssociationFacetField(weight, "dim", label): a=5, b=NaN, c=10. It counts MatchAllDocsQuery with TaxonomyFacetFloatAssociations (SUM) and asserts that getTopChildren(1, "dim") returns c, or b if NaN ranks first. Deterministic (3 ordinals, so dense counting) and single-threaded; it draws no random values itself, and it failed under every seed tried (10 derived seeds, 5 more from 5EED1530, and the tie-break's). Set -Ptests.asserts explicitly: with a fixed seed and no value, Lucene's build picks the assertion mode from the seed.

The ratio trigger (clicks / impressions with 0/0) needs the queries module, the top-1 vs top-2 contradiction a second call, and the call-to-call variation a taxonomy of more than 1024 labels; all three are executed evidence in the collapsed explanation above, not part of the repro.

TestFloatFacetTopChildrenNaN > testNaNLabelDoesNotDisplaceHigherValue FAILED
    java.lang.AssertionError: expected top-1 c or b, but was [a (5.0)]
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:5737D7D41F8E5B8F]:0)
        at junit@4.13.2/org.junit.Assert.fail(Assert.java:89)
        at junit@4.13.2/org.junit.Assert.assertTrue(Assert.java:42)
        at org.apache.lucene.facet.taxonomy.TestFloatFacetTopChildrenNaN.testNaNLabelDoesNotDisplaceHigherValue(TestFloatFacetTopChildrenNaN.java:60)

1 test completed, 1 failed

# -Ptests.asserts=false: the same failure and message

• Contract. Facets#getTopChildren: "Returns the topN child labels under the specified path." (Facets.java:39-41). TopOrdAndFloatQueue: "Keeps highest results, first by largest float value, then tie-break by smallest ord." (TopOrdAndFloatQueue.java:19). Only getAllChildren disclaims order: "Users should make no assumptions about ordering of the children" (Facets.java:32-36). The gap, said plainly: neither text says where NaN ranks or promises in so many words that a smaller top-k is a prefix of a larger one, so the case rests on the finite labels: whatever rank NaN gets, 5 must not be returned in place of 10.
• NaN is accepted, not rejected. No javadoc in taxonomy/, TopOrd*.java or Facets.java mentions NaN. Where the module does not accept NaN it throws: "min cannot be NaN" / "max cannot be NaN" (range/DoubleRange.java:62, :69; rangeonrange/DoubleRange.java:44, :51; facetset/DimRange.java:63, :70, :87, :94).
• History. 9.10.0 admitted a child only if (value > 0) and only above the queue's bottom (FloatTaxonomyFacets.java:218, :221), both false for NaN. #12966 (9ba4af7b883c) switched to count > 0 to keep zero and negative labels (CHANGES.txt:2922, 9.11.0 Bug Fixes: "Aggregation facets no longer assume that aggregation values are positive."); its commit message says "The only change in behaviour users should notice is the fix for non-positive aggregation values". NaN is not discussed in #12585, #12966 or #13358.
• Tests. TestTaxonomyFacetAssociations#testNonPositiveAggregations asserts value order including 0.0 and -1.0 (:562-565). No facet test uses NaN.
• Precedent. LUCENE-4937 (CHANGES.txt:14181, "Fix incorrect sorting of float/double values (+/-0, NaN).") fixed the same < / > pattern in sort comparators with Float.compare.

The strongest case for "intended": NaN is not a valid value. Core says so for scores (TopScoreDocCollector.java:30-31: "The values Float.NaN and Float.NEGATIVE_INFINITY are not valid scores", LUCENE-2271 / #3347); "largest float value" is undefined for NaN; PriorityQueue only promises a "partial ordering" (PriorityQueue.java:30-32); the facet APIs are @lucene.experimental; and AssociationAggregationFunction has a TODO that valid values are assumed positive (:25-28).

Why it fails: the misordered labels are finite (5 displaces 10, -3 displaces 7), so no rank for NaN fits, and none explains identical calls returning different labels; the NaN comes from ordinary data: finite inputs to Lucene's own arithmetic (0/0 in DivFloatFunction, or two finite doubles that the float cast turns into +Inf and -Inf); the core note covers hit scores in one collector, and the facet module documents no such rule and rejects NaN explicitly where it does not accept it; "partial ordering" describes the heap, not a licence for a non-transitive lessThan, and @lucene.experimental marks unstable API, not permission for wrong results; the TODO dates from 2022 (LUCENE-10444), is about MIN support, and was overtaken by #12966, which made non-positive values supported; and 9.10.0 kept the finite labels in order. Verdict: not intended, a regression. Expect the "NaN is not valid" reply and answer it with the finite labels and the 0/0 trigger.

Option A was applied in a scratch worktree of 645d4fe14a20 and run with gradle (the worktree was removed after the runs), and shadowed onto the stock jars for the targeted checks and the sweep. Option B is the study's fix, validated by shadow runs. C, D and E were not built. On 9.11-9.12 the queue in use is TopOrdAndFloatNumberQueue (9.12.3 TopOrdAndFloatNumberQueue.java:41-50, the same comparator), so a 9.x backport changes that class.

One method, TopOrdAndFloatQueue.java:36-45. For two non-NaN values it decides exactly as today (-0f != 0f is false); NaN ranks above every number, two NaNs tie by ordinal. Unlike the plain Float.compare of getTopDims, it keeps -0.0 and +0.0 tied.

@Override
public boolean lessThan(OrdAndValue other) {
  OrdAndFloat otherOrdAndFloat = (OrdAndFloat) other;
  // Float.compare gives NaN a consistent rank (above every number); the != test keeps -0.0
  // and +0.0 tied, so the order of non-NaN values is unchanged
  if (value != otherOrdAndFloat.value) {
    int cmp = Float.compare(value, otherOrdAndFloat.value);
    if (cmp != 0) {
      return cmp < 0;
    }
  }
  return ord > otherOrdAndFloat.ord;
}

Trade-offs

• Ranks NaN first, consistent with FloatTaxonomyFacets.valueComparator, which getTopDims uses for dims. Being a strict total order, it also makes the result independent of the visiting order, so the sparse path stops varying. Upstream may prefer NaN last (C) or dropped (D); the repro accepts any of them.
• Two more code lines than B, plus a two-line comment. For 9.12, the same change goes into TopOrdAndFloatNumberQueue.

What the checks validated

• Gradle, stock 645d4fe14a20 (seed DEADBEEF): the repro fails with -Ptests.asserts=true and false.
• Gradle with the fix, assertions on: the repro and the whole facet test module, 40 classes, 307 tests, 0 failures, 7 skipped; :lucene:facet:checkGoogleJavaFormat passes. Assertions off: the repro and the two upstream float-facet test classes, 23 tests, 0 failures.
• Shadowed onto the 645d4fe14a20 jars: the repro passes with -ea and -da; a 7-method check (4 NaN cases incl. the 0/0 ratio, 3 controls) passes 7 of 7 and an 8-method check (MAX, the sparse path with 60 calls, NaN from finite double weights, getTopDims, 4 controls) passes 8 of 8, each with -ea and -da; the bounded-exhaustive sweep drops from 8,524 failing child checks (of 97,184 with a NaN input) to 0, 0 of 119,424 without NaN before and after, every other sweep family unchanged.

Same place: int cmp = Float.compare(value, otherOrdAndFloat.value); if (cmp != 0) return cmp < 0; return ord > otherOrdAndFloat.ord;. Simplest; the same order as valueComparator and as float sorting since LUCENE-4937.

Trade-offs

Also orders -0.0 below +0.0, a change for that pair. The built-in SUM and MAX fold from +0.0 and never produce -0.0, but AssociationAggregationFunction is public, so a custom function could (raised by the cross-model reviewer and the adjudication). TopOrdAndFloatQueue and OrdAndFloat are public classes too (TopOrdAndFloatQueue.java:20, :28, :30), so code outside Lucene can fill the queue with -0.0 directly.

What the checks validated

Shadowed: the repro, the finder's, the independent reproducer's and the reviewer's end-to-end tests, the 7-method and 8-method checks, the sweep (8,524 to 0), and the upstream TestTaxonomyFacetAssociations and TestTaxonomyFacetValueSource (22 of 22) pass. Not run through gradle.

Same shape as A, with if (Float.isNaN(value) != Float.isNaN(other)) return Float.isNaN(value); before the value test.

Trade-offs

Keeps NaN labels out of short top-k lists, but then children and dims (getTopDims, NaN first) order NaN differently.

The effective 9.10.0 behaviour.

Trade-offs

Changes childCount and makes getTopChildren disagree with getAllChildren, which reports NaN labels.

As TopScoreDocCollector does for scores.

Trade-offs

Leaves the 0/0 expression path silently wrong; nothing rejects such a value today.

Method: non-formal first signal, then formal and exhaustive checking.

• A planning AI tool wrote a randomized differential probe of the stock main jar for a comparator-law oracle: 300 random TaxonomyFacetFloatAssociations SUM facets with one NaN-capable label; the planning record reports 22 with a wrong top-k among the non-NaN labels (the probe's source is kept, its raw output is not).
• The hunting AI tool checked the comparator with SMT (cvc5 1.4.2 and z3 4.12.2, floating point and bit vectors): lessThan is not transitive with NaN (with a witness of the repro's shape), is a strict order without NaN, and the Float.compare variant is a strict total order over all floats (for distinct ordinals). It also showed that the built-in SUM and MAX folds never produce -0.0.
• A bounded-exhaustive sweep of the stock jar (1-4 labels, inputs {1, 2, 3, NaN, +Inf, -Inf, -0.0}, every k, association and value-source SUM and MAX, dense and sparse counting, 1 or 2 segments) found 8,524 failing child checks of 97,184 with a NaN input and 0 of 119,424 without; re-run on 645d4fe14a20 for this page with the same numbers.
• The case was reduced to a public-API JUnit with three triggers, and later to the one-test repro.