cockroachdb / cockroachdb/cockroach

Missed index range scan on right side of LEFT OUTER JOIN with join-key predicates in ON

Open
#175,603 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 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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.