GitHub user Waloid24 edited a discussion: [Proposal] Fix ORCA selectivity
damping for predicates with outer references
### Proposers
Andrei
### Proposal Status
Under Discussion
### Abstract
Cloudberry's `SelectivityOfPredicate()` can estimate that adding an
outer-reference predicate to a conjunction increases the fraction of rows
passing the filter. This proposal applies damping only when combining outer
predicates’ conditional selectivity estimates, then multiplies the result by
the local selectivity. It reuses the existing conjunction estimator and honors
`optimizer_damping_factor_filter` instead of a hardcoded default.
### Motivation
## Motivation
ORCA's `CFilterStatsProcessor::SelectivityOfPredicate()` estimates predicate
selectivity when evaluating candidate index conditions. Its current damping
formula can increase the estimated fraction of qualifying rows when another
condition is added through `AND`. This contradicts the fact that a conjunction
cannot admit more rows than any of its constituent conditions.
### Current mathematical model
Let the predicate be:
$$
L \land E_1 \land \cdots \land E_k,
$$
where $L$ combines the local conditions and each $E_i$ is a conjunct containing
outer references.
The function first estimates statistics after applying $L$. Its initial
selectivity is:
$$
s_L = \frac{N_L}{N},
$$
where $N$ is the estimated base-table cardinality and $N_L$ is the estimated
cardinality after local filtering.
For each outer predicate, it assigns a selectivity multiplier $q_i$:
- For a recognized equality between a local column and an outer expression,
$q_i=1/D_i$, provided the estimated NDV $D_i\ge1$.
- Otherwise, it uses the default selectivity $0.4$.
- Constant `TRUE` expressions are ignored.
The NDVs come from the statistics **after local filtering**. Accordingly, these
multipliers can be interpreted as heuristic estimates of the conditional
probabilities $P(E_i\mid L)$.
The function first multiplies the estimates:
$$
r_{\mathrm{raw}} = s_L\prod_{i=1}^{k}q_i.
$$
It then counts the outer predicates, adding one for the complete local
condition if $s_L<1$:
$$
m = k + \mathbf{1}_{s_L<1}.
$$
If $m \le 1$, no final damping correction is applied:
$$
S_{\mathrm{current}} = r_{\mathrm{raw}}.
$$
If $m > 1$, the function divides the product by the damping correction and caps
the result at one:
$$
S_{\mathrm{current}} = \min\left(1,\frac{r_{\mathrm{raw}}}{0.75^m}\right).
$$
The coefficient in this final correction is always `0.75`, taken from
`PstatsconfDefault()`, rather than the configured
`optimizer_damping_factor_filter`.
### Required properties
Let $p_i=P(A_i)$ be the selectivity of predicate $A_i$, for $n$ predicates
evaluated over the same population. Their individual selectivities do not
determine their conjunction: the result also depends on how the qualifying rows
overlap.
Let $F_d(p_1,\ldots,p_n)$ estimate the conjunction at damping coefficient
$d\in[0,1]$. Damping should interpolate between independence ($d=1$) and
maximum overlap ($d=0$):
$$
F_1(p_1,\ldots,p_n)=\prod_i p_i,
\qquad
F_0(p_1,\ldots,p_n)=\min_i p_i.
$$
Maximum overlap means that every row satisfying the most restrictive predicate
also satisfies the others. This model covers dependence that increases overlap
relative to independence, not every possible dependence.
The estimate should satisfy:
$$
\prod_i p_i\le F_d(p_1,\ldots,p_n)\le\min_i p_i.
$$
The upper bound is required by conjunction semantics; the product lower bound
belongs to the chosen damping model.
Adding a predicate with selectivity $p_{n+1}$ must not increase the estimate,
with the existing inputs and coefficient unchanged:
$$
F_d(p_1,\ldots,p_n,p_{n+1})\le F_d(p_1,\ldots,p_n).
$$
A neutral predicate with selectivity one must leave the result unchanged, as
must reordering the inputs. For example, selectivities $0.1$ and $0.2$ allow an
estimate between $0.02$ and $0.1$.
### Applying this to outer predicates
The outer estimates $q_i$ use statistics after local filtering, so we interpret
them as approximations to $P(E_i\mid L)$. The probability decomposition is:
$$
P(L\cap E_1\cap\cdots\cap E_k)
=P(L)P(E_1\cap\cdots\cap E_k\mid L).
$$
Therefore, let the proposed overall estimate $S_d$ be:
$$
S_d=s_LF_d(q_1,\ldots,q_k).
$$
Damping combines the outer estimates within the locally filtered population.
The local selectivity remains a separate multiplier. For $k\ge1$:
$$
s_L\prod_i q_i\le S_d\le s_L\min_i q_i\le s_L.
$$
Without outer predicates, return $s_L$. With one outer predicate, return
$s_Lq_1$ for every coefficient.
### Theoretical counterexample
Suppose local filtering retains an estimated 1,000 of 10,000 rows, so
$s_L=0.1$. Add an outer equality with $D_1=1$, giving $q_1=1$. This multiplier
excludes no locally qualifying rows, so the combined estimate should remain
$0.1$.
Instead, the current implementation counts two factors and returns:
$$
S_{\mathrm{current}}=\frac{0.1\times1}{0.75^2}\approx0.177778.
$$
Adding a conjunct increases the estimated qualifying population from 1,000 to
approximately 1,778 rows. Capping the result at one does not prevent this
violation.
Even a cap at $s_L$ would be insufficient: with $s_L=0.1$ and $q_1=0.2$, the
current formula returns approximately $0.035556$, exceeding the
conditional-model result $s_Lq_1=0.02$.
The change would preserve these bounds and honor the configured damping
coefficient in an estimate used for index selection.
### SQL demonstrations
Create a 10,000-row inner table and a single-row outer table. The bitmap
indexes and disabled hash joins encourage ORCA to consider index conditions
containing outer references.
The estimates below refer to the value returned by
`CFilterStatsProcessor::SelectivityOfPredicate()`, which can be inspected in a
debugger. They are not necessarily the row estimates shown by `EXPLAIN`.
~~~~sql
SET optimizer = off;
CREATE TABLE damping_inner (
id integer,
a integer,
b integer,
c integer,
z integer
) USING heap DISTRIBUTED RANDOMLY;
INSERT INTO damping_inner
SELECT
n,
n % 10,
(n / 10) % 5,
(n / 50) % 4,
0
FROM generate_series(0, 9999) AS g(n);
CREATE TABLE damping_outer (
b integer,
c integer,
z integer
) USING heap DISTRIBUTED REPLICATED;
INSERT INTO damping_outer VALUES (0, 0, 0);
CREATE INDEX damping_inner_abcz
ON damping_inner USING bitmap (a, b, c, z);
CREATE INDEX damping_inner_bcza
ON damping_inner USING bitmap (b, c, z, a);
ANALYZE damping_inner;
ANALYZE damping_outer;
SET optimizer = on;
SET optimizer_enable_hashjoin = off;
SET optimizer_damping_factor_filter = 0.75;
~~~~
The generated data has the following properties:
| Property | Value |
|---|---:|
| Inner rows | 10,000 |
| NDV of `a` | 10 |
| NDV of `b` | 5 |
| NDV of `c` | 4 |
| NDV of `z` | 1 |
#### 1. Local predicate only
~~~~sql
EXPLAIN (ANALYZE, TIMING OFF)
SELECT i.*
FROM damping_outer AS o
CROSS JOIN damping_inner AS i
WHERE i.a = 1;
~~~~
The query returns exactly 1,000 rows, corresponding to a selectivity of $0.1$.
In the debugger, the function returned `0.099999003112316131`; the small
difference comes from ORCA's normalization of floating-point frequencies.
This is the baseline. Damping does not affect this single equality. The
calculations below use the idealized value $s_L=0.1$ for clarity.
#### 2. Add a neutral outer predicate
~~~~sql
EXPLAIN (ANALYZE, TIMING OFF)
SELECT i.*
FROM damping_outer AS o
CROSS JOIN damping_inner AS i
WHERE i.a = 1
AND i.z = o.z;
~~~~
Both `i.z` and the single outer row's `o.z` are zero, so the additional
condition excludes no rows:
$$
s_L=0.1,\qquad q_z=1.
$$
The actual output remains 1,000 rows.
| Implementation | Calculation | Approximate selectivity |
|---|---|---:|
| Original | $s_L/0.75^2$ | 0.177778 |
| Expected | $s_L\times1$ | 0.1 |
The original formula increases the estimate when a conjunct is added. Instead,
the corrected formula should preserve the baseline estimate, as required.
### Implementation
## Implementation
We propose keeping the local selectivity separate and applying the existing
conjunction estimator only to predicates containing outer references.
### Combine conditional outer estimates
Let $s_L$ be the estimated local selectivity and $q_i$ the estimated
selectivity of outer predicate $E_i$ within the locally filtered population.
For $k$ outer predicates and damping coefficient $d$, the overall estimate is:
$$
S_d=s_L F_d(q_1,\ldots,q_k),
$$
where $F_d$ combines the outer estimates. The local filter is not included in
this damping step: it has already been estimated, and its output defines the
population to which the outer estimates apply.
The implementation preserves the existing individual estimates: $q_i=1/D_i$ for
a recognized outer equality with NDV $D_i\ge1$, and the default selectivity
otherwise. Constant `TRUE` expressions are ignored.
Instead of multiplying these estimates immediately, the function collects their
scale factors $SF_i=1/q_i$ and passes them to
`CScaleFactorUtils::CalcScaleFactorCumulativeConj()`.
### Reuse the existing conjunction formula
The helper sorts the scale factors in descending order. Equivalently, the outer
selectivities are ordered as:
$$
q_{(1)}\le q_{(2)}\le\cdots\le q_{(k)},
$$
where $q_{(j)}$ is the selectivity at position $j$ after sorting. For $0<d\le1$
and $k\ge1$, its calculation corresponds to:
$$
F_d(q_1,\ldots,q_k)
=q_{(1)}\prod_{j=2}^{k}\min\left(1,\frac{q_{(j)}}{d^j}\right).
$$
The smallest selectivity is preserved. Each remaining contribution is at most
one, giving:
$$
s_L\prod_i q_i\le S_d\le s_L\min_i q_i\le s_L.
$$
At $d=1$, the result is the ordinary product. With one outer predicate, it is
$s_Lq_1$. With no outer predicates, the helper returns scale factor one and the
result remains $s_L$.
`SelectivityOfPredicate()` returns the local selectivity divided by the
combined outer scale factor. This replaces the old division of the complete
product by $0.75^m$ and removes the counting of the local condition as an
additional damping factor.
### Use the configured coefficient
The helper will receive the active statistics configuration from
`GetStatsConf()`. The final aggregation will therefore honor
`optimizer_damping_factor_filter` instead of constructing a default
configuration with coefficient `0.75`. This proposal reuses the shared helper
without modifying its implementation.
### Separate follow-up for zero damping
Explicit handling of `optimizer_damping_factor_filter = 0` will be covered by a
separate proposal and PR. That change will allow zero in the filter
configuration assertion and handle it in the shared conjunction helper as
maximum overlap:
$$
F_0(q_1,\ldots,q_k)=\min_i q_i,
\qquad
S_0=s_L\min_i q_i
\quad (k\ge1).
$$
Changes to the assertion and explicit zero-damping handling are outside the
scope of this proposal.
### Rollout/Adoption Plan
_No response_
### Are you willing to submit a PR?
- [X] Yes I am willing to submit a PR!
GitHub link: https://github.com/apache/cloudberry/discussions/2005
----
This is an automatically sent email for [email protected].
To unsubscribe, please send an email to: [email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
