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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
