cockroachdb / cockroachdb/cockroach

opt: multi-column stats fail to correct scan underestimates for correlated columns with skewed joint frequencies

Open
#172,459 2 comments 0 reactions 0 assignees View on GitHub
A-sql-optimizer A-sql-table-stats branch-master C-bug O-support P-3 T-sql-queries
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.