cockroachdb / cockroachdb/cockroach

sql/stats: forecasted histograms often have num_eq = 0

Open
#126,522 3 comments 0 reactions 0 assignees View on GitHub
A-sql-table-stats branch-master C-bug O-testcluster P-3 T-sql-queries
Dominant language
Go
Stars
32.5k
Forks
4.1k
PR merge metrics
PR metrics pending

Description

Forecasted histograms often have num_eq = 0 in histogram buckets. When the upper bounds of forecasted histograms correspond to real user-supplied values this can cause queries using those values to under-estimate row counts, leading to bad plans.

Here's an example:

```sql
CREATE TABLE a (a INT, INDEX (a)) WITH (sql_stats_automatic_collection_enabled = false);

-- Inject statistics that represent a containing 10 rows each of [0, 15], [0, 20], and [0, 25]
ALTER TABLE a INJECT STATISTICS '[
{
"avg_size": 2,
"columns": [
"a"
],
"created_at": "2024-07-01 00:00:00.000000",
"distinct_count": 15,
"histo_buckets": [
{
"distinct_range": 0,
"num_eq": 10,
"num_range": 0,
"upper_bound": "0"
},
{
"distinct_range": 2,
"num_eq": 10,
"num_range": 20,
"upper_bound": "3"
},
{
"distinct_range": 2,
"num_eq": 10,
"num_range": 20,
"upper_bound": "6"
},
{
"distinct_range": 2,
"num_eq": 10,
"num_range": 20,
"upper_bound": "9"
},
{
"distinct_range": 2,
"num_eq": 10,
"num_range": 20,
"upper_bound": "12"
},
{
"distinct_range": 2,
"num_eq": 10,
"num_range": 20,
"upper_bound": "15"
}
],
"histo_col_type": "INT8",
"histo_version": 3,
"null_count": 0,
"row_count": 150
},
{
"avg_size": 9,
"columns": [
"rowid"
],
"created_at": "2024-07-01 00:00:00.000000",
"distinct_count": 150,
"null_count": 0,
"row_count": 150
},
{
"avg_size": 2,
"columns": [
"a"
],
"created_at": "2024-07-02 00:00:00.000000",
"distinct_count": 20,
"histo_buckets": [
{
"distinct_range": 0,
"num_eq": 10,
"num_range": 0,
"upper_bound": "0"
},
{
"distinct_range": 3,
"num_eq": 10,
"num_range": 30,
"upper_bound": "4"
},
{
"distinct_range": 3,
"num_eq": 10,
"num_range": 30,
"upper_bound": "8"
},
{
"distinct_range": 3,
"num_eq": 10,
"num_range": 30,
"upper_bound": "12"
},
{
"distinct_range": 3,
"num_eq": 10,
"num_range": 30,
"upper_bound": "16"
},
{
"distinct_range": 3,
"num_eq": 10,
"num_range": 30,
"upper_bound": "20"
}
],
"histo_col_type": "INT8",
"histo_version": 3,
"null_count": 0,
"row_count": 200
},
{
"avg_size": 9,
"columns": [
"rowid"
],
"created_at": "2024-07-02 00:00:00.000000",
"distinct_count": 200,
"null_count": 0,
"row_count": 200
},
{
"avg_size": 2,
"columns": [
"a"
],
"created_at": "2024-07-03 00:00:00.000000",
"distinct_count": 25,
"histo_buckets": [
{
"distinct_range": 0,
"num_eq": 10,
"num_range": 0,
"upper_bound": "0"
},
{
"distinct_range": 4,
"num_eq": 10,
"num_range": 40,
"upper_bound": "5"
},
{
"distinct_range": 4,
"num_eq": 10,
"num_range": 40,
"upper_bound": "10"
},
{
"distinct_range": 4,
"num_eq": 10,
"num_range": 40,
"upper_bound": "15"
},
{
"distinct_range": 4,
"num_eq": 10,
"num_range": 40,
"upper_bound": "20"
},
{
"distinct_range": 4,
"num_eq": 10,
"num_range": 40,
"upper_bound": "25"
}
],
"histo_col_type": "INT8",
"histo_version": 3,
"null_count": 0,
"row_count": 250
},
{
"avg_size": 9,
"columns": [
"rowid"
],
"created_at": "2024-07-03 00:00:00.000000",
"distinct_count": 250,
"null_count": 0,
"row_count": 250
}
]';

SELECT jsonb_array_elements(stat->'histo_buckets')
FROM (
SELECT jsonb_array_elements(statistics) AS stat
FROM [SHOW STATISTICS USING JSON FOR TABLE a WITH FORECAST]
)
WHERE stat->>'name' = '__forecast__' AND stat->>'columns' = '["a"]';
```

This gives the following forecasted histogram, which has many buckets with num_eq = 0:

```
jsonb_array_elements
----------------------------------------------------------------------------------------------
{"distinct_range": 0, "num_eq": 14, "num_range": 0, "upper_bound": "0"}
{"distinct_range": 2.4643775411485005, "num_eq": 0, "num_range": 5, "upper_bound": "1"}
{"distinct_range": 2.1506730619211063, "num_eq": 14, "num_range": 37, "upper_bound": "6"}
{"distinct_range": 2.4643775411485005, "num_eq": 0, "num_range": 5, "upper_bound": "7"}
{"distinct_range": 1.613046554247106, "num_eq": 14, "num_range": 37, "upper_bound": "11"}
{"distinct_range": 2.4643775411485005, "num_eq": 0, "num_range": 5, "upper_bound": "12"}
{"distinct_range": 2.1506730619211063, "num_eq": 14, "num_range": 37, "upper_bound": "17"}
{"distinct_range": 2.4643775411484925, "num_eq": 0, "num_range": 5, "upper_bound": "18"}
{"distinct_range": 1.613046554247106, "num_eq": 14, "num_range": 37, "upper_bound": "22"}
{"distinct_range": 2.4643775411484765, "num_eq": 0, "num_range": 5, "upper_bound": "23"}
{"distinct_range": 2.1506730619211063, "num_eq": 0, "num_range": 37, "upper_bound": "28"}
(11 rows)

Time: 3ms total (execution 3ms / network 0ms)
```

A query using one of these upper_bound values will under-estimate the row count:

```
demo@127.0.0.1:26257/demoapp/defaultdb> EXPLAIN SELECT * FROM a WHERE a = 18;
info
--------------------------------------------------------------------------------------------------------------------------------
distribution: local
vectorized: true

• scan
estimated row count: 0 (<0.01% of the table; stats collected 0 seconds ago; using stats forecast for 2 days in the future)
table: a@a_a_idx
spans: [/18 - /18]
(7 rows)

Time: 10ms total (execution 9ms / network 0ms)

demo@127.0.0.1:26257/demoapp/defaultdb> SET optimizer_use_forecasts = off;
SET

Time: 0ms total (execution 0ms / network 0ms)

demo@127.0.0.1:26257/demoapp/defaultdb> EXPLAIN SELECT * FROM a WHERE a = 18;
info
--------------------------------------------------------------------------------
distribution: local
vectorized: true

• scan
estimated row count: 10 (3.8% of the table; stats collected 0 seconds ago)
table: a@a_a_idx
spans: [/18 - /18]
(7 rows)

Time: 3ms total (execution 2ms / network 1ms)
```

Jira issue: CRDB-39957

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.