morrySnow commented on code in PR #18784:
URL: https://github.com/apache/doris/pull/18784#discussion_r1193462747
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/cost/CostModelV2.java:
##########
@@ -156,6 +157,20 @@ public Cost
visitAbstractPhysicalSort(AbstractPhysicalSort<? extends Plan> sort,
return new CostV2(startCost, runCost, statistics.computeSize());
}
+ @Override
+ public Cost visitPhysicalPartitionTopN(PhysicalPartitionTopN<? extends
Plan> partitionTopN, PlanContext context) {
Review Comment:
do we need to update cost model v1?
##########
fe/fe-core/src/main/java/org/apache/doris/statistics/StatisticalType.java:
##########
@@ -43,6 +43,7 @@ public enum StatisticalType {
SET_OPERATION_NODE,
SCHEMA_SCAN_NODE,
SORT_NODE,
+ PARTITION_TOPN_MODE,
Review Comment:
Please sort in lexicographic order
##########
fe/fe-core/src/main/java/org/apache/doris/planner/PartitionSortNode.java:
##########
@@ -0,0 +1,307 @@
+// 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.planner;
+
+import org.apache.doris.analysis.Analyzer;
+import org.apache.doris.analysis.Expr;
+import org.apache.doris.analysis.ExprSubstitutionMap;
+import org.apache.doris.analysis.SlotDescriptor;
+import org.apache.doris.analysis.SlotId;
+import org.apache.doris.analysis.SlotRef;
+import org.apache.doris.analysis.SortInfo;
+import org.apache.doris.analysis.TupleDescriptor;
+import org.apache.doris.common.NotImplementedException;
+import org.apache.doris.common.UserException;
+import org.apache.doris.statistics.StatisticalType;
+import org.apache.doris.statistics.StatsRecursiveDerive;
+import org.apache.doris.thrift.TExplainLevel;
+import org.apache.doris.thrift.TPartitionSortNode;
+import org.apache.doris.thrift.TPlanNode;
+import org.apache.doris.thrift.TPlanNodeType;
+import org.apache.doris.thrift.TSortInfo;
+import org.apache.doris.thrift.TopNAlgorithm;
+
+import com.google.common.base.Joiner;
+import com.google.common.base.MoreObjects;
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+import org.apache.logging.log4j.LogManager;
+import org.apache.logging.log4j.Logger;
+
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Objects;
+import java.util.Set;
+
+/**
+ * PartitionSortNode.
+ */
+public class PartitionSortNode extends PlanNode {
Review Comment:
add a comment only used in Nereids
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalPartitionTopN.java:
##########
@@ -0,0 +1,166 @@
+// 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.trees.plans.logical;
+
+import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.LogicalProperties;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.OrderExpression;
+import org.apache.doris.nereids.trees.expressions.Slot;
+import org.apache.doris.nereids.trees.expressions.WindowExpression;
+import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.trees.plans.PlanType;
+import org.apache.doris.nereids.trees.plans.algebra.PartitionTopN;
+import org.apache.doris.nereids.trees.plans.visitor.PlanVisitor;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+
+import java.util.List;
+import java.util.Objects;
+import java.util.Optional;
+
+/**
+ * Logical partition-top-N plan.
+ */
+public class LogicalPartitionTopN<CHILD_TYPE extends Plan> extends
LogicalUnary<CHILD_TYPE> implements PartitionTopN {
+ private final Expression function;
+ private final List<Expression> partitionKeys;
+ private final List<OrderExpression> orderKeys;
+ private final Boolean hasGlobalLimit;
+ private final long partitionLimit;
+
+ public LogicalPartitionTopN(WindowExpression windowExpr, Boolean
hasGlobalLimit, long partitionLimit,
+ CHILD_TYPE child) {
+ this(windowExpr.getFunction(), windowExpr.getPartitionKeys(),
windowExpr.getOrderKeys(),
+ hasGlobalLimit, partitionLimit, Optional.empty(),
+ Optional.empty(), child);
+ }
+
+ public LogicalPartitionTopN(Expression function, List<Expression>
partitionKeys, List<OrderExpression> orderKeys,
+ Boolean hasGlobalLimit, long partitionLimit,
CHILD_TYPE child) {
+ this(function, partitionKeys, orderKeys, hasGlobalLimit,
partitionLimit,
+ Optional.empty(), Optional.empty(), child);
+ }
+
+ /**
+ * Constructor for LogicalPartitionTopN.
+ */
+ public LogicalPartitionTopN(Expression function, List<Expression>
partitionKeys, List<OrderExpression> orderKeys,
+ Boolean hasGlobalLimit, long partitionLimit,
Optional<GroupExpression> groupExpression,
+ Optional<LogicalProperties> logicalProperties,
CHILD_TYPE child) {
+ super(PlanType.LOGICAL_PARTITION_TOP_N, groupExpression,
logicalProperties, child);
+ this.function = function;
+ this.partitionKeys = ImmutableList.copyOf(partitionKeys);
+ this.orderKeys = ImmutableList.copyOf(orderKeys);
Review Comment:
check not null
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/StatsCalculator.java:
##########
@@ -464,6 +478,32 @@ private Statistics computeTopN(TopN topN) {
return stats.withRowCount(Math.min(stats.getRowCount(),
topN.getLimit()));
}
+ private Statistics computePartitionTopN(PartitionTopN partitionTopN) {
+ Statistics stats = groupExpression.childStatistics(0);
+ double rowCount = stats.getRowCount();
+ List<Expression> partitionKeys = partitionTopN.getPartitionKeys();
+ if (!partitionTopN.hasGlobalLimit() && !partitionKeys.isEmpty()) {
Review Comment:
i think there are a minor issue here. we first do row count prune in
PartitionTopN node, and we will do row count prune in later Filter or Limit
too. So it is equal that we do row count prune twice. What do u think @englefly
?
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/PushdownFilterThroughWindow.java:
##########
@@ -0,0 +1,204 @@
+// 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.rules.rewrite.logical;
+
+import org.apache.doris.nereids.rules.Rule;
+import org.apache.doris.nereids.rules.RuleType;
+import org.apache.doris.nereids.rules.rewrite.OneRewriteRuleFactory;
+import org.apache.doris.nereids.trees.expressions.BinaryOperator;
+import org.apache.doris.nereids.trees.expressions.EqualTo;
+import org.apache.doris.nereids.trees.expressions.ExprId;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.LessThan;
+import org.apache.doris.nereids.trees.expressions.LessThanEqual;
+import org.apache.doris.nereids.trees.expressions.NamedExpression;
+import org.apache.doris.nereids.trees.expressions.Or;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
+import org.apache.doris.nereids.trees.expressions.WindowExpression;
+import org.apache.doris.nereids.trees.expressions.literal.IntegerLikeLiteral;
+import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.trees.plans.logical.LogicalEmptyRelation;
+import org.apache.doris.nereids.trees.plans.logical.LogicalPartitionTopN;
+import org.apache.doris.nereids.trees.plans.logical.LogicalWindow;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableSet;
+
+import java.util.List;
+import java.util.Set;
+import java.util.function.Predicate;
+
+/**
+ * Push down the 'filter' into the 'window'.
+ * It will convert the filter condition to the 'limit value' and push down
below the 'window'.
+ * But there are some restrictions, the details are explained below.
+ * For example:
+ * 'SELECT * FROM (
+ * SELECT *, ROW_NUMBER() OVER (ORDER BY b) AS row_number
+ * FROM t
+ * ) AS tt WHERE row_number <= 100;'
+ * The filter 'row_number <= 100' can be pushed down into the window operator.
+ * The following will demonstrate how the plan changes:
+ * Logical plan tree:
+ * any_node
+ * |
+ * filter (row_number <= 100)
+ * |
+ * window (PARTITION BY a ORDER BY b)
+ * |
+ * any_node
+ * transformed to:
+ * any_node
+ * |
+ * filter (row_number <= 100)
+ * |
+ * window (PARTITION BY a ORDER BY b)
+ * |
+ * partition_topn(PARTITION BY: a, ORDER BY b, Partition Limit:
100)
+ * |
+ * any_node
+ */
+
+public class PushdownFilterThroughWindow extends OneRewriteRuleFactory {
+
+ @Override
+ public Rule build() {
+ return logicalFilter(logicalWindow()).then(filter -> {
+ LogicalWindow<Plan> window = filter.child();
+
+ // We have already done such optimization rule, so just ignore it.
+ if (window.child(0) instanceof LogicalPartitionTopN) {
+ return filter;
+ }
+
+ // Check the window function. There are some restrictions for
window function:
+ // * The number of window function should be 1.
+ // * The window function should be one of the 'row_number()',
'rank()', 'dense_rank()'.
+ // * The window type should be 'ROW'.
+ // * The window frame should be 'UNBOUNDED' to 'CURRENT'.
+ // * The 'PARTITION' key and 'ORDER' key can not be empty at the
same time.
+ List<NamedExpression> windowExprs = window.getWindowExpressions();
+ if (windowExprs.size() != 1) {
+ return filter;
+ }
+ NamedExpression windowExpr = windowExprs.get(0);
+ if (windowExpr.children().size() != 1 || !(windowExpr.child(0)
instanceof WindowExpression)) {
+ return filter;
+ }
+
+ WindowExpression windowFunc = (WindowExpression)
windowExpr.child(0);
+ // Check the window function name.
+ if (!LogicalWindow.checkWindowFuncName4PartitionTopN(windowFunc)) {
+ return filter;
+ }
+
+ // Check the partition key and order key.
+ if
(!LogicalWindow.checkWindowPartitionAndOrderKey4PartitionTopN(windowFunc)) {
+ return filter;
+ }
+
+ // Check the window type and window frame.
+ if (!LogicalWindow.checkWindowFrame4PartitionTopN(windowFunc)) {
+ return filter;
+ }
+
+ // Check the filter conditions. Now, we currently only support
simple conditions of the form
+ // 'column </ <=/ = constant'. We will extract some related
conjuncts and do some check.
+ Set<Expression> conjuncts = filter.getConjuncts();
+ boolean existsORConditionsInConjuncts =
conjuncts.stream().anyMatch(this::existOR);
+ if (existsORConditionsInConjuncts) {
+ return filter;
+ }
+
+ Set<Expression> relatedConjuncts =
extractRelatedConjuncts(conjuncts, windowExpr.getExprId());
+
+ boolean hasPartitionLimit = false;
+ long partitionLimit = Long.MAX_VALUE;
+
+ for (Expression conjunct : relatedConjuncts) {
+ Preconditions.checkArgument(conjunct instanceof
BinaryOperator);
+ BinaryOperator op = (BinaryOperator) conjunct;
+ Expression leftChild = op.children().get(0);
+ Expression rightChild = op.children().get(1);
+
+ Preconditions.checkArgument(leftChild instanceof SlotReference
+ && rightChild instanceof IntegerLikeLiteral);
+
+ long limitVal = ((IntegerLikeLiteral)
rightChild).getLongValue();
+ // Adjust the value for 'limitVal' based on the comparison
operators.
+ if (conjunct instanceof LessThan) {
+ limitVal--;
+ }
+ if (limitVal < 0) {
+ return new LogicalEmptyRelation(filter.getOutput());
+ }
+ if (hasPartitionLimit) {
+ partitionLimit = Math.min(partitionLimit, limitVal);
+ } else {
+ partitionLimit = limitVal;
+ hasPartitionLimit = true;
+ }
+ }
+
+ if (!hasPartitionLimit) {
+ return filter;
+ }
+ // return PartitionTopN -> Window -> Filter
+ return filter.withChildren(window.withChildren(
+ new LogicalPartitionTopN<>(windowFunc, false, partitionLimit,
window.child(0))));
+ }).toRule(RuleType.PUSHDOWN_FILTER_THROUGH_WINDOW);
+ }
+
+ private boolean existOR(Expression conjunct) {
+ if (conjunct instanceof Or) {
+ return true;
+ }
+
+ for (Expression child : conjunct.children()) {
+ if (existOR(child)) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ private Set<Expression> extractRelatedConjuncts(Set<Expression> conjuncts,
ExprId slotRefID) {
+ Predicate<Expression> condition = conjunct -> {
+ if (!(conjunct instanceof BinaryOperator)) {
+ return false;
+ }
+ BinaryOperator op = (BinaryOperator) conjunct;
+ Expression leftChild = op.children().get(0);
+ Expression rightChild = op.children().get(1);
+
+ if (!(conjunct instanceof LessThan || conjunct instanceof
LessThanEqual || conjunct instanceof EqualTo)) {
+ return false;
+ }
+
+ // Now, we only support the column on the left side.
Review Comment:
add a TODO
##########
fe/fe-core/src/main/java/org/apache/doris/planner/PartitionSortNode.java:
##########
@@ -0,0 +1,307 @@
+// 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.planner;
+
+import org.apache.doris.analysis.Analyzer;
+import org.apache.doris.analysis.Expr;
+import org.apache.doris.analysis.ExprSubstitutionMap;
+import org.apache.doris.analysis.SlotDescriptor;
+import org.apache.doris.analysis.SlotId;
+import org.apache.doris.analysis.SlotRef;
+import org.apache.doris.analysis.SortInfo;
+import org.apache.doris.analysis.TupleDescriptor;
+import org.apache.doris.common.NotImplementedException;
+import org.apache.doris.common.UserException;
+import org.apache.doris.statistics.StatisticalType;
+import org.apache.doris.statistics.StatsRecursiveDerive;
+import org.apache.doris.thrift.TExplainLevel;
+import org.apache.doris.thrift.TPartitionSortNode;
+import org.apache.doris.thrift.TPlanNode;
+import org.apache.doris.thrift.TPlanNodeType;
+import org.apache.doris.thrift.TSortInfo;
+import org.apache.doris.thrift.TopNAlgorithm;
+
+import com.google.common.base.Joiner;
+import com.google.common.base.MoreObjects;
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+import org.apache.logging.log4j.LogManager;
+import org.apache.logging.log4j.Logger;
+
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Objects;
+import java.util.Set;
+
+/**
+ * PartitionSortNode.
+ */
+public class PartitionSortNode extends PlanNode {
+ private static final Logger LOG =
LogManager.getLogger(PartitionSortNode.class);
+ List<Expr> resolvedTupleExprs;
Review Comment:
why not private?
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalPartitionTopN.java:
##########
@@ -0,0 +1,166 @@
+// 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.trees.plans.logical;
+
+import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.LogicalProperties;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.OrderExpression;
+import org.apache.doris.nereids.trees.expressions.Slot;
+import org.apache.doris.nereids.trees.expressions.WindowExpression;
+import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.trees.plans.PlanType;
+import org.apache.doris.nereids.trees.plans.algebra.PartitionTopN;
+import org.apache.doris.nereids.trees.plans.visitor.PlanVisitor;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+
+import java.util.List;
+import java.util.Objects;
+import java.util.Optional;
+
+/**
+ * Logical partition-top-N plan.
+ */
+public class LogicalPartitionTopN<CHILD_TYPE extends Plan> extends
LogicalUnary<CHILD_TYPE> implements PartitionTopN {
+ private final Expression function;
+ private final List<Expression> partitionKeys;
+ private final List<OrderExpression> orderKeys;
+ private final Boolean hasGlobalLimit;
+ private final long partitionLimit;
+
+ public LogicalPartitionTopN(WindowExpression windowExpr, Boolean
hasGlobalLimit, long partitionLimit,
+ CHILD_TYPE child) {
+ this(windowExpr.getFunction(), windowExpr.getPartitionKeys(),
windowExpr.getOrderKeys(),
+ hasGlobalLimit, partitionLimit, Optional.empty(),
+ Optional.empty(), child);
+ }
+
+ public LogicalPartitionTopN(Expression function, List<Expression>
partitionKeys, List<OrderExpression> orderKeys,
+ Boolean hasGlobalLimit, long partitionLimit,
CHILD_TYPE child) {
+ this(function, partitionKeys, orderKeys, hasGlobalLimit,
partitionLimit,
+ Optional.empty(), Optional.empty(), child);
+ }
+
+ /**
+ * Constructor for LogicalPartitionTopN.
+ */
+ public LogicalPartitionTopN(Expression function, List<Expression>
partitionKeys, List<OrderExpression> orderKeys,
+ Boolean hasGlobalLimit, long partitionLimit,
Optional<GroupExpression> groupExpression,
+ Optional<LogicalProperties> logicalProperties,
CHILD_TYPE child) {
+ super(PlanType.LOGICAL_PARTITION_TOP_N, groupExpression,
logicalProperties, child);
+ this.function = function;
+ this.partitionKeys = ImmutableList.copyOf(partitionKeys);
+ this.orderKeys = ImmutableList.copyOf(orderKeys);
+ this.hasGlobalLimit = hasGlobalLimit;
+ this.partitionLimit = partitionLimit;
+ }
+
+ @Override
+ public List<Slot> computeOutput() {
+ return child().getOutput();
+ }
+
+ public Expression getFunction() {
+ return function;
+ }
+
+ @Override
+ public List<Expression> getPartitionKeys() {
+ return partitionKeys;
+ }
+
+ public List<OrderExpression> getOrderKeys() {
+ return orderKeys;
+ }
Review Comment:
do we need put this method into interface PartitionTopN?
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/PushdownFilterThroughWindow.java:
##########
@@ -0,0 +1,204 @@
+// 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.rules.rewrite.logical;
+
+import org.apache.doris.nereids.rules.Rule;
+import org.apache.doris.nereids.rules.RuleType;
+import org.apache.doris.nereids.rules.rewrite.OneRewriteRuleFactory;
+import org.apache.doris.nereids.trees.expressions.BinaryOperator;
+import org.apache.doris.nereids.trees.expressions.EqualTo;
+import org.apache.doris.nereids.trees.expressions.ExprId;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.LessThan;
+import org.apache.doris.nereids.trees.expressions.LessThanEqual;
+import org.apache.doris.nereids.trees.expressions.NamedExpression;
+import org.apache.doris.nereids.trees.expressions.Or;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
+import org.apache.doris.nereids.trees.expressions.WindowExpression;
+import org.apache.doris.nereids.trees.expressions.literal.IntegerLikeLiteral;
+import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.trees.plans.logical.LogicalEmptyRelation;
+import org.apache.doris.nereids.trees.plans.logical.LogicalPartitionTopN;
+import org.apache.doris.nereids.trees.plans.logical.LogicalWindow;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableSet;
+
+import java.util.List;
+import java.util.Set;
+import java.util.function.Predicate;
+
+/**
+ * Push down the 'filter' into the 'window'.
+ * It will convert the filter condition to the 'limit value' and push down
below the 'window'.
+ * But there are some restrictions, the details are explained below.
+ * For example:
+ * 'SELECT * FROM (
+ * SELECT *, ROW_NUMBER() OVER (ORDER BY b) AS row_number
+ * FROM t
+ * ) AS tt WHERE row_number <= 100;'
+ * The filter 'row_number <= 100' can be pushed down into the window operator.
+ * The following will demonstrate how the plan changes:
+ * Logical plan tree:
+ * any_node
+ * |
+ * filter (row_number <= 100)
+ * |
+ * window (PARTITION BY a ORDER BY b)
+ * |
+ * any_node
+ * transformed to:
+ * any_node
+ * |
+ * filter (row_number <= 100)
+ * |
+ * window (PARTITION BY a ORDER BY b)
+ * |
+ * partition_topn(PARTITION BY: a, ORDER BY b, Partition Limit:
100)
+ * |
+ * any_node
+ */
+
+public class PushdownFilterThroughWindow extends OneRewriteRuleFactory {
+
+ @Override
+ public Rule build() {
+ return logicalFilter(logicalWindow()).then(filter -> {
+ LogicalWindow<Plan> window = filter.child();
+
+ // We have already done such optimization rule, so just ignore it.
+ if (window.child(0) instanceof LogicalPartitionTopN) {
+ return filter;
+ }
+
+ // Check the window function. There are some restrictions for
window function:
+ // * The number of window function should be 1.
+ // * The window function should be one of the 'row_number()',
'rank()', 'dense_rank()'.
+ // * The window type should be 'ROW'.
+ // * The window frame should be 'UNBOUNDED' to 'CURRENT'.
+ // * The 'PARTITION' key and 'ORDER' key can not be empty at the
same time.
+ List<NamedExpression> windowExprs = window.getWindowExpressions();
+ if (windowExprs.size() != 1) {
+ return filter;
+ }
+ NamedExpression windowExpr = windowExprs.get(0);
+ if (windowExpr.children().size() != 1 || !(windowExpr.child(0)
instanceof WindowExpression)) {
+ return filter;
+ }
+
+ WindowExpression windowFunc = (WindowExpression)
windowExpr.child(0);
+ // Check the window function name.
+ if (!LogicalWindow.checkWindowFuncName4PartitionTopN(windowFunc)) {
+ return filter;
+ }
+
+ // Check the partition key and order key.
+ if
(!LogicalWindow.checkWindowPartitionAndOrderKey4PartitionTopN(windowFunc)) {
+ return filter;
+ }
+
+ // Check the window type and window frame.
+ if (!LogicalWindow.checkWindowFrame4PartitionTopN(windowFunc)) {
+ return filter;
+ }
+
+ // Check the filter conditions. Now, we currently only support
simple conditions of the form
+ // 'column </ <=/ = constant'. We will extract some related
conjuncts and do some check.
+ Set<Expression> conjuncts = filter.getConjuncts();
+ boolean existsORConditionsInConjuncts =
conjuncts.stream().anyMatch(this::existOR);
Review Comment:
why check this? i think we could push any one of conjunct in this set
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/rules/rewrite/logical/PushdownFilterThroughWindow.java:
##########
@@ -0,0 +1,204 @@
+// 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.rules.rewrite.logical;
+
+import org.apache.doris.nereids.rules.Rule;
+import org.apache.doris.nereids.rules.RuleType;
+import org.apache.doris.nereids.rules.rewrite.OneRewriteRuleFactory;
+import org.apache.doris.nereids.trees.expressions.BinaryOperator;
+import org.apache.doris.nereids.trees.expressions.EqualTo;
+import org.apache.doris.nereids.trees.expressions.ExprId;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.LessThan;
+import org.apache.doris.nereids.trees.expressions.LessThanEqual;
+import org.apache.doris.nereids.trees.expressions.NamedExpression;
+import org.apache.doris.nereids.trees.expressions.Or;
+import org.apache.doris.nereids.trees.expressions.SlotReference;
+import org.apache.doris.nereids.trees.expressions.WindowExpression;
+import org.apache.doris.nereids.trees.expressions.literal.IntegerLikeLiteral;
+import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.trees.plans.logical.LogicalEmptyRelation;
+import org.apache.doris.nereids.trees.plans.logical.LogicalPartitionTopN;
+import org.apache.doris.nereids.trees.plans.logical.LogicalWindow;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableSet;
+
+import java.util.List;
+import java.util.Set;
+import java.util.function.Predicate;
+
+/**
+ * Push down the 'filter' into the 'window'.
+ * It will convert the filter condition to the 'limit value' and push down
below the 'window'.
+ * But there are some restrictions, the details are explained below.
+ * For example:
+ * 'SELECT * FROM (
+ * SELECT *, ROW_NUMBER() OVER (ORDER BY b) AS row_number
+ * FROM t
+ * ) AS tt WHERE row_number <= 100;'
+ * The filter 'row_number <= 100' can be pushed down into the window operator.
+ * The following will demonstrate how the plan changes:
+ * Logical plan tree:
+ * any_node
+ * |
+ * filter (row_number <= 100)
+ * |
+ * window (PARTITION BY a ORDER BY b)
+ * |
+ * any_node
+ * transformed to:
+ * any_node
+ * |
+ * filter (row_number <= 100)
+ * |
+ * window (PARTITION BY a ORDER BY b)
+ * |
+ * partition_topn(PARTITION BY: a, ORDER BY b, Partition Limit:
100)
+ * |
+ * any_node
+ */
+
+public class PushdownFilterThroughWindow extends OneRewriteRuleFactory {
+
+ @Override
+ public Rule build() {
+ return logicalFilter(logicalWindow()).then(filter -> {
+ LogicalWindow<Plan> window = filter.child();
+
+ // We have already done such optimization rule, so just ignore it.
+ if (window.child(0) instanceof LogicalPartitionTopN) {
+ return filter;
+ }
+
+ // Check the window function. There are some restrictions for
window function:
+ // * The number of window function should be 1.
+ // * The window function should be one of the 'row_number()',
'rank()', 'dense_rank()'.
+ // * The window type should be 'ROW'.
+ // * The window frame should be 'UNBOUNDED' to 'CURRENT'.
+ // * The 'PARTITION' key and 'ORDER' key can not be empty at the
same time.
+ List<NamedExpression> windowExprs = window.getWindowExpressions();
Review Comment:
duplicate codes with PushdownLimit, do some abstract
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/StatsCalculator.java:
##########
@@ -115,6 +118,7 @@
*/
public class StatsCalculator extends DefaultPlanVisitor<Statistics, Void> {
public static double DEFAULT_AGGREGATE_RATIO = 0.5;
+ public static double DEFAULT_COLUMN_NDV_RATION = 0.5;
Review Comment:
```suggestion
public static double DEFAULT_COLUMN_NDV_RATIO = 0.5;
```
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalPartitionTopN.java:
##########
@@ -0,0 +1,166 @@
+// 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.trees.plans.logical;
+
+import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.LogicalProperties;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.OrderExpression;
+import org.apache.doris.nereids.trees.expressions.Slot;
+import org.apache.doris.nereids.trees.expressions.WindowExpression;
+import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.trees.plans.PlanType;
+import org.apache.doris.nereids.trees.plans.algebra.PartitionTopN;
+import org.apache.doris.nereids.trees.plans.visitor.PlanVisitor;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+
+import java.util.List;
+import java.util.Objects;
+import java.util.Optional;
+
+/**
+ * Logical partition-top-N plan.
+ */
+public class LogicalPartitionTopN<CHILD_TYPE extends Plan> extends
LogicalUnary<CHILD_TYPE> implements PartitionTopN {
+ private final Expression function;
+ private final List<Expression> partitionKeys;
+ private final List<OrderExpression> orderKeys;
+ private final Boolean hasGlobalLimit;
+ private final long partitionLimit;
+
+ public LogicalPartitionTopN(WindowExpression windowExpr, Boolean
hasGlobalLimit, long partitionLimit,
+ CHILD_TYPE child) {
+ this(windowExpr.getFunction(), windowExpr.getPartitionKeys(),
windowExpr.getOrderKeys(),
+ hasGlobalLimit, partitionLimit, Optional.empty(),
+ Optional.empty(), child);
+ }
+
+ public LogicalPartitionTopN(Expression function, List<Expression>
partitionKeys, List<OrderExpression> orderKeys,
+ Boolean hasGlobalLimit, long partitionLimit,
CHILD_TYPE child) {
+ this(function, partitionKeys, orderKeys, hasGlobalLimit,
partitionLimit,
+ Optional.empty(), Optional.empty(), child);
+ }
+
+ /**
+ * Constructor for LogicalPartitionTopN.
+ */
+ public LogicalPartitionTopN(Expression function, List<Expression>
partitionKeys, List<OrderExpression> orderKeys,
+ Boolean hasGlobalLimit, long partitionLimit,
Optional<GroupExpression> groupExpression,
Review Comment:
```suggestion
boolean hasGlobalLimit, long partitionLimit,
Optional<GroupExpression> groupExpression,
```
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/stats/StatsCalculator.java:
##########
@@ -464,6 +478,32 @@ private Statistics computeTopN(TopN topN) {
return stats.withRowCount(Math.min(stats.getRowCount(),
topN.getLimit()));
}
+ private Statistics computePartitionTopN(PartitionTopN partitionTopN) {
+ Statistics stats = groupExpression.childStatistics(0);
+ double rowCount = stats.getRowCount();
+ List<Expression> partitionKeys = partitionTopN.getPartitionKeys();
+ if (!partitionTopN.hasGlobalLimit() && !partitionKeys.isEmpty()) {
+ // If there is no global limit. So result for the cardinality
estimation is:
+ // NDV(partition key) * partitionLimit
+ Map<Expression, ColumnStatistic> childSlotToColumnStats =
stats.columnStatistics();
+ List<ColumnStatistic> partitionByKeyStats = partitionKeys.stream()
+ .filter(childSlotToColumnStats::containsKey)
+ .map(childSlotToColumnStats::get)
+ .filter(s -> !s.isUnKnown)
+ .collect(Collectors.toList());
+ if (partitionByKeyStats.isEmpty()) {
+ // all column stats are unknown, use default ratio
+ rowCount = rowCount * DEFAULT_COLUMN_NDV_RATION;
+ } else {
+ rowCount = Math.min(rowCount,
partitionByKeyStats.stream().map(s -> s.ndv)
+ .max(Double::compare).get());
+ }
+ } else {
+ rowCount = Math.min(rowCount, partitionTopN.getPartitionLimit());
+ }
+ return stats.withRowCount(rowCount);
Review Comment:
we only update row count? i think we should update column stats too,
@englefly
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalPartitionTopN.java:
##########
@@ -0,0 +1,166 @@
+// 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.trees.plans.logical;
+
+import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.LogicalProperties;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.OrderExpression;
+import org.apache.doris.nereids.trees.expressions.Slot;
+import org.apache.doris.nereids.trees.expressions.WindowExpression;
+import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.trees.plans.PlanType;
+import org.apache.doris.nereids.trees.plans.algebra.PartitionTopN;
+import org.apache.doris.nereids.trees.plans.visitor.PlanVisitor;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+
+import java.util.List;
+import java.util.Objects;
+import java.util.Optional;
+
+/**
+ * Logical partition-top-N plan.
+ */
+public class LogicalPartitionTopN<CHILD_TYPE extends Plan> extends
LogicalUnary<CHILD_TYPE> implements PartitionTopN {
+ private final Expression function;
+ private final List<Expression> partitionKeys;
+ private final List<OrderExpression> orderKeys;
+ private final Boolean hasGlobalLimit;
+ private final long partitionLimit;
+
+ public LogicalPartitionTopN(WindowExpression windowExpr, Boolean
hasGlobalLimit, long partitionLimit,
+ CHILD_TYPE child) {
+ this(windowExpr.getFunction(), windowExpr.getPartitionKeys(),
windowExpr.getOrderKeys(),
+ hasGlobalLimit, partitionLimit, Optional.empty(),
+ Optional.empty(), child);
+ }
+
+ public LogicalPartitionTopN(Expression function, List<Expression>
partitionKeys, List<OrderExpression> orderKeys,
+ Boolean hasGlobalLimit, long partitionLimit,
CHILD_TYPE child) {
+ this(function, partitionKeys, orderKeys, hasGlobalLimit,
partitionLimit,
+ Optional.empty(), Optional.empty(), child);
+ }
+
+ /**
+ * Constructor for LogicalPartitionTopN.
+ */
+ public LogicalPartitionTopN(Expression function, List<Expression>
partitionKeys, List<OrderExpression> orderKeys,
+ Boolean hasGlobalLimit, long partitionLimit,
Optional<GroupExpression> groupExpression,
+ Optional<LogicalProperties> logicalProperties,
CHILD_TYPE child) {
+ super(PlanType.LOGICAL_PARTITION_TOP_N, groupExpression,
logicalProperties, child);
+ this.function = function;
+ this.partitionKeys = ImmutableList.copyOf(partitionKeys);
+ this.orderKeys = ImmutableList.copyOf(orderKeys);
+ this.hasGlobalLimit = hasGlobalLimit;
+ this.partitionLimit = partitionLimit;
+ }
+
+ @Override
+ public List<Slot> computeOutput() {
+ return child().getOutput();
+ }
+
+ public Expression getFunction() {
+ return function;
+ }
Review Comment:
do we need put this method into interface PartitionTopN
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/logical/LogicalPartitionTopN.java:
##########
@@ -0,0 +1,166 @@
+// 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.trees.plans.logical;
+
+import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.properties.LogicalProperties;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.OrderExpression;
+import org.apache.doris.nereids.trees.expressions.Slot;
+import org.apache.doris.nereids.trees.expressions.WindowExpression;
+import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.trees.plans.PlanType;
+import org.apache.doris.nereids.trees.plans.algebra.PartitionTopN;
+import org.apache.doris.nereids.trees.plans.visitor.PlanVisitor;
+import org.apache.doris.nereids.util.Utils;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+
+import java.util.List;
+import java.util.Objects;
+import java.util.Optional;
+
+/**
+ * Logical partition-top-N plan.
+ */
+public class LogicalPartitionTopN<CHILD_TYPE extends Plan> extends
LogicalUnary<CHILD_TYPE> implements PartitionTopN {
+ private final Expression function;
Review Comment:
use an enum to instead of function
##########
fe/fe-core/src/main/java/org/apache/doris/planner/PartitionSortNode.java:
##########
Review Comment:
does this class copy from SortNode? i think we could only retain
constructor, toThrift, ...
all function use for Legacy planner could be removed.
--
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]
