cockroachdb / cockroachdb/cockroach

opt: poor cardinality estimate for self-join with aggregation

Open
#148,632 0 comments 0 reactions 0 assignees View on GitHub
A-sql-optimizer A-sql-table-stats branch-release-23.1 branch-release-23.2 branch-release-24.1 branch-release-24.3 branch-release-25.1 branch-release-25.2 C-performance O-support P-3 T-sql-queries
Dominant language
Go
Stars
32.5k
Forks
4.1k
PR merge metrics
PR metrics pending

Description

In the following example, the optimizer produces a very poor cardinality estimate for the self-join.

```sql
CREATE TABLE abc (
a INT NOT NULL,
b INT NOT NULL,
c INT NOT NULL,
PRIMARY KEY (a, b)
);
INSERT INTO abc SELECT i, i, i FROM generate_series(0, 9999) AS s (i);
ANALYZE abc;

EXPLAIN ANALYZE
SELECT *
FROM (
SELECT a, max(b) AS max_b
FROM abc
WHERE c >= 2000
GROUP BY a
) AS abc1
JOIN abc AS abc2
ON abc2.a = abc1.a
AND abc2.b = abc1.max_b;
```

On v25.2.1 the estimated row count for the self-join is 1, and actual row count is 8000:

```
• merge join
│ sql nodes: n1
│ regions: us-east1
│ actual row count: 8,000
│ execution time: 411µs
│ estimated max memory allocated: 330 KiB
│ estimated max sql temp disk usage: 0 B
│ sql cpu time: 411µs
│ estimated row count: 1
│ equality: (a, b) = (a, max)
│ left cols are key
│ right cols are key

├── • scan
│ sql nodes: n1
│ kv nodes: n1
│ regions: us-east1
│ actual row count: 10,000
│ KV time: 2ms
│ KV rows decoded: 10,000
│ KV bytes read: 343 KiB
│ KV gRPC calls: 1
│ estimated max memory allocated: 390 KiB
│ sql cpu time: 548µs
│ estimated row count: 10,000 (100% of the table; stats collected 0 seconds ago)
│ table: abc@abc_pkey
│ spans: FULL SCAN

└── • group (streaming)
│ sql nodes: n1
│ regions: us-east1
│ actual row count: 8,000
│ execution time: 48µs
│ sql cpu time: 48µs
│ estimated row count: 8,000
│ group by: a
│ ordered: +a

└── • filter
│ sql nodes: n1
│ regions: us-east1
│ actual row count: 8,000
│ execution time: 29µs
│ sql cpu time: 29µs
│ estimated row count: 8,000
│ filter: c >= 2000

└── • scan
sql nodes: n1
kv nodes: n1
regions: us-east1
actual row count: 10,000
KV time: 2ms
KV rows decoded: 10,000
KV bytes read: 343 KiB
KV gRPC calls: 1
estimated max memory allocated: 390 KiB
sql cpu time: 528µs
estimated row count: 10,000 (100% of the table; stats collected 0 seconds ago)
table: abc@abc_pkey
spans: FULL SCAN
```

This might be a similar issue to #41204 but the prototype fix in #138094 doesn't seem to change this estimate. I think this is a different issue from #56441.

Jira issue: CRDB-51711

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.