Spatial heatmaps count big indexed shapes in cells outside a circle or polygon input

HeatmapFacetCounter.calcFacets (also reached through PrefixTreeStrategy.calcFacets) takes any shape as its input and promises, for one that is not a rectangle, that "the non-intersecting cells will all be 0" (HeatmapFacetCounter.java:86-90). The term walk visits heatmap-level cells only when they intersect the input, so points come out right. But a non-point document that RecursivePrefixTreeStrategy indexed as a leaf cell coarser than the heatmap level reaches the visitor once, as an "ancestor", and calcFacets adds its count to every heatmap cell under that leaf, or to every cell when the leaf contains the whole heatmap, without checking those cells against the input (:216-235, :246-286). With a circle, polygon or shape-collection input, cells inside its bounding box but outside the shape report counts. In the repro (the setup of upstream testQueryCircle plus one square document) 8 cells that do not touch circle(0, 0, 89) report 1 instead of 0; one country-sized rectangle under a 3° circle lights up 164 cells outside it. Ordinary rectangle inputs and point data are not affected, and no error is raised. It has been there since the heatmap was added in 5.1.0 (LUCENE-6191, 2015). The recommended fix gives ancestor counts only to cells whose grid cell intersects a non-rectangular input.

• Heatmap: calcFacets(context, topAcceptDocs, inputShape, facetLevel, maxCells) returns a grid of columns x rows counts. Each heatmap cell is one prefix-tree cell at facetLevel, and the grid covers the input's bounding box. For the input the javadoc says: "We always return a rectangle of integers even if the inputShape isn't a rectangle -- the non-intersecting cells will all be 0." (HeatmapFacetCounter.java:86-90). Both classes involved are @lucene.experimental (HeatmapFacetCounter.java:38, PrefixTreeFacetCounter.java:45).
• Prefix-tree indexing: RecursivePrefixTreeStrategy stores a shape as grid cells of several sizes (one term each). A point is a chain of cells down to the finest level. A larger shape gets big "leaf" cells where a cell lies inside it (tree/FilterCellIterator.java:51; pruneLeafyBranches, on by default, replaces four leaf siblings by their parent, RecursivePrefixTreeStrategy.java:56, :162-174) and small cells along its boundary.
• Ancestor: an indexed leaf coarser than facetLevel. The facet walk reports it once, and "the count can be considered to be added to all cells below" (PrefixTreeFacetCounter.java:54-59).

1. PrefixTreeFacetCounter.compute walks the terms with an AbstractVisitingPrefixTreeQuery over the input (PrefixTreeFacetCounter.java:131-136) and descends only into the children that intersect it, cell.getNextLevelCells(queryShape) (AbstractVisitingPrefixTreeQuery.java:244-245). A cell at facetLevel is counted directly (HeatmapFacetCounter.java:198-214), so point documents outside the input give 0.
2. A coarser leaf that intersects the input is passed to the visitor once (PrefixTreeFacetCounter.java:185-191). If it contains the whole heatmap region it goes to allCellsAncestorCount (HeatmapFacetCounter.java:216-217), otherwise to the ancestors map (:218-224).
3. calcFacets adds allCellsAncestorCount to every heatmap cell (:230-235) and each ancestor's count to every heatmap cell under its rectangle through intersectInterval/incrementRange (:246-286, :291-338). Neither path tests a cell against inputShape.
4. For an ordinary Rectangle input every heatmap cell intersects the input, so this puts nothing outside it. For a circle, polygon or shape collection, the bounding box's corners lie outside the shape, and the cells there get the count. What matters is the input shape, not the indexed data: a point input is not a Rectangle either (in the harness, point inputs at longitude +180 got such counts too).

Non-geo world [-90, 90]², QuadPrefixTree with 4 levels, default strategy settings (the setup of upstream testQueryCircle). Doc 0 is the point (88, 88); doc 1 is the square [45, 90]², indexed as one level-2 leaf plus level-4 leaves in the cells that only touch its left and bottom edges. calcFacets with circle(0, 0, 89) at level 4 returns a 16 x 16 heatmap of 11.25° cells. The square covers 4 x 4 of them. The 8 that do not touch the circle, the top row [45, 90] x [78.75, 90], the right column [78.75, 90] x [45, 78.75] and [67.5, 78.75]², each report 1. The point, in the corner cell [78.75, 90]², is correctly not counted: that cell reports 1 with the circle input and 2 with the circle's bounding box as input. The cells that intersect the circle (17 non-zero) are the same with and without the fix. With assertions on and off alike, and on every release run from 5.1.0 to 10.5.2 (as a main() port before 9.0).

Bigger shapes give bigger errors: one rectangle of about 40° x 25° (geo, GeohashPrefixTree with 11 levels) under circle(0, 40, 3) at level 4 gives a 24 x 35 heatmap in which 164 of the 184 cells outside the circle report 1: an almost filled rectangle instead of a disc. The same was seen with geohash circles, a shape-collection input (15 of 62 cells outside it), a leaf that covers the whole heatmap (4 of 4 corner cells) and a rectangle that is not grid-aligned (48 of 84 cells).

• Who is hit. Applications that compute a spatial heatmap with PrefixTreeStrategy.calcFacets or HeatmapFacetCounter.calcFacets (opt-in lucene/spatial-extras module, @lucene.experimental) with a non-rectangular input (circle, polygon, shape collection, buffered geometry) over a field that holds non-point shapes indexed with leaves coarser than the heatmap level, which default RecursivePrefixTreeStrategy settings commonly produce for large non-point shapes. Downstream, Solr's heatmap facet takes its input shape as WKT (facet.heatmap.geom), and its own circle test shows the wrong cells (see Why it is a bug).
• Who is not hit. Ordinary rectangular inputs (the usual map viewport), a null input (the whole world) and point-only data.
• What goes wrong. Cells inside the input's bounding box but outside the shape report non-zero counts: each gets the count of every coarse document whose leaf covers it. No error. The document filter (topAcceptDocs) and deletions are still honoured, and no document is counted only outside the shape: in an executed probe (3,715 random trials over three prefix-tree configurations, one indexed shape per document) the error only moves where an already-counted document's count lands.
• Scale. One document is enough. The error grows with the size of the indexed shapes relative to the heatmap cells: 8 cells in the minimal repro, 164 for one country-sized shape under a small circle.
• How likely. Rare: it needs both a non-rectangular heatmap input and coarse non-point documents, and the searches found no prior report since 5.1.0, although a downstream golden test encodes the wrong values.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected:<0> but was:<1>
       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.TestHeatmapAncestorCellsOutsideInputShape.testCoarseLeafCountedOutsideCircleInput(TestHeatmapAncestorCellsOutsideInputShape.java:54)

• The contract is specific and unqualified. "We always return a rectangle of integers even if the inputShape isn't a rectangle -- the non-intersecting cells will all be 0." (HeatmapFacetCounter.java:86-90). It names the non-rectangular case. It came in the feature's first commit (248121bb3f7, LUCENE-6191) with the Shape parameter and the circle test; on LUCENE-6191 (#7253) the author posted this exact text when they switched the input from Rectangle to Shape.
• The upstream test only uses points. testQueryCircle (TestHeatmapFacetCounter.java:94-132) asserts the promise with two point documents, which never produce coarse leaves; testRandom uses rectangle inputs only (:160-291).
• Internally inconsistent. In the corner cell [78.75, 90]² the point (88, 88) is excluded and the square is included: the cell reports 1 with the circle input and 2 with the circle's bounding box as input.
• Not grid approximation. "The shape's boundary is approximated to a grid precision" (PrefixTreeStrategy.java:50-51) does not explain it: in the downstream circle case the two wrong cells are DISJOINT from the circle by the tree's own cell relation at the heatmap level, and an independent reproducer's documents are exactly grid-aligned.
• Nothing relaxes it. No CHANGES entry, MIGRATE note, test, commit or issue changes the promise; none of the later commits on calcFacets (LUCENE-6650, LUCENE-7291, LUCENE-7787, LUCENE-9394, reformatting) adds a check of the ancestor cells against the input.
• Precedent. LUCENE-7291 (#8346), a different wrong ancestor-count accumulation in the same method (dateline-crossing heatmaps), was called "a real bug" by the author and released in 6.1.0 and 5.5.2 (its JIRA fix versions also list 6.0.2 and 5.6, which were never released).
• The author called the sibling pattern a bug. On LUCENE-5735 (#6797), on 2015-02-05, four days before the heatmap commit: "There's a bug in NumberRangePrefixTreeStrategy.calcFacets in which all cells above the parent are counted as topLeaves, when really that can only be done if the leaf cell _contains_ the facet range."

The strongest case for intended behaviour (the cross-model reviews rated it moderate; the independent reproducer rated it weak, and the devil's advocate found that none of the arguments holds): prefix-tree faceting counts grid-approximated indexed cells; the visitor javadoc says an ancestor's count "can be considered to be added to all cells below" (PrefixTreeFacetCounter.java:54-59); on LUCENE-6191 the author accepted "blocky effects (e.g. all cells on one side of the heatmap could be +1 due to matching an adjacent country)"; the API is experimental; and Solr's SpatialHeatmapFacetsTest circle case expects [0, 1, 1, 1, 1, 1, 1, 0] // curved; we have a 0 in its top row, where columns 1 and 6 do not touch the circle, so a golden output already encodes the behaviour.

Why it fails: the calcFacets promise is about the input shape and names the non-rectangular case; the visitor wording describes the visitor's stream, which calcFacets must map onto its own documented output; "blocky effects" are about indexed shapes inside the heatmap region, not about cells outside the input; experimental status lowers impact, not validity; and the downstream test's own comment is consistent with zeros where the circle curves away, so its two uncommented 1s look like an unnoticed artifact (a reading of the comment, not proof). With the fix its top row becomes [0, 0, 1, 1, 1, 1, 0, 0]. Verdict: not intended, a defect.

Fix A was built and validated in a scratch worktree and with the finder's harness, together with a simpler variant of it. Fixes B and C were built and checked by the finder and an independent reproducer; D and E were not built. Any code fix changes two cells of Solr's circle-input heatmap test.

When the input is not a Rectangle and at least one coarse leaf was found, a small helper (InputShapeCells) decides, the first time an ancestor's count would be added to a heatmap cell, whether the cell intersects the input, and caches the answer in a byte[]. It looks up the grid's own cell at facetLevel under the heatmap cell's center and relates its shape to the input, the relation the term walk uses for the cells it visits (AbstractVisitingPrefixTreeQuery.java:244-245). Both ancestor paths (the allCellsAncestorCount loop and incrementRange) skip cells that do not intersect; counts made directly at the heatmap level are untouched. +78/-6 in HeatmapFacetCounter.java; with the new test method, +40 in TestHeatmapFacetCounter.java.

final InputShapeCells inputCells =
    inputShape instanceof Rectangle || (allCellsAncestorCount[0] == 0 && ancestors.isEmpty())
        ? null
        : new InputShapeCells(heatmap, inputShape, grid, facetLevel, cellWidth, cellHeight);
// in the allCellsAncestorCount loop and in incrementRange:
if (inputCells == null || inputCells.intersects(cBase + r)) {
  heatmap.counts[cBase + r] += count;
}
// InputShapeCells.intersects(index), once per cell (condensed): the grid's cell at
// facetLevel under the heatmap cell's center, related to the input
Cell cell = null;
for (CellIterator it = grid.getTreeCellIterator(center, facetLevel); it.hasNext(); ) cell = it.next();
relation[index] = cell.getShape().relate(inputShape).intersects() ? (byte) 1 : (byte) 2;

Trade-offs

• Cost: no extra per-cell lookup or relate and no mask for rectangle inputs, a null input, point data, or when no coarse leaf intersects the input (only a few conditionals). Otherwise at most one grid-cell lookup (facetLevel steps) and one relate per heatmap cell that an ancestor touches (bounded by maxCells), and a byte[] the size of the heatmap. For a complex polygon the relate is the main cost; a refinement could skip the per-cell check for an ancestor that lies WITHIN the input. No benchmark was run.
• A simpler variant relates a cell rectangle rebuilt from the heatmap region (dateline-wrapped, clamped to the world bounds) instead of the grid's cell (+66/-6). It passes every test too, but in the harness it drops 18 counts in cells that touch a circle at exactly one point in a Web Mercator world, where the rebuilt rectangle and the grid's cell differ in the last digits. Fix A has none.
• Downstream: the top row of Solr's circle-input heatmap test changes from [0, 1, 1, 1, 1, 1, 1, 0] to [0, 0, 1, 1, 1, 1, 0, 0].

What the checks validated

• Scratch worktree at a9779ef3c193, gradle, JDK 25: stock with the new test, the standalone repro and verifier suites: 16 tests, 9 fail, with assertions on and off.
• With fix A the whole lucene/spatial-extras module passes: 30 suites, 129 tests (12 of them added: the repro, the new test method and the verifiers' 10), 5 skipped, 0 failed, with assertions on (together with checkGoogleJavaFormat, ecjLintMain, ecjLintTest, forbiddenApisMain, forbiddenApisTest) and off.
• Standalone runner with fix A shadowed: the repro 1 of 1 and the independent reproducer's suite 6 of 6, assertions on and off; the devil's advocate's probes 4 of 4.
• The finder's harness (3,125,522 heatmaps, 262,910,034 cells), stock against fix A: cells outside a circle or point input with a count go from 224,179 to 0 in the geo and the plain non-geo worlds and from 24,548 to 43 in a Web Mercator world (which stock already gets wrong for rectangle inputs too, from separate bugs); no cell loses a count it should keep; exceptions unchanged; every other category identical.

After all ancestor counts are applied, if the input is not a Rectangle and there were ancestors, rebuild the rectangle of every non-zero cell, relate it to the input and set the cell to 0 if it does not intersect (+25 lines).

Trade-offs

Smallest diff, but it relates every non-zero cell, not only those under coarse leaves, and can also zero a count made at the heatmap level. In the harness's Web Mercator world its rectangles, not clamped to the world bounds, throw 459 more InvalidShapeExceptions than stock for circle inputs, and it drops 50 counts it should keep. Not recommended as it is.

What the checks validated

The repro passes (the finder); upstream TestHeatmapFacetCounter passes 20 of 20 (assertions on, 5 iterations; the cross-model reviews) and 12 of 12 (off, 3 iterations; the review); in the harness's earlier revision, without the Web Mercator world, all 245,020 cells outside the input with a count go to 0.

Whenever the input is not a Rectangle, relate every heatmap cell up front and let both ancestor paths skip the masked cells (the independent reproducer's fix).

Trade-offs

Pays one relate per cell for every non-rectangular heatmap, even for point-only data, and its rebuilt rectangles are not clamped to the world bounds. Its 6 tests and the finder's test pass with it; not run through the harness.

For an ancestor that is not WITHIN the input, walk its sub-cells down to facetLevel with getNextLevelCells(inputShape) and count only the cells reached, as the term walk would for a finely indexed shape.

Trade-offs

Reuses the walk's pruning (sub-trees WITHIN the input need no per-cell relate), but it is more code than A and changes how ancestors flow through calcFacets. It may be the cleaner design, and it is the approach the author described for the sibling defect on LUCENE-5735 ("walk the sub-cells").

For example: cells that do not intersect a non-rectangular input are 0, except for documents indexed with cells coarser than facetLevel.

Trade-offs

No behaviour or downstream change, a credible compatibility choice for an experimental API, but it keeps the inconsistency: a point in a cell outside the shape is left out, a coarse shape in the same cell is counted.

Method: bounded-exhaustive translation validation (the hunt's semi-formal tier).

• The hunt unit checked HeatmapFacetCounter.calcFacets against a reference: a document is counted in a heatmap cell if it has a term at that cell or below it, or a leaf term above it whose cell contains it; only accepted documents; and 0 for cells that do not intersect the input shape, as the javadoc says.
• On the stock main jars: 2,446,632 heatmaps, 228,939,474 cells, over geo and non-geo quad, packed-quad and geohash trees (2-5 levels), 30 index seeds of 1-10 point, rectangle and circle documents per configuration, deletions and several segments; rectangle, point and circle inputs. Rectangle inputs with positive area gave 0 mismatches; circle (and some point) inputs gave non-zero cells outside the input, all from documents indexed with coarse leaves. A separate effect for zero-area inputs at longitude +180 with the packed quad tree (2,523 cells) is not this bug. Four planted mutants were all detected.
• The finder then read the ancestor code and the javadoc line and reduced it to a public-API JUnit on the stock main jars. A review by another model family (OpenAI GPT-5.6) ran its own tests before the candidate was filed.