Bounding Nearest-Neighbour Joins with a Distance Limit

A nearest-neighbour join always succeeds. That is its defining property and its central danger: ask which road segment is closest to a sensor and you will get an answer whether the nearest segment is four metres away or forty kilometres away. The four-metre match is the enrichment you wanted; the forty-kilometre match is a fabrication that enters the output indistinguishable from the real ones, carries a road name that is simply wrong, and propagates into every downstream aggregate. This guide covers how to bound a proximity join so that an implausible match is recorded as a non-match, how to choose the bound from the data rather than from intuition, and how to monitor the distance distribution so a drifting bound is noticed before it silently starts excluding good matches. It belongs to spatial join and enrichment quality checks under spatial data freshness and quality metrics.

Match-distance distribution split by a plausibility bound into real matches and fabrications A histogram of nearest-neighbour match distances shows a dense cluster between zero and about thirty metres, then a long sparse tail extending to several kilometres. A vertical bound is drawn at fifty metres. Everything left of the bound is labelled as plausible matches. The sparse tail right of the bound is labelled as fabrications, and an annotation notes that without the bound these are returned with the same confidence as the cluster. A second annotation marks the gap between the cluster and the tail as the natural place to set the bound. The distribution tells you where the bound belongs bound = 50 m set in the gap, not at a percentile of the whole set plausible matches fabrications — returned with identical confidence when unbounded match distance (log scale, metres) count

Problem framing: unbounded means undetectable

Two consequences follow from a proximity join always returning a row.

The first is that the failure has no signature in the output. An unmatched point in a containment join is at least absent; a fabricated proximity match is present, populated and wrong. Nothing downstream can distinguish it, because the distance that would have revealed it was discarded when the join projected its columns.

The second is that the fabrication rate rises exactly when the data is worst. A region where the right layer has poor coverage produces the most distant matches, so the areas with the least reliable reference data get the most confident-looking enrichment. This inverts the usual expectation that data quality problems are localised to the visibly bad areas.

Bounding the join fixes both. ST_DWithin turns “the nearest thing, wherever it is” into “the nearest thing within a plausible radius, or nothing”, which restores the unmatched category and makes the failure countable. It also lets the spatial index prune the search rather than scanning outward indefinitely, so the bounded form is usually the faster one as well.

Implementation: bound the predicate, keep the distance

The bound belongs inside the join, and the distance belongs in the output so it can be aggregated.

-- Bounded nearest neighbour. LATERAL with ORDER BY <-> uses the index for the
-- k-nearest search; ST_DWithin inside the WHERE gives the planner a bound to
-- prune with, so this is both more correct and cheaper than an unbounded join.
SELECT
  s.sensor_id,
  n.segment_id,
  n.distance_m
FROM curated.sensors s
LEFT JOIN LATERAL (
  SELECT r.segment_id,
         s.geom <-> r.geom AS distance_m
  FROM curated.road_segments r
  WHERE ST_DWithin(s.geom, r.geom, 50)     -- the plausibility bound, in metres
  ORDER BY s.geom <-> r.geom               -- index-assisted nearest ordering
  LIMIT 1
) n ON TRUE;
-- Rows where n.segment_id IS NULL are honest non-matches, not silent fabrications.

Three details make this correct rather than merely functional.

LEFT JOIN LATERAL ... ON TRUE is what preserves the non-matches. An inner lateral join drops sensors with no candidate inside the bound, putting you back in the position the bound was meant to escape.

The distance is projected into the output rather than used only in the predicate. Without it there is no histogram, and without the histogram you cannot tell whether the bound is generous, tight, or drifting.

The units must match the geometry’s coordinate system. ST_DWithin on geographic coordinates measures in degrees, not metres, and a bound of 50 on an unprojected layer means fifty degrees — effectively unbounded. Either cast to geography, which measures in metres, or work in a projected system whose units are metres. This is the single most common way a bound silently does nothing, and it is worth asserting in a test.

Emitting the outcomes alongside gives the metric set described in the parent topic:

SELECT
  COUNT(*)                                              AS evaluated,
  COUNT(segment_id)                                     AS matched,
  COUNT(*) - COUNT(segment_id)                          AS unmatched_outside_bound,
  percentile_disc(0.50) WITHIN GROUP (ORDER BY distance_m) AS p50_distance_m,
  percentile_disc(0.99) WITHIN GROUP (ORDER BY distance_m) AS p99_distance_m
FROM enrichment.sensor_segment;

Choosing the bound from the data

Do not guess. Run the join once, unbounded, over a representative sample, and plot the distance distribution. Real proximity relationships produce a dense cluster near zero; fabrications produce a sparse, wide tail. The bound belongs in the gap between them, not at a percentile of the combined set — a percentile is contaminated by the tail it is trying to exclude.

Where no clean gap exists, derive the bound from the physical meaning of the relationship instead. A sensor mounted on a road is within a few metres of it; an address associated with a parcel is inside or immediately adjacent to it; a vessel report matched to a berth is within a berth length. Physical reasoning gives a defensible number and, importantly, one you can explain when someone asks why a match was rejected.

Record the bound alongside the join’s metrics and treat a change to it as a change to the join’s identity — it invalidates the baseline in exactly the way a predicate change does.

Effect of bound choice on the split between accepted matches and rejections Three horizontal bars compare bound settings for the same layer pair. A bound that is too tight, at five metres, accepts eighty-one percent and rejects a substantial number of genuine matches, shown as a wrongly-rejected segment. A well-chosen bound at fifty metres accepts ninety-seven percent with a small rejected segment made almost entirely of genuine non-matches. An unbounded join accepts one hundred percent, with a segment marked as fabrications that are indistinguishable in the output. A note states that the middle setting is the only one whose rejections are informative. Too tight rejects real matches; unbounded hides fabrications bound 5 m accepts 81% · the rejected block is mostly genuine matches wrongly excluded bound 50 m accepts 97% · the rejections are real non-matches, and therefore informative unbounded accepts 100% · the last block is fabrications, indistinguishable downstream The unbounded bar and the well-bounded bar have almost the same accepted length — the difference is entirely in what happens to the last 3%. Candidate density by area type, and the bound each supports Five area types are compared on candidate density for a road-segment layer. A dense urban centre has many candidates within a few metres. A suburban area has fewer. A rural area has far fewer. A remote area may have none within a kilometre. Offshore has none at all. Each row states the bound that area type supports, illustrating why a single global bound is generous in one place and punitive in another. Candidate density varies by orders of magnitude — so a single global bound cannot fit dense urban centre 5 m bound is ample suburban 20 m rural 80 m remote often no candidate at all offshore no candidate by definition

Verification: prove the bound is doing something

Three assertions, each catching a distinct real failure.

Assert the units. Run the join against a sample with a deliberately tiny bound — one metre — and confirm the match count collapses. If it does not, the bound is being interpreted in degrees and is effectively infinite.

Assert the non-match path. Insert a point far from every candidate and confirm it appears in the output with a null match rather than disappearing or acquiring a distant one. This catches an inner lateral join that silently drops rows.

Assert the distribution is stable. Compare this run’s p99 match distance against the previous week’s. A rising p99 within the bound means candidate coverage is thinning — the right layer is losing features in some area — and it is an early warning that arrives well before the match rate itself moves.

Gotchas

Geographic coordinates with a metre-valued bound. The single most common defect. Cast to geography or reproject; never assume the number means what you intended.

Filtering by distance after an unbounded join. Functionally similar, materially worse: the planner cannot use the bound to prune, so the query scans far more, and the filtered-out rows are usually discarded rather than counted.

A bound tuned on one region applied globally. Urban and rural candidate densities differ by orders of magnitude, so one bound may be generous in a city and punitive in the countryside. Where that matters, carry the bound per region from the layer registry rather than as a constant.

Ignoring ties. Two candidates at identical distance produce a non-deterministic pick, which shows up later as unexplained reassignment between runs. Add a deterministic secondary ordering — by identifier — so repeated runs agree.

No monitoring on the rejected count. A bound that silently starts rejecting a third of the input is as damaging as no bound at all, in the opposite direction. Alert on the rejection rate against its baseline exactly as you would on match rate.

FAQ

Should the bound reject or flag?

Reject in the enrichment output and retain the rejected rows with a null match plus the observed distance. That keeps them countable and reprocessable while ensuring nothing downstream consumes a fabricated relationship. Flagging without excluding relies on every consumer honouring the flag, which they will not.

How does this differ from a containment join with a buffer?

A buffered containment join asks “is this within N metres of any polygon”; a bounded nearest-neighbour join asks “which is the closest, if any is within N metres”. The second returns an identity and a distance, the first returns membership. Use containment when the relationship is spatial belonging and proximity when it is nearest-of-several.

Does the bound hurt performance?

It usually helps substantially. ST_DWithin lets the index restrict candidates, whereas an unbounded nearest-neighbour search expands until it finds something and can scan a large fraction of the table in sparse areas. The correctness argument and the performance argument point the same way — see spatial index health monitoring for the index-side view.

What if some matches legitimately exceed the bound?

Then the bound encodes a modelling assumption that is wrong for part of your data, and the fix is a per-category or per-region bound rather than a looser global one. Loosening globally to accommodate a minority reintroduces fabrications everywhere else.

How should the bound be reviewed over time?

Quarterly, against the observed distribution. Candidate layers gain and lose features, and a bound set against a two-year-old distribution may now sit inside the cluster rather than in the gap. Reviewing it alongside the join’s baseline keeps the two consistent.