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 1abb19d0fd filter estimation refactor (#18170)
1abb19d0fd is described below

commit 1abb19d0fdc804f7dfe1bd7b80520fb63647337b
Author: minghong <[email protected]>
AuthorDate: Fri Mar 31 08:49:38 2023 +0800

    filter estimation refactor (#18170)
---
 .../nereids/stats/ColumnStatsAdjustVisitor.java    | 64 ++++++++++++++++++++++
 .../doris/nereids/stats/ExpressionEstimation.java  |  4 ++
 .../doris/nereids/stats/FilterEstimation.java      | 10 +++-
 .../apache/doris/statistics/StatisticRange.java    | 12 ++++
 .../doris/nereids/stats/FilterEstimationTest.java  | 29 ++++++++++
 5 files changed, 116 insertions(+), 3 deletions(-)

diff --git 
a/fe/fe-core/src/main/java/org/apache/doris/nereids/stats/ColumnStatsAdjustVisitor.java
 
b/fe/fe-core/src/main/java/org/apache/doris/nereids/stats/ColumnStatsAdjustVisitor.java
new file mode 100644
index 0000000000..1f789f7deb
--- /dev/null
+++ 
b/fe/fe-core/src/main/java/org/apache/doris/nereids/stats/ColumnStatsAdjustVisitor.java
@@ -0,0 +1,64 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+package org.apache.doris.nereids.stats;
+
+import org.apache.doris.nereids.trees.expressions.Cast;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.visitor.ExpressionVisitor;
+import org.apache.doris.statistics.ColumnStatistic;
+import org.apache.doris.statistics.Statistics;
+
+/**
+ * table: T(A, B)
+ * T.stats = (rows=10,
+ *            {
+ *                A->ndv=10, rows=10
+ *                B->...
+ *            }
+ *           )
+ * after node: filter(cast(A as double)=1.0)
+ * filter.stats = (rows = 1
+ *          {
+ *           A->ndv=m, rows=1
+ *           B->ndv=m, rows=1
+ *           cast(A as double) -> ndv=1, rows=1
+ *          }
+ *         )
+ *
+ * m is computed by function computeNdv()
+ *
+ * filter.stats should be adjusted.
+ * A.columnStats should be equal to "cast(A as double)".columnStats
+ * for other expressions(except cast), we also need to adjust their input 
column stats.
+ *
+ */
+public class ColumnStatsAdjustVisitor extends 
ExpressionVisitor<ColumnStatistic, Statistics> {
+    @Override
+    public ColumnStatistic visit(Expression expr, Statistics context) {
+        expr.children().forEach(child -> child.accept(this, context));
+        return null;
+    }
+
+    public ColumnStatistic visitCast(Cast cast, Statistics context) {
+        ColumnStatistic colStats = context.findColumnStatistics(cast);
+        if (colStats != null) {
+            context.addColumnStats(cast.child(), colStats);
+        }
+        return null;
+    }
+}
diff --git 
a/fe/fe-core/src/main/java/org/apache/doris/nereids/stats/ExpressionEstimation.java
 
b/fe/fe-core/src/main/java/org/apache/doris/nereids/stats/ExpressionEstimation.java
index 93c20a986c..782609afd5 100644
--- 
a/fe/fe-core/src/main/java/org/apache/doris/nereids/stats/ExpressionEstimation.java
+++ 
b/fe/fe-core/src/main/java/org/apache/doris/nereids/stats/ExpressionEstimation.java
@@ -141,6 +141,10 @@ public class ExpressionEstimation extends 
ExpressionVisitor<ColumnStatistic, Sta
     }
 
     public ColumnStatistic visitCast(Cast cast, Statistics context) {
+        ColumnStatistic stats = context.findColumnStatistics(cast);
+        if (stats != null) {
+            return stats;
+        }
         return cast.child().accept(this, context);
     }
 
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 6bc3bc96c6..7cebe8f81d 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
@@ -175,9 +175,11 @@ public class FilterEstimation extends 
ExpressionVisitor<Statistics, EstimationCo
         if (statsForLeft.histogram != null) {
             return estimateLessThanLiteralWithHistogram(leftExpr, 
statsForLeft, val, context, contains);
         }
+        //rightRange.distinctValues should not be used
+        StatisticRange rightRange = new StatisticRange(statsForLeft.minValue, 
val, statsForLeft.ndv);
         return estimateBinaryComparisonFilter(leftExpr,
                 statsForLeft,
-                new StatisticRange(Double.NEGATIVE_INFINITY, val, 
statsForLeft.ndv), context);
+                rightRange, context);
     }
 
     private Statistics updateGreaterThanLiteral(Expression leftExpr, 
ColumnStatistic statsForLeft,
@@ -185,7 +187,8 @@ public class FilterEstimation extends 
ExpressionVisitor<Statistics, EstimationCo
         if (statsForLeft.histogram != null) {
             return estimateGreaterThanLiteralWithHistogram(leftExpr, 
statsForLeft, val, context, contains);
         }
-        StatisticRange rightRange = new StatisticRange(val, 
Double.POSITIVE_INFINITY,
+        //rightRange.distinctValues should not be used
+        StatisticRange rightRange = new StatisticRange(val, 
statsForLeft.maxValue,
                 statsForLeft.ndv);
         return estimateBinaryComparisonFilter(leftExpr, statsForLeft, 
rightRange, context);
     }
@@ -358,7 +361,7 @@ public class FilterEstimation extends 
ExpressionVisitor<Statistics, EstimationCo
             StatisticRange rightRange, EstimationContext context) {
         StatisticRange leftRange =
                 new StatisticRange(leftStats.minValue, leftStats.maxValue, 
leftStats.ndv);
-        StatisticRange intersectRange = leftRange.intersect(rightRange);
+        StatisticRange intersectRange = leftRange.cover(rightRange);
         ColumnStatisticBuilder leftColumnStatisticBuilder = new 
ColumnStatisticBuilder(leftStats)
                 .setMinValue(intersectRange.getLow())
                 .setMaxValue(intersectRange.getHigh())
@@ -366,6 +369,7 @@ public class FilterEstimation extends 
ExpressionVisitor<Statistics, EstimationCo
         double sel = leftRange.overlapPercentWith(rightRange);
         Statistics updatedStatistics = context.statistics.withSel(sel);
         updatedStatistics.addColumnStats(leftExpr, 
leftColumnStatisticBuilder.build());
+        leftExpr.accept(new ColumnStatsAdjustVisitor(), updatedStatistics);
         return updatedStatistics;
     }
 
diff --git 
a/fe/fe-core/src/main/java/org/apache/doris/statistics/StatisticRange.java 
b/fe/fe-core/src/main/java/org/apache/doris/statistics/StatisticRange.java
index fa2b1e1cb7..bbc95169e9 100644
--- a/fe/fe-core/src/main/java/org/apache/doris/statistics/StatisticRange.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/statistics/StatisticRange.java
@@ -110,6 +110,18 @@ public class StatisticRange {
         return empty();
     }
 
+    public StatisticRange cover(StatisticRange other) {
+        double newLow = Math.max(low, other.low);
+        double newHigh = Math.min(high, other.high);
+        if (newLow <= newHigh) {
+            double overlapPercentOfLeft = overlapPercentWith(other);
+            double overlapDistinctValuesLeft = overlapPercentOfLeft * 
distinctValues;
+            double coveredDistinctValues = minExcludeNaN(distinctValues, 
overlapDistinctValuesLeft);
+            return new StatisticRange(newLow, newHigh, coveredDistinctValues);
+        }
+        return empty();
+    }
+
     public StatisticRange union(StatisticRange other) {
         double overlapPercentThis = this.overlapPercentWith(other);
         double overlapPercentOther = other.overlapPercentWith(this);
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 49b19f5f52..dbe1d9a1a1 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
@@ -18,6 +18,7 @@
 package org.apache.doris.nereids.stats;
 
 import org.apache.doris.nereids.trees.expressions.And;
+import org.apache.doris.nereids.trees.expressions.Cast;
 import org.apache.doris.nereids.trees.expressions.EqualTo;
 import org.apache.doris.nereids.trees.expressions.Expression;
 import org.apache.doris.nereids.trees.expressions.GreaterThan;
@@ -28,7 +29,9 @@ import 
org.apache.doris.nereids.trees.expressions.LessThanEqual;
 import org.apache.doris.nereids.trees.expressions.Not;
 import org.apache.doris.nereids.trees.expressions.Or;
 import org.apache.doris.nereids.trees.expressions.SlotReference;
+import org.apache.doris.nereids.trees.expressions.literal.DoubleLiteral;
 import org.apache.doris.nereids.trees.expressions.literal.IntegerLiteral;
+import org.apache.doris.nereids.types.DoubleType;
 import org.apache.doris.nereids.types.IntegerType;
 import org.apache.doris.statistics.ColumnStatistic;
 import org.apache.doris.statistics.ColumnStatisticBuilder;
@@ -838,4 +841,30 @@ class FilterEstimationTest {
         Assertions.assertEquals(10, statsC.minValue);
         Assertions.assertEquals(40, statsC.maxValue);
     }
+
+    @Test
+    public void testBetweenCastFilter() {
+        SlotReference a = new SlotReference("a", IntegerType.INSTANCE);
+        ColumnStatisticBuilder builder = new ColumnStatisticBuilder()
+                .setNdv(100)
+                .setAvgSizeByte(4)
+                .setNumNulls(0)
+                .setMaxValue(100)
+                .setMinValue(0)
+                .setSelectivity(1.0)
+                .setCount(100);
+        DoubleLiteral begin = new DoubleLiteral(40.0);
+        DoubleLiteral end = new DoubleLiteral(50.0);
+        LessThan less = new LessThan(new Cast(a, DoubleType.INSTANCE), end);
+        GreaterThan greater = new GreaterThan(new Cast(a, 
DoubleType.INSTANCE), begin);
+        And and = new And(less, greater);
+        Statistics stats = new Statistics(100, new HashMap<>());
+        stats.addColumnStats(a, builder.build());
+        FilterEstimation filterEstimation = new FilterEstimation();
+        Statistics result = filterEstimation.estimate(and, stats);
+        Assertions.assertEquals(result.getRowCount(), 10, 0.01);
+        ColumnStatistic colStats = result.findColumnStatistics(a);
+        Assertions.assertTrue(colStats != null);
+        Assertions.assertEquals(10, colStats.ndv, 0.1);
+    }
 }


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to