You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cloudberry.apache.org by "Waloid24 (via GitHub)" <gi...@apache.org> on 2026/09/15 16:58:29 UTC
[PR] [Bug] Fix ORCA selectivity damping for outer references [cloudberry]
Waloid24 opened a new pull request, #2006:
URL: https://github.com/apache/cloudberry/pull/2006
Addresses the proposal #2005
### What does this PR do?
SelectivityOfPredicate() applies damping to the product of local and outer predicate estimates, which can increase the result above the local selectivity. This violates the bounds of a conjunction when .
Outer predicate estimates use statistics after local filtering. Treat them as conditional selectivities and combine them using the existing conjunction estimator, then multiply by the local estimate. This preserves the local estimate as an upper bound and leaves it unchanged when an outer predicate has selectivity one.
Use the active statistics configuration for this aggregation so that optimizer_damping_factor_filter controls the correction, rather than the hardcoded default. These estimates participate in index selection, so the change can affect planning decisions.
### Type of Change
- [ ] Bug fix (non-breaking change)
### Test Plan
Manually (with `lldb`) compare selectivity estimates produced by the old and new versions of the `CFilterStatsProcessor::SelectivityOfPredicate` function.
Create tables:
~~~~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;
~~~~
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. Only a local predicate
~~~~sql
EXPLAIN (ANALYZE, TIMING OFF)
SELECT i.*
FROM damping_outer AS o
CROSS JOIN damping_inner AS i
WHERE i.a = 1;
~~~~
As expected (and the original version does), 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.
2. Add an outer predicate that excludes no rows
~~~~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.
New version leaves the estimated selectivity as `0.099999003112316131` (~`0.1`). While the original version returns local_selectivity/0.75^2 = 0.177778 > 0.1*1 = 0.1
3. One local predicate and two outer predicates
~~~~sql
EXPLAIN (ANALYZE, TIMING OFF)
SELECT i.*
FROM damping_outer AS o
CROSS JOIN damping_inner AS i
WHERE i.a = 1
AND i.b = o.b
AND i.c = o.c;
~~~~
Again, local selectivity is `0.099999003112316131`. Among `1,000` rows satisfying `a = 1`, exactly `200` have `b = 0`. So `q_b = 0.2`. Similarly, `q_c = 0.25`. Actual output is `25` rows. At `d=0.75`, the patched calculation gives selectivity 0.1 * 0.2 * min(1,0.25/0.75^2) = 0.008888800276650323` (`0.008889` from theoretical calculation).
The original implementation gives `0.011851733702200431` (from theory it can't be more than `0.1 * 0.2 = 0.02` and less than `0.005`).
- With `SET optimizer_damping_factor_filter = 1` (predicates independence):
The old version does not react to changes in the `optimizer_damping_factor_filter` parameter because it always uses the default value. It returns `0.011851733702200431`. The new version returns `0.0049999501556158062`, which is consistent with the theoretical value of `0.005`.
- With `SET optimizer_damping_factor_filter = 0`:
Fallback to PostgreSQL optimizer.
### Impact
**Performance:**
Yes, potentially. The planner can choose a plan which better aligns with the actual data distribution in the table.
**User-facing changes:**
No.
**Dependencies:**
No.
### Checklist
- [ ] Followed [contribution guide](https://cloudberry.apache.org/contribute/code)
- [ ] Added/updated documentation
- [ ] Reviewed code for security implications
- [ ] This PR contains AI-assisted code generation
- [ ] Requested review from [cloudberry committers](https://github.com/orgs/apache/teams/cloudberry-committers)
---
<!-- Join our community:
- Mailing list: [dev@cloudberry.apache.org](https://lists.apache.org/list.html?dev@cloudberry.apache.org) (subscribe: dev-subscribe@cloudberry.apache.org)
- Discussions: https://github.com/apache/cloudberry/discussions -->
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@cloudberry.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@cloudberry.apache.org
For additional commands, e-mail: commits-help@cloudberry.apache.org
Re: [PR] [Bug] Fix ORCA selectivity damping for outer references [cloudberry]
Posted by "yjhjstz (via GitHub)" <gi...@apache.org>.
yjhjstz commented on code in PR #2006:
URL: https://github.com/apache/cloudberry/pull/2006#discussion_r4032367390
##########
src/backend/gporca/libnaucrates/src/statistics/CFilterStatsProcessor.cpp:
##########
@@ -144,64 +150,30 @@ CFilterStatsProcessor::SelectivityOfPredicate(CMemoryPool *mp,
GPOS_ASSERT(nullptr != local_col_ref);
CDouble ndv = result_stats->GetNDVs(local_col_ref);
- if (ndv < 1.0)
- {
- // An NDV of less than 1 means that we have no stats on this column
- result = result * CHistogram::DefaultSelectivity;
- }
- else
+ // an NDV below 1 means that we have no stats on this column
+ if (ndv >= 1.0)
{
- result = result * (1 / ndv);
+ scale_factor = ndv;
}
}
- else
- {
- // a comparison col op <outer ref> other than an equals
- result = result * CHistogram::DefaultSelectivity;
- }
- num_outer_ref_preds++;
- }
- else
- {
- // if it is a true filter, then we had no expressions with outer refs
- if (!CUtils::FScalarConstTrue(pexpr))
- {
- // some other expression, not of the form col op <outer ref>,
- // e.g. an OR expression
- result = result * CHistogram::DefaultSelectivity;
- num_outer_ref_preds++;
- }
}
+ outer_scale_factors->Append(GPOS_NEW(mp) CDouble(scale_factor));
}
expr_with_outer_refs->Release();
outer_ref_exprs->Release();
}
- // apply damping factor to the outer ref predicates whose selectivities we multiplied above
- if (have_local_preds)
- {
- // add one for the combined non-outer refs which were dampened internally,
- // but not in combination with the preds on outer refs
- num_outer_ref_preds++;
- }
- if (1 < num_outer_ref_preds)
- {
- CStatisticsConfig *stats_config =
- CStatisticsConfig::PstatsconfDefault(mp);
-
- result =
- std::min(result.Get() / CScaleFactorUtils::DampedFilterScaleFactor(
- stats_config, num_outer_ref_preds)
- .Get(),
- 1.0);
-
- stats_config->Release();
- }
+ const CDouble outer_scale_factor =
+ CScaleFactorUtils::CalcScaleFactorCumulativeConj(stats_config,
Review Comment:
Reusing `CalcScaleFactorCumulativeConj` here changes the damping shape for the **outer-only** case (no local predicate), and for 3+ outer refs it is more aggressive than the code it replaces:
- old: `prod(1/ndv_i) / 0.75^n` (one division for the whole group; `have_local_preds` is false so no +1)
- new: factor k (sorted desc) is divided by `0.75^k` for k >= 1, i.e. `0.75^(1+2+...+(n-1))`
n=2: both x1.78. n=3: old x2.37, new x5.62. n=4: old x3.16, new x17.8.
Repro on the patched build (AO table, `btree (x, y, z)`, NDV 3 each, 10k rows, replicated 1-row outer):
```sql
CREATE TABLE ao3 (id int, x int, y int, z int, w int) WITH (appendonly=true) DISTRIBUTED RANDOMLY;
INSERT INTO ao3 SELECT n, n % 3, (n/3) % 3, (n/9) % 3, n % 7 FROM generate_series(0, 9999) g(n);
CREATE INDEX ao3_xyz ON ao3 USING btree (x, y, z);
CREATE TABLE out3 (x int, y int, z int) DISTRIBUTED REPLICATED;
INSERT INTO out3 VALUES (0,0,0);
ANALYZE ao3; ANALYZE out3;
SET optimizer_enable_hashjoin = off;
EXPLAIN SELECT i.* FROM out3 o CROSS JOIN ao3 i WHERE i.x = o.x AND i.y = o.y AND i.z = o.z;
```
True selectivity is 371/10000 = 0.037. gdb at the return: old `0.0878` (below the 0.10 AO-btree gate at `CXformUtils.cpp` `AO_TABLE_BTREE_INDEX_SELECTIVITY_THRESHOLD`) -> `Bitmap Index Scan on ao3_xyz`; new `local=1 outer_sf=6.407 result=0.156` -> the btree is rejected and the plan becomes `Seq Scan on ao3` + `Join Filter: ((i.x = o.x) AND (i.y = o.y) AND (i.z = o.z))`. So for this shape the PR both worsens the estimate and loses the index.
##########
src/backend/gporca/libnaucrates/src/statistics/CFilterStatsProcessor.cpp:
##########
@@ -132,7 +132,13 @@ CFilterStatsProcessor::SelectivityOfPredicate(CMemoryPool *mp,
for (ULONG ul = 0; ul < size; ul++)
{
CExpression *pexpr = (*outer_ref_exprs)[ul];
+ if (CUtils::FScalarConstTrue(pexpr))
+ {
+ continue;
+ }
+
CColRef *local_col_ref = nullptr;
+ CDouble scale_factor = 1 / CHistogram::DefaultSelectivity;
Review Comment:
Minor, and pre-existing, but since this block is being rewritten with `ParseCmpType()` already available: these outer-ref conjuncts are join predicates from a statistics standpoint (see the comment above `DeriveStatsWithOuterRefs` in `CJoinStatsProcessor.cpp`), and the real join pipeline scores them differently:
- `<, <=, >, >=` -> `CScaleFactorUtils::DefaultInequalityJoinPredScaleFactor` (3.0) in `CHistogram.cpp`
- unsupported / complex (e.g. an OR of outer refs) -> `CScaleFactorUtils::DefaultJoinPredScaleFactor` (100) in `CJoinStatsProcessor.cpp`
Here both fall into `1 / CHistogram::DefaultSelectivity` (2.5), so the same predicate is scored 2.5 for index ranking and 3.0 (or 100) for cardinality. Using the named join constants would align the two without changing the structure; `1 / CHistogram::DefaultSelectivity` is also already spelled out verbatim in three other places in stats code, so a named constant would help either way.
##########
src/backend/gporca/libnaucrates/src/statistics/CFilterStatsProcessor.cpp:
##########
@@ -144,64 +150,30 @@ CFilterStatsProcessor::SelectivityOfPredicate(CMemoryPool *mp,
GPOS_ASSERT(nullptr != local_col_ref);
CDouble ndv = result_stats->GetNDVs(local_col_ref);
- if (ndv < 1.0)
- {
- // An NDV of less than 1 means that we have no stats on this column
- result = result * CHistogram::DefaultSelectivity;
- }
- else
+ // an NDV below 1 means that we have no stats on this column
+ if (ndv >= 1.0)
{
- result = result * (1 / ndv);
+ scale_factor = ndv;
}
}
- else
- {
- // a comparison col op <outer ref> other than an equals
- result = result * CHistogram::DefaultSelectivity;
- }
- num_outer_ref_preds++;
- }
- else
- {
- // if it is a true filter, then we had no expressions with outer refs
- if (!CUtils::FScalarConstTrue(pexpr))
- {
- // some other expression, not of the form col op <outer ref>,
- // e.g. an OR expression
- result = result * CHistogram::DefaultSelectivity;
- num_outer_ref_preds++;
- }
}
+ outer_scale_factors->Append(GPOS_NEW(mp) CDouble(scale_factor));
}
expr_with_outer_refs->Release();
outer_ref_exprs->Release();
}
- // apply damping factor to the outer ref predicates whose selectivities we multiplied above
- if (have_local_preds)
- {
- // add one for the combined non-outer refs which were dampened internally,
- // but not in combination with the preds on outer refs
- num_outer_ref_preds++;
- }
- if (1 < num_outer_ref_preds)
- {
- CStatisticsConfig *stats_config =
- CStatisticsConfig::PstatsconfDefault(mp);
-
- result =
- std::min(result.Get() / CScaleFactorUtils::DampedFilterScaleFactor(
- stats_config, num_outer_ref_preds)
- .Get(),
- 1.0);
-
- stats_config->Release();
- }
+ const CDouble outer_scale_factor =
+ CScaleFactorUtils::CalcScaleFactorCumulativeConj(stats_config,
+ outer_scale_factors);
+ outer_scale_factors->Release();
result_stats->Release();
local_expr->Release();
- return result;
+ // Outer selectivities are conditional on the local filter. Damping only
+ // their conjunction preserves the local estimate as an upper bound.
+ return local_selectivity / outer_scale_factor;
Review Comment:
This treats the local group and the outer group as independent (no damping between them), whereas the old code counted the local group as one more damped predicate. Two consequences I measured:
- A single outer equality with a local predicate gets **no damping at all**: `a=1 AND b=o.b` -> old `0.0356`, new `0.0200` (= 0.1 * 1/5 exactly).
- ORCA's local path (`MakeHistHashMapConjFilter` -> `CalcScaleFactorCumulativeConj`) *does* damp two local equalities. So with identical NDVs (say 100 each), `a=5 AND b=6` scores `1/(100 * max(1, 100*0.75^2)) = 1.78e-4`, while `a=5 AND c=<outer>` scores `0.01/100 = 1.0e-4`. The outer-ref constant is ranked as strictly more selective than a literal purely because of its syntactic form, which biases `PexprBitmapSelectBestIndex` toward indexes covering outer-ref columns.
The stated invariant (`result <= local_selectivity`) does not require dropping cross-group damping: if you append `1 / local_selectivity` to `outer_scale_factors` and return `1 / CalcScaleFactorCumulativeConj(...)`, the product is still >= its largest factor, so the result stays <= min(local, each outer) while local and outer predicates are damped together, consistent with how purely local conjunctions are handled.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@cloudberry.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@cloudberry.apache.org
For additional commands, e-mail: commits-help@cloudberry.apache.org
Re: [PR] [Bug] Fix ORCA selectivity damping for outer references [cloudberry]
Posted by "Waloid24 (via GitHub)" <gi...@apache.org>.
Waloid24 commented on code in PR #2006:
URL: https://github.com/apache/cloudberry/pull/2006#discussion_r4048158083
##########
src/backend/gporca/libnaucrates/src/statistics/CFilterStatsProcessor.cpp:
##########
@@ -144,64 +150,30 @@ CFilterStatsProcessor::SelectivityOfPredicate(CMemoryPool *mp,
GPOS_ASSERT(nullptr != local_col_ref);
CDouble ndv = result_stats->GetNDVs(local_col_ref);
- if (ndv < 1.0)
- {
- // An NDV of less than 1 means that we have no stats on this column
- result = result * CHistogram::DefaultSelectivity;
- }
- else
+ // an NDV below 1 means that we have no stats on this column
+ if (ndv >= 1.0)
{
- result = result * (1 / ndv);
+ scale_factor = ndv;
}
}
Review Comment:
> Minor, and pre-existing, but since this block is being rewritten with `ParseCmpType()`...
So you suggest to add here a block:
~~~~c
else
{
scale_factor =
CScaleFactorUtils::DefaultInequalityJoinPredScaleFactor;
}
~~~~
?
##########
src/backend/gporca/libnaucrates/src/statistics/CFilterStatsProcessor.cpp:
##########
Review Comment:
I noticed now here we also should not sort `scale_factors` array because we do the same inside `CalcScaleFactorCumulativeConj`
##########
src/backend/gporca/libnaucrates/src/statistics/CFilterStatsProcessor.cpp:
##########
@@ -144,64 +150,30 @@ CFilterStatsProcessor::SelectivityOfPredicate(CMemoryPool *mp,
GPOS_ASSERT(nullptr != local_col_ref);
CDouble ndv = result_stats->GetNDVs(local_col_ref);
- if (ndv < 1.0)
- {
- // An NDV of less than 1 means that we have no stats on this column
- result = result * CHistogram::DefaultSelectivity;
- }
- else
+ // an NDV below 1 means that we have no stats on this column
+ if (ndv >= 1.0)
{
- result = result * (1 / ndv);
+ scale_factor = ndv;
}
}
- else
- {
- // a comparison col op <outer ref> other than an equals
- result = result * CHistogram::DefaultSelectivity;
- }
- num_outer_ref_preds++;
- }
- else
- {
- // if it is a true filter, then we had no expressions with outer refs
- if (!CUtils::FScalarConstTrue(pexpr))
- {
- // some other expression, not of the form col op <outer ref>,
- // e.g. an OR expression
- result = result * CHistogram::DefaultSelectivity;
- num_outer_ref_preds++;
- }
}
Review Comment:
> Minor, and pre-existing, but since this block is being rewritten with `ParseCmpType()`...
And here you suggest to add a block:
~~~~c
else
{
// if it is a true filter, then we had no expressions with outer refs
if (!CUtils::FScalarConstTrue(pexpr))
{
// some other expression, not of the form col op <outer ref>,
// e.g. an OR expression
scale_factor = CScaleFactorUtils::DefaultJoinPredScaleFactor;
}
}
~~~~
?
Could it be too severe reduction in selectivity?
##########
src/backend/gporca/libnaucrates/src/statistics/CFilterStatsProcessor.cpp:
##########
@@ -144,64 +150,30 @@ CFilterStatsProcessor::SelectivityOfPredicate(CMemoryPool *mp,
GPOS_ASSERT(nullptr != local_col_ref);
CDouble ndv = result_stats->GetNDVs(local_col_ref);
- if (ndv < 1.0)
- {
- // An NDV of less than 1 means that we have no stats on this column
- result = result * CHistogram::DefaultSelectivity;
- }
- else
+ // an NDV below 1 means that we have no stats on this column
+ if (ndv >= 1.0)
{
- result = result * (1 / ndv);
+ scale_factor = ndv;
}
}
- else
- {
- // a comparison col op <outer ref> other than an equals
- result = result * CHistogram::DefaultSelectivity;
- }
- num_outer_ref_preds++;
- }
- else
- {
- // if it is a true filter, then we had no expressions with outer refs
- if (!CUtils::FScalarConstTrue(pexpr))
- {
- // some other expression, not of the form col op <outer ref>,
- // e.g. an OR expression
- result = result * CHistogram::DefaultSelectivity;
- num_outer_ref_preds++;
- }
}
+ outer_scale_factors->Append(GPOS_NEW(mp) CDouble(scale_factor));
}
expr_with_outer_refs->Release();
outer_ref_exprs->Release();
}
- // apply damping factor to the outer ref predicates whose selectivities we multiplied above
- if (have_local_preds)
- {
- // add one for the combined non-outer refs which were dampened internally,
- // but not in combination with the preds on outer refs
- num_outer_ref_preds++;
- }
- if (1 < num_outer_ref_preds)
- {
- CStatisticsConfig *stats_config =
- CStatisticsConfig::PstatsconfDefault(mp);
-
- result =
- std::min(result.Get() / CScaleFactorUtils::DampedFilterScaleFactor(
- stats_config, num_outer_ref_preds)
- .Get(),
- 1.0);
-
- stats_config->Release();
- }
+ const CDouble outer_scale_factor =
+ CScaleFactorUtils::CalcScaleFactorCumulativeConj(stats_config,
Review Comment:
I guess if the problem happens only for a few number of predicate we can keep the previous formula but cap its result at local selectivity.
##########
src/backend/gporca/libnaucrates/src/statistics/CFilterStatsProcessor.cpp:
##########
@@ -144,64 +150,30 @@ CFilterStatsProcessor::SelectivityOfPredicate(CMemoryPool *mp,
GPOS_ASSERT(nullptr != local_col_ref);
CDouble ndv = result_stats->GetNDVs(local_col_ref);
- if (ndv < 1.0)
- {
- // An NDV of less than 1 means that we have no stats on this column
- result = result * CHistogram::DefaultSelectivity;
- }
- else
+ // an NDV below 1 means that we have no stats on this column
+ if (ndv >= 1.0)
{
- result = result * (1 / ndv);
+ scale_factor = ndv;
}
}
- else
- {
- // a comparison col op <outer ref> other than an equals
- result = result * CHistogram::DefaultSelectivity;
- }
- num_outer_ref_preds++;
- }
- else
- {
- // if it is a true filter, then we had no expressions with outer refs
- if (!CUtils::FScalarConstTrue(pexpr))
- {
- // some other expression, not of the form col op <outer ref>,
- // e.g. an OR expression
- result = result * CHistogram::DefaultSelectivity;
- num_outer_ref_preds++;
- }
}
+ outer_scale_factors->Append(GPOS_NEW(mp) CDouble(scale_factor));
}
expr_with_outer_refs->Release();
outer_ref_exprs->Release();
}
- // apply damping factor to the outer ref predicates whose selectivities we multiplied above
- if (have_local_preds)
- {
- // add one for the combined non-outer refs which were dampened internally,
- // but not in combination with the preds on outer refs
- num_outer_ref_preds++;
- }
- if (1 < num_outer_ref_preds)
- {
- CStatisticsConfig *stats_config =
- CStatisticsConfig::PstatsconfDefault(mp);
-
- result =
- std::min(result.Get() / CScaleFactorUtils::DampedFilterScaleFactor(
- stats_config, num_outer_ref_preds)
- .Get(),
- 1.0);
-
- stats_config->Release();
- }
+ const CDouble outer_scale_factor =
+ CScaleFactorUtils::CalcScaleFactorCumulativeConj(stats_config,
+ outer_scale_factors);
+ outer_scale_factors->Release();
result_stats->Release();
local_expr->Release();
- return result;
+ // Outer selectivities are conditional on the local filter. Damping only
+ // their conjunction preserves the local estimate as an upper bound.
+ return local_selectivity / outer_scale_factor;
Review Comment:
When I looked closer at ORCA's local path (`MakeHistHashMapConjFilter` -> `CalcScaleFactorCumulativeConj`) I noticed that `ApplyCorrelatedStatsToScaleFactorFilterCalculation` function works slightly wrong (at least it seems like).
`ApplyCorrelatedStatsToScaleFactorFilterCalculation` function takes into account the functional dependence between predicates in the presence of extended statistics. But when do: `s2 = 1 / result_histograms->Find(&colid)->GetFrequency().Get();` to process a dependent column, after the function `result_histograms->Find(&colid)->GetFrequency().Get()` we get always ~1.0 because we count a sum of frequencies from all buckets. But its intention seems like to get a scale factor of histogram after applying predicate. I can add a separate issue to report it there.
For example, let's say we have the same `damping_partial` table. And we do:
~~~~sql
SELECT *
FROM damping_partial
WHERE a = 10 AND b = 0;
~~~~
Total rows = 20000
Rows with `a = 10` = 1000 => P(a=10) = 0.05
Rows with `b = 0` = 2000 => P(b=0) = 0.1
Dependency degree a->b = 0.5
The overall formula to count such dependencies:
~~~~c
/*
* Now factor in the selectivity for all the "implied" clauses into
* the final one, using this formula:
*
* P(a,b) = P(a) * (f + (1-f) * P(b))
*
* where 'f' is the degree of validity of the dependency.
*/
~~~~
Existing implementation uses the total frequency of the normalized `b` histogram, giving `s2 = 1`:
20000 * 0.05 * (0.5 + (1-0.5)*1) = **1000**
Correct implementation (when we first get a histogram after applying a filter and then count scale factor) uses the selectivity of b = 0, giving `s2 = 0.1`:
20000 * 0.05 * (0.5 + (1-0.5)*0.1) = **550**
The real value number of rows with `a=10` and `b=0` is 100.
It seems important because after the function `ApplyCorrelatedStatsToScaleFactorFilterCalculation` we will not consider these dependent predicates anymore (`child_pred->SetEstimated()`).
##########
src/backend/gporca/libnaucrates/src/statistics/CFilterStatsProcessor.cpp:
##########
@@ -144,64 +150,30 @@ CFilterStatsProcessor::SelectivityOfPredicate(CMemoryPool *mp,
GPOS_ASSERT(nullptr != local_col_ref);
CDouble ndv = result_stats->GetNDVs(local_col_ref);
- if (ndv < 1.0)
- {
- // An NDV of less than 1 means that we have no stats on this column
- result = result * CHistogram::DefaultSelectivity;
- }
- else
+ // an NDV below 1 means that we have no stats on this column
+ if (ndv >= 1.0)
{
- result = result * (1 / ndv);
+ scale_factor = ndv;
}
}
- else
- {
- // a comparison col op <outer ref> other than an equals
- result = result * CHistogram::DefaultSelectivity;
- }
- num_outer_ref_preds++;
- }
- else
- {
- // if it is a true filter, then we had no expressions with outer refs
- if (!CUtils::FScalarConstTrue(pexpr))
- {
- // some other expression, not of the form col op <outer ref>,
- // e.g. an OR expression
- result = result * CHistogram::DefaultSelectivity;
- num_outer_ref_preds++;
- }
}
+ outer_scale_factors->Append(GPOS_NEW(mp) CDouble(scale_factor));
}
expr_with_outer_refs->Release();
outer_ref_exprs->Release();
}
- // apply damping factor to the outer ref predicates whose selectivities we multiplied above
- if (have_local_preds)
- {
- // add one for the combined non-outer refs which were dampened internally,
- // but not in combination with the preds on outer refs
- num_outer_ref_preds++;
- }
- if (1 < num_outer_ref_preds)
- {
- CStatisticsConfig *stats_config =
- CStatisticsConfig::PstatsconfDefault(mp);
-
- result =
- std::min(result.Get() / CScaleFactorUtils::DampedFilterScaleFactor(
- stats_config, num_outer_ref_preds)
- .Get(),
- 1.0);
-
- stats_config->Release();
- }
+ const CDouble outer_scale_factor =
+ CScaleFactorUtils::CalcScaleFactorCumulativeConj(stats_config,
+ outer_scale_factors);
+ outer_scale_factors->Release();
result_stats->Release();
local_expr->Release();
- return result;
+ // Outer selectivities are conditional on the local filter. Damping only
+ // their conjunction preserves the local estimate as an upper bound.
+ return local_selectivity / outer_scale_factor;
Review Comment:
> A single outer equality with a local predicate gets **no damping at all**
I guess there is no problem here (`CFilterStatsProcessor::SelectivityOfPredicate`) because the maths tells us that damping is not needed here; we already take the statistics for outer predicates, provided after internal predicate exists, i.e. obtain NDVs after local filtering (see conditional probabilities in #2005). The purpose of damping factor is to add a degree of correlation between predicates while we've already took this into account when correcting statistics of outer predicate with an existing local predicates. So it seems like damping factor is a bit artificial here. But I agree with your comment that with this patch we will unintentionally prefer indexes covering outer-ref columns.
I'll add a patch that is coherent with your suggestion.
##########
src/backend/gporca/libnaucrates/src/statistics/CFilterStatsProcessor.cpp:
##########
@@ -144,64 +150,30 @@ CFilterStatsProcessor::SelectivityOfPredicate(CMemoryPool *mp,
GPOS_ASSERT(nullptr != local_col_ref);
CDouble ndv = result_stats->GetNDVs(local_col_ref);
- if (ndv < 1.0)
- {
- // An NDV of less than 1 means that we have no stats on this column
- result = result * CHistogram::DefaultSelectivity;
- }
- else
+ // an NDV below 1 means that we have no stats on this column
+ if (ndv >= 1.0)
{
- result = result * (1 / ndv);
+ scale_factor = ndv;
}
}
- else
- {
- // a comparison col op <outer ref> other than an equals
- result = result * CHistogram::DefaultSelectivity;
- }
- num_outer_ref_preds++;
- }
- else
- {
- // if it is a true filter, then we had no expressions with outer refs
- if (!CUtils::FScalarConstTrue(pexpr))
- {
- // some other expression, not of the form col op <outer ref>,
- // e.g. an OR expression
- result = result * CHistogram::DefaultSelectivity;
- num_outer_ref_preds++;
- }
}
+ outer_scale_factors->Append(GPOS_NEW(mp) CDouble(scale_factor));
}
expr_with_outer_refs->Release();
outer_ref_exprs->Release();
}
- // apply damping factor to the outer ref predicates whose selectivities we multiplied above
- if (have_local_preds)
- {
- // add one for the combined non-outer refs which were dampened internally,
- // but not in combination with the preds on outer refs
- num_outer_ref_preds++;
- }
- if (1 < num_outer_ref_preds)
- {
- CStatisticsConfig *stats_config =
- CStatisticsConfig::PstatsconfDefault(mp);
-
- result =
- std::min(result.Get() / CScaleFactorUtils::DampedFilterScaleFactor(
- stats_config, num_outer_ref_preds)
- .Get(),
- 1.0);
-
- stats_config->Release();
- }
+ const CDouble outer_scale_factor =
+ CScaleFactorUtils::CalcScaleFactorCumulativeConj(stats_config,
Review Comment:
Yes, I agree for this case
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@cloudberry.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@cloudberry.apache.org
For additional commands, e-mail: commits-help@cloudberry.apache.org