cockroachdb / cockroachdb/cockroach
sql/opt: Optimizer misses impossible condition for NULL-constrained equality join
- Dominant language
- Go
- Stars
- 32.5k
- Forks
- 4.1k
- PR merge metrics
- PR metrics pending
Description
**Describe the problem**
CockroachDB appears to miss an impossible-condition optimization for an inner equality join when one equality column is constrained to `NULL`.
The reproducer contains the following semantic pattern:
```sql
SELECT t1.c1 AS ref0, t0.c0
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t1.c0 IS NULL;
```
Under ordinary SQL equality semantics, `NULL = anything` is not `TRUE`. Therefore, once `t1.c0 IS NULL` is known, the inner join predicate `t1.c0 = t0.c0` cannot be satisfied. The query is provably empty and could be optimized to a `norows` / empty-result plan.
However, CockroachDB still plans and executes real joins over the NULL-key index spans. In the attached result, the optimizer chooses a plan with cost about `4346.5`:
```text
top-k
└── lookup join
└── merge join
├── scan t0@i0 spans: [/NULL - /NULL]
└── scan t1@i3 spans: [/NULL - /NULL]
```
`EXPLAIN ANALYZE` shows that this plan returns zero rows, but still decodes `4,000` KV rows from the NULL-key spans:
```text
execution time: 4ms
rows decoded from KV: 4,000
scan t0@i0:
KV rows decoded: 2,000
actual row count: 2,000
spans: [/NULL - /NULL]
scan t1@i3:
KV rows decoded: 2,000
actual row count: 2,000
spans: [/NULL - /NULL]
```
For comparison, the attached script also includes an explicitly empty baseline:
```sql
EXPLAIN ANALYZE
SELECT t1.c1 AS ref0, t0.c0
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0
WHERE FALSE;
```
This baseline is optimized to a `norows` plan:
```text
execution time: 59µs
• norows
actual row count: 0
```
So in this run, the observed plan took about `4ms`, while the empty-result baseline took about `59µs`, roughly a `68x` difference. The absolute timing is small at this scale, but the important point is that CockroachDB performs scan/join work over NULL-key ranges even though the result is guaranteed to be empty. This work should scale with the number of NULL rows.
This is not a correctness bug: the query result is correct. The issue is that the optimizer misses a contradiction. The likely root cause is that CockroachDB derives NULL-span constraints from `t1.c0 IS NULL`, but does not combine them with the NULL-rejecting property of ordinary equality joins. Since `t1.c0 = t0.c0` must evaluate to `TRUE` for an inner join match, and `t1.c0` is known to be `NULL`, the join condition is impossible under SQL three-valued logic.
**To Reproduce**
1. Start a CockroachDB node or cluster.
2. Run the attached SQL script:
```bash
cockroach sql --insecure --host=localhost:xxxx -f crdb_null_eq_impossible_repro.sql > crdb_null_eq_impossible_repro_result.txt
```
3. The script creates a database, creates two test tables, inserts both non-NULL and NULL rows, creates indexes, runs `ANALYZE`, and then runs sanity checks plus `EXPLAIN` / `EXPLAIN ANALYZE` queries.
The key sanity checks are:
```sql
SELECT COUNT(*) AS eq_join_should_be_zero
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t1.c0 IS NULL;
```
This returns `0`, as expected.
The NULL-safe control query returns rows:
```sql
SELECT EXISTS(
SELECT 1
FROM t1 INNER JOIN t0 ON t1.c0 IS NOT DISTINCT FROM t0.c0
WHERE t1.c0 IS NULL
LIMIT 1
) AS null_safe_join_has_rows;
```
This returns `true`, confirming that both tables really contain NULL rows and that the zero-row result is due to ordinary equality semantics, not due to missing data.
The main query is:
```sql
EXPLAIN ANALYZE
SELECT t1.c1 AS ref0, t0.c0
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t1.c0 IS NULL
ORDER BY t0.c3 ASC, t0.c0 DESC
LIMIT 2;
```
Observed behavior from the attached result:
```text
• top-k
└── • lookup join
└── • merge join
├── • scan
│ table: t0@i0
│ spans: [/NULL - /NULL]
└── • scan
table: t1@i3
spans: [/NULL - /NULL]
```
The query returns zero rows, but it still decodes KV rows from both NULL-key spans:
```text
execution time: 4ms
rows decoded from KV: 4,000
scan t0@i0:
KV rows decoded: 2,000
actual row count: 2,000
spans: [/NULL - /NULL]
scan t1@i3:
KV rows decoded: 2,000
actual row count: 2,000
spans: [/NULL - /NULL]
```
The same missed contradiction also appears without `ORDER BY` / `LIMIT`:
```sql
EXPLAIN ANALYZE
SELECT t1.c1 AS ref0, t0.c0
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t1.c0 IS NULL;
```
In the attached run, this plan still performs a merge join over NULL spans and decodes 4,000 KV rows before returning zero rows.
For comparison, the attached script also includes an explicitly empty baseline:
```sql
EXPLAIN ANALYZE
SELECT t1.c1 AS ref0, t0.c0
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0
WHERE FALSE;
```
This correctly produces a `norows` plan:
```text
execution time: 59µs
• norows
actual row count: 0
```
In this local run, the main `ORDER BY ... LIMIT` query took about `4ms`, while the explicit empty baseline took about `59µs`, roughly a 68x difference. The absolute timing is small for this scale, but the important point is the unnecessary KV scan/join work. The cost should scale with the number of NULL-key rows.
**Expected behavior**
CockroachDB should recognize that the predicate combination is unsatisfiable:
```sql
t1.c0 IS NULL
AND t1.c0 = t0.c0
```
For an inner join using ordinary SQL equality, this condition cannot evaluate to `TRUE`. The optimizer should be able to fold the query to an empty result, ideally producing a `norows` / empty plan and avoiding scans of the NULL-key spans.
The same reasoning should apply both with and without `ORDER BY` / `LIMIT`.
**Additional data / screenshots**
Attached files:
- `crdb_null_eq_impossible_repro.sql`
[crdb_null_eq_impossible_repro.sql](https://github.com/user-attachments/files/29854109/crdb_null_eq_impossible_repro.sql)
- `crdb_null_eq_impossible_repro_result.txt`
[crdb_null_eq_impossible_repro_result.txt](https://github.com/user-attachments/files/29854116/crdb_null_eq_impossible_repro_result.txt)
The SQL script contains the full schema, data generation, indexes, statistics collection, sanity checks, and the `EXPLAIN` / `EXPLAIN ANALYZE` statements.
**Environment:**
- CockroachDB version: `CockroachDB CCL v26.2.2`
- Server OS: Ubuntu 22.04.4 LTS
- Client app: `cockroach sql`
**Additional context**
This looks like a missed optimizer contradiction-detection opportunity rather than a result correctness issue.
A possible root cause is that the optimizer derives and uses NULL-span constraints from `t1.c0 IS NULL`, but does not combine them with the NULL-rejecting property of ordinary equality joins. Since `t1.c0 = t0.c0` must be `TRUE` for an inner join match, and `t1.c0` is known to be `NULL`, the equality join condition is impossible under SQL three-valued logic.
The issue is more visible on NULL-heavy data because CockroachDB scans and joins the NULL-key ranges even though the final result is guaranteed to be empty.
Jira issue: CRDB-65632
Contributor guide
Research direction
Start by running the attached crdb_null_eq_impossible_repro.sql and compare EXPLAIN ANALYZE for the equality join with the FALSE baseline. Then inspect CockroachDB's optimizer handling of IS NULL constraints and inner equality joins; done when both query variants recognize the contradiction as a norows/empty plan without scanning NULL-key spans.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go, sql
- Domain
- databases, performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 48/100