Lat/lon distance queries can miss a point exactly at the radius, and match one just beyond it

A lat/lon distance query is documented to match "points within the specified distance", and Lucene's own distance is SloppyMath.haversinMeters, the value a distance sort and LatLonPoint.nearest report. To avoid an asin per document, the query compares each point's sort key with one threshold key that GeoUtils.distanceQuerySortKey(radius) computes per query. Several adjacent sort keys round to the same distance in metres, so the threshold must be the largest key whose distance is <= radius. The binary search instead returns the first key it meets whose distance equals the radius, which can sit below the point's own key (the point is dropped), When no key has exactly that distance it returns lo, the key where the search ends, whose distance is beyond the radius (its assert checks only that; in the repro it is the first key beyond it), and a point on that key matches. Example: the distance sort and haversinMeters both put a point 8154434.476304402 m from the center, and LatLonPoint.newDistanceQuery, LatLonDocValuesField.newSlowDistanceQuery and LatLonShape.newDistanceQuery(Circle) with exactly that radius all return 0 hits. With radius = the distance-sort value of the k-th hit, that very hit is missing in 92 of 400 trials. No special configuration is needed; every release from 6.1.0 (2016, LUCENE-7215) to 10.6.0 (by reading) and main. Searching on haversinMeters(key) <= radius and returning hi, the last key that passed (+12/-16 in one method), makes the repro pass, and one complete lucene/core test run with it passed (assertions on, seed DEADBEEF).

• Sort key: SloppyMath.haversinSortKey(lat1, lon1, lat2, lon2), the first half of the haversine formula, a double between 0 and 2 that grows with distance. Its low three bits are cleared "so subsequent rounding does not create ties" (SloppyMath.java:73-74), so only every 8th double can be a point's key.
• Distance: haversinMeters(key) = TO_METERS * 2 * asin(min(1, sqrt(key * 0.5))) (SloppyMath.java:57-59). haversinMeters(lat1, lon1, lat2, lon2) is exactly haversinMeters(haversinSortKey(...)) (:47-49), so a point's Lucene distance is a function of its key.
• Threshold: to skip the asin per document, a distance query computes once GeoUtils.distanceQuerySortKey(radius) and matches a point when its key is <= that threshold (LatLonPointDistanceQuery.java:107-108, GeoEncodingUtils.java:176 and :381-383; Circle2D.java:415, :438, :443 for every Circle geometry, including LatLonDocValuesField.newSlowDistanceQuery and LatLonShape).

1. Consecutive keys often give the same distance value (around the first repro point, runs of 2 or 3 keys; tables below). "key <= threshold" equals "distance <= radius" only if the threshold is the largest key whose distance is <= radius.
2. distanceQuerySortKey (GeoUtils.java:114-141) binary-searches the bit patterns 0 to Double.MAX_VALUE (about 63 steps). When haversinMeters(mid) == radius it returns mid at once (:127-128), whichever key of the run it hit first: a point on a later key of the run is at exactly the radius but fails.
3. When no key has exactly the radius' distance, it returns lo (:136-140), the key where the search ends: it tested above the radius and the key just before it tested below, so where distance does not decrease as the key grows it is the smallest key beyond the radius. The assert haversinMeters(ceil) > radius checks only the first part. A point on that key matches although it is beyond the radius.

Radius 8154434.476304402 m, the point's own distance (keys as offsets from the point's key):

Radius 1.6056103066824857E7 m, one ulp below the second point's distance:

No key has distance exactly 1.6056103066824857E7 (the distances jump from ...853 to ...859), so the search returns the point's own key and the point matches. With the fix the thresholds are key 0 and key -1, and both points are classified as haversinMeters says.

On random encoded points roughly a fifth to a third of "radius = a point's distance" queries miss that point, and a similar share of "radius one ulp below" queries still match it; the rate depends on the points (494 and 457 of 2,000 random pairs in one run, 154 and 147 of 480 queries per factory in another).

• Which queries. LatLonPoint.newDistanceQuery, LatLonDocValuesField.newSlowDistanceQuery, their IndexOrDocValuesQuery combination, LatLonShape.newDistanceQuery with a Circle (INTERSECTS, WITHIN, and DISJOINT with the errors mirrored) and LatLonPoint.newGeometryQuery / LatLonDocValuesField.newSlowGeometryQuery with a Circle: all nine tested factories share the threshold and show identical counts (400 point documents; CONTAINS and indexed lines or polygons were not run). By reading, the same threshold is used wherever a Circle is evaluated and in the points query's cell relations. The first two are not @lucene.experimental.
• Default vs opt-in. Nothing to opt into: the error is in the per-query threshold, not in the codec, writer or searcher. The repro runs under the test framework's randomized writer config, codec and searcher, the finder's harness under a default IndexWriterConfig with NoMergePolicy and a plain IndexSearcher; both fail the same way, with assertions on and off.
• When it bites. Only a radius equal to a point's own Lucene distance, or less than one sort-key step below it (a few ulps of the distance for radii under 19,000 km). Typed or random radii practically never land there, which is why upstream's random tests pass. Reusing a distance Lucene computed does: "everything at least as close as my k-th nearest hit" (radius = the k-th distance-sort value) lost that very hit in 92 of 400 trials (116 of 400 with another seed), once the nearest hit at 683007.9829461674 m, whose own distance as radius returned 0 hits. LatLonPoint.nearest reports the same value as the distance sort (by reading, and equal for the repro point), so a radius taken from it should behave the same; that workflow was not run. "Strictly closer than this document" (radius Math.nextDown of its distance) can still return the document.
• Scale. A point is dropped only when its distance equals the radius exactly; a wrongly matched point was at most about 2e-8 m beyond the radius for radii under 19,000 km, and 2.6e-5 m in the worst case near the antipodal maximum (1.2 million radii probed; measured, not proven). That is far below the coordinate encoding (about 4.7 mm of latitude) and the documented 40 cm error of haversinMeters. The harm is inconsistency: the query disagrees with the distance the same application shows from Lucene's sort.
• How likely. Rare; the searches listed under Prior reports found no earlier report.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: hits at radius 8154434.476304402 m expected:<1> but was:<0>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:647)
       org.apache.lucene.document.TestDistanceQueryRadiusBoundary.testPointAtExactlyTheRadiusMatches(TestDistanceQueryRadiusBoundary.java:45)

• The method promises exactness. "binary search to find the exact sortKey needed to match the specified radius any sort key lte this is a query match" (GeoUtils.java:110-113); haversinSortKey "always compares the same" as haversinMeters (SloppyMath.java:61-64), though that reads most naturally as a claim about ordering, not as a promise that a radius maps back to an exact key.
• The public contract is inclusive. "matching points within the specified distance", radiusMeters the "maximum distance from the center in meters" (LatLonPoint.java:285-292; LatLonDocValuesField.java:196-209 says the same).
• Upstream's oracle is exact. SloppyMath.haversinMeters(centerLat, centerLon, lats[id], lons[id]) <= radiusMeters, no tolerance (BaseGeoPointTestCase.java:1061). It never draws a radius equal to a point's distance; TestGeoUtils.java:49 carries "TODO: randomly quantize radius too, to provoke exact math errors?".
• A speed change, not a semantics change. Until 6.0.1 the leaf check was SloppyMath.haversinMeters(h1) <= radiusMeters. LUCENE-7215 (#8270, CHANGES "Optimizations") replaced it with the key comparison; its issue says "we just need to compute the exact sort key needed for comparisons" and never discusses the boundary. The original query (LUCENE-7054, #8110) came with a random test "that doesn't have any leniency/tolerance/deltas ... to keep testing exact".
• Precedent. LUCENE-7185 (#8240) fixed the same kind of key/metre tie inconsistency for the distance sort, by masking the low bits of the sort key.
• Wrong in both directions. A deliberately lenient threshold would never drop a point at the radius; this one drops them (equality branch) and admits points beyond it (ceil branch).

The strongest case for "works as designed" (built by the intended-behaviour checker; the cross-model reviewers raised it too): SloppyMath is "Math functions that trade off accuracy for speed" with up to 40 cm error (SloppyMath.java:31, :38); GeoUtils and Circle are @lucene.experimental (GeoUtils.java:49, Circle.java:47); the ceil comment and assert show the author knew the returned key is beyond the radius; and no test pins the exact boundary.

Why it fails: the 40 cm figure compares haversinMeters with the true haversine, not the query with haversinMeters, the number the distance sort and nearest report; the equality branch causes false negatives, so the cut is not conservative; the method's own javadoc says "exact"; LatLonPoint.newDistanceQuery is not experimental; and the change that introduced it was filed as an optimization of an exact predicate. The ceil comment explains why an exact match may not exist, not that the boundary may move. What the rebuttal does not cover: the public javadocs ("within the specified distance", "maximum distance from the center in meters") name no distance function, do not promise agreement with the distance sort and define no rounding at the boundary, so maintainers can call the exact boundary unspecified, and documenting it as approximate is a legitimate choice. Expect the "sloppy by design" push-back.

One fix was applied in a scratch worktree at a9779ef3c193 and run through gradle; the alternatives were not run.

Workaround today: to include a point at a known distance d, pass Math.nextUp(d) as the radius (0 misses over 480 such queries for each of the 9 factories in the fact check's run); a point one more ulp beyond can then match by the same bug.

In GeoUtils.distanceQuerySortKey (GeoUtils.java:114-141) drop the equality early return and the ceil return: move lo past every key with haversinMeters(key) <= radius, move hi below every key above it, and return hi. The search ends on a key hi that tested within the radius while hi + 1 tested beyond it; where distance does not decrease as the key grows, that is the largest key within the radius. The javadoc gains "the largest sort key whose distance is less than or equal to the radius", and an assert haversinMeters(floor) <= radius replaces the old ceil assert (it holds for every radius the query constructors accept: hi ends on the last key that passed). The "effectively infinite" branch is unchanged. The finder wrote this fix and the independent reproducer the same one; this version adds the javadoc sentence and the assert. For the PR, qualify the javadoc sentence and the code comment ("assuming the distance does not decrease as the key grows") or limit them to point keys: at the one measured dip they do not hold for raw keys (below).

    long lo = 0;
    long hi = Double.doubleToRawLongBits(Double.MAX_VALUE);
    while (lo <= hi) {
      long mid = (lo + hi) >>> 1;
      double midRadius = haversinMeters(Double.longBitsToDouble(mid));
      if (midRadius <= radius) {
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }
    double floor = Double.longBitsToDouble(hi);
    assert haversinMeters(floor) <= radius;
    return floor;

Trade-offs

• Cost (not benchmarked): no per-document change; the search stays bounded at about 63 haversinMeters calls per query, and the stock code already runs the full search whenever no key has exactly the radius' distance. Radii that hit an equal-distance key, such as distances reused from a sort, used to stop early and now run the full search; that per-query cost was not measured.
• Premise: exact if haversinMeters(key) never decreases as the key grows. For arguments up to sin(73 degrees) (keys up to about 1.83) SloppyMath.asin interpolates from one of 8,193 table cells (SloppyMath.java:144-155, :239-243); above that it uses an fdlibm-derived formula (:156-169). So the cell boundaries and the switch are where a dip could hide. A scan of 2,074,872,896 adjacent key pairs (every boundary and the switch +/-65,536 keys, the last 1M keys before 2.0, 1,000 random runs of 1M keys) found exactly one decrease: one ulp (1.86e-9 m) at key 1.4201579892440324 (about 12,770 km), on the boundary between cells 7218 and 7219. There, for radius 1.2770150274362441E7 the fix returns a key 2 below the dip while 2 later keys have exactly that distance; neither has its low 3 bits clear, so no point can sit on them. Over the 4,514 radii equal to a distance of the 8,193 nearest keys, that is the fix's only miss; stock misclassifies a key with its low 3 bits clear (one a point could have; the probe checks only the bit mask) for 232 of those radii. Measured, not proven.
• Inputs: the query constructors reject negative and NaN radii (LatLonPointDistanceQuery.java:62-64, Circle.java:63-65), but distanceQuerySortKey is public and does not check its argument. On a direct call with a negative or NaN radius the fixed loop ends at hi = -1: the new assert fails with assertions on, and with them off the method returns NaN, which no key is <= (stock: 0.0 for a negative radius; for NaN its own assert fails, +Infinity with assertions off). A PR may want an explicit argument check.
• For the PR (not done here): the threshold also drives BKD cell pruning and acceptance and the grid relations (GeoUtils.java:147-180, GeoEncodingUtils.java:176-187, :379-385, LatLonPointDistanceQuery.java:197-218, Circle2D.java:421-424); the tests here use one-document indexes, a 400-document harness and random point pairs, so a PR test should also cover cells fully inside and outside the circle. The regression tests do not pin the dip spot or invalid direct inputs.

What the checks validated

• Stock plus the tests: the 2 repro tests and the new TestGeoUtils test fail (3 of 10 tests in the two classes), with assertions on (seed DEADBEEF) and off (5EED0573).
• With the fix: org.apache.lucene.geo.*, org.apache.lucene.document.*LatLon*, org.apache.lucene.search.TestLatLon* and the repro, 40 suites, 434 tests, 26 skipped, 0 failed, assertions on and off; :lucene:core:check -x test (format, ecjLint, forbiddenApis) passes; one complete lucene/core test run (JDK 25, aarch64, assertions on, seed DEADBEEF): 749 suites, 8,892 tests, 322 skipped, 0 failed.
• The independent reproducer's 3-test class passes with the fix; earlier checks found 0 errors over the finder's 13,320 factory queries, 20,000 random pairs and 8,000 history queries per factory on main and on 6.1.0.

Keep the key test, but for keys within a few steps of the threshold compute haversinMeters(key) <= radius.

Trade-offs

Exact even where haversinMeters dips, given a proven bound on how many keys around the threshold to check; one more branch per document and an asin only for points next to the boundary; more code to review. Not run.

haversinMeters(key) <= radius for every candidate document, as before 6.1.0.

Trade-offs

Exact, but brings back the per-document asin that LUCENE-7215 removed for speed. Not run.

Javadoc only.

Trade-offs

No code change and a legitimate maintainer choice, but the query keeps disagreeing with the distance sort and nearest, contradicts the method's own "exact sortKey" javadoc, and leaves the k-th-hit workflow broken.

Method: translation validation of the real jar's distance predicates at the radius boundary (semi-formal tier).

• A hunt unit on lat/lon geo queries planned a check of "a radius at the exact distance of a grid point". Its harness ran the 9 public distance-query factories over 400 encoded points and 40 centers with radius 0, d, nextDown(d) and nextUp(d) (d = SloppyMath.haversinMeters(center, point)), against upstream's own oracle haversinMeters(center, point) <= radius: 154 of 480 radius-d queries missed the point and 147 of 480 radius-nextDown(d) queries matched it, for every factory; nextUp(d) and radius 0 were always right (logged per kind for LatLonPoint.newDistanceQuery; the fact check's own run confirms it for all nine).
• Reading GeoUtils.distanceQuerySortKey gave the cause; a patched copy (a search for the last key within the radius) removed every mismatch (0 of 13,320 factory queries), and a public-API JUnit on fixed coordinates reproduced it on the stock jar.
• Then an independent reproducer, reading-only reviews by a model from another family (OpenAI GPT-5.6), an intended-behaviour devil's advocate, an adjudication and a credibility audit; this doc's runs added a targeted probe of the fix's monotonicity premise.