cockroachdb / cockroachdb/cockroach

sql: ST_DWithin inverted join fails for POINT EMPTY geography input

Open
#175,342 1 comment 0 reactions 0 assignees View on GitHub
C-bug O-community X-blathers-untriaged
Dominant language
Go
Stars
32.5k
Forks
4.1k
PR merge metrics
PR metrics pending

Description

## Describe the problem

A geography `ST_DWithin` inverted join fails when a probe row contains `POINT EMPTY`. The query should have no matches, but instead returns:

```text
(XXUUU) unable to construct span expression
```

The empty geography is a valid, non-NULL value. Direct predicate evaluation returns `false`, and the same join through the primary index returns a count of `0`. The error occurs when the spatial inverted index is used to construct search spans for that probe row.

## Environment

- Upstream source revision: [`8812064a015d2faf99d3fc7e15880f94042954b0`](https://github.com/cockroachdb/cockroach/commit/8812064a015d2faf99d3fc7e15880f94042954b0) (the `master` revision checked when preparing this report).
- Linux, amd64.
- Reproduced with the native SQL logic-test harness, `local` configuration.

## To reproduce

Run the following in a fresh database. Both geographies use the default SRID 4326, and the distance is positive.

```sql
CREATE TABLE empty_geography_probe (
id INT PRIMARY KEY,
geog GEOGRAPHY
);

CREATE TABLE empty_geography_indexed (
id INT PRIMARY KEY,
geog GEOGRAPHY,
INVERTED INDEX idx (geog)
);

INSERT INTO empty_geography_probe VALUES (1, 'POINT EMPTY');
INSERT INTO empty_geography_indexed VALUES (1, 'POINT(0 0)');

-- Control: false, false.
SELECT 'POINT EMPTY'::GEOGRAPHY IS NULL,
ST_DWithin('POINT EMPTY'::GEOGRAPHY,
'POINT(0 0)'::GEOGRAPHY, 1.0, true);

-- Control: returns 0.
SELECT count(*)
FROM empty_geography_probe AS p
INNER HASH JOIN empty_geography_indexed@empty_geography_indexed_pkey AS g
ON ST_DWithin(p.geog, g.geog, 1.0, true);

-- Fails with: unable to construct span expression (SQLSTATE XXUUU).
SELECT count(*)
FROM empty_geography_probe AS p
INNER INVERTED JOIN empty_geography_indexed@idx AS g
ON ST_DWithin(p.geog, g.geog, 1.0, true);
```

The explicit index and join hints make the failing execution path reproducible without relying on cost estimates or table size.

## Expected behavior and semantic references

The last query should return one row containing `0`, just like the control. A non-aggregated inner join should return no rows for this empty probe.

This follows CockroachDB's existing predicate contract: [the geography `DWithin` implementation](https://github.com/cockroachdb/cockroach/blob/8812064a015d2faf99d3fc7e15880f94042954b0/pkg/geo/geogfn/dwithin.go#L45-L58) handles an empty input by returning `false` without an error, and [the existing empty-geography unit tests](https://github.com/cockroachdb/cockroach/blob/8812064a015d2faf99d3fc7e15880f94042954b0/pkg/geo/geogfn/dwithin_test.go#L136-L157) assert that behavior.

The [CockroachDB JOIN documentation](https://docs.cockroachlabs.com/docs/stable/joins#inner-joins) says inner joins return matching rows; [the inverted-join section](https://docs.cockroachlabs.com/docs/stable/joins#inverted-joins) documents this join form. PostGIS also documents `ST_DWithin(empty, anything, distance)` as false in its [empty geometry semantics](https://postgis.net/development/docs/internals/empty-geometry/#predicates). The CockroachDB implementation and direct SQL control establish the geography behavior here independently of the PostGIS reference.

## Root cause

The runtime span-construction path loses the distinction between an empty candidate set and an expression that cannot constrain an inverted index:

1. [`s2GeographyIndex.DWithin`](https://github.com/cockroachdb/cockroach/blob/8812064a015d2faf99d3fc7e15880f94042954b0/pkg/geo/geoindex/s2_geography_index.go#L151-L205) converts its input using `AsS2(geo.EmptyBehaviorOmit)`. For `POINT EMPTY`, there are no S2 regions to cover and the resulting key-span list is empty.
2. [`getSpanExprForGeographyIndex`](https://github.com/cockroachdb/cockroach/blob/8812064a015d2faf99d3fc7e15880f94042954b0/pkg/sql/opt/invertedidx/geo.go#L139-L143) passes those spans to `GeoUnionKeySpansToSpanExpr`.
3. [`GeoUnionKeySpansToSpanExpr`](https://github.com/cockroachdb/cockroach/blob/8812064a015d2faf99d3fc7e15880f94042954b0/pkg/sql/opt/invertedexpr/geo_expression.go#L59-L62) returns `inverted.NonInvertedColExpression{}` when the span list has length zero.
4. [`geoDatumsToInvertedExpr.Convert`](https://github.com/cockroachdb/cockroach/blob/8812064a015d2faf99d3fc7e15880f94042954b0/pkg/sql/opt/invertedidx/geo.go#L1132-L1146) accepts a nil expression as an empty result, but otherwise requires `*inverted.SpanExpression`. The non-nil `NonInvertedColExpression` fails that type assertion and produces the error above, before the exact `ST_DWithin` predicate can reject the candidate.

A fix needs to represent the provably empty `DWithin` result as no matches in the runtime inverted-join path. Care is needed if changing the shared conversion helper: an unconstrained/non-indexable expression must not generally be treated as an empty result. For a left inverted join, an empty probe should still preserve the left row with NULLs on the right.

## Regression test

The following fragment can be appended to `pkg/sql/logictest/testdata/logic_test/geospatial_index`. On the revision above, the control subtest passes and the inverted-join subtest fails. After a fix, both should pass.

Observed native test result:

```text
PASS: TestLogic_geospatial_index/empty_geography_control
FAIL: TestLogic_geospatial_index/empty_geography_inverted_regression
expected success, but found
(XXUUU) unable to construct span expression
```

SQL logic-test fragment

```text
subtest empty_geography_control

statement ok
CREATE TABLE empty_geography_probe (id INT PRIMARY KEY, geog GEOGRAPHY)

statement ok
INSERT INTO empty_geography_probe VALUES (1, 'POINT EMPTY')

statement ok
CREATE TABLE empty_geography_indexed (id INT PRIMARY KEY, geog GEOGRAPHY, INVERTED INDEX idx (geog))

statement ok
INSERT INTO empty_geography_indexed VALUES (1, 'POINT(0 0)')

query BB
SELECT 'POINT EMPTY'::GEOGRAPHY IS NULL,
ST_DWithin('POINT EMPTY'::GEOGRAPHY, 'POINT(0 0)'::GEOGRAPHY, 1.0, true)
----
false false

query I
SELECT count(*) FROM empty_geography_probe AS p
INNER HASH JOIN empty_geography_indexed@empty_geography_indexed_pkey AS g
ON ST_DWithin(p.geog, g.geog, 1.0, true)
----
0

subtest empty_geography_inverted_regression

query I
SELECT count(*) FROM empty_geography_probe AS p
INNER INVERTED JOIN empty_geography_indexed@idx AS g
ON ST_DWithin(p.geog, g.geog, 1.0, true)
----
0
```

Run both subtests together so the setup in the control subtest is executed:

```sh
bazel test //pkg/sql/logictest/tests/local:local_test \
--test_sharding_strategy=disabled \
--test_filter='^TestLogic_geospatial_index$/^empty_geography_(control|inverted_regression)$'
```

Useful follow-up coverage for a fix would include both sphere/spheroid modes, other typed empty geographies, swapped predicate arguments, NULL probes, and a left inverted join that must retain the unmatched probe row. Those are suggested extensions; the minimal reproduction above isolates the inner-join failure.

Jira issue: CRDB-68340

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.