cockroachdb / cockroachdb/cockroach
opt: improve filter selectivity estimates
- Dominant language
- Go
- Stars
- 32.5k
- Forks
- 4.1k
- PR merge metrics
- PR metrics pending
Description
When a filter expression can easily filter a column's histogram values we can, in general, produce good quality selectivity estimates for the filter. Expressions like `a = 10` or `a > 10 and a < 1000` are examples of expressions that can trivially filter a histogram.
However, there are some expressions where we cannot easily filter a column's histogram to produce a good estimate, like `a % 3 = 0` or `s % 'foobar'`. In these cases, we default to a crude default selectivity estimate of 1/3. In many cases, this is a wild over-estimation, causing poor query plans. As one example of problems these over-estimations can cause, limit hints become under-estimated from a selectivity over-estimation (they are inversely proportional), which can be one cause of the problems described in #84461.
I recently experimented with Postgres and explored its source code looking for ways to improve our selectivity estimates for these trickier filters. My notes are [here](https://gist.github.com/mgartner/5cfc2b2b4b6e388092f0c5fcedd0a0db). Below are ideas for improvements to CRDB inspired by the interesting things I came across.
### 1. Decrease the default selectivity for equality expressions
We should consider lowering the default selectivity for equality expressions (any expression with `=` at the root). Our current default selectivity of 1/3 is _very_ high in most cases. Postgres uses a default selectivity of 0.005 for equality expressions:
https://github.com/postgres/postgres/blob/cca97ce6a6653df7f4ec71ecd54944cc9a6c4c16/src/backend/utils/adt/selfuncs.c#L261-L267
https://github.com/postgres/postgres/blob/cca97ce6a6653df7f4ec71ecd54944cc9a6c4c16/src/include/utils/selfuncs.h#L34
### 2. Use histogram boundaries as a sample
Postgres consults the values of histogram boundaries and the MCV (most common values) list to improve selectivity estimates. For expressions in the form `variable constant`, it evaluates the expression with each of the values in the histograms and MCV list replacing `variable`. The fraction of values for which the expression evaluates to true becomes the selectivity. Assuming these values are a representative sample, this should yield a quality selectivity estimate.
https://github.com/postgres/postgres/blob/cca97ce6a6653df7f4ec71ecd54944cc9a6c4c16/src/backend/utils/adt/selfuncs.c#L902-L908
If the selectivity from this becomes too low, which may be common given that the list only contains ~100 or so values, the selectivity is clamped to 0.0001:
https://github.com/postgres/postgres/blob/cca97ce6a6653df7f4ec71ecd54944cc9a6c4c16/src/backend/utils/adt/selfuncs.c#L987-L989
We don't have an MCV list, but we can use the upper-bounds of histogram buckets to do something similar.
### 3. Set different default selectivities for different operators
This is a generalization of (1).
Each operator in Postgres can specify a selectivity calculation function. For example, the `%` similarity operator uses `matchingsel`:
```sql
SELECT oprname, oprrest FROM pg_operator WHERE oprcode = 'similarity_op'::REGPROC;
-- oprname | oprrest
-- ---------+-------------
-- % | matchingsel
```
https://github.com/postgres/postgres/blob/cca97ce6a6653df7f4ec71ecd54944cc9a6c4c16/src/backend/utils/adt/selfuncs.c#L3217-L3227
https://github.com/postgres/postgres/blob/cca97ce6a6653df7f4ec71ecd54944cc9a6c4c16/src/include/utils/selfuncs.h#L49
It falls-back to these defaults when it can't perform any better estimate. For example, `matchingsel`, with a default selectivity of `1/100` is used for the similarity operator in expressions of the form `var1 % var2`.
Specifying default selectivities on a per-operator basis can help us avoid the 1/3 over-estimation.
Jira issue: CRDB-36417
Contributor guide
Assessment
This issue has not been assessed yet.