Spatial Range and Nearest-Neighbor Search

Range search and nearest-neighbor search look like the same question — “what is close to this point?” — but they compile to fundamentally different execution shapes, and DuckDB Spatial rewards knowing which one you actually asked. A bounded range query (“every feature within distance $d$”) has a fixed search window that the && bounding-box operator and an R-tree can prune directly; a k-nearest-neighbor (kNN) query (“the $k$ closest features, whatever radius that takes”) has no fixed window and no native operator in DuckDB, so you approximate it with an expanding ST_DWithin radius, ST_Expand bbox windows, LATERAL per-probe subqueries, or ROW_NUMBER/QUALIFY ranking. This guide sits under Modern Spatial SQL Query Patterns and works through the configuration, canonical patterns, plan validation, and regression harness that keep both query shapes index-driven and deterministic as the data grows.

Runtime Configuration & Memory Guardrails #

Proximity queries are index-bound, not memory-bound, in the healthy case — the whole point is that the R-tree hands the engine a tiny candidate set before any exact distance runs. The failure mode is the opposite: a query that defeats the index falls back to a full cross product and materializes decoded geometry for every pair, so the session setup exists to make index routing reliable and to bound the blast radius when it slips.

INSTALL spatial;          -- one-time fetch into the local extension cache
LOAD spatial;             -- per-session; ST_DWithin / ST_Distance need it loaded

-- Match physical cores. R-tree probing is memory-bandwidth bound, so hyperthread
-- siblings contend for the same cache lines rather than adding useful parallelism.
SET threads = 8;

-- Ceiling for the join's working set. A well-pruned proximity query needs little;
-- set it low enough that an accidental cross join spills or errors early instead
-- of silently swallowing the box's RAM.
SET memory_limit = '6GB';

-- Drop row-order guarantees so the index scan and hash build parallelize. Re-impose
-- order only on the final result with an explicit ORDER BY.
SET preserve_insertion_order = false;

-- Quiet the progress bar so EXPLAIN ANALYZE timings reflect the query, not render cost.
SET enable_progress_bar = false;

Before running range or kNN workloads in production, confirm these preconditions hold:

• The spatial extension is installed and loaded in the session.
• Probe and candidate layers share one CRS — both projected to metres for a true metric radius, or both in EPSG:4326 with the radius expressed in degrees (never mixed).
• An R-tree index exists on the candidate layer’s native GEOMETRY column so the && stage is index-servable.
• memory_limit leaves headroom for both inputs plus the index, so a mis-pruned run spills gracefully instead of OOM-killing the process.

Trade-off: a metric radius requires a projected CRS, which costs a one-time reprojection at ingestion but makes every subsequent ST_DWithin correct and comparable; leaving data in EPSG:4326 skips that cost but forces every radius to be a degree value that stretches north–south. The reprojection rules and the distortion budget are analyzed in CRS mapping and transformations. Build the index once with the strategies in the R-tree spatial indexing internals reference before benchmarking either pattern.

Primary Execution Patterns #

The two shapes diverge on one axis: whether the search window is known before the query runs. Range search fixes the window at radius $d$; kNN discovers the window by expanding until $k$ candidates are found. Both must keep the R-tree engaged — the moment an exact ST_Distance runs against every row, the query is quadratic.

Bounded range search: ST_DWithin with the && pre-filter #

A range query has a fixed answer set — everything inside radius $d$. The correct form pairs the && bounding-box overlap in the ON clause (the index-servable stage) with an exact ST_DWithin guard, so the R-tree prunes the vast majority of pairs before any real distance is computed. ST_DWithin internally expands the probe geometry’s envelope by $d$ and tests overlap first, but stating the && explicitly against the bare indexed column guarantees the planner routes it through the index rather than hoping it infers the rewrite:

-- All shops within 500 m of each incident. Requires a projected (metric) CRS.
SELECT i.id AS incident_id, s.id AS shop_id,
       ST_Distance(i.geom, s.geom) AS metres
FROM incidents i
JOIN shops s
  ON s.geom && ST_Expand(i.geom, 500.0)   -- Stage 1: MBR overlap, R-tree scan
WHERE ST_DWithin(i.geom, s.geom, 500.0);  -- Stage 2: exact radius on survivors

ST_Expand(i.geom, 500.0) grows the incident’s envelope by the radius so the && test captures every candidate whose bounding box could fall within $d$; ST_DWithin then rejects the corner cases the square envelope over-selects. Keep s.geom bare on the left of && — wrapping the indexed column in any function hides it from the R-tree and collapses the query back to a nested loop. This is the same two-stage discipline that drives the spatial joins and proximity filters reference; range search is simply the distance-predicated case of that join.

kNN search: no native operator, four approximations #

DuckDB has no <-> distance-order operator and no LIMIT k index descent like PostGIS’s kNN GiST. There is no single fixed radius that returns exactly $k$ rows, so every kNN implementation is an approximation strategy that reintroduces a bounded window and then ranks within it. Four patterns cover essentially all cases:

1. Expanding ST_DWithin radius. Start with a guess radius, probe the R-tree, and if fewer than $k$ rows come back, double the radius and re-probe. Cheap when a good radius estimate exists.
2. ST_Expand bbox windows. The bounding-box analogue of the above — grow a square window with ST_Expand and re-probe. Slightly over-selects (square vs circle) but stays purely index-servable.
3. LATERAL per-probe subquery. For each probe row, run a correlated subquery ordered by ST_Distance with LIMIT k, guarded by an ST_DWithin radius so the R-tree stays engaged. The most direct expression of “k nearest per probe”.
4. ROW_NUMBER/QUALIFY ranking. Compute a bounded candidate set once, then rank with a window function and keep the top $k$ per probe. Best when probes are many and the candidate window is shared.

The LATERAL form reads closest to the intent:

-- 3 nearest shops to each incident, R-tree kept engaged by the ST_DWithin guard.
SELECT i.id AS incident_id, n.id AS shop_id, n.metres
FROM incidents i
CROSS JOIN LATERAL (
    SELECT s.id, ST_Distance(i.geom, s.geom) AS metres
    FROM shops s
    WHERE s.geom && ST_Expand(i.geom, 2000.0)   -- index-servable window guard
      AND ST_DWithin(i.geom, s.geom, 2000.0)     -- radius guard keeps it bounded
    ORDER BY metres                               -- exact rank on the small survivor set
    LIMIT 3
) AS n;

The ST_Expand/ST_DWithin guard is doing the heavy lifting: without it, the subquery orders every shop by distance per incident — an $O(N \times M)$ disaster. With it, the R-tree hands each probe a handful of candidates and the ORDER BY ... LIMIT 3 sorts only those. The full implementation, including the QUALIFY ROW_NUMBER() alternative and the loop that widens the guard when it returns fewer than $k$ rows, is worked through in the kNN queries with ST_DWithin walkthrough.

The QUALIFY form trades the correlated subquery for a single ranked pass, which the planner can sometimes vectorize better when there are many probes:

-- Same 3-NN result via ranking, one bounded candidate set, no LATERAL.
SELECT incident_id, shop_id, metres
FROM (
    SELECT i.id AS incident_id, s.id AS shop_id,
           ST_Distance(i.geom, s.geom) AS metres,
           ROW_NUMBER() OVER (PARTITION BY i.id ORDER BY ST_Distance(i.geom, s.geom)) AS rk
    FROM incidents i
    JOIN shops s
      ON s.geom && ST_Expand(i.geom, 2000.0)
    WHERE ST_DWithin(i.geom, s.geom, 2000.0)
) ranked
QUALIFY rk <= 3;   -- QUALIFY filters on the window result without a wrapping subquery

Both forms depend on the guard radius (2000 m here) being wide enough to contain the true $k$-th neighbour for every probe. When it is not, the result is silently short — a probe in a sparse region returns two neighbours when you asked for three. Handling that correctly means an expanding retry, covered in the walkthrough.

Execution Plan Validation #

The only reliable way to confirm the R-tree stayed engaged is to read the plan. A healthy proximity query shows an RTREE_INDEX_SCAN (or an index-driven join) feeding a small candidate set into the exact distance stage; the anti-pattern is a NESTED_LOOP_JOIN that evaluates ST_Distance on the full product.

EXPLAIN
SELECT i.id, s.id
FROM incidents i
JOIN shops s
  ON s.geom && ST_Expand(i.geom, 500.0)
WHERE ST_DWithin(i.geom, s.geom, 500.0);

What to assert in the measured plan:

• Scan type. An RTREE_INDEX_SCAN or index-driven join over the candidate layer is correct. A SEQ_SCAN of shops under a NESTED_LOOP_JOIN means the && predicate never reached the index — check that the indexed column is bare and the CRS/units line up.
• Candidate cardinality. The row count entering the exact ST_DWithin/ST_Distance stage should be a small multiple of the final result, not the full candidate-layer size. A candidate count near $N \times M$ is the signature of a missing pre-filter.
• Filter selectivity. In EXPLAIN ANALYZE, the &&/index stage should discard the large majority of pairs. If the exact-distance node processes most of the input, the bounding-box stage is not selective — usually a degree radius applied to metric data or vice versa.

-- Measured plan: confirm the index scan runs and time the exact-distance node.
EXPLAIN ANALYZE
SELECT i.id, s.id
FROM incidents i
JOIN shops s
  ON s.geom && ST_Expand(i.geom, 500.0)
WHERE ST_DWithin(i.geom, s.geom, 500.0);

For kNN, additionally confirm the LATERAL subquery reports a per-probe candidate count in the low tens, not the full candidate layer — a large count means the guard radius is too wide or absent, and the ORDER BY ... LIMIT k is sorting far more than it should. The internal cost of the index probe itself is detailed in the R-tree spatial indexing internals reference.

Performance Trade-offs #

The three viable strategies for “k nearest” trade index leverage against setup cost and correctness guarantees. Measure against your own density distribution, but these are the typical ranges:

The dominant decision is guard-radius sizing. Too tight and sparse-region probes return fewer than $k$ neighbours (silent under-count); too wide and every probe drags a large candidate set through the exact sort, erasing the index advantage. A materialized grid sidesteps the R-tree entirely but cannot see neighbours that fall just across a cell boundary, so it is an approximation — acceptable for density estimation, wrong for “the single closest hospital”. The grid pre-aggregation mechanics are shared with the vectorized aggregations reference, and the pairwise matrix form appears in calculating distance matrices with SQL.

Edge Cases & Anti-Patterns #

Degree radius on metric data, or metric radius on degrees (silent wrong answers). ST_DWithin(a, b, 500) means 500 coordinate units. In EPSG:4326 that is 500 degrees — the entire planet; in a metre-based projection it is 500 metres. There is no unit tag on the number.

-- Confirm the CRS before choosing a radius value; expect a projected SRID, not 4326.
SELECT DISTINCT ST_SRID(geom) AS srid FROM shops;

Ties at the boundary (non-deterministic kNN). When several candidates sit at exactly the $k$-th distance, LIMIT k picks an arbitrary subset and ROW_NUMBER breaks the tie by physical order, so two runs can return different neighbours. Add a deterministic tiebreak to the ordering:

-- Deterministic ranking: distance first, then a stable key to resolve ties.
ROW_NUMBER() OVER (PARTITION BY i.id ORDER BY ST_Distance(i.geom, s.geom), s.id)

Empty results needing radius expansion (silent under-count). A guard radius that fits dense areas returns fewer than $k$ rows in sparse ones. The fix is not a bigger fixed radius — that penalizes every dense probe — but an expanding retry that widens the window only for the probes that came up short, detailed in the kNN queries walkthrough.

Bare ST_Distance(a, b) < d instead of ST_DWithin (defeated index). Writing the radius as WHERE ST_Distance(i.geom, s.geom) < 500 computes an exact distance for every pair before filtering — there is no envelope to push to the R-tree.

-- Anti-pattern: exact distance on every pair, no index-servable predicate.
SELECT i.id, s.id FROM incidents i JOIN shops s
ON ST_Distance(i.geom, s.geom) < 500;

-- Fix: ST_DWithin exposes an expandable envelope the R-tree can pre-filter on.
SELECT i.id, s.id FROM incidents i JOIN shops s
ON s.geom && ST_Expand(i.geom, 500.0)
WHERE ST_DWithin(i.geom, s.geom, 500.0);

Great-circle distance expected from planar ST_Distance. ST_Distance is planar; on EPSG:4326 it returns a degree magnitude, not metres, and never accounts for Earth curvature. For true ground distance, project both inputs to a suitable metric CRS first — the reprojection is a hard requirement for any radius you intend to interpret in metres.

Query Regression Analysis #

A proximity query that silently loses its index degrades from milliseconds to minutes without changing its result, so the regression guard asserts on the plan, not the wall clock. Capture the plan as JSON, walk the tree, and fail if a nested loop or a sequential scan of the candidate layer appears where the index scan belongs. This harness slots into the orchestration covered in Python and DuckDB integration workflows.

import duckdb
import json

con = duckdb.connect(":memory:")
con.execute("INSTALL spatial; LOAD spatial;")
con.execute("SET threads = 8; SET memory_limit = '6GB';")

QUERY = """
SELECT i.id, s.id
FROM incidents i
JOIN shops s
  ON s.geom && ST_Expand(i.geom, 500.0)
WHERE ST_DWithin(i.geom, s.geom, 500.0)
"""

# FORMAT JSON yields a machine-readable plan tree for diffing across builds.
plan = json.loads(
    con.execute(f"EXPLAIN (FORMAT JSON) {QUERY}").fetchone()[1]
)

# A nested loop, or a plain scan of the candidate layer, means the R-tree was defeated.
BANNED = {"NESTED_LOOP_JOIN"}
REQUIRED_ANY = {"RTREE_INDEX_SCAN", "INDEX_SCAN"}

def walk(node):
    yield node.get("name", "")
    for child in node.get("children", []):
        yield from walk(child)

found = set(walk(plan[0])) if isinstance(plan, list) else set(walk(plan))
assert not (found & BANNED), f"Proximity plan regressed to a cross product: {found & BANNED}"
assert found & REQUIRED_ANY, f"No index scan in proximity plan; got nodes {found}"

Track three signals across builds: the presence of the index-scan node (its disappearance is a hard regression), the candidate-row count entering the exact-distance stage (a jump toward $N \times M$ predicts a defeated pre-filter), and per-probe kNN candidate depth (a rising guard-radius candidate count means the sort is doing more work than the index). For running the capture without blocking an event loop, see async execution patterns; to hand the matched rows to GeoPandas without a serialization round-trip, see DuckDB-to-GeoPandas sync.

Diagnostic thresholds to alert on:

Related #

See also

• kNN queries with ST_DWithin — the full LATERAL, QUALIFY, and expanding-radius implementation of nearest-neighbor search.
• Spatial joins and proximity filters — the two-stage && pre-filter discipline that range search is a distance-predicated case of.
• R-tree spatial indexing internals — how the index that both patterns rely on is built and probed.
• CRS mapping and transformations — the projected-CRS requirement behind every metric radius.

Up: Modern Spatial SQL Query Patterns