S2PrefixTree: a Contains query for a point misses the document stored at that same point when the point lies on an S2 cell edge, such as the equator

With RecursivePrefixTreeStrategy over the experimental S2PrefixTree (Geo3d spatial context), a Contains query whose shape is a point P misses every document indexed as exactly P when P lies on an S2 cell edge: Contains(Point(10, 0)) returns 0 hits for a document at Point(10, 0), while Intersects returns 1, and the geohash and quad trees return 1. Indexing stores a point under one cell per level (S2CellId.fromLatLng), but S2PrefixTreeCell.getNextLevelCells has no point case and returns every child cell that touches P (2 on an edge, 4 at (0,0)); ContainsPrefixTreeQuery ANDs the documents of those children, and the child P was not stored under has none. It affects every release from 7.3.0 to 10.6.0 (10.6.0 by reading) and main, also through CompositeSpatialStrategy. A point case in getNextLevelCells that returns the one child P is stored under, as LegacyCell already does for the other trees, fixes it without reindexing.

• Prefix tree (RPT): RecursivePrefixTreeStrategy indexes a shape as the grid cells it covers, one term per cell, from coarse to fine levels. A query walks the same grid from the top and looks the cells up.
• S2 cells: S2PrefixTree uses S2 geometry: the sphere is projected onto the 6 faces of a cube, the 6 faces are the first level, and each further level splits a cell into 4 children (16 or 64 with arity 2 or 3), the first split running along the face's centre lines. So on the four equatorial faces the face borders (longitudes ±45 and ±135) are cell edges from the first level on, the equator and longitudes 0, ±90 and 180 from the second level on, and (0,0), the centre of face 0, is a corner where 4 cells meet.
• Contains: SpatialOperation.Contains, the OGC "Covers" predicate: the indexed shape covers the query shape, boundary included; equal shapes count.

S2PrefixTree.getTreeCellIterator (S2PrefixTree.java:141-155 at a9779ef3c193) handles a Point by computing S2CellId.fromLatLng(S2LatLng.fromDegrees(lat, lon)).parent(...) and emitting that cell and its ancestors: exactly one cell per level. For a point on an edge, fromLatLng puts it into one of the touching cells.

For Contains, RecursivePrefixTreeStrategy.makeQuery builds a ContainsPrefixTreeQuery (RecursivePrefixTreeStrategy.java:199-201). Its visitor asks cell.getNextLevelCells(queryShape) (ContainsPrefixTreeQuery.java:120) and computes "the AND of all child results" (:111): a child with no indexed term makes the result empty and stops the loop (:123-124, :137); otherwise the next child is searched only among the documents found so far (:138).

S2PrefixTreeCell.getNextLevelCells (S2PrefixTreeCell.java:156-173) builds all children and returns new FilterCellIterator(cells.iterator(), shapeFilter). FilterCellIterator keeps every cell whose relation to the filter intersects() (FilterCellIterator.java:48-53), and a closed cell whose border passes through the point intersects it. The geohash and quad trees special-case a point and return only the sub-cell it falls in (LegacyCell.java:134-143):

if (shapeFilter instanceof Point point) {
  LegacyCell cell = getSubCell(point);
  cell.shapeRel = SpatialRelation.CONTAINS;
  return new SingletonCellIterator(cell);
}

Of the touching children, only the one the point was stored under has terms for the document, so the AND is empty. For Point(10, 0) this happens at the second level, where the equator splits face 0 into a northern and a southern half: the query side gets 2 children there. A probe with the arity-1 S2 tree at its maximum depth (31 levels) measured 2 children for 11 points on the equator, the face borders and the face-centre meridians and 4 for (0,0); all 12 miss with Contains and are found by Intersects, while (1,10), (46,20), (10,0.001) and (91,10) get 1 child per level and are found by both. A trace of the stock visitor on the repro's index shows it asks the world cell, face 0 and the .0 side down to level 7 for children and never .1 or anything below it: after .0's leaf term the term enumeration is used up, so seek(.1) is false and the loop breaks (ContainsPrefixTreeQuery.java:144-145, :123-124, :137).

• Intersects: for a point query makeQuery takes the grid-aligned fast path (RecursivePrefixTreeStrategy.java:185-187): with pointsOnly a single TermQuery on the indexing cell (:218-229), else a visiting query that ORs over the cells it visits, so extra cells only add hits.
• IsWithin: RPT passes no buffer (queryBuffer -1, :191-198), so the query walks the cells with no point filter (WithinPrefixTreeQuery.java:74).
• Rectangle and circle documents (the area shapes tested): one that covers P is indexed under every cell it intersects, including all the touching ones, so it is still found. Polygons, lines and shape collections were not tested.
• Shallow trees: the edge must exist at the tree's depth. With new S2PrefixTree(ctx, 1) (faces only) the equator is not an edge yet and (10, 0) and (0, 0) are found; from 2 levels on they are missed. (45, 20), on a face edge, is missed from 1 level on.
• The two sides disagree: the index stores an edge point under one cell, the query follows every touching cell. The recommended fix makes the query side follow the index side, so it needs no reindexing; changing the index side instead is the other option.

• Who. Applications that use RecursivePrefixTreeStrategy, or CompositeSpatialStrategy (which pre-filters Contains with RPT's own Contains query, CompositeSpatialStrategy.java:139-142), over S2PrefixTree, and run Contains (alias "Covers") with a point as the query shape.
• Opt-in. S2PrefixTree is @lucene.experimental and works only with a context whose shape factory is an S2ShapeFactory, i.e. the Geo3d context (constructor check, S2PrefixTree.java:83-85; CHANGES for LUCENE-8126: "It can only be used currently with Geo3D spatial context"). SpatialPrefixTreeFactory defaults to geohash for a geo context and selects S2 for prefixTree="s2"; Solr's RPT field types build their tree through that factory and parse Contains (code reading, not run). A GitHub code search found no use of S2PrefixTree in Elasticsearch or OpenSearch.
• What is lost. Documents indexed as exactly the query point, when that point lies on an S2 cell edge that exists at the tree's depth: on the equator, and in the band around the equator on the face borders (longitudes ±45, ±135) and the face-centre meridians (0, ±90, 180), and (0,0), a common placeholder coordinate (all of these tried; multi-valued documents not tested). Continuous coordinates rarely land exactly on an edge; round-number and placeholder data does. With CompositeSpatialStrategy, a point document and a rectangle around it, Contains(p) returns 1 of the 2 true matches.
• Silent, deterministic, false negatives only. No exception, the same with assertions off, per document, so at any index size. In 600 random Contains(point) queries (300 per tree, 2 trees, 400 random documents per tree), the stock hits were always a subset of the fixed hits.
• How likely. Contains(point) against point data is an equality test that users would usually write as Intersects; the realistic case is a mixed-shape field asked "which shapes cover this location" when the location equals a stored point on a cell edge. No prior report was found in the recorded searches, although the code dates from 7.3.0 (2018); the registry rates the likelihood rare and the priority low.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: 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.junit.Assert.assertEquals(Assert.java:633)
       org.apache.lucene.spatial.prefix.tree.TestS2PointOnCellEdgeContains.testContainsPointOnEquator(TestS2PointOnCellEdgeContains.java:51)

• Contract. SpatialOperation.Contains: "Meets the 'Covers' OGC definition (boundary-neutral)", evaluate = indexedShape.relate(queryShape) == CONTAINS || indexedShape.equals(queryShape) (SpatialOperation.java:75-87). ContainsPrefixTreeQuery: "Finds docs where its indexed shape CONTAINS the query shape. For use on RecursivePrefixTreeStrategy". RecursivePrefixTreeStrategy.makeQuery has an explicit Contains branch and throws UnsupportedSpatialOperation only for other operations (:199-203). CHANGES: "LUCENE-4645: Added support for the 'Contains' spatial predicate for RecursivePrefixTreeStrategy".
• Approximation may only add matches. SpatialArgs: the error "effectively inflates the size of the shape but should not shrink it", and it is 0 for a point.
• Upstream tests assert this for the other trees. TestRandomSpatialOpFuzzyPrefixTree.testContains ensures "true-positive matches (if the predicate on the raw shapes match then the search should find those same matches)", sometimes queries with "an existing indexed shape" (when it is a point or a rectangle), and uses power-of-two boundaries for "the prospect of edge conditions we want to test"; it runs only the quad and geohash trees. The only S2 RPT test, TestGeo3dRpt, runs only Intersects.
• The tree disagrees with itself. Its index side stores a point in one cell per level; its query side follows every touching cell. In LUCENE-8126 (#9174) the tree's author wrote that S2 "Cells at the same level are disjoint" (in a comment about leaf pruning, not about queries). The legacy trees make the query side follow the index side for points (LegacyCell.java:134-143).
• History. The introducing commit added the S2 cell class without the point case and tested S2 with Intersects only; no review or JIRA comment discusses Contains or edge points.
• Precedent. LUCENE-4770 (#5835): a false negative from an index-side versus query-side cell mismatch in the legacy trees' Intersects (TermQueryPrefixTreeStrategy over indexed non-point shapes), fixed as a bug in 4.2.

The strongest case for "works as designed" (the reading-only cross-model reviews rated it moderate; one of them, the refute lens, returned "not real" at low confidence for a procedural reason, as it could not run the repro, while its static analysis agreed on the root cause): PrefixTreeStrategy's class javadoc, which RPT inherits, says "Only SpatialOperation#Intersects is supported" (PrefixTreeStrategy.java:52-53); S2 cells are closed, so a point on an edge really does touch several cells, and Cell#getNextLevelCells only promises the cells "optionally filtered by shapeFilter"; and S2PrefixTree, RPT and ContainsPrefixTreeQuery are all @lucene.experimental.

The answer: the "Only Intersects" sentence was written on 2012-09-24 (84c5a4addeb), six months before LUCENE-4645 added Contains to RPT (8b573c413d4, 2013-04-03), and makeQuery, the ContainsPrefixTreeQuery javadoc and the CompositeSpatialStrategy javadoc ("All predicates are supported except for the BBox* ones, and Disjoint") all say Contains works. Closed cells would justify "several touching cells" only if the index side did the same, and it does not. @lucene.experimental is about API stability, not missing results. A maintainer could still prefer an index-side fix, a Contains-only fix or a documentation change. Verdict: not intended (the intended-behaviour devil's advocate, high confidence, and the adjudication). Expect the "Only Intersects" sentence to be quoted back; answer with LUCENE-4645 and the dates, and consider fixing that sentence in the same patch.

One fix was applied in a scratch worktree at a9779ef3c193 and run through gradle (seed DEADBEEF) and through the scope probes; the alternatives were not run. The workaround was checked in the scope probe only.

For a point filter, return a SingletonCellIterator of the child cell S2CellId.fromLatLng(point).parent(childLevel) with shapeRel CONTAINS: the cell the index side uses, and the pattern of LegacyCell. This is the finder's fix rewritten with imports instead of fully qualified names and with a comment; the logic is the same (+12 lines). It changes every S2 traversal that filters by a point, not only Contains (see the trade-offs); faceting with a point shape was not tested.

   @Override
   public CellIterator getNextLevelCells(Shape shapeFilter) {
+    if (shapeFilter instanceof Point point) {
+      // A point gets the one child cell it is indexed under (see S2PrefixTree.getTreeCellIterator),
+      // not every child that touches it: on a cell edge 2 to 4 children touch the point.
+      int childLevel = cellId == null ? 0 : cellId.level() + tree.arity;
+      S2CellId child =
+          S2CellId.fromLatLng(S2LatLng.fromDegrees(point.getY(), point.getX())).parent(childLevel);
+      S2PrefixTreeCell cell = new S2PrefixTreeCell(tree, child);
+      cell.shapeRel = SpatialRelation.CONTAINS;
+      return new SingletonCellIterator(cell);
+    }
     S2CellId[] children;

Trade-offs

• No reindexing, no format change: the index side already writes the single fromLatLng path.
• The other point callers take the single path too: the visiting queries (AbstractVisitingPrefixTreeQuery.java:245), i.e. RPT's Intersects without pointsOnly, the Intersects pre-filter of CompositeSpatialStrategy and PrefixTreeFacetCounter with a point shape. They then visit 1 cell per level instead of 2 to 4. An area document that covers the point is still indexed under that cell: in the probe the Intersects answers did not change. The facet counter with a point shape was not probed. Indexing never passes a point, and IsWithin passes no filter.
• Tests: the upstream tests never ran Contains on S2, so their passing shows only that nothing else broke; add the repro (or an S2 grid in a Contains test) with the fix.
• Javadoc: consider fixing PrefixTreeStrategy's stale "Only SpatialOperation#Intersects is supported" sentence in the same patch.
• Valid depths assumed: like the index side, the point case computes parent(childLevel) and assumes a depth S2 supports; S2PrefixTree does not check maxLevels against getMaxLevels(arity) (the base constructor only asserts it is positive, SpatialPrefixTree.java:38-42). This predates the patch.

What the checks validated

• Stock a9779ef3c193 (scratch worktree, gradle, seed DEADBEEF): the repro fails 1 of 1 with assertions on and off; the closest suites (TestS2PrefixTree, TestGeo3dRpt, TestRandomSpatialOpFuzzyPrefixTree, TestSpatialPrefixTree, TestCompositeStrategy) pass: 19 tests, 1 skipped.
• With the fix: the repro passes with assertions on and off; the same closest suites pass (19 tests, 1 skipped); the whole :lucene:spatial-extras:test with the repro in place passes (118 tests, 5 skipped, 0 failures); TestS2PrefixTree, TestGeo3dRpt and TestRandomSpatialOpFuzzyPrefixTree with 5 iterations and a random seed pass (80 tests, 5 skipped); ecjLintMain, ecjLintTest and checkGoogleJavaFormat pass. The repro's class javadoc first failed checkGoogleJavaFormat on its wrapping; after a comment-only edit (formatted with ./gradlew tidy, which left the fix unchanged) the edited repro fails on stock and passes with the fix, assertions on and off. fix.diff and fix-with-test.diff pass git apply --check on a clean tree.
• Scope probe (main jars, stock and with the fixed class): 6 edge points and 1 off-edge point, 8 documents each (the point, 6 rectangles that have the point on an edge (4) or at a corner (2), and a circle around it), Intersects, Contains and IsWithin, SPHERE and WGS84, 4 tree shapes. Stock: Contains misses 6 documents in each configuration (48 misses; the probe lists the first 40, all edge-point documents, and each count of 6 matches the 6 edge points). Fixed: 0 misses, and the Intersects and IsWithin lines are identical to stock.
• Earlier hunt runs with the same logic: the finder's and the independent reproducer's JUnits pass; the security probe (600 random Contains(point) queries, 300 per tree) finds 0 misses; the four upstream S2/RPT suites passed 17 of 17 and 170 of 170 over 10 iterations.

For a point query, descend only the cells of getTreeCellIterator.

Trade-offs

Fixes Contains for any tree, but changes a query shared by all trees to work around one tree's cell iterator, and leaves the S2 Intersects traversal visiting extra cells.

Make the index side match the query side instead.

Trade-offs

Gives the index side closed-cell semantics, but needs reindexing and writes up to 4x the terms for edge points. The pointsOnly Intersects fast path would still work: it looks up the single getTreeCellIterator cell (RecursivePrefixTreeStrategy.java:218-229), which stays among the indexed terms.

In the OGC sense "covers P" and "intersects P" are the same predicate for a point: a shape covers a point exactly when the point lies in the closed shape.

Trade-offs

Only for point query shapes; checked on the probe's shapes only.

What the checks validated

In the scope probe, with point, rectangle and circle documents, the two predicates had identical sets of true document-query pairs in all 8 configurations, and stock Intersects missed none of them.

Method: a randomized differential test (non-formal tier; the finder tagged it semi-formal) in a hunt unit on spatial-extras.

• The harness indexed random rectangles, circles and points snapped to a 5- or 10-degree grid (150 documents and 60 queries in each of two S2 configurations) and reported every document that SpatialOperation.evaluate says should match but the query missed. Among its findings it flagged Contains, indexed Point(160, 0), query the same point, on S2PrefixTree only; the same run also reported other S2 Within and area-shape Contains misses, which are not part of this report.
• A point probe then showed that S2 Contains misses the tested points on S2 cell edges ((160,0), (10,0), (45,20)), while off-edge points and the geohash and quad trees find them; the finder found the cause by reading S2PrefixTreeCell.getNextLevelCells and confirmed it with a public-API JUnit on the stock main jar.
• It was then checked by an independent reproducer, an intended-behaviour devil's advocate, reading-only reviews by a model from another family (OpenAI GPT-5.6), an adjudication, a history, prior-report and security follow-up, and an audit. Found 2026-10-26 on main ea57360912ed; re-checked on a9779ef3c193.