cockroachdb / cockroachdb/cockroach
opt: not decorrelating aggregation subquery in select clause
- Dominant language
- Go
- Stars
- 32.5k
- Forks
- 4.1k
- PR merge metrics
- PR metrics pending
Description
Following are a set of correlated subqueries that the optimizer doesn't seem to automatically decorrelate, at least not with the given statistics:
```sql
CREATE TABLE ab (a INT PRIMARY KEY, b INT);
CREATE TABLE ca (c INT PRIMARY KEY, a INT);
CREATE TABLE da (d INT PRIMARY KEY, a INT);
INSERT INTO ab SELECT i, i FROM generate_series(0, 999) s(i);
INSERT INTO ca SELECT i, i FROM generate_series(0, 999) s(i);
INSERT INTO da SELECT i, i FROM generate_series(0, 999) s(i);
ANALYZE ab;
ANALYZE ca;
ANALYZE da;
EXPLAIN ANALYZE
SELECT ab.*,
COALESCE((SELECT count(*) FROM ca WHERE ca.a = ab.a GROUP BY ca.a), 0) AS ccount,
COALESCE((SELECT count(*) FROM da WHERE da.a = ab.a GROUP BY da.a), 0) AS dcount
FROM ab
ORDER BY ab.b
LIMIT 1000;
```
This becomes two apply joins over a scan:
```
----------------------------------------------------------------------------------------------------
planning time: 795µs
execution time: 908ms
distribution: local
vectorized: true
rows read from KV: 1,000 (33 KiB, 1 gRPC calls)
cumulative time spent in KV: 526µs
maximum memory usage: 450 KiB
network usage: 0 B (0 messages)
sql cpu time: 897ms
estimated RUs consumed: 0
• render
│
└── • top-k
│ nodes: n1
│ actual row count: 1,000
│ estimated max memory allocated: 80 KiB
│ estimated max sql temp disk usage: 0 B
│ sql cpu time: 317µs
│ estimated row count: 1,000
│ order: +b
│ k: 1000
│
└── • apply join (left outer)
│ nodes: n1
│ actual row count: 1,000
│ sql cpu time: 896ms
│ estimated row count: 1,000
│
└── • apply join (left outer)
│ estimated row count: 1,000
│
└── • scan
nodes: n1
actual row count: 1,000
KV time: 526µs
KV contention time: 0µs
KV rows read: 1,000
KV bytes read: 33 KiB
KV gRPC calls: 1
estimated max memory allocated: 70 KiB
sql cpu time: 146µs
estimated row count: 1,000 (100% of the table; stats collected 11 seconds ago)
table: ab@ab_pkey
spans: FULL SCAN
(45 rows)
Time: 911ms total (execution 910ms / network 0ms)
```
Manually decorrelating gives a much faster plan:
```sql
EXPLAIN ANALYZE
SELECT ab.*, COALESCE(ccount.cnt, 0), COALESCE(dcount.cnt, 0)
FROM ab
LEFT JOIN (SELECT a, count(*) AS cnt FROM ca GROUP BY a) AS ccount USING (a)
LEFT JOIN (SELECT a, count(*) AS cnt FROM da GROUP BY a) AS dcount USING (a)
ORDER BY ab.b
LIMIT 1000;
```
using hash joins over hash grouping:
```
info
--------------------------------------------------------------------------------------------------------
planning time: 671µs
execution time: 4ms
distribution: local
vectorized: true
rows read from KV: 3,000 (98 KiB, 3 gRPC calls)
cumulative time spent in KV: 1ms
maximum memory usage: 2.1 MiB
network usage: 0 B (0 messages)
sql cpu time: 2ms
estimated RUs consumed: 0
• sort
│ nodes: n1
│ actual row count: 1,000
│ estimated max memory allocated: 80 KiB
│ estimated max sql temp disk usage: 0 B
│ sql cpu time: 40µs
│ estimated row count: 1,000
│ order: +b
│
└── • render
│
└── • hash join (left outer)
│ nodes: n1
│ actual row count: 1,000
│ estimated max memory allocated: 140 KiB
│ estimated max sql temp disk usage: 0 B
│ sql cpu time: 76µs
│ estimated row count: 1,000
│ equality: (a) = (a)
│ left cols are key
│ right cols are key
│
├── • hash join (left outer)
│ │ nodes: n1
│ │ actual row count: 1,000
│ │ estimated max memory allocated: 120 KiB
│ │ estimated max sql temp disk usage: 0 B
│ │ sql cpu time: 76µs
│ │ estimated row count: 1,000
│ │ equality: (a) = (a)
│ │ left cols are key
│ │ right cols are key
│ │
│ ├── • top-k
│ │ │ nodes: n1
│ │ │ actual row count: 1,000
│ │ │ estimated max memory allocated: 40 KiB
│ │ │ estimated max sql temp disk usage: 0 B
│ │ │ sql cpu time: 240µs
│ │ │ estimated row count: 1,000
│ │ │ order: +b
│ │ │ k: 1000
│ │ │
│ │ └── • scan
│ │ nodes: n1
│ │ actual row count: 1,000
│ │ KV time: 397µs
│ │ KV contention time: 0µs
│ │ KV rows read: 1,000
│ │ KV bytes read: 33 KiB
│ │ KV gRPC calls: 1
│ │ estimated max memory allocated: 70 KiB
│ │ sql cpu time: 133µs
│ │ estimated row count: 1,000 (100% of the table; stats collected 21 seconds ago)
│ │ table: ab@ab_pkey
│ │ spans: FULL SCAN
│ │
│ └── • group (hash)
│ │ nodes: n1
│ │ actual row count: 1,000
│ │ estimated max memory allocated: 680 KiB
│ │ estimated max sql temp disk usage: 0 B
│ │ sql cpu time: 381µs
│ │ estimated row count: 1,000
│ │ group by: a
│ │
│ └── • scan
│ nodes: n1
│ actual row count: 1,000
│ KV time: 405µs
│ KV contention time: 0µs
│ KV rows read: 1,000
│ KV bytes read: 33 KiB
│ KV gRPC calls: 1
│ estimated max memory allocated: 60 KiB
│ sql cpu time: 123µs
│ estimated row count: 1,000 (100% of the table; stats collected 21 seconds ago)
│ table: ca@ca_pkey
│ spans: FULL SCAN
│
└── • group (hash)
│ nodes: n1
│ actual row count: 1,000
│ estimated max memory allocated: 680 KiB
│ estimated max sql temp disk usage: 0 B
│ sql cpu time: 450µs
│ estimated row count: 1,000
│ group by: a
│
└── • scan
nodes: n1
actual row count: 1,000
KV time: 677µs
KV contention time: 0µs
KV rows read: 1,000
KV bytes read: 33 KiB
KV gRPC calls: 1
estimated max memory allocated: 60 KiB
sql cpu time: 130µs
estimated row count: 1,000 (100% of the table; stats collected 21 seconds ago)
table: da@da_pkey
spans: FULL SCAN
(113 rows)
Time: 5ms total (execution 5ms / network 1ms)
```
This seems to happen regardless of whether `ca` and `da` have indexes on `a`.
Jira issue: CRDB-27333
Contributor guide
Assessment
This issue has not been assessed yet.