Reducing Candidate Pairs With Bbox Covering Columns

This guide adds a numeric bounding-box covering to both sides of a spatial join so the expensive geometry predicate runs on a fraction of the pairs, and shows how to verify that the reduction actually happened rather than assuming it.

Context and prerequisites

The exact predicate in a spatial join costs roughly the same in every engine, because most of them call the same geometry library. What differs — by orders of magnitude — is how many pairs reach it. A numeric covering is the cheapest available way to reduce that number, and it works in any engine that can compare doubles. This recipe uses Trino and Spark SQL; the surrounding decisions are in spatial join optimization, and the pushdown mechanics in predicate pushdown optimization.

What a covering does

The filter is conservative: it never rejects a pair whose geometries actually meet, so the result is exact. It does admit false positives — two boxes can overlap while their geometries do not, as the right-hand pair shows — which is why the exact predicate still runs. The value is entirely in how many pairs it eliminates before that point.

The reduction depends on how well each geometry fills its box. Compact features fill their boxes well and the filter is highly selective; long diagonal features — rivers, roads, flight paths — fill them poorly, and a pair of diagonal boxes overlaps far more often than the geometries do.

Complete working solution

-- Both tables carry four DOUBLE columns derived at write time.
-- Trino / Spark SQL compatible.
SELECT t.asset_id, r.region_id
FROM   lakehouse.spatial.telemetry t
JOIN   reference.regions r
  ON   t.bbox_min_x <= r.bbox_max_x        -- the covering test:
 AND   t.bbox_max_x >= r.bbox_min_x        -- four comparisons, no decode
 AND   t.bbox_min_y <= r.bbox_max_y
 AND   t.bbox_max_y >= r.bbox_min_y
 AND   ST_Intersects(                       -- the exact test, on survivors only
         ST_GeomFromBinary(t.geom_wkb),
         ST_GeomFromBinary(r.geom_wkb))
WHERE  t.event_day = DATE '2026-03-11';

# Deriving the covering at write time. Spark 3.5 + Sedona.
enriched = (raw
  .selectExpr("*",
      "ST_XMin(ST_GeomFromWKB(geom_wkb)) AS bbox_min_x",
      "ST_YMin(ST_GeomFromWKB(geom_wkb)) AS bbox_min_y",
      "ST_XMax(ST_GeomFromWKB(geom_wkb)) AS bbox_max_x",
      "ST_YMax(ST_GeomFromWKB(geom_wkb)) AS bbox_max_y"))

(enriched
   .sortWithinPartitions("bbox_min_x", "bbox_min_y")
   .writeTo("lakehouse.spatial.telemetry").append())

The four columns cost 32 bytes per row before compression, and they compress extremely well on a sorted table because neighbouring rows have near-identical bounds — in practice the overhead is a low single-digit percentage of the geometry column they accelerate.

Step-by-step walkthrough

1. Write the overlap test as four separate comparisons. Some engines will recognise a function-based overlap test and some will not; four plain comparisons on plain columns are understood by every optimiser and are individually pushable into the scan.

2. Put the covering conditions before the exact predicate. Optimisers reorder conjunctions using selectivity estimates, and their estimate for a geometry function is frequently a fixed default unrelated to the data. Writing the order explicitly removes the dependence on that guess.

3. Derive the covering from the stored geometry. If the geometry is transformed or repaired after the covering is computed, the two disagree and the filter starts rejecting pairs it should keep — which produces silently missing results rather than an error.

4. Sort on the covering columns. The same columns that make the join filter cheap also make the file and row-group statistics tight, so the covering pays twice: once at the scan and once at the join.

5. Keep the columns inside the statistics window. A covering column with no min/max in the manifest still filters at the join, but contributes nothing to file pruning — which is the larger of the two savings.

Common errors and fixes

Verification

-- Two counts, run once, tell you whether the covering earns its storage.
SELECT
  count_if(t.bbox_min_x <= r.bbox_max_x AND t.bbox_max_x >= r.bbox_min_x
       AND t.bbox_min_y <= r.bbox_max_y AND t.bbox_max_y >= r.bbox_min_y) AS box_pairs,
  count_if(ST_Intersects(ST_GeomFromBinary(t.geom_wkb),
                         ST_GeomFromBinary(r.geom_wkb)))                   AS exact_pairs
FROM lakehouse.spatial.telemetry t
CROSS JOIN reference.regions r
WHERE t.event_day = DATE '2026-03-11';

A false-positive rate above about ninety percent means the boxes are not discriminating, which almost always indicates elongated diagonal geometries. The remedy is an additional covering that is not a box — a set of grid cells covering each feature — which discriminates on shape rather than only on extent and reduces the pair count for exactly the geometries where boxes fail.

Run the measurement once per join shape rather than continuously; the selectivity is a property of the data’s geometry and changes slowly. Re-measure after any change to the layers involved, and record the number alongside the job so a later slowdown can be attributed correctly.

When a Box Is Not Enough

Bounding boxes fail for a specific and recognisable class of geometry, and knowing the signature saves a lot of fruitless tuning.

Both shapes have the same problem: the box is a poor description of where the geometry actually is. A route from one corner of a region to another has a box covering the whole region, so it appears to overlap every query window in it. An archipelago’s box covers the sea between its islands.

The remedy in both cases is a cell covering: precompute the set of grid cells each feature actually touches, store it as an array column, and join on cell overlap rather than on box overlap. A diagonal route touches a narrow chain of cells rather than a rectangular block, and the discrimination improves by roughly the ratio between the box area and the corridor area — which for a long route is a factor of tens.

-- A cell covering discriminates on shape, not only on extent.
SELECT DISTINCT t.asset_id, r.region_id
FROM   lakehouse.spatial.telemetry t
JOIN   reference.routes r
  ON   arrays_overlap(t.covering_cells, r.covering_cells)
 AND   ST_Intersects(ST_GeomFromBinary(t.geom_wkb),
                     ST_GeomFromBinary(r.geom_wkb));

The cost is storage — an array of cell identifiers per feature — and a deduplication step, because a pair sharing several cells matches several times. Both are modest next to the reduction on the shapes where boxes fail, and neither is worth paying on the shapes where boxes work. Deciding per layer, from the measured false-positive rate, is the right granularity.

Keeping the Covering Correct

A covering is derived data, and derived data that disagrees with its source produces silently wrong results rather than errors.

Three assertions keep it honest. Coverage: every geometry must lie inside its own box, checked at write time on every row — this catches the derive-then-transform ordering mistake that is the most common cause of missing results. Presence: no null covering columns on a table where they are required, which catches a write path that bypassed the derivation. Statistics: min and max present in the file metadata for all four columns, which catches the schema-position mistake that silently disables file pruning.

All three are cheap, and all three belong in the same gate as the geometry validation described in geometry validation and repair rather than in a separate check. A batch that satisfies the table’s whole contract or is rejected as a unit is far easier to reason about than several partial gates at several stages.

Cost and Payback

The arithmetic is worth stating because the storage objection comes up every time and the numbers settle it quickly.

Four DOUBLE columns are 32 bytes per row uncompressed. On a sorted table they compress to a small fraction of that, because consecutive rows differ only in the low-order bits — measurements on real telemetry tables put the compressed overhead in the region of three to six percent of the geometry column’s size.

Against that, the reduction in a typical point-to-region join is between one and three orders of magnitude in the number of exact predicate evaluations. Since the exact predicate is the dominant CPU cost in most spatial joins, and since the covering also enables file-level pruning that the geometry column can never provide, the payback is immediate on any table that is joined more than once.

The case where it does not pay is a table that is only ever written and never joined spatially — a raw landing zone, an archive read only by identifier. There the columns are pure overhead and can reasonably be omitted, provided the decision is recorded so that the first person to attempt a spatial join understands why the table is slow and what to do about it.