cockroachdb / cockroachdb/cockroach
opt: multi-column stats fail to correct scan underestimates for correlated columns with skewed joint frequencies
- Dominant language
- Go
- Stars
- 32.5k
- Forks
- 4.1k
- PR merge metrics
- PR metrics pending
Description
When a query filters on several columns at once, the optimizer estimates the result size by taking each filter's fraction of the table separately and multiplying them together -- implicitly assuming the columns are unrelated. Real data often breaks that assumption: in the example below, a user's rows live entirely inside that user's own groups, so "rows in these 2 groups" and "rows belonging to alice" are the ***same*** rows. The correct combined selectivity is **P(A) × P(B | A)**, but the optimizer uses **P(A) × P(B)**; the estimate is off by exactly the lift P(B|A) / P(B), which real data can make arbitrarily large.
The optimizer's only defense today is multi-column statistics, but those record just the number of distinct column-value *combinations* (`selectivityFromMultiColDistinctCounts`) -- not how many rows each combination holds. They can signal "these columns are related", but not "alice's combinations hold 1,000 rows each while most others hold a handful". When the correlation lives in the row counts rather than the combination counts, the correction falls far short and the estimate stays near the independence product.
Example:
```sql
CREATE TABLE t (
id INT PRIMARY KEY,
grp STRING NOT NULL,
usr STRING,
INDEX grp_usr_idx (grp, usr)
);
-- 200k rows, 200 groups x 1000 rows. alice owns groups g000 and g001
-- entirely (2,000 rows). The other 198 groups have 10 distinct users
-- each (pool of 100), plus some NULLs.
INSERT INTO t
SELECT i,
'g' || lpad((i % 200)::STRING, 3, '0'),
CASE
WHEN i % 200 < 2 THEN 'alice'
WHEN (i / 200)::INT % 10 = 0 THEN NULL
ELSE 'u' || lpad((((i / 200)::INT % 10) * 10 + (i % 200) % 10)::STRING, 3, '0')
END
FROM generate_series(0, 199999) AS s(i);
ANALYZE t;
EXPLAIN ANALYZE SELECT * FROM t
WHERE grp IN ('g000','g001') AND usr = 'alice';
-- estimated row count: 176 actual: 2,000 (9.5x under)
-- Each filter alone is estimated exactly: P(grp IN ...) = 1% and
-- P(usr = 'alice') = 1%. But these groups are wholly alice's, so
-- P(usr = 'alice' | grp IN ...) = 100%: the correct estimate is
-- 1% x 100% of 200k = 2,000 rows. The optimizer computes
-- 1% x 1% = 20 rows instead, which the multi-column stats
-- correction lifts only to 176.
EXPLAIN ANALYZE SELECT * FROM t
WHERE grp IN ('g000','g001') AND (usr = 'alice' OR usr IS NULL);
-- estimated row count: 353 actual: 2,000 (4.8x under)
```
Related: #67573 (distinct-count guardrails; this is the residual), #49698 (multi-column histograms), #34422.
Revealed by the same customer escalation as #172206.
Epic: none
Jira issue: CRDB-65697
Contributor guide
Research direction
Start with the optimizer's multi-column statistics path, especially selectivityFromMultiColDistinctCounts, and review related issues #67573, #49698, and #34422 for context. Reproduce the two SQL examples after ANALYZE and investigate how estimates should account for skewed joint frequencies; done means the correlated queries no longer substantially underestimate their actual row counts.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go, sql
- Domain
- databases
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Needs clarification
- Newbie friendliness
- 35/100