This is an automated email from the ASF dual-hosted git repository.
englefly pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/master by this push:
new c2f5d26f051 [improvement](fe) Avoid under-estimating not-in predicate
row count (#66632)
c2f5d26f051 is described below
commit c2f5d26f0510edc72154ba44bbd2ad27cc60dc18
Author: minghong <[email protected]>
AuthorDate: Tue Aug 18 17:43:44 2026 +0800
[improvement](fe) Avoid under-estimating not-in predicate row count (#66632)
### What problem does this PR solve?
Issue Number: N/A
Problem Summary:
[not-in rows] is estimated as [total rows] - [in rows] in
FilterEstimation#visitNot. [in rows] is usually over-estimated when the
in-options cover the whole ndv or the ndv statistics is inaccurate,
which makes [not-in rows] under-estimated to nearly 0 and misleads the
join reorder / limit pushdown. Following the starrocks implementation
(PredicateStatisticsCalculator#visitInPredicate), when the estimated in
selectivity reaches 1.0 (full coverage), fall back to the default not-in
coefficient 1 - DEFAULT_IN_COEFFICIENT instead of 0 to avoid too small
estimation.
### Release note
None
### Check List (For Author)
- Test: Unit test (FilterEstimationTest: added testNotInFullCoverage and
testNotInAlmostFullCoverage; all 63 tests in the class pass)
- Behavior changed: Yes (not-in row count estimation may increase when
in-options cover the whole ndv)
- Does this need documentation: No
### What problem does this PR solve?
Issue Number: close #xxx
Related PR: #xxx
Problem Summary:
### Release note
None
### Check List (For Author)
- Test <!-- At least one of them must be included. -->
- [ ] Regression test
- [ ] Unit Test
- [ ] Manual test (add detailed scripts or steps below)
- [ ] No need to test or manual test. Explain why:
- [ ] This is a refactor/code format and no logic has been changed.
- [ ] Previous test can cover this change.
- [ ] No code files have been changed.
- [ ] Other reason <!-- Add your reason? -->
- Behavior changed:
- [ ] No.
- [ ] Yes. <!-- Explain the behavior change -->
- Does this need documentation?
- [ ] No.
- [ ] Yes. <!-- Add document PR link here. eg:
https://github.com/apache/doris-website/pull/1214 -->
### Check List (For Reviewer who merge this PR)
- [ ] Confirm the release note
- [ ] Confirm test cases
- [ ] Confirm document
- [ ] Add branch pick label <!-- Add branch pick label that this PR
should merge into -->
---
.../doris/nereids/stats/FilterEstimation.java | 12 ++++-
.../doris/nereids/stats/FilterEstimationTest.java | 58 ++++++++++++++++++++++
2 files changed, 69 insertions(+), 1 deletion(-)
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/stats/FilterEstimation.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/stats/FilterEstimation.java
index 482f7872be6..c21468afa26 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/stats/FilterEstimation.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/stats/FilterEstimation.java
@@ -58,6 +58,7 @@ import org.apache.doris.statistics.StatisticsBuilder;
import com.google.common.base.Preconditions;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;
+import org.apache.commons.math3.util.Precision;
import org.jetbrains.annotations.NotNull;
import java.util.ArrayList;
@@ -854,8 +855,17 @@ public class FilterEstimation extends
ExpressionVisitor<Statistics, EstimationCo
Expression child = not.child();
Statistics childStats = child.accept(this, context);
childStats.normalizeColumnStatistics();
+ double rowCount = context.statistics.getRowCount() -
childStats.getRowCount();
+ if (child instanceof InPredicate
+ && Precision.equals(childStats.getRowCount(),
context.statistics.getRowCount(), 0.000001)) {
+ // [not in rows] = [total rows] - [in rows], while [in rows] is
usually over-estimated when the
+ // options cover the whole ndv or the ndv statistics is
inaccurate, which makes [not in rows]
+ // under-estimated to nearly 0. Following starrocks, fall back to
a default coefficient to
+ // avoid the not-in rows being too small.
+ rowCount = context.statistics.getRowCount() * (1 -
DEFAULT_IN_COEFFICIENT);
+ }
//if estimated rowCount is 0, adjust to 1 to make upper join reorder
reasonable.
- double rowCount = Math.max(context.statistics.getRowCount() -
childStats.getRowCount(), 1);
+ rowCount = Math.max(rowCount, 1);
StatisticsBuilder statisticsBuilder = new
StatisticsBuilder(context.statistics).setRowCount(rowCount);
// update key col stats
for (Slot slot : not.child().getInputSlots()) {
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/nereids/stats/FilterEstimationTest.java
b/fe/fe-core/src/test/java/org/apache/doris/nereids/stats/FilterEstimationTest.java
index 8533adb3061..bd0a782fbdc 100644
---
a/fe/fe-core/src/test/java/org/apache/doris/nereids/stats/FilterEstimationTest.java
+++
b/fe/fe-core/src/test/java/org/apache/doris/nereids/stats/FilterEstimationTest.java
@@ -567,6 +567,64 @@ class FilterEstimationTest {
Assertions.assertEquals(1000 * 7.0 / 10.0, estimated.getRowCount());
}
+ // a not in (1, 2, ..., 10)
+ // a belongs to [1, 10], ndv = 10, the options cover the whole ndv
+ // [in rows] is over-estimated as full coverage, so [not in rows] falls
back to a default coefficient
+ // instead of being estimated as 0 (see visitNot).
+ @Test
+ public void testNotInFullCoverage() {
+ SlotReference a = new SlotReference("a", IntegerType.INSTANCE);
+ ArrayList<Expression> options = new ArrayList<>();
+ for (int i = 1; i <= 10; i++) {
+ options.add(new IntegerLiteral(i));
+ }
+ InPredicate inPredicate = new InPredicate(a, options);
+ Not not = new Not(inPredicate);
+ Map<Expression, ColumnStatistic> slotToColumnStat = new HashMap<>();
+ ColumnStatisticBuilder builder = new ColumnStatisticBuilder()
+ .setNdv(10)
+ .setAvgSizeByte(4)
+ .setNumNulls(0)
+ .setMinValue(1)
+ .setMinExpr(new IntLiteral(1))
+ .setMaxValue(10)
+ .setMaxExpr(new IntLiteral(10));
+ slotToColumnStat.put(a, builder.build());
+ Statistics stat = new Statistics(1000, slotToColumnStat);
+ FilterEstimation filterEstimation = new FilterEstimation();
+ Statistics estimated = filterEstimation.estimate(not, stat);
+ Assertions.assertEquals(1000 * (1 -
FilterEstimation.DEFAULT_IN_COEFFICIENT),
+ estimated.getRowCount(), 0.01);
+ }
+
+ // a not in (1, 2, ..., 9)
+ // a belongs to [1, 10], ndv = 10, the options cover 9/10 of the ndv
+ // [not in rows] should still be estimated as [total rows] - [in rows]
without fall back
+ @Test
+ public void testNotInAlmostFullCoverage() {
+ SlotReference a = new SlotReference("a", IntegerType.INSTANCE);
+ ArrayList<Expression> options = new ArrayList<>();
+ for (int i = 1; i <= 9; i++) {
+ options.add(new IntegerLiteral(i));
+ }
+ InPredicate inPredicate = new InPredicate(a, options);
+ Not not = new Not(inPredicate);
+ Map<Expression, ColumnStatistic> slotToColumnStat = new HashMap<>();
+ ColumnStatisticBuilder builder = new ColumnStatisticBuilder()
+ .setNdv(10)
+ .setAvgSizeByte(4)
+ .setNumNulls(0)
+ .setMinValue(1)
+ .setMinExpr(new IntLiteral(1))
+ .setMaxValue(10)
+ .setMaxExpr(new IntLiteral(10));
+ slotToColumnStat.put(a, builder.build());
+ Statistics stat = new Statistics(1000, slotToColumnStat);
+ FilterEstimation filterEstimation = new FilterEstimation();
+ Statistics estimated = filterEstimation.estimate(not, stat);
+ Assertions.assertEquals(1000 * 1.0 / 10.0, estimated.getRowCount(),
0.01);
+ }
+
// c>100
// a is primary-key, a.ndv is reduced
// b is normal, b.ndv is smaller: newNdv = ndv * (1 - Math.pow(1 -
selectivity, rowCount / ndv));
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
