cockroachdb / cockroachdb/cockroach

sql/opt: Optimizer misses impossible condition for NULL-constrained equality join

Open
#172,396 2 comments 0 reactions 0 assignees View on GitHub
C-enhancement O-community T-sql-queries X-blathers-triaged
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.