cockroachdb / cockroachdb/cockroach

opt: improve filter selectivity estimates

Open
#119,966 0 comments 0 reactions 0 assignees View on GitHub
C-enhancement T-sql-queries
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

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.