cockroachdb / cockroachdb/cockroach
opt: under-estimating join row count with multiple predicates leads to lookup join
- Dominant language
- Go
- Stars
- 32.5k
- Forks
- 4.1k
- PR merge metrics
- PR metrics pending
Description
Here's a contrived case where the optimizer is massively under-estimating the row count of a join with multiple predicates on highly-correlated columns. Consequently the optimizer picks a lookup join instead of hash join, which is about twice as slow:
```sql
-- Create two tables. Columns a, b, and c are perfectly correlated, as are columns d and e.
CREATE TABLE abc (
a INT,
b INT,
c INT,
INDEX (a, b, c)
);
CREATE TABLE de (
d INT,
e INT,
INDEX (d, e)
);
INSERT INTO abc SELECT i % 20, i % 20, i % 20 FROM generate_series(0, 99999) s(i);
INSERT INTO de SELECT i % 10, i % 10 FROM generate_series(0, 9999) s(i);
ANALYZE abc;
ANALYZE de;
-- The optimizer estimates 12k rows for this join, 5m are actually produced.
EXPLAIN ANALYZE SELECT * FROM abc JOIN de ON e = a WHERE b = 3 AND c = 3 AND d = 3;
-- Hash join runs in half the time.
EXPLAIN ANALYZE SELECT * FROM abc INNER HASH JOIN de ON e = a WHERE b = 3 AND c = 3 AND d = 3;
```
This is on v24.1.0-alpha.5.
Jira issue: CRDB-37543
Contributor guide
Assessment
This issue has not been assessed yet.