[Proposal] Fix ORCA selectivity damping for predicates with outer references

[Waloid24]

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 &gt; 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.

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

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

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&lt;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?

• Yes I am willing to submit a PR!

[Waloid24]

See MR #2006

[Waloid24]

See MR #2007