You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@doris.apache.org by GitBox <gi...@apache.org> on 2022/05/30 07:28:29 UTC
[GitHub] [incubator-doris] EmmyMiao87 commented on a diff in pull request #9807: [Enhancement](Nereids)rewrite framework used in Memo
EmmyMiao87 commented on code in PR #9807:
URL: https://github.com/apache/incubator-doris/pull/9807#discussion_r884392628
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/cascades/OptimizePlanJob.java:
##########
@@ -33,7 +33,7 @@
/**
* Job to optimize {@link org.apache.doris.nereids.trees.plans.Plan} in {@link org.apache.doris.nereids.memo.Memo}.
*/
-public class OptimizePlanJob extends Job {
Review Comment:
The name of class should be 'OptimizeGroupExpr'
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/rewrite/RewriteTopDownJob.java:
##########
@@ -21,20 +21,64 @@
import org.apache.doris.nereids.jobs.Job;
import org.apache.doris.nereids.jobs.JobType;
import org.apache.doris.nereids.memo.Group;
+import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.pattern.GroupExpressionMatching;
+import org.apache.doris.nereids.rules.Rule;
+import org.apache.doris.nereids.trees.TreeNode;
+
+import com.google.common.base.Preconditions;
+
+import java.util.List;
+import java.util.Objects;
/**
* Top down job for rewrite, use pattern match.
*/
-public class RewriteTopDownJob extends Job {
+public class RewriteTopDownJob<NODE_TYPE extends TreeNode> extends Job<NODE_TYPE> {
private final Group group;
+ private final List<Rule<NODE_TYPE>> rules;
+ private final boolean childrenOptimized;
+
+ public RewriteTopDownJob(Group group, List<Rule<NODE_TYPE>> rules, PlannerContext context) {
+ this(group, rules, context, false);
+ }
- public RewriteTopDownJob(Group group, PlannerContext context) {
- super(JobType.TOP_DOWN_REWRITE, context);
- this.group = group;
+ private RewriteTopDownJob(Group group, List<Rule<NODE_TYPE>> rules,
+ PlannerContext context, boolean childrenOptimized) {
+ super(JobType.BOTTOM_UP_REWRITE, context);
Review Comment:
```suggestion
super(JobType.TOP_DOWN_REWRITE, context);
```
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/cascades/OptimizePlanJob.java:
##########
@@ -46,22 +46,20 @@ public void execute() {
List<Rule<Plan>> validRules = new ArrayList<>();
List<Rule<Plan>> explorationRules = getRuleSet().getExplorationRules();
List<Rule<Plan>> implementationRules = getRuleSet().getImplementationRules();
- prunedInvalidRules(groupExpression, explorationRules);
- prunedInvalidRules(groupExpression, implementationRules);
- validRules.addAll(explorationRules);
- validRules.addAll(implementationRules);
+ validRules.addAll(getValidRules(groupExpression, explorationRules));
+ validRules.addAll(getValidRules(groupExpression, implementationRules));
validRules.sort(Comparator.comparingInt(o -> o.getRulePromise().promise()));
- for (Rule rule : validRules) {
+ for (Rule<Plan> rule : validRules) {
pushTask(new ApplyRuleJob(groupExpression, rule, context));
// If child_pattern has any more children (i.e non-leaf), then we will explore the
// child before applying the rule. (assumes task pool is effectively a stack)
for (int i = 0; i < rule.getPattern().children().size(); ++i) {
Pattern childPattern = rule.getPattern().child(i);
- if (childPattern.arity() > 0) {
- Group childSet = groupExpression.getChildren().get(i);
- pushTask(new ExploreGroupJob(childSet, context));
+ if (childPattern.arity() > 0 && Pattern.FIXED.equals(childPattern)) {
Review Comment:
Should it be a non-Fixed pattern that requires explore group expr?
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/cascades/ExplorePlanJob.java:
##########
@@ -32,7 +32,7 @@
/**
* Job to explore {@link GroupExpression} in {@link org.apache.doris.nereids.memo.Memo}.
*/
-public class ExplorePlanJob extends Job {
Review Comment:
The name of class should be 'ExploreGroupExpr'
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/trees/Utils.java:
##########
@@ -0,0 +1,75 @@
+// 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;
+
+import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.operators.Operator;
+import org.apache.doris.nereids.operators.plans.logical.LogicalBinaryOperator;
+import org.apache.doris.nereids.operators.plans.logical.LogicalLeafOperator;
+import org.apache.doris.nereids.operators.plans.logical.LogicalUnaryOperator;
+import org.apache.doris.nereids.operators.plans.physical.PhysicalBinaryOperator;
+import org.apache.doris.nereids.operators.plans.physical.PhysicalLeafOperator;
+import org.apache.doris.nereids.operators.plans.physical.PhysicalUnaryOperator;
+import org.apache.doris.nereids.properties.LogicalProperties;
+import org.apache.doris.nereids.trees.plans.logical.LogicalBinary;
+import org.apache.doris.nereids.trees.plans.logical.LogicalLeaf;
+import org.apache.doris.nereids.trees.plans.logical.LogicalUnary;
+import org.apache.doris.nereids.trees.plans.physical.PhysicalBinary;
+import org.apache.doris.nereids.trees.plans.physical.PhysicalLeaf;
+import org.apache.doris.nereids.trees.plans.physical.PhysicalUnary;
+
+/**
+ * Utility class for creating trees.
+ */
+public class Utils {
+ /**
+ * Generate a {@link TreeNode} subclass from a {@link GroupExpression}.
+ *
+ * @param groupExpression source to generate TreeNode
+ * @return generated TreeNode subclass
+ */
+ public static TreeNode treeNodeWithoutChildren(GroupExpression groupExpression) {
+ Operator operator = groupExpression.getOperator();
+ LogicalProperties logicalProperties = groupExpression.getParent().getLogicalProperties();
+ if (operator instanceof LogicalLeafOperator) {
Review Comment:
There is no need to abstract a class because it needs to be classified.
(In my opinion)
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/cascades/ApplyRuleJob.java:
##########
@@ -53,20 +54,19 @@ public ApplyRuleJob(GroupExpression groupExpression, Rule<Plan> rule, PlannerCon
@Override
public void execute() throws AnalysisException {
- if (groupExpression.hasExplored(rule)) {
+ if (groupExpression.hasApplied(rule)) {
return;
}
// TODO: need to find all plan reference tree that match this pattern
Review Comment:
Remove this comment
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/pattern/GroupExpressionMatching.java:
##########
@@ -0,0 +1,130 @@
+// 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.pattern;
+
+import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.trees.TreeNode;
+import org.apache.doris.nereids.trees.Utils;
+
+import com.google.common.collect.Lists;
+
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Objects;
+
+/**
+ * Get all pattern matching subtree in query plan from a group expression.
+ */
+public class GroupExpressionMatching<NODE_TYPE extends TreeNode> implements Iterable<NODE_TYPE> {
+ private final Pattern pattern;
+ private final GroupExpression groupExpression;
+
+ public GroupExpressionMatching(Pattern pattern, GroupExpression groupExpression) {
+ this.pattern = Objects.requireNonNull(pattern);
+ this.groupExpression = Objects.requireNonNull(groupExpression);
+ }
+
+ @Override
+ public GroupExpressionIterator<NODE_TYPE> iterator() {
Review Comment:
Please add some example in comment.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/cascades/OptimizePlanJob.java:
##########
@@ -46,22 +46,20 @@ public void execute() {
List<Rule<Plan>> validRules = new ArrayList<>();
List<Rule<Plan>> explorationRules = getRuleSet().getExplorationRules();
List<Rule<Plan>> implementationRules = getRuleSet().getImplementationRules();
- prunedInvalidRules(groupExpression, explorationRules);
- prunedInvalidRules(groupExpression, implementationRules);
- validRules.addAll(explorationRules);
- validRules.addAll(implementationRules);
+ validRules.addAll(getValidRules(groupExpression, explorationRules));
Review Comment:
Even if the operator type of root does not match rule , the apply rule task will be generated as long as it has not been used.
Can this logic be optimized? For example, only generate tasks for rules that satisfy the conditions?
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/cascades/ApplyRuleJob.java:
##########
@@ -53,20 +54,19 @@ public ApplyRuleJob(GroupExpression groupExpression, Rule<Plan> rule, PlannerCon
@Override
public void execute() throws AnalysisException {
- if (groupExpression.hasExplored(rule)) {
+ if (groupExpression.hasApplied(rule)) {
return;
}
// TODO: need to find all plan reference tree that match this pattern
- PatternMatching patternMatching = new PatternMatching();
- for (Plan<?, ?> plan : patternMatching) {
- if (!rule.check(plan, context)) {
- continue;
- }
- List<Plan> newPlanList = rule.transform(plan, context);
- for (Plan newPlan : newPlanList) {
+ GroupExpressionMatching<Plan> groupExpressionMatching
+ = new GroupExpressionMatching(rule.getPattern(), groupExpression);
+ for (TreeNode treeNode : groupExpressionMatching) {
Review Comment:
```suggestion
for (Plan plan : groupExpressionMatching) {
```
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/memo/GroupExpression.java:
##########
@@ -17,42 +17,47 @@
package org.apache.doris.nereids.memo;
+import org.apache.doris.nereids.operators.Operator;
import org.apache.doris.nereids.rules.Rule;
import org.apache.doris.nereids.rules.RuleType;
-import org.apache.doris.nereids.trees.plans.Plan;
import com.clearspring.analytics.util.Lists;
import java.util.BitSet;
import java.util.List;
+import java.util.Objects;
/**
* Representation for group expression in cascades optimizer.
*/
public class GroupExpression {
private Group parent;
private List<Group> children;
- private final Plan<?, ?> plan;
+ private final Operator op;
private final BitSet ruleMasks;
private boolean statDerived;
- public GroupExpression(Plan<?, ?> plan) {
- this(plan, Lists.newArrayList());
+ public GroupExpression(Operator op) {
+ this(op, Lists.newArrayList());
}
/**
* Constructor for GroupExpression.
*
- * @param plan {@link Plan} to reference
+ * @param op {@link Operator} to reference
* @param children children groups in memo
*/
- public GroupExpression(Plan<?, ?> plan, List<Group> children) {
- this.plan = plan;
- this.children = children;
+ public GroupExpression(Operator op, List<Group> children) {
+ this.op = Objects.requireNonNull(op);
+ this.children = Objects.requireNonNull(children);
this.ruleMasks = new BitSet(RuleType.SENTINEL.ordinal());
this.statDerived = false;
}
+ public int arity() {
Review Comment:
Out of curiosity, is there any particular emphasis on naming the number of children `arity`?
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/pattern/GroupMatching.java:
##########
@@ -0,0 +1,105 @@
+// 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.pattern;
+
+import org.apache.doris.nereids.memo.Group;
+import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.operators.OperatorType;
+import org.apache.doris.nereids.trees.TreeNode;
+
+import com.google.common.collect.Lists;
+
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Objects;
+
+/**
+ * Get all pattern matching subtree in query plan from a group.
+ */
+public class GroupMatching<NODE_TYPE extends TreeNode> implements Iterable<NODE_TYPE> {
+ private final Pattern pattern;
+ private final Group group;
+
+ public GroupMatching(Pattern pattern, Group group) {
+ this.pattern = Objects.requireNonNull(pattern);
+ this.group = Objects.requireNonNull(group);
+ }
+
+ public Iterator<NODE_TYPE> iterator() {
+ return new GroupIterator<>(pattern, group);
+ }
+
+ /**
+ * Iterator to get all subtrees from a group.
+ */
+ public static class GroupIterator<NODE_TYPE extends TreeNode> implements Iterator<NODE_TYPE> {
Review Comment:
Please add example in comment
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Memo.java:
##########
@@ -17,65 +17,142 @@
package org.apache.doris.nereids.memo;
+import org.apache.doris.nereids.trees.TreeNode;
+import org.apache.doris.nereids.trees.expressions.Expression;
import org.apache.doris.nereids.trees.plans.Plan;
-import org.apache.doris.nereids.trees.plans.logical.LogicalPlan;
+import com.google.common.base.Preconditions;
import com.google.common.collect.Lists;
-import com.google.common.collect.Sets;
+import com.google.common.collect.Maps;
import java.util.List;
-import java.util.Set;
+import java.util.Map;
/**
* Representation for memo in cascades optimizer.
+ *
+ * @param <NODE_TYPE> should be {@link Plan} or {@link Expression}
*/
-public class Memo {
+public class Memo<NODE_TYPE extends TreeNode> {
private final List<Group> groups = Lists.newArrayList();
- private final Set<GroupExpression> groupExpressions = Sets.newHashSet();
- private Group rootSet;
+ // we could not use Set, because Set has no get method.
+ private final Map<GroupExpression, GroupExpression> groupExpressions = Maps.newHashMap();
+ private Group root;
- public void initialize(LogicalPlan plan) {
- rootSet = newGroupExpression(plan, null).getParent();
+ public void initialize(NODE_TYPE node) {
+ root = copyIn(node, null, false).getParent();
}
- public Group getRootSet() {
- return rootSet;
+ public Group getRoot() {
+ return root;
}
/**
- * Add plan to Memo.
+ * Add node to Memo.
*
- * @param plan {@link Plan} to be added
- * @param target target group to add plan. null to generate new Group
- * @return Reference of plan in Memo
+ * @param node {@link Plan} or {@link Expression} to be added
+ * @param target target group to add node. null to generate new Group
+ * @param rewrite whether to rewrite the node to the target group
+ * @return Reference of node in Memo
*/
- // TODO: need to merge PlanRefSet if new PlanRef is same with some one already in memo
- public GroupExpression newGroupExpression(Plan<?, ?> plan, Group target) {
- List<GroupExpression> childGroupExpr = Lists.newArrayList();
- for (Plan<?, ?> childrenPlan : plan.children()) {
- childGroupExpr.add(newGroupExpression(childrenPlan, null));
+ public GroupExpression copyIn(NODE_TYPE node, Group target, boolean rewrite) {
Review Comment:
Please add unit test for this function ~
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org