cockroachdb / cockroachdb/cockroach

sql/opt: version of SplitDisjunctionOfJoinTerms rule for left join

Open
#94,382 1 comment 0 reactions 0 assignees View on GitHub
A-sql-optimizer C-enhancement O-support P-3 T-sql-queries
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.