cockroachdb / cockroachdb/cockroach

Optimize Scan Spans for FULL OUTER JOIN Predicates on Join Keys

Open
#175,448 1 comment 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

**Is your feature request related to a problem? Please describe.**
Hi, CockroachDB deverlopment. Thanks for reading my report.
I find a missed optimization. CockroachDB currently performs full scans for some `FULL OUTER JOIN` queries even when predicates on the join keys can safely constrain both inputs. For example:
```sql
CREATE TABLE t0 (c0 INT PRIMARY KEY);
CREATE TABLE t1 (c0 INT PRIMARY KEY);
INSERT INTO t0 SELECT * FROM generate_series(1, 1000000);
INSERT INTO t1 SELECT * FROM generate_series(1, 1000);

EXPLAIN SELECT * FROM t0 FULL OUTER JOIN t1 ON t0.c0 = t1.c0 WHERE t0.c0 IN (1, 2, 3) OR t1.c0 IN (4, 5, 6);
• filter
│ filter: (c0 IN (1, 2, 3)) OR (c0 IN (4, 5, 6))

└── • merge join (full outer)
│ equality: (c0) = (c0)
│ left cols are key
│ right cols are key

├── • scan
│ missing stats
│ table: t0@t0_pkey
│ spans: FULL SCAN

└── • scan
missing stats
table: t1@t1_pkey
spans: FULL SCAN

EXPLAIN SELECT * FROM t0 INNER JOIN t1 ON t0.c0 = t1.c0 WHERE t0.c0 IN (1, 2, 3) OR t1.c0 IN (4, 5, 6);
• merge join
│ equality: (c0) = (c0)
│ left cols are key
│ right cols are key

├── • scan
│ missing stats
│ table: t0@t0_pkey
│ spans: [/1 - /6]

└── • scan
missing stats
table: t1@t1_pkey
spans: [/1 - /6]
```
Here, both tables in `FULL OUTER JOIN` case are scanned with: `spans: FULL SCAN`. In comparison, the equivalent `INNER JOIN` case derives: `spans: [/1 - /6]`

**Describe the solution you'd like**
Since `t0.c0` and `t1.c0` are primary keys and also the equality join keys, any row satisfying the filter must have a join-key value within `[1, 6]`.
The optimizer could therefore derive scan constraints for both sides of the `FULL OUTER JOIN`, for example: `spans: [/1 - /6]` instead of performing full scans. This could significantly reduce unnecessary scanning when the input tables are large.

**Additional context**
- CockroachDB version: CCL v26.3.1 (docker image cockroachdb/cockroach:v26.3.1, built 2026/08/24)
- Server OS: official Docker image (Linux x86_64 host, Ubuntu 20.04)
- Client app: built-in cockroach sql CLI (also reproduced via JDBC)

Jira issue: CRDB-68375

Contributor guide

Open the contributing guide

Research direction

Run the two EXPLAIN examples from the issue and compare the scan spans for FULL OUTER JOIN and INNER JOIN. Trace the optimizer paths that derive constraints from join-key predicates, then add coverage showing that the full outer join produces bounded spans such as [/1 - /6] without changing its results.

Written by the indexing model from the issue text.

Assessment

Tech stack
go, sql
Domain
databases
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.