duckdb / duckdb/duckdb-spatial

Potential Bug: Non-deterministic results from ST_Within spatial join (point-in-polygon)

Open
#840 7 comments 0 reactions 0 assignees View on GitHub
Dominant language
C
Stars
708
Forks
96
Avg merge
1d 21h
Merged PRs (30d)
5

Description

**Summary**

A point-in-polygon spatial join using `ST_Within` between a points table and a polygon (boundaries) table returns a different, incomplete subset of matched rows on repeated, identical executions of the same query against unchanged data. Filtering the same query down to a single partition (one month of data) consistently returns correct, complete results every time. Running the unfiltered query returns a different set of missing partitions on each execution.

**Environment**

- DuckDB library_version: v1.5.2
- source_id: 8a5851971fa
- codename: variegata
- Client: R (duckdb R package)
- OS: Windows (air-gapped environment, no direct internet access on the machine running the query — extension installed via local/offline mirror)
- Spatial extension: loaded via `INSTALL spatial; LOAD spatial;`
(exact spatial extension build: dc1996b)

**Data**

- Points table: ~18M rows public domain crime data from policeuk, geometry column type `GEOMETRY`, CRS EPSG:27700 (British National Grid), points constructed via `ST_Point(lon, lat)` then `ST_Transform(..., always_xy := true)` then `ST_SetCRS(..., 'EPSG:27700')`.
- Boundaries table: ~1M polygons (UK ONS/OS administrative boundaries), geometry column cast explicitly to native `GEOMETRY` type, also EPSG:27700.
- Both tables are materialised (`CREATE TABLE ... AS SELECT`), not views.

**Query**

```sql
CREATE TABLE points_joined AS
SELECT p.*, b.boundary_id
FROM points_table p
JOIN boundaries_native b
ON ST_Within(p.geom, b.geom)
```

(Also tested with an added `p.geom && b.geom` bounding-box pre-filter - same non-deterministic behavior. Also tested with an RTREE index on
`boundaries_native.geom` — same behavior, and separately confirmed the index was not being used by the planner via `EXPLAIN` in any case, so index presence/absence does not appear to affect the bug.)

**Steps to reproduce**

1. Materialise points table and boundaries table as described above, both in native `GEOMETRY` type, matching CRS (EPSG:27700).
2. Run the join query above, unfiltered (no `WHERE` clause).
3. Check `SELECT DISTINCT year_month FROM points_joined` (points table has a `year_month` column derived from source filename).
4. Observe that one or more months are missing entirely from the result — e.g., `2025-03` absent.
5. Re-run the identical query (same connection or a fresh connection) — a *different* set of months is now missing.
6. Re-run the query filtered to a single month at a time, e.g. `WHERE p.year_month = '2025-03'` — this consistently and correctly returns matched rows for that month on every run.

**Expected behaviour**

The join should return the same, complete set of matches every time, given unchanged input data — i.e., it should be deterministic, and should match the union of results obtained by running the query separately for each `year_month` partition.

**Actual behaviour**

Non-deterministic: different months are dropped from the result set on different executions of the identical query. Forcing single-threaded execution (`SET threads TO 1`) changed the failure mode from "different months missing each run" to "deterministically only the first month present, every other month dropped" — i.e., still incorrect, just consistently incorrect rather than randomly incorrect.

**What has been ruled out**

- CSV ingestion / upstream data loss: confirmed all expected rows and all months are present in `points_table` prior to the join (`SELECT year_month, COUNT(*) FROM points_table GROUP BY year_month` shows expected row counts for every month).
- The `&&` bounding-box operator as sole cause: removing it entirely and using bare `ST_Within` alone still produces non-deterministic results.
- RTREE index as cause: no index was present for the runs that still showed non-determinism; index presence/absence did not change the behaviour.
- Threading as a full explanation: single-threaded execution changed the symptom (random → deterministic) but did not fix correctness - suggests the underlying issue is likely inside the SPATIAL_JOIN operator / join implementation itself, not purely a race condition exposed by parallelism.
- Tested disabling the automatic SPATIAL_JOIN operator but does not restore deterministic results

**Additional notes**

- I tried to make a minimal case and couldn't reproduce it at small scale, so it may be scale/memory-dependent
- As a workaround, falling back to `sf::st_join` (R) for the point-in-polygon association, at a performance cost, since correctness is the priority.

Contributor guide

No contributing guide indexed for this repository

Research direction

Start with the reported ST_Within query and the SPATIAL_JOIN operator, comparing the unfiltered join with the single-month version. Reproduce with the native GEOMETRY tables, then compare parallel execution with SET threads TO 1 and the tested operator settings. Done means the join returns the complete, identical set of matches across repeated executions.

Written by the indexing model from the issue text.

Assessment

Tech stack
c, r, sql
Domain
data, database
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
38/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.