Geo3D distance and path sorts skip the secondary sort for hits outside the shape's bounding box

Geo3DDocValuesField.newDistanceSort(field, lat, lon, maxRadiusMeters, planet) and newPathSort sort hits by ascending distance; a document without the field, and any hit outside the circle or path, gets distance +Infinity, so in new Sort(distanceSort, secondary) the secondary SortField must order all of them (Sort: "if it produces a tie, then the second SortField is used to break the tie"). Geo3DPointDistanceComparator keeps a bounding box built from the queue's weakest distance and lets compareBottom reject hits outside it without computing their distance. When that weakest distance is +Infinity, the box is the shape's own box, and compareBottom starts at -1 and skips every value outside it, so a later out-of-box hit returns -1 ("not competitive") although it ties at +Infinity. The secondary SortField is never asked, so earlier out-of-radius hits in doc order keep their places. Five documents at latitude 60 sorted around (0, 0) with a 1,000 km radius and a tie key descending give [1, 0] for the top 2, while the full order is [4, 3, 2, 1, 0]. Documents without the field and out-of-radius points inside the box are tie-broken correctly, and hits inside the radius (by their decoded doc-value point) are compared normally. The code is unchanged since the sorts were added in 6.1.0 (LUCENE-7212, 2016). Starting cmp at 0 when the bottom is +Infinity fixes it (a one-line change, validated with the repro and the whole spatial3d module).

• Geo3D distance sort: Geo3DDocValuesField.newDistanceSort(field, latitude, longitude, maxRadiusMeters, planetModel) (lucene/spatial3d) "orders documents by ascending distance from the location"; "If a document is missing the field, then by default it is treated as having Double#POSITIVE_INFINITY distance (missing values sort last)" (Geo3DDocValuesField.java:164-192). newPathSort does the same for a path (:194-225); both build a Geo3DPointSortField whose comparator is Geo3DPointDistanceComparator (Geo3DPointSortField.java:44-46).
• Outside the shape: the distance of a point outside the circle (or path) is +Infinity (GeoBaseDistanceShape.java:47-53), the same value as a missing document. FieldDoc.fields[0] reports Infinity for both.
• Ties: new Sort(a, b) checks a first, "but if it produces a tie, then the second SortField is used to break the tie" (Sort.java:58-62).
• The queue bottom: a top-n search keeps n hits in a queue; the weakest one is the bottom. compareBottom(doc) answers whether a new hit beats it: positive, 0 for a tie (then the next SortField decides), negative for worse (LeafFieldComparator.java:54-67).
• The bounding-box shortcut: "When the least competitive item on the priority queue changes (setBottom), we recompute a bounding box representing competitive distance to the top-N. Then in compareBottom, we can quickly reject hits based on bounding box alone" (Geo3DPointDistanceComparator.java:33-40).

1. The box for an +Infinity bottom. setBottom (Geo3DPointDistanceComparator.java:77-89) calls getDistanceBounds(bounds, ARC, bottomDistance); for +Infinity it returns the shape's own XYZ box (GeoBaseDistanceShape.java:80-87). A radius below the minimum angular resolution gives a GeoDegeneratePoint, which is not a GeoBaseDistanceShape but behaves the same way (GeoCircleFactory.java:43-46, GeoDegeneratePoint.java:174-187).
2. The rejection. compareBottom (:97-134) starts with cmp = -1 (:108) and skips (continue) every value outside the box (:118-125). A hit whose points are all outside the box returns -1, although its distance, +Infinity, ties with the bottom. For a finite bottom the shortcut is right: such a point is outside the shape, so +Infinity is worse.
3. The secondary sort is skipped. MultiLeafFieldComparator.compareBottom returns the first non-zero result (:52-64), and the collector drops the hit (TopFieldCollector.java:92-96).
4. The inconsistency. A document without the field returns Double.compare(bottomDistance, +Infinity) = 0 (:101-103) and is tie-broken; an out-of-radius point inside the box computes its distance, +Infinity, also gets 0 and is tie-broken. Only out-of-box points are rejected.

Docs 0-4 at (60, 0) with tie 0-4, top 2 by distance (1,000 km circle at (0, 0)), then tie descending. Docs 0 and 1 fill the queue; the bottom is doc 0 (+Infinity, tie 0). Docs 2, 3 and 4 lie outside the circle's box, so each returns -1 and is dropped. The page is [1, 0]; the full order, [4, 3, 2, 1, 0], starts with [4, 3].

Not affected: hits inside the radius (inside the box, finite distance), documents without the field, doc-id tie-breaking (the earliest documents win anyway), and the outside-distance sorts, whose comparator has no box.

• Who is exposed. Users of Geo3DDocValuesField.newDistanceSort or newPathSort (lucene/spatial3d, opt-in) with a secondary SortField whose query also matches documents outside the radius or path. No upstream test uses either factory.
• When it shows. The comparator drops a hit it should keep when all three hold: (1) the queue is full and its bottom is +Infinity (fewer than n of the hits collected so far lie inside the radius); (2) a later hit has all its decoded points outside the shape's XYZ bounding box, which holds for most far-away points; (3) the later SortFields would rank that hit ahead of the bottom. The page is then wrong unless later hits would have pushed that hit out anyway. (3) never holds when the secondary key follows doc-id order; it does for a key that runs against doc order, such as "newest first" in an index built in time order. An index sort or a reordered index changes which hits arrive first.
• The usual pairing hides it. With the matching Geo3DPoint.newDistanceQuery, out-of-radius hits normally do not match (read, not run; the query reads the indexed points and the sort the coarser doc values, so a hit right at the edge can still sort as +Infinity).
• Worst case is ordinary. In an index built in time order, "then newest first" can keep old out-of-radius documents that came first and drop newer ones whose points lie outside the box (documents without the field, in-box points and in-radius hits are still compared and can displace the old ones). A small radius or a deep page makes an +Infinity bottom more likely.
• Silent. No exception; totalHits and the hits inside the radius are right. Default IndexWriterConfig, codec and searcher; 5 documents in one segment are enough; assertions on or off; the JUnit runs got two different random codecs with the same result.
• Layout-dependent. It was first seen as top-n results of an index-sorted index (1,200 documents per segment) that differ from a force-merged single-segment copy of the same documents.
• How likely. Plausible: a little-used API, hidden by the usual pairing and by doc-id tie-breaking, and no report since 6.1.0 (2016).

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => org.junit.ComparisonFailure: expected:<[[4, 3]]> but was:<[[1, 0]]>
       org.junit.Assert.assertEquals(Assert.java:117)
       org.junit.Assert.assertEquals(Assert.java:146)
       org.apache.lucene.spatial3d.TestGeo3DDistanceSortOutsideRadiusTie.testTopNOutsideRadiusUsesSecondarySort(TestGeo3DDistanceSortOutsideRadiusTie.java:57)

• The Sort contract. "the first SortField is checked first, but if it produces a tie, then the second SortField is used to break the tie" (Sort.java:58-62). The full search orders out-of-radius hits by the secondary key, so the same Sort returns different documents for different n.
• The comparator contract. compareBottom "should return the same result as FieldComparator#compare(int,int)", 0 if equal (LeafFieldComparator.java:54-67); compare uses Double.compare of the stored distances (Geo3DPointDistanceComparator.java:72-74), which gives 0 for two +Infinity values.
• Two kinds of +Infinity. A document without the field returns 0 (:101-103); an out-of-radius document reports the same Infinity in FieldDoc.fields[0] but gets -1.
• It depends on a box. In the repro, an out-of-circle point inside the circle's XYZ box competes on tie, and a far point with a better tie does not: [3, 1] instead of [2, 3] (executed). No intended rule could give that split.
• The box is documented as a shortcut to "quickly reject hits" (:33-40); LUCENE-7212 describes the LatLon box it copies as rejecting "hits that won't compete anyway". A shortcut must not change results.
• The LatLon twin already treats an +Infinity bottom as "any possible value competes". In LUCENE-7102 (#8157, fixed 2016-03; its trigger was missing-first sorting, and LatLon has no radius), @rmuir wrote "+Inf means we've filled the priority queue with only missing values, so any possible value competes", and the LatLon box was made unbounded for that case.
• No precondition in the javadoc. "maxRadiusMeters is the maximum radius in meters" (Geo3DDocValuesField.java:179); nothing says out-of-radius hits come back unordered or that the query must stay inside the radius. No upstream test covers the Geo3D sorts; LUCENE-7212's last comment still lists "tests" as needed.

The strongest case for "works as designed" (rated weak by the devil's advocate and by a reviewer from another model family): the sort was meant to run with the matching query. In LUCENE-7212 (#8267) its author explains that an unbounded Geo3D distance sort "would not perform reasonably", so "If you introduced an upper bound to the circle radius as an additional argument, then it would work fine without additional geo3d code", and "The arguments would have to correspond exactly, though, to \"newXXXQuery\", including distance bounds". The javadoc begins "Creates a SortField for sorting by distance within a circle" (Geo3DDocValuesField.java:165). On that reading, out-of-radius hits were never meant to be there. A maintainer could add that GeoBaseDistanceShape and LeafFieldComparator are marked @lucene.experimental.

Why it fails: the requirement lives in a 2016 design comment, not in the API docs, and the code does not enforce it. Any query is accepted, and out-of-radius hits get a defined value, +Infinity, the same as documents without the field, which the comparator does tie-break. Whether such a hit reaches the secondary key depends on an internal box and on doc order, so the result for one Sort changes with n and with the segment layout. Experimental status allows API changes; it does not lift the Sort and compareBottom contracts of the public factories. The fix costs one comparison and changes nothing inside the radius. A maintainer may still prefer to document the pairing; the two kinds of +Infinity would stay inconsistent.

The shortcut is only wrong when the bottom is +Infinity, so both validated fixes return 0 instead of -1 in that case and leave everything else unchanged; they give identical results. Starting cmp at 0 is the shortest and tests the bottom once per document; the finder's version adds the same rule next to the shortcut and tests it once per out-of-box value. Skipping the box while the bottom is +Infinity (as the LatLon comparator does) would also work but computes every distance. Documenting "use with the matching distance query" changes nothing in the code and leaves the inconsistency; until a fix ships, that pairing is the workaround.

In Geo3DPointDistanceComparator.compareBottom, replace int cmp = -1; by a start value of 0 when bottomDistance is Double.POSITIVE_INFINITY (+3/-1 in one file). Every distance is at most +Infinity, so the document ties or wins; a value inside the shape is inside the shape's box, so it is still compared and gives 1. The finite-bottom path is unchanged.

     int numValues = currentDocs.docValueCount();
     assert numValues > 0;
 
-    int cmp = -1;
+    // Nothing sorts after an +Infinity bottom: the document ties with it (0), unless one of its
+    // values lies inside the shape (and so inside the bounds) and has a finite distance (1).
+    int cmp = bottomDistance == Double.POSITIVE_INFINITY ? 0 : -1;
     for (int i = 0; i < numValues; i++) {
       long encoded = currentDocs.nextValue();
 

Trade-offs

• While the bottom is +Infinity, an out-of-box hit now reaches the secondary comparator instead of being rejected; if it wins, copy computes its distance and setBottom runs, which rebuilds the box on its first 1,024 calls and then on every 64th. A document without the field takes the same path today, minus the distance computation. Not benchmarked.
• Results change only for out-of-radius hits, which were wrong.

What the checks validated

• Scratch worktree of a9779ef3c193, gradle, JDK 25: stock + the new test, 6 of 7 fail with assertions on and off; + the fix, the new test and TestGeo3DDocValues (8 tests) pass with assertions on and off, the whole lucene/spatial3d module (20 suites, 188 tests, 3 skipped) passes with assertions on and off, and :lucene:spatial3d:check -x test (ecjLint, forbiddenApis, checkGoogleJavaFormat) passes.
• Standalone runner: 7 of 7 with assertions on and off.
• No upstream test exercises a Geo3D sort, so the module run shows only that nothing else changes.

In the out-of-bounds branch, before continue: if (bottomDistance == Double.POSITIVE_INFINITY) { cmp = Math.max(cmp, 0); } (+5 lines: a 2-line comment and a 3-line branch). Same results as the first option, since a document has at least one value and every in-box value gives 0 or 1 against an +Infinity bottom.

           || y < priorityQueueBounds.getMinimumY()
           || z > priorityQueueBounds.getMaximumZ()
           || z < priorityQueueBounds.getMinimumZ()) {
+        // outside the bounds the distance is greater than bottomDistance, or +Infinity (outside
+        // the shape) when bottomDistance is itself +Infinity: then the document ties with it
+        if (bottomDistance == Double.POSITIVE_INFINITY) {
+          cmp = Math.max(cmp, 0);
+        }
         continue;
       }
 

Trade-offs

Same results as the first option, with +5 lines instead of +3/-1; it tests the bottom once per out-of-box value instead of once per document, but the rule sits next to the shortcut it corrects. The finder's original second comment line is 102 columns and fails checkGoogleJavaFormat; the version above rewords the comment to fit 100 columns ("the circle" became "the shape", "ties with the bottom" became "ties with it"); the code is unchanged.

What the checks validated

• The new test 7 of 7 with assertions on and off; the whole lucene/spatial3d module (188 tests) with assertions on; :lucene:spatial3d:check -x test with the reworded comment.
• Earlier: the finder's 4 tests (alone and on top of the LFV-551 and LFV-544 fixes), an independent reproducer's 7 tests with its equivalent fix, and a reviewer's 5-test box probe.

In setBottom, use an unbounded box (or a flag) when bottomDistance is +Infinity, as the LatLon comparator does since LUCENE-7102. Not built.

Trade-offs

Same results, but every hit computes its distance while the bottom is +Infinity, which costs more than the first two options.

Add to newDistanceSort and newPathSort that hits outside the radius (path) are not ordered by later SortFields and that the sort should be used with the matching Geo3DPoint.newDistanceQuery (newPathQuery). Not built.

Trade-offs

No behaviour change; but compareBottom stays inconsistent with compare and with documents that lack the field, and results still depend on doc order and the segment layout. The pairing normally keeps out-of-radius hits out (read, not run); hits right at the edge can still sort as +Infinity because the query and the sort read differently encoded points.

Method: bounded-exhaustive layout translation validation on the stock main jars, then code reading.

• The hunt unit on documented absent-field behaviour built a harness (AbsentFieldLayoutTV) that indexes the same documents in every segment layout it enumerates, plus an index-sorted variant, and compares each search with a force-merged single-segment reference.
• Its probe Sort(distance with maxRadius, id) differed only in index-sorted layouts at 1,200 documents per segment, where doc order differs from the tie-break order (11 mismatching layouts).
• An AI finder read compareBottom, found the bounding-box rejection under an +Infinity bottom, and reduced it to a 5-document single-segment JUnit without an index sort; independent AI tools then reproduced, reviewed and judged it (see the checks).