cockroachdb / cockroachdb/cockroach

opt: catastrophic underestimate for predicates beyond histogram range

Open
#173,963 0 comments 0 reactions 1 assignee Claimed by @DrewKimball View on GitHub
A-sql-optimizer C-enhancement O-agent T-sql-queries
Dominant language
Go
Stars
32.5k
Forks
4.1k
PR merge metrics
PR metrics pending

Description

**Is your feature request related to a problem? Please describe.**

When a predicate filters on values that fall beyond the maximum (or minimum) value captured in a column's histogram, the optimizer estimates a row count approaching zero. Because table statistics are sampled and refreshed only periodically, this happens routinely on growing tables.

The most common case is a **timestamp column on an append-heavy table**. Statistics are collected periodically, so the histogram's newest bucket lags behind the latest inserts, and a query over a recent *bounded* window — e.g. `WHERE created_at >= '2026-08-24 10:00:00' AND created_at < '2026-08-24 11:00:00'` — falls entirely beyond the histogram and is estimated at ~0 rows. Both bounds are finite, so this is not an open-ended inequality and `optimizer_clamp_inequality_selectivity` does not apply. The ~0-row estimate is a catastrophic underestimate that steers the optimizer into plans that are disastrous when the true count is large: a full scan plus a large index join, a bad join order, or under-provisioned memory.

CockroachDB already has two mitigations, but neither covers this case:
- `optimizer_clamp_low_histogram_selectivity` assumes that **at least one distinct value** from the column passes the filter, flooring the estimate at roughly the number of rows per distinct value (row count / distinct count).
- `optimizer_clamp_inequality_selectivity` floors open-ended inequalities at a flat threshold — but only open-ended ones, so it does nothing for a bounded window.

Assuming one distinct value only helps when a distinct value covers many rows. For **high-cardinality columns** — timestamps most of all, since they are often effectively unique — one distinct value is only ~1 row, so `optimizer_clamp_low_histogram_selectivity` floors the estimate at ~1 row and remains a catastrophic underestimate. It is also width-blind: a bounded range spanning a large fraction of the value space is still floored at a single distinct value. The clamp is therefore ineffective precisely in the high-cardinality case that matters most.

**Describe the solution you'd like**

A density-based estimate derived from the histogram's *value space* rather than its bucket contents: an equality counts as one distinct value out of the histogram's distinct count, and — crucially — a bounded range contributes its width as a fraction of the histogram's populated width. For the timestamp case, this scales the estimate with the width of the out-of-range window instead of collapsing it to a single distinct value, producing a realistic row count. Predicates with no measurable width (an unbounded range, or a range over a type such as STRING) fall back to the existing clamp.

**Describe alternatives you've considered**

- The existing clamps — the low-selectivity clamp assumes a single distinct value and is width-blind, so it is ineffective for high-cardinality columns; the inequality clamp applies only to open-ended predicates, not bounded ranges.
- More frequent statistics collection — reduces staleness but never eliminates the gap for continuously growing tables, and does nothing for sampling gaps.

**Additional context**

Affects histogram-based selectivity estimation in `pkg/sql/opt/props/histogram.go` and the clamp logic in `pkg/sql/opt/memo/statistics_builder.go`.

Jira issue: CRDB-67262

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.