cockroachdb / cockroachdb/cockroach
sql: find and include all values of enum-like columns in SQL stats histograms
- Dominant language
- Go
- Stars
- 32.5k
- Forks
- 4.1k
- PR merge metrics
- PR metrics pending
Description
When SQL stats collection samples rows in large tables containing low-cardinality, enum-like columns, it is possible that only heavy hitters are sampled and included in the resulting histograms. The missing buckets in the resulting histograms can cause the optimizer to pick bad query plans.
I've thought of three potential solutions to the problem, with a preference towards (2) due to the downsides of (1):
1. Do not pick the [sample rank](https://github.com/cockroachdb/cockroach/blob/64778f2f1c46c0a405e65dd4750da0145e25811b/pkg/sql/rowexec/sampler.go#L442) completely randomly. Give a special value for "interesting" rows, e.g., those with a never-before-seen value for a column. The downside to this is that it could sway the distribution of the histogram significantly.
2. Keep a separate sample of "interesting" rows. If you wanted to ensure that 200 unique values were found for each column to fill in the 200-bucket histograms, then you'd need to keep at most `200 * num_indexed_columns` interesting rows. We might be able to use the HLL sketches to determine if a row contains a never-before-seen value, in which case it should either be sample or added to the "interesting rows" list (**NOTE**: `(*hyperloglog.Sketch).Estimate` is not a constant-time operation, so calling it after each `(*hyperloglog.Sketch).Insert` may add significant overhead).
3. Assuming that there is an index where the leading column is an enum-like column, we could scan the gaps in sampled values after the first round of sampling. This would add a lot more moving parts, so it seems more complex than the other proposed solutions.
Jira issue: CRDB-52404
Contributor guide
Assessment
This issue has not been assessed yet.