#2005 [Proposal] Fix ORCA selectivity damping for predicates with outer references New discussion created by 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 > 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_L,F_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 se… apache/cloudberry