This is an automated email from the ASF dual-hosted git repository.
yiguolei pushed a commit to branch branch-4.1
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/branch-4.1 by this push:
new 0e06fc1361b branch-4.1: [improvement](fe) Avoid under-estimating
not-in predicate row count #66632 (#66900)
0e06fc1361b is described below
commit 0e06fc1361b6faa36eeef0811e260a3330a03a07
Author: github-actions[bot]
<41898282+github-actions[bot]@users.noreply.github.com>
AuthorDate: Mon Aug 24 09:57:31 2026 +0800
branch-4.1: [improvement](fe) Avoid under-estimating not-in predicate row
count #66632 (#66900)
Cherry-picked from #66632
Co-authored-by: minghong <[email protected]>
---
.../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 e6601269012..edc05e26b24 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
@@ -57,6 +57,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;
@@ -853,8 +854,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]
