XY distance sort as a later sort key drops closer tied hits, because its comparator keeps a too-small bounding box when the queue bottom gets farther away

XYDocValuesField.newDistanceSort sorts by ascending distance, and a document without the field counts as +Infinity and sorts last. To skip far documents cheaply, XYPointDistanceComparator keeps a box around the origin sized to the distance of the queue's weakest hit (the bottom) and rejects any point outside it without computing its distance. setBottom records every new bottom but rebuilds the box only when the bottom is below Float.MAX_VALUE, and, after 1024 calls, only on every 64th call. That is safe while the bottom only gets closer, which holds when the distance is the first SortField. As a later SortField it only breaks ties, the bottom slot changes whenever an earlier key improves, and its distance can grow: the old box is then too small, and a tied document closer than the bottom but outside the old box is silently dropped. With Sort(cat, distance), three documents and top 1, you get the document without a location instead of the one at distance 3. Wrong in every release that was run (8.5.0 to 10.6.0) and on main; a 13-line change in the comparator (+13/-2) fixes it.

1. The contract. newDistanceSort "orders documents by ascending distance from the location", and a document missing the field "is treated as having Double#POSITIVE_INFINITY distance (missing values sort last)" (document/XYDocValuesField.java:136, :139-140). Sort: if the first SortField "produces a tie, then the second SortField is used to break the tie" (search/Sort.java:58-61). LeafFieldComparator: the bottom slot "may not hold the weakest value according to your comparator, in cases where your comparator is not the primary one (ie, is only used to break ties from the comparators before it)" (search/LeafFieldComparator.java:28-31), and compareBottom "should return the same result as FieldComparator#compare(int,int) as if bottom were slot1 and the new document were slot 2" (:55-57).
2. The box. On setBottom the comparator recomputes "a bounding box representing competitive distance to the top-N" so that compareBottom can "quickly reject hits based on bounding box alone" (document/XYPointDistanceComparator.java:35-37). It starts as the full encoded range (:55-58); setBottomCounter counts calls ("adversary protection", :60-61).
3. setBottom (:82-99), the fix site. bottom = values[slot] on every call (:83), but the box is rebuilt only if (bottom < Float.MAX_VALUE && (setBottomCounter < 1024 || (setBottomCounter & 0x3F) == 0x3F)) (:87-88), from XYRectangle.fromPointDistance (:90), which throws for a non-finite radius (geo/XYRectangle.java:76-78) and pads the radius by one float ulp (:81). Otherwise the box of an earlier bottom stays.
4. compareBottom (:122-161). A point outside the box is skipped (:139-146); only a point inside gets its distance compared (:149-154). It starts at cmp = -1 (:134) and returns -1, "not competitive", when no point is inside (:160).
5. The callers. MultiLeafFieldComparator.setBottom gives the slot to every comparator (search/MultiLeafFieldComparator.java:45-49), and its compareBottom asks a later comparator only on a tie of the earlier ones (:52-63). TopFieldCollector drops a hit when compareBottom <= 0 (search/TopFieldCollector.java:79-80) and calls setBottom when the queue first fills (:107-109) and after each competitive hit (:94-98).

• Doc 0 (b, (1, 0)) fills the 1-slot queue: bottom = 1 on call 0, so the box is rebuilt with radius Math.nextUp(1f) = 1.0000001: x and y in [-1.0000001, 1.0000001].
• Doc 1 (a, no location): "a" beats "b", so the category comparator decides and doc 1 replaces doc 0. Its distance is +Infinity (sortKey, :190-208). setBottom: bottom = +Infinity; +Infinity < Float.MAX_VALUE is false, so the radius-1 box stays.
• Doc 2 (a, (3, 0)): category ties, so the distance comparator decides. x = 3 is outside the box, no point is inside, and compareBottom returns -1, although compare(+Infinity, 3) is positive. The collector drops doc 2. Top-1 = doc 1; with n = 3 the same search returns [2, 1, 0].

From call 1024 on, only calls with (counter & 63) == 63 rebuild the box (1087, 1151, ...). The finder's case: 1,100 documents at (1, 0), each with a smaller category than the one before (so each becomes the new bottom), then A (category "0", (100, 0)) and B (category "0", (50, 0)). The last rebuild is at call 1087 with bottom 1. A's call is number 1100 (1100 & 63 = 12): the bottom becomes 100 but the box keeps radius 1, so B at x = 50 is dropped and top-1 is A. With 1,000 leading documents (A's call below 1024) or 1,087 (A's call is a 64th call) B is found.

The guard bottom < Float.MAX_VALUE also skips the rebuild for a finite bottom of at least Float.MAX_VALUE, which needs extreme coordinates. The fact check ran the repro's 3 documents with doc 1 at (-Float.MAX_VALUE, 0) instead of without a location: the same wrong top-1 on main, the right one with fix A.

With the distance as the first SortField, the bottom is the farthest hit in the queue and only gets closer. A box built for an earlier, larger bottom is then too large, which costs speed but no hits. The guard and the 1024/64 rule are correct under that assumption, and only under it.

• Who is hit. Applications that use XYDocValuesField.newDistanceSort (cartesian x/y points, lucene-core, public and not @lucene.experimental) as a later SortField, for example category first and distance second, or after any key that has ties, and ask for fewer hits than match. Default IndexWriterConfig, codec and IndexSearcher, any index size.
• When. (1) Some documents have no XY location (documented as +Infinity, sorting last): whenever one of them becomes the bottom after a finite bottom, the box stays stale until a finite bottom arrives on a rebuilding call. (2) More than 1024 setBottom calls in one search's comparator, and the bottom grows on a call that does not rebuild. (3) Rarely in practice: points so far from the origin that the bottom's distance reaches Float.MAX_VALUE.
• Size of the error. Only the tie-breaking among documents that tie with the bottom on all earlier keys is wrong: a dropped document is closer than the bottom it should have replaced. Documents that win on an earlier key are unaffected, and which documents match is unchanged. In the finder's 6-document case with n = 2 the result is [4, 2] instead of [5, 4].
• Silent. No exception and no assertion, with assertions on and off.
• Not affected by this bug. The distance as the first or only SortField (the case upstream tests cover), and n at least the number of hits (the queue is full only after the last hit, if at all, so compareBottom is never called). This is no claim about other box issues, for example the separate, already known rounding of XYRectangle.fromPointDistance for large centre coordinates (LFV-767), which was not assessed here. The LatLon distance sort does not have the missing-value trigger but has the sampling trigger (LFV-1136, a separate fix site).
• Likelihood: rare. The XY distance sort is little used (the hunt's GitHub code search found no production caller in Elasticsearch, OpenSearch or Solr), distance sorts are usually nearest-first, and no report was found since 8.5.0 (2020).

The test is the hunt's minimal repro, unchanged; it passes :lucene:core:check -x test as is. It uses new IndexWriterConfig() and newDirectory(); LuceneTestCase still randomizes the default codec and the directory, and the result does not depend on them: 5 random seeds fail the same way, and the hunt's main() form with each release's default codec and NIOFSDirectory fails on every release from 8.5.0. The bug is in the comparator's in-memory state, not in the index. Use the same test as the regression test.

Executed: gradle on main 5adff78bb168 in a scratch worktree, seed 5EED1132 with assertions on and off, and 5 iterations with a random root seed, all failing; with the fix, all passing.

cp $REPRO/TestXYDistanceSortAsSecondaryKey.java $LUCENE/lucene/core/src/test/org/apache/lucene/document/
cd $LUCENE && ./gradlew :lucene:core:test --tests TestXYDistanceSortAsSecondaryKey -Ptests.seed=5EED1132 -Ptests.asserts=true
# also with -Ptests.asserts=false; 5 of 5 random-seed iterations (-Ptests.iters=5) failed the same way

TestXYDistanceSortAsSecondaryKey > testMissingValueBottomDoesNotDropCloserTiedHit FAILED
    java.lang.AssertionError: expected:<2> but was:<1>
        at __randomizedtesting.SeedInfo.seed([5EED1132:D8A341B73D36BB55]:0)
        at org.junit.Assert.fail(Assert.java:89)
        at org.junit.Assert.failNotEquals(Assert.java:835)
        at org.junit.Assert.assertEquals(Assert.java:647)
        at org.junit.Assert.assertEquals(Assert.java:633)
        at org.apache.lucene.document.TestXYDistanceSortAsSecondaryKey.testMissingValueBottomDoesNotDropCloserTiedHit(TestXYDistanceSortAsSecondaryKey.java:54)
:lucene:core:test (FAILURE): 1 test, 1  failure

# assertions off (seed 5EED1132): the same failure
# 5 iterations, random root seed C3E00AB021044CC: 5 tests, 5 failures, each expected:<2> but was:<1>
# with the fix: :lucene:core:test (SUCCESS)

• Contract. newDistanceSort promises ascending distance with missing values last (XYDocValuesField.java:136-140); neither its javadoc (:133-151) nor the class javadoc limits it to the first SortField, and Sort defines later SortFields as tie-breakers (Sort.java:58-61). LeafFieldComparator names the non-primary comparator (LeafFieldComparator.java:28-31) and requires compareBottom to agree with compare(bottom, doc) (:55-57). The class javadoc says the box represents "competitive distance to the top-N" (XYPointDistanceComparator.java:35-36); a box smaller than the bottom's distance does not.
• Tests. TestXYPointDistanceSort uses the distance only as the first SortField (TestXYPointDistanceSort.java:69, :108, :239-240), where the bottom never grows, so no test sees it. Upstream does use a distance sort as a later key elsewhere: new Sort(SortField.FIELD_SCORE, LatLonDocValuesField.newDistanceSort("foo", lat, lon)) (TestLatLonPointDistanceFeatureQuery.java:471).
• History. LUCENE-9243 (c653c04bb17, 2020-03-02, #10283, "Add fudge factor when creating a bounding box of a xycircle") switched to XYRectangle.fromPointDistance, which throws for a non-finite radius, and added bottom < Float.MAX_VALUE && in front of the rebuild. Before it, a +Infinity bottom built the full box (Math.max(-Float.MAX_VALUE, x - bottom) and so on). The issue and its PR discuss only the fudge factor. An executed counterfactual: 8.5.0 with the comparator from before the guard returns the right top-1.
• The LatLon precedent. In LUCENE-7102 (#8157, 2016), Robert Muir wrote that for a +Infinity bottom "we can just bound Integer.MIN_VALUE .. Integer.MAX_VALUE for each dimension", because "+Inf means we've filled the priority queue with only missing values, so any possible value competes"; for -Infinity, "only missing values can possibly compete anymore (and only if you have another comparator)". So the use of a distance sort next to another comparator was considered. LatLonPointDistanceComparator.setBottom has no Float.MAX_VALUE guard (LatLonPointDistanceComparator.java:88-113), and the same 3-document sort with LatLonDocValuesField returns doc 2.
• The sampling is framed as protection of speed: "don't make gobs of bounding boxes if comparator hits a worst case order (e.g. backwards distance order)" (XYPointDistanceComparator.java:84-86). Nothing documents approximate results.

The strongest "intended" case (the cross-model reviews, OpenAI GPT-5.6, rated it moderate): the box and its sampling were designed for the shrinking bottom of a nearest-first sort; the comparator is package-private and LeafFieldComparator is @lucene.experimental (LeafFieldComparator.java:41); upstream XY tests use the distance only as the first key.

Why it fails: newDistanceSort is public, not experimental and not limited to the first position, and Sort makes every later SortField a tie-breaker; LeafFieldComparator's own javadoc names the non-primary comparator, and compareBottom's contract is exact; the guard apparently exists to keep a non-finite radius away from the box helper (an inference from the code; its commit and tests do not document a kept box as intended), and before it, as in the LatLon twin, a +Infinity bottom means the full box. The argument explains how the bug arose (an assumption that held for the first key), not why dropped hits would be acceptable. Verdict: not intended, a defect (finder, reproducer, the cross-model reviews, the devil's-advocate verifier, adjudication, audit).

One fix was built and validated in a scratch worktree of 5adff78bb168; the alternatives are listed with their trade-offs. The LatLon sibling (LFV-1136) needs the same "rebuild when the bottom grows" rule in LatLonPointDistanceComparator.setBottom, a separate fix site.

A new field boxBottom remembers the bottom the current box was built for. A bottom that is not below Float.MAX_VALUE (+Infinity, or a finite distance that large) resets the full box, as the code did before LUCENE-9243 for +Infinity and as the LatLon twin does; it also catches NaN and -Infinity, which valid points and a finite origin cannot produce, so that part is only defensive. A bottom larger than boxBottom always rebuilds. A bottom that shrinks keeps the 1024/64 sampling. It is the finder's patch with the else if condition on one line, as google-java-format wants, and one comment reworded after the fact check (it used to say "no finite box covers this bottom", which is wrong for a finite bottom of at least Float.MAX_VALUE).

    if ((bottom < Float.MAX_VALUE) == false) {
      // the bottom is not below Float.MAX_VALUE (+Infinity: no location): use the full box
      this.minX = Integer.MIN_VALUE;
      this.maxX = Integer.MAX_VALUE;
      this.minY = Integer.MIN_VALUE;
      this.maxY = Integer.MAX_VALUE;
      boxBottom = Double.POSITIVE_INFINITY;
    } else if (bottom > boxBottom || setBottomCounter < 1024 || (setBottomCounter & 0x3F) == 0x3F) {
      // a box built for a smaller bottom is too small, so always rebuild when the bottom grows
      boxBottom = bottom;
      XYRectangle rectangle = XYRectangle.fromPointDistance((float) x, (float) y, (float) bottom);
      // ... unchanged: encode minX, maxX, minY, maxY from the rectangle
    }

Trade-offs

• A nearest-first sort behaves exactly as today: its bottom never grows, so bottom > boxBottom is never true after the first box.
• A later-key distance sort pays one box rebuild (one XYRectangle and four encodes, the same work as each of the first 1024 calls) each time its bottom grows, so for growth the 1024/64 throttle no longer applies: an order in which the bottom grows on almost every update rebuilds on almost every call. No benchmark was run.
• One double field per comparator; no index, format or API change.

What the checks validated

• Stock main: the repro fails with assertions on and off (seed 5EED1132) and in 5 of 5 random-seed iterations; the finder's trigger matrix fails 3 of 8 (the 3-document case, the 6-document case and the 1,102-document case: 1,100 leading documents, then A and B; its 5 controls pass).
• Fixed: the repro, the trigger matrix (8 of 8), TestXYPointDistanceSort and TestXYDocValuesQueries, 51 tests, 0 failures, 3 nightly tests skipped, assertions on; the repro and the matrix with assertions off (9 tests); the repro and TestXYPointDistanceSort over 5 random-seed iterations (25 tests, 5 nightly skipped); every test in org.apache.lucene.document plus search.TestXY* and search.TestSort*: 71 classes, 699 tests, 0 failures, 31 skipped.
• :lucene:core:check -x test (google-java-format, ecj lint, forbidden APIs, the license check) passes with the fix and the test; eclint was not configured in this checkout and Error Prone was skipped. The finder's original line layout passed every test but failed checkGoogleJavaFormat, hence the one-line condition.
• The fixed-code gradle runs and the :lucene:core:check run above used the old wording of the full-box comment. After the rewording (the only change), the patched file was re-checked: google-java-format 1.37.0 (the version Lucene main pins) leaves it unchanged, and with it shadowed in, the repro (assertions on and off), the trigger matrix (8 of 8) and the fact check's extreme-coordinate probe pass. The gradle suites were not re-run for the comment change.
• In the hunt: the repro, the reproducer's own tests (missing-value and sampling), the cross-model reviewers' own tests and upstream TestXYPointDistanceSort pass with the same logic.

Add an else that resets minX ... maxY to the full range when the bottom is not below Float.MAX_VALUE.

Trade-offs

Behaves like the comparator before LUCENE-9243 for this case, which the history check ran: it fixes the 3-document repro, but the sampling trigger still fails. Not validated as a patch.

Rebuild the box on every call.

Trade-offs

Fixes both triggers, but brings back the cost the 1024/64 rule protects against for a nearest-first sort that sees hits in backwards distance order (LUCENE-7099). Not validated.

A javadoc restriction instead of a code change.

Trade-offs

Legitimises silently wrong results that a small change removes, contradicts LeafFieldComparator's javadoc for non-primary comparators, and the LatLon twin already gets the 3-document case right. Not validated.

Method: semi-formal (a proof-obligation audit of a class's contract, witnessed by an executable repro).

• The finder read XYPointDistanceComparator against the contracts it implements (newDistanceSort's ordering, LeafFieldComparator.setBottom and compareBottom) and asked what each method must guarantee. For compareBottom to agree with compare(bottom, doc), the box must contain every point closer than the bottom; setBottom keeps that only if it rebuilds whenever the bottom grows. Two paths do not: a bottom that is not below Float.MAX_VALUE, and an unsampled call after 1024. Both matter only when the bottom can grow, which needs the distance as a later SortField.
• The finder wrote the one-test JUnit (3 documents, top 1) on the public API and ran it on main with assertions on and off, 10.6.0 and 9.12.3; and an 8-test trigger matrix (both triggers and 5 controls), each case checked against an independent sort model and against the same search with n = maxDoc; and a fix sketch that passes all of it and upstream TestXYPointDistanceSort.
• An independent reproducer, two executed cross-model reviews, a devil's-advocate verifier and an adjudication then reproduced it with their own tests (section "Prior reports, history and checks").