Taxonomy getAllDims misorders float dims, and can throw, when one dim's value is NaN

TaxonomyFacets#getAllDims sorts the per-dim results with a.value.doubleValue() > b.value.doubleValue(), then the reverse, and otherwise the dim name (TaxonomyFacets.java:580-590). Every > with NaN is false, so a dim whose value is NaN ties with every value, is placed by name only, and the comparator is no longer transitive. With dims a=1, b=NaN, c=2 (float associations, SUM), getAllDims(10) returns [a=1.0, b=NaN, c=2.0] while getTopDims(1, 10) returns [b=NaN]: getTopDims ranks with the NaN-safe valueComparator (Float.compare, FloatTaxonomyFacets.java:48) since #12966, and its javadoc says it should equal the first entries of getAllDims. With 32 or more dims, List.sort can detect the broken contract and getAllDims throws IllegalArgumentException: Comparison method violates its general contract!. NaN also comes from ordinary inputs: a clicks / views weight with 0/0, or finite weights whose float SUM overflows to +Inf and -Inf inside one dim. Hits, counts, drill-down and int facets are not affected. Released since 4.7.0; the default association path reaches it since 9.11.0. The fix sorts with valueComparator, then the dim name.

Mechanism (Lucene main 645d4fe14a20):

1. Collect. getAllDims walks the taxonomy root's children and siblings and adds one FacetResult per dim (TaxonomyFacets.java:564-578). The taxonomy lists the youngest child first (TaxonomyIndexArrays.java:253-255, :268-269), so dims added as a, b, c are visited as [c=2.0, b=NaN, a=1.0]. A dim's value is a fold over its labels that starts at 0f (FloatTaxonomyFacets.java:129-150), so one NaN label makes the dim NaN.
2. Sort. TaxonomyFacets.java:580-590:

// Sort by highest value, tie break by dim:
results.sort(
    (a, b) -> {
      if (a.value.doubleValue() > b.value.doubleValue()) {
        return -1;
      } else if (b.value.doubleValue() > a.value.doubleValue()) {
        return 1;
      } else {
        return a.dim.compareTo(b.dim);
      }
    });

1. Wrong order. For a=1, b=NaN, c=2 the comparator says a<b (name), b<c (name) and c<a (value): a cycle, so it is not a valid Comparator. On the visiting order [c, b, a], the JDK's ArrayList.sort asks only compare(b, c) = -1 and compare(a, b) = -1, takes the run as strictly descending, reverses it and returns [a=1.0, b=NaN, c=2.0]; it never compares a with c. (Shown with a verbatim copy of the comparator that logs its calls; the real getAllDims returns the same list.)
2. Exception. From 32 elements the JDK's TimSort merges sorted runs and, on some arrangements, meets the contradiction and throws IllegalArgumentException("Comparison method violates its general contract!"), which List.sort documents for a comparator that breaks its contract. Below 32 elements it never merges and never throws.
3. getTopDims uses another order. Its queue orders dims by valueComparator, then the name (TaxonomyFacets.java:610-614), and admits dims with it (:652-664). For float facets that is Float.compare (FloatTaxonomyFacets.java:48), a total order that ranks NaN above +Infinity, so it returns [b=NaN, c=2.0, a=1.0]. Int facets compare ints and cannot be NaN.
4. Where NaN comes from. Nothing checks finiteness: FloatAssociationFacetField stores any float (FloatAssociationFacetField.java:33-40), TaxonomyFacetFloatAssociations.java:151 casts any DoubleValuesSource double to float, SUM is + and MAX is Math.max (AssociationAggregationFunction.java:40-65).

Executed triggers (main 645d4fe14a20, assertions on and off; the NaN-free controls pass). Every row also failed on 10.6.0, assertions on and off; the first three also on 9.11.0 and the last three also on 10.5.2 (assertions on):

How often a NaN dim breaks the order depends on the arrangement: a simulation of the verbatim comparator (one NaN, distinct values, random order, 100,000 lists per size) misorders finite dims in 5.45% of 3-dim, 21.32% of 10-dim and 39.37% of 32-dim lists, and throws in 0.28% of 32-dim lists.

• Who. Users of TaxonomyFacetFloatAssociations over FloatAssociationFacetField weights or a DoubleValuesSource, with SUM or MAX, who call getAllDims, or compare it with getTopDims. These are opt-in facet types, and the facet classes are @lucene.experimental.
• Settings. Otherwise defaults: default IndexWriterConfig, codec, taxonomy and FacetsConfig on the association path since 9.11.0; the value-source path with the default dim config was run on 9.11.0, 10.6.0 and main, and with multiValued + requireDimCount dims it is affected since 4.7.0.
• Scale. Three dims for the wrong order; 32 or more dims with hits for the exception. getAllDims is documented for "sparse" faceting "where many different dimensions were indexed" (Facets.java:53-55).
• Effect. The "top" dim shown can be a lower-valued one; code that truncates or pages getAllDims gets the wrong dims; getTopDims and getAllDims disagree; with many dims the facet call fails. getTopDims does not use this comparator (it ranks dims with valueComparator), but the child lists it returns have a separate NaN issue (LFV-825); nothing is written to the index.
• Likelihood. Rare: ordinary weights (scores, prices, ratings) do not aggregate to NaN, but computed weights can (0/0), and so can SUM overflow.

One test class, one method, public API only: ByteBuffersDirectory, default IndexWriterConfig and FacetsConfig, single thread, nothing randomized by the test body (the seed drives only the test framework's own randomized defaults, such as the codec, locale and time zone; the test failed under three seeds, with assertions on and off). Copy it into lucene/facet/src/test/org/apache/lucene/facet/taxonomy/ of a Lucene checkout and run the command.

Before using it as the regression test of a PR, run ./gradlew :lucene:facet:tidy: it joins the two assertTrue arguments onto one line, the only change, after which the format check passes.

Left out on purpose: the getTopDims comparison, the 32-dim exception and the other NaN sources; they follow from the same comparator and were executed separately (see the mechanism above).

cp $REPRO/TestGetAllDimsNaN.java $LUCENE/lucene/facet/src/test/org/apache/lucene/facet/taxonomy/
cd $LUCENE && ./gradlew :lucene:facet:test --tests org.apache.lucene.facet.taxonomy.TestGetAllDimsNaN -Ptests.seed=DEADBEEF -Ptests.asserts=true
# and the same with -Ptests.asserts=false

# main 645d4fe14a20, gradle, -Ptests.asserts=true (the same with false)
TestGetAllDimsNaN > testGetAllDimsOrdersNonNaNDims FAILED
    java.lang.AssertionError: expected c=2.0 before a=1.0, got [a=1.0, b=NaN, c=2.0]
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:3C0FEC18EB78D5B1]: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.TestGetAllDimsNaN.testGetAllDimsOrdersNonNaNDims(TestGetAllDimsNaN.java:61)
:lucene:facet:test (FAILURE): 1 test, 1  failure

# with the fix (option A), assertions on and off
:lucene:facet:test (SUCCESS): 1 test

# the same three dims, traced (main jars, -ea and -da)
visiting order: [c=2.0, b=NaN, a=1.0]
  compare(b=NaN, c=2.0) = -1
  compare(a=1.0, b=NaN) = -1
getAllDims(10): [a=1.0, b=NaN, c=2.0]
getTopDims(1, 10): [b=NaN]
getTopDims(3, 10): [b=NaN, c=2.0, a=1.0]

• The code's intent. TaxonomyFacets.java:580: "Sort by highest value, tie break by dim". No rule for where NaN goes explains 1.0 above 2.0.
• The javadoc. Facets.java:52-57: getAllDims returns dims "sorted by the number of hits that dimension matched"; :59-62: getTopDims is "sorted by the number of hits/aggregated values ... Results should be the same as calling getAllDims and then only using the first topNDims". The base getTopDims is literally getAllDims(topNChildren).subList(0, ...) (:69-72).
• The tests. TestTaxonomyFacetAssociations.java:327-329, :359-361 and :380-382 assert that getTopDims(10, 10) equals getAllDims(10) for float associations, with finite values only. No facet test uses NaN, and the test helper FacetTestCase#sortFacetResults (:209-221) copies the same comparator.
• The JDK contract. The exception is List.sort reporting a broken Comparator, not an input check.
• History. #12966 (2024; 9.11.0 through #13358) added valueComparator and moved getTopDims to it, but left getAllDims on the 2013 comparator; none of its 55 comments and reviews mentions NaN. The same change is the 9.11.0 bug fix "Aggregation facets no longer assume that aggregation values are positive" (lucene/CHANGES.txt:2922).
• NaN is accepted. The facet module rejects NaN only for range bounds (range/DoubleRange.java:61-69, rangeonrange/DoubleRange.java:43-51, facetset/DimRange.java:62-94); weights are not checked.

The case for "intended": NaN is garbage in, as with NaN scores in core search (LUCENE-2271); the facet APIs are @lucene.experimental; the getAllDims javadoc speaks of "number of hits" and says nothing about NaN; AssociationAggregationFunction.java:25-28 assumes "valid values are always positive"; and in the minimal test every dim has one hit, so a literal "by hits, then by name" reading would accept [a, b, c].

Why it fails: (1) when c has 2 hits and value 2.0 and a has 1 hit and 1.0, the result is still [a=1.0, b=NaN, c=2.0], wrong under both readings (executed on main, 10.6.0 and 9.11.0); (2) getTopDims and getAllDims disagree wherever NaN goes, against the javadoc's stated expectation ("Results should be the same") and the upstream equality tests (finite inputs); (3) the exception is a Comparator contract violation, which experimental status does not excuse; (4) 0/0 and SUM overflow produce NaN from ordinary inputs, so rejecting explicit NaN does not prevent it; (5) #12966 already chose a NaN-safe order for getTopDims and dropped the positive-values assumption as a bug fix. The cross-model refute review rated the intended argument "weak".

Option A was built and run in a scratch worktree of 645d4fe14a20; B was run on 4.7.0 only; C was not built. Rejecting NaN weights at index time is not a fix on its own: NaN also comes from SUM overflow and from a DoubleValuesSource at query time.

Replace the two > tests in the getAllDims comparator (TaxonomyFacets.java:580-590) by valueComparator, then the dim name. Full diff:

--- a/lucene/facet/src/java/org/apache/lucene/facet/taxonomy/TaxonomyFacets.java
+++ b/lucene/facet/src/java/org/apache/lucene/facet/taxonomy/TaxonomyFacets.java
@@ -580,13 +580,11 @@
     // Sort by highest value, tie break by dim:
     results.sort(
         (a, b) -> {
-          if (a.value.doubleValue() > b.value.doubleValue()) {
-            return -1;
-          } else if (b.value.doubleValue() > a.value.doubleValue()) {
-            return 1;
-          } else {
-            return a.dim.compareTo(b.dim);
+          int cmp = valueComparator.compare(b.value, a.value);
+          if (cmp != 0) {
+            return cmp;
           }
+          return a.dim.compareTo(b.dim);
         });
     return results;
   }

// Sort by highest value, tie break by dim:
results.sort(
    (a, b) -> {
      int cmp = valueComparator.compare(b.value, a.value);
      if (cmp != 0) {
        return cmp;
      }
      return a.dim.compareTo(b.dim);
    });

Trade-offs

• One order for both methods; a NaN dim is listed first, where getTopDims already puts it.
• Int facets: Comparator.comparingInt gives today's order. Float facets: Float.compare and > differ only on NaN and on a -0.0/+0.0 pair; the built-in SUM and MAX folds start at +0.0 and cannot produce -0.0 (solver queries; reasoned, not executed).
• A custom AssociationAggregationFunction (public abstract class) that returns -0.0f would now be ordered below +0.0 instead of by name (read, not run).
• Scope: this fixes the dim order of getAllDims only (and with it the disagreement with getTopDims and the exception). The child labels inside each dim come from getTopChildren, whose queue can still pick the wrong children when a label is NaN: that is LFV-825, with its own fix.
• Optional: change the test helper FacetTestCase#sortFacetResults the same way (identical for finite values).

What the checks validated

Scratch worktree of 645d4fe14a20, gradle --no-daemon, OpenJDK 25.0.3, seed DEADBEEF:

• stock + test: fails with assertions on and off; git apply of the fix is clean;
• fix + test: passes with assertions on and off;
• fix + test, --tests 'org.apache.lucene.facet.taxonomy.*': 139 tests, 6 skipped, 0 failures;
• fix + test, all of :lucene:facet:test: 307 tests, 8 skipped, 0 failures (40 classes, including TestTaxonomyFacetAssociations, TestTaxonomyFacetValueSource, TestTaxonomyFacetCounts and TestTaxonomyFacetCounts2);
• fix + tidied test: :lucene:facet:checkGoogleJavaFormat passes;
• earlier, shadowed onto the main jars: every verifier's and the tie-break's tests pass. Not run: the full Lucene suite, nightly tests, benchmarks.

Double.compare(b.value.doubleValue(), a.value.doubleValue()), then the dim name: the same order as A, for branches without valueComparator (before 9.11.0).

Trade-offs

On main, A keeps one source of truth with getTopDims.

What the checks validated

4.7.0 release jars with only the comparator replaced: the history program passes.

Make the float valueComparator (FloatTaxonomyFacets.java:48) NaN-last and use it in getAllDims as in A.

Trade-offs

Arguably friendlier output, but it changes what getTopDims returns today and its admission test (TaxonomyFacets.java:652-664).

The hunt targeted NaN and other special values in the facet top-k paths. A sweep over the stock jar (1-4 labels and 4 dims, inputs {1, 2, 3, NaN, +Inf, -Inf, -0.0}, association and value-source facets, SUM and MAX, dense and sparse, 1 or 2 segments, assertions on and off) found 928 getAllDims-order failures and 11,022 getTopDims-vs-getAllDims failures, all with a NaN dim and none without one. SMT queries (cvc5 and z3) showed that the getAllDims order is not transitive with NaN and transitive without it, and that it differs from the getTopDims order only on NaN or a signed-zero pair, which the SUM and MAX folds cannot produce. A pure-Java simulation of the verbatim comparator found that 12,843 of 200,000 random lists throw, the smallest with 32 dims, and a seeded search then reproduced the exception on the stock jar. An independent scan of the compiled classes for comparators without a NaN branch flagged the same site.