LatLon distance sort used as a tie-breaker drops closer tied hits after 1024 queue updates

LatLonDocValuesField.newDistanceSort speeds up distance sorting with a bounding box around the distance of the queue's worst hit (the bottom): compareBottom rejects any point outside the box without computing its distance. setBottom rebuilds the box on each of the first 1024 bottom updates, then only on every 64th. That is safe while the bottom distance only shrinks, which holds when distance is the first sort key. When distance only breaks ties of an earlier key, a hit that wins on that key can move the bottom farther away; the old, smaller box then rejects a tied hit that is closer than the new bottom, and the top N (or a searchAfter page) is silently wrong. One test with 1026 documents and default settings shows it on main; a main() form of an earlier version of this test gives the same wrong top hit on 13 releases from 6.1.0 to 10.6.0, and every release in between has the same guard line. A one-condition fix (also rebuild when the bottom grows) passes the repro and the existing distance-sort tests.

1. Every competitive hit updates the bottom. TopFieldCollector calls setBottom after each hit that enters a full queue (search/TopFieldCollector.java:94-100, and :102-112 when the queue first fills). MultiLeafFieldComparator.setBottom passes the bottom slot to every comparator, the later ones too (search/MultiLeafFieldComparator.java:45-49).
2. The sampled rebuild (fix site). LatLonPointDistanceComparator.setBottom always sets bottom = values[slot] (:89) but rebuilds the box only if setBottomCounter < 1024 || (setBottomCounter & 0x3F) == 0x3F (:93), "if comparator hits a worst case order (e.g. backwards distance order)" (:90-92). The counter is never reset (:66, :112) and getLeafComparator returns the same object for every segment (:185-194), so the count is per collector, not per segment: one collector for all segments with the default IndexSearcher (search/IndexSearcher.java:226-231), one per slice with an executor (:760-772).
3. The repro, step by step. Doc 0 fills the empty queue (search/TopFieldCollector.java:102-112) and docs 1..1023 each replace the top-1 hit on cat: updates with counter 0..1023, each rebuilding a box of about 1.1 km radius (0.01 degrees of latitude plus the 7 cm pad of geo/Rectangle.java:150). Doc 1024 wins on cat (1000 < 3977) without a distance check; its update has counter 1024, 1024 & 0x3F is 0, so bottom becomes about 2,002 km while the 1.1 km box stays.
4. The drop. Doc 1025 ties on cat, so MultiLeafFieldComparator.compareBottom asks the distance comparator (:52-64). Latitude 13.5 is outside the box, so compareBottom returns its initial cmp = -1 without computing the distance (LatLonPointDistanceComparator.java:148-160, :176), and thresholdCheck drops the hit (search/TopFieldCollector.java:79-92). Its distance, about 1,501 km, would have won. searchAfter uses the same check (:186, :228); a two-page check probe returns the farther tied document as page 2 on main and the closer one with fix A.
5. Why the first key is safe. As the first key, a new bottom only arrives with a closer hit, so an old box is always large enough. A later key has no such guarantee, as LeafFieldComparator states.

Mechanism check (N filler documents; run in the earlier test's layout, re-run by the fact check in the repro's own layout with the same table): wrong exactly when the far document's update skips the rebuild (N = 1024, 1086, 1088, 2048), right when it rebuilds (N = 1000, 1023, 1087, 2047).

Also with a missing location (found by reading, then run by the fact check): after 1024 updates, a bottom hit without a location (sort key +Infinity, :212) is another way the bottom grows; main returns that tied document instead of the closer one, and fix A returns the closer one.

• Who. Any search with LatLonDocValuesField.newDistanceSort as the second or later SortField: "newest first, then nearest", "category, then nearest", "rating, then nearest". Public API only; default IndexWriterConfig, codec and searcher.
• When. More than 1024 bottom updates in one collector, which can happen when the earlier key's best values arrive late in doc-id order (for example newest first over documents indexed in date order). Then the bottom distance must grow on one of the 63 of 64 updates that keep the box, and a document tied on the earlier keys must lie between the stale box and the new bottom distance.
• How often (a probe, not the repro). Sort(day INT desc, distance), top 10, documents indexed in day order, locations uniform in a 2 by 2 degree area, 20 random trials per size, compared with a brute-force sort: a wrong top 10 in 11/20 trials with 6,000 documents, 11/20 with 5,000 and 10/20 with 3,600; 0/20 with 600 documents (fewer than 1024 updates); 0/20 for the three larger sizes with the fix. With an IntField first key sorted by SortedNumericSortField (desc), where the numeric comparator can skip documents, 6,000 documents still gave 11/20 wrong.
• Effect. Silent: no exception, totalHits the same as with the fix and the match set unchanged, the same with -ea and -da (a check probe prints both). A closer tied document is replaced by a farther one in the top N or on a searchAfter page.
• Versions. Every release from 6.1.0 (2016) to 10.6.0 (13 of them run, the rest have the same guard line), and main.

• Deterministic: the test has no random input; the test framework still randomizes its usual environment from the seed (codec, similarity, locale, time zone, some writer settings). It failed in every run: the standalone runner (seed DEADBEEF, -ea and -da) and gradle (seed DEADBEEF, codec Asserting(Lucene104), asserts on and off).
• 1024 filler documents is the smallest count that shows it: with 1023, doc 1024's update still rebuilds the box and the result is correct.
• The test does not force one segment (no NoMergePolicy, no leaf-count assertion); with the default settings the 1026 documents end in one segment (a check probe prints segments=1), and the counter spans segments anyway.
• MatchAllDocsQuery.INSTANCE does not exist on 10.0.0 and older; use new MatchAllDocsQuery() there.
• checkGoogleJavaFormat passes with the file in the tree. As a regression test, the same method fits in TestLatLonPointDistanceSort.

cp $REPRO/TestLatLonDistanceSortSecondaryKey.java $LUCENE/lucene/core/src/test/org/apache/lucene/document/
cd $LUCENE && ./gradlew :lucene:core:test \
  --tests org.apache.lucene.document.TestLatLonDistanceSortSecondaryKey -Ptests.seed=DEADBEEF
# also with -Ptests.asserts=false: same failure

# gradle, scratch worktree at 5adff78bb168, -Ptests.seed=DEADBEEF (same with -Ptests.asserts=false)
TestLatLonDistanceSortSecondaryKey > testCloserTiedDocIsNotDropped FAILED
    java.lang.AssertionError: expected:<1025> but was:<1024>
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:6FA20F4851EBD307]: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.TestLatLonDistanceSortSecondaryKey.testCloserTiedDocIsNotDropped(TestLatLonDistanceSortSecondaryKey.java:55)
:lucene:core:test (FAILURE): 1 test, 1  failure

# with fix A: :lucene:core:test (SUCCESS): 1 test (asserts on and off)

• search/LeafFieldComparator.java:28-31: 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)". The note dates from LUCENE-1779 (2009), before this comparator existed.
• search/LeafFieldComparator.java:55-57: compareBottom "should return the same result as FieldComparator#compare(int,int) as if bottom were slot1 and the new document were slot 2".
• search/Sort.java:59-61: "if it produces a tie, then the second SortField is used to break the tie".
• document/LatLonDocValuesField.java:143: "This sort orders documents by ascending distance from the location." The class javadoc says "Sorting by distance is efficient" (:40).
• search/FieldValueHitQueue.java:146-151 builds comparators for later sort fields as usual; document/LatLonPointSortField.java:41-43 neither rejects nor special-cases that position.

• TestLatLonPointDistanceSort always puts distance first (Sort(distanceSort, id), :241).
• TestLatLonPointDistanceFeatureQuery sorts by score, then distance (:471), but that score falls with the same distance, so the two keys agree and the bottom distance still only shrinks.

• The guard came with the box in e169050dc3f (LUCENE-7099, 2016-03-11); its parent computed exact distances.
• LUCENE-7103 (#8158) treats the worst case, in which the distance function "could still get called many times", as a speed problem only; on LUCENE-7212 (#8267) the author described the box as rejecting "hits that won't compete anyway", with "a guard in the code to start doing it less often (only every Nth update)".
• Five days later 6f124e10017 removed the javadoc warning that distance sorting may be expensive, because "this sort makes bounding boxes for you".

The case. The sampling is a deliberate, ten-year-old speed guard that is sound for the use it was designed and tested for (distance first); the same guard was copied into the XY, Geo3D and nearest-neighbour code; and LeafFieldComparator is @lucene.experimental, so users should put distance first or live with it.

Why it fails. The user touches only public, non-experimental API (Sort, SortField, newDistanceSort). Sort makes tie-breaking keys a normal feature, LeafFieldComparator names the non-primary case, and newDistanceSort documents an ascending distance order; the comparator cannot even tell its position. Upstream called the guard a way to rebuild the box less often, never a licence to drop hits, and copying it only spreads the same unstated assumption. Two separately prompted cross-model reviews (both OpenAI GPT-5.6, the same model) and a devil's-advocate check built this case; all three found the bug real and the case weak. The nearest-neighbour search (NearestNeighbor) has the same guard line but is not a sort comparator; it is not part of this finding.

Option A was built and tested in a scratch worktree of 5adff78bb168; B and D were not built; C was run only as a control.

Add a field boxBottom (initially +Infinity, which matches the initial unbounded box), set it whenever the box is rebuilt, and add || bottom > boxBottom to the rebuild condition.

  // the bottom value the current bounding box(es) were built for (infinite: no box yet)
  double boxBottom = Double.POSITIVE_INFINITY;

  public void setBottom(int slot) {
    bottom = values[slot];
    // Keeping an old box is only safe if the bottom did not grow, which can happen when this
    // comparator only breaks ties of an earlier sort field: always rebuild the box then.
    if (setBottomCounter < 1024 || (setBottomCounter & 0x3F) == 0x3F || bottom > boxBottom) {
      boxBottom = bottom;
      Rectangle box = Rectangle.fromPointDistance(latitude, longitude, haversin2(bottom));
      ...

Trade-offs

• No change when distance is the first key: the bottom only shrinks, so the new condition is never true.
• As a later key, the box is rebuilt on every update that grows the bottom: the same per-update cost as the first 1024 updates; if the bottom grows on nearly every update (an adversarial order), that is a rebuild on nearly every update, the cost the sampling avoids today. No benchmark was run.
• Also covers a +Infinity bottom (the rebuilt box is then the whole world; the fact check's missing-location probe passes with fix A) and any other way the bottom can grow.

What the checks validated

• Gradle, scratch worktree at 5adff78bb168, JDK 25.0.3, -Ptests.seed=DEADBEEF: the repro fails without the fix and passes with it, asserts on and off.
• With the fix: org.apache.lucene.document.* plus TestNearest, 504 tests, 26 skipped, 0 failures; TestLatLonPointDistanceSort and TestNearest with -Ptests.nightly=true, 9 tests (testRandomHuge included); checkGoogleJavaFormat passes.
• The finder's version of the same condition removes every wrong top 10 of the probe (0/20 for 3,600, 5,000 and 6,000 documents). Not run: the full lucene/core suite.

LatLonPointSortField.getComparator already receives Pruning.NONE for every later sort field (search/FieldValueHitQueue.java:146-151) but ignores it (document/LatLonPointSortField.java:41-43); it could tell the comparator to rebuild on every update.

Trade-offs

Other callers pass Pruning.NONE too (the grouping collectors, NonPruningSortField) and would lose the sampling where it is safe; it does not cover a bottom that grows for another reason.

Always rebuild the box. A comparator with only this change passes an independent version of the test, and so does 6.1.0 with the same change.

Trade-offs

Brings back the worst-case cost LUCENE-7099 and LUCENE-7103 guarded against (data in decreasing distance order, a huge top N).

No code change.

Trade-offs

Contradicts Sort's tie-break contract and LeafFieldComparator's non-primary note; users cannot see the limit coming.

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

• The obligation: for every document, compareBottom(doc) equals compare(bottom, doc) (LeafFieldComparator.java:55-57), including for a comparator that is not the primary one (:28-31).
• Discharging it for LatLonPointDistanceComparator needs "every point outside the current box is farther than the current bottom". A rebuilt box gives that; a kept box gives it only if the bottom did not grow since the box was built. Distance as the first key guarantees that; a later key does not.
• The finder then built a one-test JUnit (public API; an earlier form of the repro shown here, with NoMergePolicy, the default codec set explicitly and fillers at 0.009 degrees) that fails on main with -ea and -da, checked that it passes with the fix, mapped exactly which filler counts fail (the mechanism check) and measured the newest-then-nearest probe. The repro on this page is a later, minimal form of that test with plain default settings.
• An independent reproducer, cross-model reviews (OpenAI GPT-5.6), a devil's-advocate check, an adjudication, a history and prior-art follow-up, a credibility audit and a final repro check followed (see the checks).