cockroachdb / cockroachdb/cockroach
sql/opt: version of SplitDisjunctionOfJoinTerms rule for left join
- Dominant language
- Go
- Stars
- 32.5k
- Forks
- 4.1k
- PR merge metrics
- PR metrics pending
Description
In #74303 two new exploration rules were added, `SplitDisjunctionOfJoinTerms` and `SplitDisjunctionOfAntiJoinTerms`, which split inner joins, semi joins, and anti joins with disjunctions in their join predicates into unioned joins. It would be nice to also have a version of this rule for left join (or other outer joins).
Here's an example of a query that would benefit:
```sql
CREATE TABLE x (
x INT PRIMARY KEY
);
CREATE TABLE abc (
a INT PRIMARY KEY,
b INT,
c INT,
INDEX (b),
INDEX (c)
);
INSERT INTO x SELECT generate_series(0, 15);
INSERT INTO abc SELECT x + y * 16, x, y FROM x, generate_series(0, 1023) s(y);
ANALYZE x;
ANALYZE abc;
EXPLAIN
SELECT x, sum(a)
FROM x LEFT JOIN abc ON b = x OR c = x
WHERE x > 14
GROUP BY x;
```
The plan for this query currently uses a cross join over a full table scan of `abc`:
```
demo@127.0.0.1:26257/defaultdb> EXPLAIN
-> SELECT x, sum(a)
-> FROM x LEFT JOIN abc ON b = x OR c = x
-> WHERE x > 14
-> GROUP BY x;
info
---------------------------------------------------------------------------------------------
distribution: local
vectorized: true
• group (hash)
│ estimated row count: 1
│ group by: x
│
└── • cross join (right outer)
│ estimated row count: 1,039
│ pred: (b = x) OR (c = x)
│
├── • scan
│ estimated row count: 16,384 (100% of the table; stats collected 12 minutes ago)
│ table: abc@abc_pkey
│ spans: FULL SCAN
│
└── • scan
estimated row count: 1 (6.3% of the table; stats collected 12 minutes ago)
table: x@x_pkey
spans: [/15 - ]
(20 rows)
Time: 2ms total (execution 2ms / network 0ms)
```
If we (incorrectly) rewrite the query to use `UNION` over two left joins, the plan looks much better (though it now generates different results):
```
demo@127.0.0.1:26257/defaultdb> EXPLAIN
-> SELECT x, sum(a)
-> FROM (
-> SELECT x, a
-> FROM x LEFT JOIN abc ON b = x
-> WHERE x > 14
-> UNION
-> SELECT x, a
-> FROM x LEFT JOIN abc ON c = x
-> WHERE x > 14
-> )
-> GROUP BY x;
info
------------------------------------------------------------------------------------------------
distribution: local
vectorized: true
• group (hash)
│ estimated row count: 2
│ group by: x
│
└── • union
│ estimated row count: 1,050
│
├── • merge join (right outer)
│ │ estimated row count: 1,034
│ │ equality: (b) = (x)
│ │ right cols are key
│ │
│ ├── • scan
│ │ estimated row count: 1,034 (6.3% of the table; stats collected 20 minutes ago)
│ │ table: abc@abc_b_idx
│ │ spans: [/15 - ]
│ │
│ └── • scan
│ estimated row count: 1 (6.3% of the table; stats collected 20 minutes ago)
│ table: x@x_pkey
│ spans: [/15 - ]
│
└── • lookup join (left outer)
│ estimated row count: 16
│ table: abc@abc_c_idx
│ equality: (x) = (c)
│ pred: c > 14
│
└── • scan
estimated row count: 1 (6.3% of the table; stats collected 20 minutes ago)
table: x@x_pkey
spans: [/15 - ]
(35 rows)
Time: 4ms total (execution 4ms / network 0ms)
```
This exact rewrite won't usually work (in fact I think it's incorrect in this case), so I imagine this rule will be tricky to get right.
Jira issue: CRDB-22866
Contributor guide
Assessment
This issue has not been assessed yet.