cockroachdb / cockroachdb/cockroach

opt: under-estimating join row count with multiple predicates leads to lookup join

Open
#121,790 1 comment 0 reactions 0 assignees View on GitHub
A-sql-optimizer C-performance T-sql-queries
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

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.