cockroachdb / cockroachdb/cockroach
Missed index range scan on right side of LEFT OUTER JOIN with join-key predicates in ON
- 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 team, thanks for reading my report.
I’d like to report a missed optimization for `LEFT OUTER JOIN` queries where the `ON` condition is a disjunction of join-key equalities and the `WHERE` clause constrains the left side. CockroachDB performs a full scan on the right input, even though the `ON` and `WHERE` clauses together effectively constrain its join-key values. PostgreSQL, MySQL, and MariaDB all derive index range scans on both sides.
**To Reproduce**
```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, 1000000);
EXPLAIN SELECT * FROM t0 LEFT OUTER JOIN t1 ON ((t0.c0 = 1 AND t1.c0 = 1) OR (t0.c0 = 2 AND t1.c0 = 2)) WHERE t0.c0 IN (1, 2);
• cross join (right outer)
│ pred: ((c0 = 1) AND (c0 = 1)) OR ((c0 = 2) AND (c0 = 2))
│
├── • scan
│ missing stats
│ table: t1@t1_pkey
│ spans: FULL SCAN
│
└── • scan
missing stats
table: t0@t0_pkey
spans: [/1 - /2]
```
**Describe alternatives you've considered**
`t1` can be scanned with `spans: /1-/3` (or `c0 IN (1,2)`), as PostgreSQL, MySQL, and MariaDB already do.
```sql
-- PostgreSQL
EXPLAIN SELECT * FROM t0 LEFT OUTER JOIN t1 ON ((t0.c0 = 1 AND t1.c0 = 1) OR (t0.c0 = 2 AND t1.c0 = 2)) WHERE t0.c0 IN (1, 2);
Nested Loop Left Join (cost=0.68..21.45 rows=1 width=16)
Join Filter: (((t0.c0 = 1) AND (t1.c0 = 1)) OR ((t0.c0 = 2) AND (t1.c0 = 2)))
-> Index Only Scan using t0_pkey on t0 (cost=0.25..12.53 rows=1 width=8)
Index Cond: (c0 = ANY ('{1,2}'::bigint[]))
-> Index Only Scan using t1_pkey on t1 (cost=0.42..8.88 rows=2 width=8)
Index Cond: (c0 = ANY ('{1,2}'::integer[]))
-- MySQL
EXPLAIN SELECT * FROM t0 LEFT OUTER JOIN t1 ON ((t0.c0 = 1 AND t1.c0 = 1) OR (t0.c0 = 2 AND t1.c0 = 2)) WHERE t0.c0 IN (1, 2);
-> Left hash join (no condition), extra conditions: (((t1.c0 = 1) and (t0.c0 = 1)) or ((t1.c0 = 2) and (t0.c0 = 2))) (cost=2.63 rows=4)
-> Filter: (t0.c0 in (1,2)) (cost=0.91 rows=2)
-> Covering index range scan on t0 using PRIMARY over (c0 = 1) OR (c0 = 2) (cost=0.91 rows=2)
-> Hash
-> Covering index range scan on t1 using PRIMARY over (c0 = 1) OR (c0 = 2) (cost=0.81 rows=2)
-- MariaDB
EXPLAIN SELECT * FROM t0 LEFT OUTER JOIN t1 ON ((t0.c0 = 1 AND t1.c0 = 1) OR (t0.c0 = 2 AND t1.c0 = 2)) WHERE t0.c0 IN (1, 2);
+------+-------------+-------+-------+---------------+---------+---------+------+------+-------------------------------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+------+-------------+-------+-------+---------------+---------+---------+------+------+-------------------------------------------------+
| 1 | SIMPLE | t0 | range | PRIMARY | PRIMARY | 4 | NULL | 2 | Using where |
| 1 | SIMPLE | t1 | range | PRIMARY | PRIMARY | 4 | NULL | 2 | Using where; Using join buffer (flat, BNL join) |
+------+-------------+-------+-------+---------------+---------+---------+------+------+-------------------------------------------------+
```
**Suggested solution**
Extend the optimizer to derive scan constraints on the right side of outer joins. When the `ON` condition is a disjunction of conjunctions equating join keys, and the `WHERE` clause restricts the left side to a set of values, the right side can be restricted to the union of the corresponding values from the `ON` condition. Here that union is `{1,2}`, so `t1` should use `spans: /1-/3` (or an equivalent `IN` list).
**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-68492
Contributor guide
Research direction
Start by running the supplied SQL reproduction and comparing its EXPLAIN output with the expected right-side range scan. Investigate the optimizer's outer-join constraint derivation; done means the right input is restricted to the corresponding join-key values instead of using a FULL SCAN, with coverage for the reported query shape.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- sql
- Domain
- databases
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 42/100