LatLonPoint.newDistanceFeatureQuery can skip a closer document under top-k pruning: its radius search stops up to 1 m short and the box adds only 7 cm

When a top-k search scored by LatLonPoint.newDistanceFeatureQuery has counted enough hits (1,000 for IndexSearcher#search(query, k)), the collector passes the lowest score that can still enter the top k to the query's scorer, which may then skip only documents scoring below it. The scorer turns that score into a radius with a binary search (computeMaxDistance) that stops once the interval is at most 1 m wide and returns its lower end, although distances up to the upper end may still compete. It then visits only the documents inside a lat/lon box built from that radius with Rectangle.fromPointDistance, which pads it by 7 cm. A competitive document between the box edge and the true cut-off is never visited, and a farther one is returned in its place. Because the box circumscribes the circle, this only happens near due north, south, east or west of the origin, and the skipped document lies in a thin band just beyond the box edge: less than about 0.53 m beyond it on a scorer's first threshold update and 0.93 m on later updates. The javadoc's own example use, a SHOULD boost next to another scoring query, is by code reading not affected. In the repro, search(newDistanceFeatureQuery("loc", 1, 0, 0, 1000), 1) returns a document 999.999 m north of the origin (score 0.50000024) instead of one 999.803 m north (score 0.5000492). Every release from 8.0.0 to 10.6.0 and main is affected (8.8.2 to 8.11.3 by inference); the fix is one line.

• The threshold. IndexSearcher#search(query, n) uses TopScoreDocCollectorManager(n, after, 1000) (search/IndexSearcher.java:100, :597-599). Once more than 1,000 hits are counted, TopScoreDocCollector calls scorer.setMinCompetitiveScore(Math.nextUp(topScore)) (search/TopScoreDocCollector.java:116-119, :154-164); in a later segment setScorer passes on the threshold already reached (:84-91).
• The radius. DistanceScorer#computeMaxDistance (document/LatLonPointDistanceFeatureQuery.java:283-308): javadoc "... so we binary search the maximum distance. The limit is set to 1 meter." (:284-285); invariant score(min) >= minScore && score(max) < minScore (:295); while (max - min > 1) (:296); assert min == Double.MAX_VALUE || score(min + 1) < minScore; (:306); return min; (:307). The first search starts from EARTH_MEAN_RADIUS_METERS * Math.PI (:256), so after 25 halvings the interval is 0.5965 m wide; later searches start from the previous radius and can end up to 1 m wide.
• The box. setMinCompetitiveScore (:353-472) builds Rectangle.fromPointDistance(originLat, originLon, maxDistance) (:375), which uses (radiusMeters + 7E-2) / EARTH_MEAN_RADIUS_METERS (geo/Rectangle.java:149-150, comment // LUCENE-7143). When fewer than min(leadCost, it.cost()) / 8 points are estimated in the box (:462-469), it replaces the iterator with the documents inside the box after the current one (:382-460, :470-471).
• Sampling. After the first 256 calls, setMinCompetitiveScore recomputes the radius and the box only on every 32nd call (:360-364); in between, the previous radius and box stay in place. The repro needs a single call; the sampling affects how often later updates happen, not the size of the gap.
• The repro's numbers (public Lucene classes on the main jar): threshold nextUp(0.50000024) = 0.5000003 after the 1,001st hit; bisection from 20,015 km in 25 steps to [999.7288 m, 1000.3253 m], returning 999.7288 m; box north edge 999.7988 m (encoded latitude 214543); doc 2001 at 999.8033 m (encoded latitude 214544) is outside; the true cut-off is 999.9989 m. A box built from 1000.3253 m (fix A) or from 999.7288 + 1 m (fix B) contains it.
• Only near the axes. The box is the circle's circumscribed lat/lon rectangle, so it touches the circle only due N/S/E/W. For r = 1000 m, a document 0.1 / 0.3 / 0.6 m beyond r is outside the box only within +-0.44 / +-1.23 / +-1.86 degrees of a cardinal bearing (outside the north edge when (r + d) cos(bearing) > r + 0.07 m).
• Scoring is unchanged. score() recomputes the distance from doc values (:311-316, :235-245; the distance is SloppyMath.haversinMeters, not an exact geodesic), so pruned and exhaustive search give every document the same float score; only the visited set differs.
• Size of the gap. Over every float threshold in [0.5, 1) for pivots 1 m to 1,000 km (58,720,256 values), on a scorer's first update the true radius exceeds the returned one by 0.24-0.30 m on average and at most 0.5965 m, and 80-87% of thresholds leave a competitive distance beyond the 7 cm pad; on later updates the gap can reach 0.9994 m. The first-update bound holds for every threshold: the first search always starts from 20,015,114 m, so its final interval is always 0.5965 m wide; later intervals are at most 1 m wide by the loop condition (:296).
• Three sizes; keep them apart. (1) How far the returned radius falls short of the true cut-off: under 0.5965 m on a first update, under 1 m later. (2) How far a skipped document lies beyond the box edge: (1) minus the 7 cm pad, so under about 0.53 m and 0.93 m. (3) How much farther the returned k-th hit is than the skipped one: (2) plus up to one float step of the score, because the returned hit scores just below the threshold (nextUp(topScore), search/TopScoreDocCollector.java:160) and the score is a float (:279-281), so its distance can lie anywhere in one float step, about (pivot + distance) x 6e-8 to 1.2e-7 m. By calculation with the scorer's formula and loop (first update, pivots 1 m to 1,000 km), the bound on (3) is under 0.60 m up to 100 km, 0.62-0.76 m at 1,000 km, 0.78-1.00 m at 3,000 km, 1.13-1.46 m at 8,000 km and 1.59-2.43 m at 15,000 km; computed, not a search that was run. In the repro (3) is 0.196 m.
• The integer sibling is exact. LongDistanceFeatureQuery#computeMaxDistance (document/LongDistanceFeatureQuery.java:273-294) has the same loop and return min on long distances, where max - min <= 1 leaves nothing unresolved (0 mismatches in the same exhaustive check). The double copy inherited it.

• Who is hit. Applications that rank top-k results by LatLonPoint.newDistanceFeatureQuery where the distance query alone sets the score: the top-level query, with or without a weight (BoostQuery), or the SHOULD clause next to FILTER clauses (ReqOptSumScorer.java:282-295 forwards the threshold when the required side scores 0), and later segments, which inherit the threshold. By code reading also the only scoring clause of a conjunction (ConjunctionScorer.java:88-92) and DisjunctionMaxQuery with tieBreaker 0 (DisjunctionMaxScorer.java:116-120). By the finder's reading not when another scoring clause is combined with it, which is the javadoc's example use (a SHOULD boost next to a scoring query).
• Default vs opt-in. Default codec, IndexWriterConfig and IndexSearcher#search(query, k), which prunes after 1,000 counted hits. Using the query is an explicit choice of a public core API.
• What goes wrong. Silently, a document that scores higher than the k-th returned hit is missing from the top k and a farther one is returned. Returned documents are real matches with the same scores as in an exhaustive search.
• Size. The skipped document lies less than about 0.53 m (first threshold update) to 0.93 m (later updates) beyond the box edge, near due N/S/E/W of the origin. The hit returned in its place is farther by at most that band plus one float step of the score: by calculation under about 0.6 m up to 100 km from the origin, more at continental distances (about 1.1 to 2.4 m at 8,000 to 15,000 km); 0.196 m in the repro.
• Scale. No minimum index size beyond the pruning start (the repro has 2,002 documents), but the box must hold fewer than one eighth of the candidates; when it would hold more, for example with dense data around the origin, the scorer keeps its old iterator and nothing is skipped.
• How often on natural data. Uniform random points (200,000 in a 20 km square or 1,000,000 in a 5 km square at latitude 45, pivot 1 km, k = 10 or 1): one segment 0 of 1,000, 0 of 300 and 0 of 1,000 queries; ten segments 1 of 1,000 and 2 of 300 (0.67%); 0 with the fix. The finder's explanation: a later segment's scorer receives the converged threshold once and bisects from 20,015 km, while within one segment the threshold usually keeps rising past the gap. With one planted near-threshold document at a near-cardinal bearing, 46 of 300 random configurations returned the wrong top-1 (0 with the fix, and 0 for the distance sort and the long sibling).
• Workaround. A distance sort (LatLonDocValuesField.newDistanceSort), which the randomized check found correct, or no pruning (new TopScoreDocCollectorManager(k, Integer.MAX_VALUE)), at the cost of scoring every match.

Copy the test into lucene/core/src/test/org/apache/lucene/document/ of a Lucene checkout and run the command below. It uses public Lucene APIs plus Lucene's test framework (LuceneTestCase, TestUtil) and no package-private member. Fixed data, one thread, the default codec pinned with TestUtil.getDefaultCodec() (so the random test codec cannot change the point tree), ByteBuffersDirectory and a plain IndexSearcher.

Doc 0 sits at encoded latitude 214586 on longitude 0 (999.9991 m due north of (0, 0)), the 2,000 fillers at latitude 40 to 42 and longitude 100, and the last doc, 2001, at encoded latitude 214544 (999.8033 m due north). The fillers matter twice: search(query, 1) starts pruning only after 1,000 counted hits, and they make the box selective enough to replace the iterator. A sweep of the filler count, on an earlier copy of the test, passed with 500, 998 and 999 fillers and failed with 1,000, 1,500, 2,000, 2,100, 2,500 and 3,000.

It failed in every recorded run: seed DEADBEEF with assertions on and off under gradle and the standalone runner, and seed 5EED1234 5 of 5 times. It passes :lucene:core:checkGoogleJavaFormat.

cp $REPRO/TestLatLonDistanceFeatureMinCompetitiveGap.java $LUCENE/lucene/core/src/test/org/apache/lucene/document/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.document.TestLatLonDistanceFeatureMinCompetitiveGap -Ptests.seed=DEADBEEF -Ptests.asserts=true
# and once more with -Ptests.asserts=false: it fails both ways

# gradle, fresh worktree at main 645d4fe14a20, -Ptests.seed=DEADBEEF -Ptests.asserts=true (the same with false)
TestLatLonDistanceFeatureMinCompetitiveGap > testClosestDocReturned FAILED
    java.lang.AssertionError: top-1 doc expected:<2001> but was:<0>
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:B2B0C866892F948E]: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.apache.lucene.document.TestLatLonDistanceFeatureMinCompetitiveGap.testClosestDocReturned(TestLatLonDistanceFeatureMinCompetitiveGap.java:55)

# standalone runner, the same test (tests_run=1 failures=1 each, seed DEADBEEF)
main 645d4fe14a20    -ea and -da   top-1 doc expected:<2001> but was:<0>
10.6.0               -ea and -da   the same
10.0.0, 9.12.3       -da           the same

# the numbers behind it (public Lucene classes on the main jar)
doc 0     lat bits 214586 lat 0.008993195  distance 999.9991 m  score 0.50000024
last doc  lat bits 214544 lat 0.008991435  distance 999.8033 m  score 0.5000492
minCompetitiveScore = nextUp(score(doc 0)) = 0.5000003  last doc competes: true
bisection: 25 steps, min 999.7288 m, max 1000.3253 m (width 0.5965 m); returns min
true competitive radius 999.9989 m
box for radius 999.7288 m (+7 cm pad): maxLat bits 214543 -> last doc (214544) inside: false, doc 0 (214586) inside: false
box for radius 1000.3253 m (+7 cm pad): maxLat bits 214671 -> last doc (214544) inside: true, doc 0 (214586) inside: true
box for radius 1000.7288 m (+7 cm pad): maxLat bits 214757 -> last doc (214544) inside: true, doc 0 (214586) inside: true
north edge of box(min) = 999.7988 m from the origin

• Contract. Scorable#setMinCompetitiveScore: "Tell the scorer that its iterator may safely ignore all documents whose score is less than the given minScore" (search/Scorable.java:45-52). The skipped document scores about 800 float ulps above the threshold.
• Test. TestLatLonPointDistanceFeatureQuery#testRandom runs CheckHits.checkTopScores(random(), q, searcher) (:396-437, :431), which requires TOP_SCORES and COMPLETE top-k to agree and asserts s1.score() < minScore for every skipped document (CheckHits.java:690-697, :748). Its random points are spread over the whole globe, so they are unlikely to land in the sub-metre band.
• Public javadoc. LatLonPoint#newDistanceFeatureQuery gives the exact score formula and mentions no approximation (document/LatLonPoint.java:357-368).
• The original review allowed over-inclusion only. In LUCENE-8482 (#9528), Adrien Grand (jpountz) wrote that when updating the iterator "it's fine if some documents still have a score that is less than the minimum competitive score" and that with a box "we will only fail to exclude documents that are within the bounding box of the circle but not in the circle itself" (comment of 2018-09-07).
• History. The loop was copied from LongDistanceFeatureQuery (LUCENE-8340, a9acdfdb544, 2018-09-04), where it is exact; the 7 cm pad in Rectangle.fromPointDistance is older (045659533cd, LUCENE-7147, 2016-03-29) and was sized for tiny-radius boxes (LUCENE-7143, #8198), not for a search tolerance.

The case (built by the intended-behaviour devil's advocate; every reviewer rated it weak): the method's javadoc says "The limit is set to 1 meter", so a 1 m pruning tolerance is documented; in #9528 the author, Ignacio Vera, and the reviewer both called a rounding effect "expected"; SloppyMath.haversinMeters is documented as off by up to 40 cm (util/SloppyMath.java:38), so a misranking inside a sub-metre band is within the score's precision; and the effect is small and rare.

Why it fails: the javadoc is on a private method and says when the search stops, not that pruning may drop competitive documents, and the next assert shows the author knew the cut-off lies above min. The "expected" in #9528 is about two very close points whose float scores tie in a boost-vs-sort test; here the skipped score is strictly higher. Both scoring modes compute the same score from the same encoded values, so distance accuracy cannot explain a disagreement between them. Small and rare is a question of priority (Low), not of intent.

Two one-line options, both validated with gradle in a fresh scratch worktree at 645d4fe14a20 (JDK 25.0.3, seed DEADBEEF, 2026-10-30): the minimal test fails without a fix and passes with either one, with assertions on and off. Both remove the reproduced gap and passed the suites listed; neither is proven for every coordinate (poles, dateline, large radii) beyond the randomized checks. A is the finder's fix and the one most checked, B is an independent reproducer's fix and changes less behaviour. Neither was benchmarked. Not recommended: a larger pad in Rectangle.fromPointDistance, which LatLonPointDistanceQuery, the distance sort comparator, NearestNeighbor, GeoEncodingUtils and Circle2D share; it would widen all their boxes and would not name the cause.

In computeMaxDistance, return max; instead of return min;, with assert score(max) < minScore; replacing assert min == Double.MAX_VALUE || score(min + 1) < minScore; and one javadoc sentence. The loop invariant gives score(max) < minScore and the score never rises with distance, so every document that scores at least the threshold is closer than max and inside the box.

      assert score(min) >= minScore;
-      assert min == Double.MAX_VALUE || score(min + 1) < minScore;
-      return min;
+      assert score(max) < minScore;
+      return max;

Trade-offs

• The early return at :289 (score(previousMaxDistance) >= minScore) can no longer fire after a scorer's first bisection, because the returned max always scores below its threshold, so every sampled call re-runs the bisection (at most 25 score evaluations). By code reading the box is still rebuilt only when the result changes (:368-371). Not benchmarked.
• The box radius is now up to 0.6-1 m above the true cut-off instead of up to 1 m below it: a few more candidates at the edge, none skipped.

What the checks validated

Gradle, fresh scratch worktree at 645d4fe14a20, -Ptests.seed=DEADBEEF, 2026-10-30:

• the minimal test fails without the fix with -Ptests.asserts=true and false, and passes with it both ways; after git apply -R it fails again;
• TestLatLonPointDistanceFeatureQuery with -Ptests.iters=20: 160 tests, 0 failures;
• --tests 'org.apache.lucene.document.*': 60 suites, 499 tests, 26 skipped, 0 failures (among them TestLatLonPointDistanceFeatureQuery, TestLongDistanceFeatureQuery, TestLatLonPointDistanceSort and the minimal test); this run and the 20-iteration run did not set -Ptests.asserts, so each ran only in the build's seed-derived default assertion mode;
• :lucene:core:checkGoogleJavaFormat passes with the fix and the test.
• Earlier, in the hunt, with the change shadowed onto the stock jars: the finder's test passes 6 of 6 with -ea and -da, and the independent reproducer's 6 of 6 with -ea (and with -da in the fact check's run); the randomized differential goes from 46 of 300 wrong top-1 to 0, the ten-segment natural-data runs to 0 and the scorer-level contract test to 0; the same line changed in the 8.0.0 source makes 8.0.0 pass.

Rectangle.fromPointDistance(originLat, originLon, maxDistance + 1) at :375, with a comment; the independent reproducer's fix. The loop exits with max - min <= 1, so every competitive distance is below min + 1, as the existing assert at :306 says.

Trade-offs

The bisection, its early return and how often the box is rebuilt stay as they are; the box reaches up to 1.07 m beyond min, slightly larger than with A; the call site now depends on the loop's 1 m tolerance, so a later change of one must update the other.

What the checks validated

Gradle, same worktree and seed: the minimal test passes with assertions on and off; TestLatLonPointDistanceFeatureQuery with 20 iterations: 160 tests, 0 failures; the org.apache.lucene.document package: 60 suites, 499 tests, 26 skipped, 0 failures (these two in the default assertion mode only); the format check passes. Earlier the reproducer's own 6-method test passed 6 of 6 with it.

Method: semi-formal (a hypothesis from code reading, witnessed by a tool). The hunt plan for the distance-feature pruning area pointed at the 1 m bisection that keeps the lower end while the box pads only 7 cm.

• Solver. With cvc5 1.4.2 (QF_FP), query q1, a proof attempt that the loop invariant and the exit test imply score(r + 0.075) < minScore, came back SAT in 20 s; q2, the real bisection unrolled 11 steps from a reachable previous radius of 2,048 m (pivot 1000, boost 1, a symbolic float threshold), came back SAT in about 3 minutes. Both models were replayed on the JVM.
• Exhaustive check. A JVM transcription of the search over every float threshold in [0.5, 1) for 7 pivots (58,720,256 thresholds) measured the gap (0.24-0.30 m on average, at most 0.5965 m on a first update) and found 0 mismatches for the integer sibling.
• Tests. A public-API JUnit on the stock main jar failed; randomized and natural-data probes measured how often it happens. The adjudication's credibility audit and the registration check re-ran it; it was later reduced to the single test shown here.