morrySnow commented on code in PR #12147: URL: https://github.com/apache/doris/pull/12147#discussion_r957241907
########## fe/fe-core/src/test/java/org/apache/doris/nereids/util/MemoValidator.java: ########## @@ -0,0 +1,109 @@ +// 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.util; + +import org.apache.doris.nereids.memo.Group; +import org.apache.doris.nereids.memo.GroupExpression; +import org.apache.doris.nereids.memo.GroupId; +import org.apache.doris.nereids.memo.Memo; +import org.apache.doris.nereids.trees.plans.Plan; + +import com.google.common.collect.Sets; +import org.junit.jupiter.api.Assertions; + +import java.util.IdentityHashMap; +import java.util.Map.Entry; +import java.util.Set; + +public class MemoValidator { Review Comment: please add some comment to explain what this validator check to ########## fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Memo.java: ########## @@ -129,91 +111,178 @@ public CascadesContext newCascadesContext(StatementContext statementContext) { } /** - * Insert groupExpression to target group. - * If group expression is already in memo and target group is not null, we merge two groups. - * If target is null, generate new group. - * If target is not null, add group expression to target group + * init memo by a first plan. + * @param plan first plan + * @return plan's corresponding group + */ + private Group init(Plan plan) { + Preconditions.checkArgument(!(plan instanceof GroupPlan), "Cannot init memo by a GroupPlan"); + Preconditions.checkArgument(!plan.getGroupExpression().isPresent(), + "Cannot init memo by a plan which contains a groupExpression"); + + // initialize children recursively + List<Group> childrenGroups = plan.children() + .stream() + .map(this::init) + .collect(ImmutableList.toImmutableList()); + + plan = replaceChildrenToGroupPlan(plan, childrenGroups); + GroupExpression newGroupExpression = new GroupExpression(plan, childrenGroups); + Group group = new Group(groupIdGenerator.getNextId(), newGroupExpression, plan.getLogicalProperties()); + + groups.put(group.getGroupId(), group); + if (groupExpressions.containsKey(newGroupExpression)) { + throw new IllegalStateException("groupExpression already exists in memo, maybe a bug"); + } + groupExpressions.put(newGroupExpression, newGroupExpression); + return group; + } + + /** + * add or replace the plan into the target group. * - * @param groupExpression groupExpression to insert - * @param target target group to insert groupExpression Review Comment: use `<pre>` to wrap the table ``` <pre> ... <pre/> ########## fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/Plan.java: ########## @@ -43,13 +44,26 @@ public interface Plan extends TreeNode<Plan> { LogicalProperties getLogicalProperties(); - default LogicalProperties computeLogicalProperties(Plan... inputs) { + boolean canResolve(); + + default boolean resolved() { + return !(getLogicalProperties() instanceof UnboundLogicalProperties); + } + + default boolean childrenResolved() { + return children() + .stream() + .map(Plan::getLogicalProperties) + .allMatch(p -> !(p instanceof UnboundLogicalProperties)); Review Comment: ```suggestion return children() .stream() .allMatch(Plan::resolved); ``` ########## fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Memo.java: ########## @@ -277,12 +346,172 @@ public void addEnforcerPlan(GroupExpression groupExpression, Group group) { groupExpression.setOwnerGroup(group); } + private CopyInResult rewriteByExistsPlan(Group targetGroup, Plan existsPlan) { Review Comment: ```suggestion private CopyInResult rewriteByExistedPlan(Group targetGroup, Plan existedPlan) { ``` ########## fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Memo.java: ########## @@ -277,12 +346,172 @@ public void addEnforcerPlan(GroupExpression groupExpression, Group group) { groupExpression.setOwnerGroup(group); } + private CopyInResult rewriteByExistsPlan(Group targetGroup, Plan existsPlan) { + GroupExpression existedLogicalExpression = existsPlan instanceof GroupPlan + ? ((GroupPlan) existsPlan).getGroup().getLogicalExpression() // get first logicalGroupExpression + : existsPlan.getGroupExpression().get(); + if (targetGroup != null) { + Group existedGroup = existedLogicalExpression.getOwnerGroup(); + // clear targetGroup, from exist group move all logical groupExpression + // and logicalProperties to target group + eliminateFromGroupAndMoveToTargetGroup(existedGroup, targetGroup, existsPlan.getLogicalProperties()); + } + return CopyInResult.of(false, existedLogicalExpression); + } + + private CopyInResult rewriteByNewGroupExpression(Group targetGroup, Plan newPlan, + GroupExpression newGroupExpression) { + if (targetGroup == null) { + // case 2: + // if not exist target group and not exist the same group expression, + // then create new group with the newGroupExpression + Group newGroup = new Group(groupIdGenerator.getNextId(), newGroupExpression, + newPlan.getLogicalProperties()); + groups.put(newGroup.getGroupId(), newGroup); + groupExpressions.put(newGroupExpression, newGroupExpression); + } else { + // case 3: + // if exist the target group, clear all origin group expressions in the + // existedExpression's owner group and reset logical properties, the + // newGroupExpression is the init logical group expression + reInitGroup(targetGroup, newGroupExpression, newPlan.getLogicalProperties()); + } + return CopyInResult.of(true, newGroupExpression); + } + + private CopyInResult rewriteByExistedGroupExpression(Group targetGroup, Plan existedPlan, + GroupExpression existedExpression, GroupExpression newExpression) { + if (targetGroup != null && !targetGroup.equals(existedExpression.getOwnerGroup())) { + // case 4: + existedExpression.propagateApplied(newExpression); + moveParentExpressionsReference(existedExpression.getOwnerGroup(), targetGroup); + recycleGroup(existedExpression.getOwnerGroup()); + reInitGroup(targetGroup, newExpression, existedPlan.getLogicalProperties()); + return CopyInResult.of(true, newExpression); + } else { + // case 5: + // if targetGroup is null or targetGroup equal to the existedExpression's ownerGroup, + // then recycle the temporary new group expression + recycleExpression(newExpression); + return CopyInResult.of(false, existedExpression); + } + } + + /** + * eliminate fromGroup, clear targetGroup, then move the logical group expressions in the fromGroup to the toGroup. + * + * the scenario is: + * ``` + * Group 1(project, the targetGroup) Group 1(logicalOlapScan, the targetGroup) + * | => + * Group 0(logicalOlapScan, the fromGroup) + * ``` + * + * we should recycle the group 0, and recycle all group expressions in group 1, then move the logicalOlapScan to + * the group 1, and reset logical properties of the group 1. + */ + private void eliminateFromGroupAndMoveToTargetGroup(Group fromGroup, Group targetGroup, + LogicalProperties logicalProperties) { + if (fromGroup == targetGroup) { + return; + } + // simple check targetGroup is the ancestors of the fromGroup, not check completely because of performance + if (fromGroup == root) { + throw new IllegalStateException( + "TargetGroup should be ancestors of fromGroup, but fromGroup is root. Maybe a bug"); + } + + List<GroupExpression> logicalExpressions = fromGroup.clearLogicalExpressions(); + recycleGroup(fromGroup); + + recycleLogicalExpressions(targetGroup); + recyclePhysicalExpressions(targetGroup); + + for (GroupExpression logicalExpression : logicalExpressions) { + targetGroup.addLogicalExpression(logicalExpression); + } + targetGroup.setLogicalProperties(logicalProperties); + } + + private void reInitGroup(Group group, GroupExpression initLogicalExpression, LogicalProperties logicalProperties) { + recycleLogicalExpressions(group); + recyclePhysicalExpressions(group); + + group.setLogicalProperties(logicalProperties); + group.addLogicalExpression(initLogicalExpression); + + // note: put newGroupExpression must behind recycle existedExpression(reInitGroup method), + // because existedExpression maybe equal to the newGroupExpression and recycle + // existedExpression will recycle newGroupExpression + groupExpressions.put(initLogicalExpression, initLogicalExpression); + } + private Plan replaceChildrenToGroupPlan(Plan plan, List<Group> childrenGroups) { + if (childrenGroups.isEmpty()) { + return plan; + } List<Plan> groupPlanChildren = childrenGroups.stream() .map(GroupPlan::new) .collect(ImmutableList.toImmutableList()); LogicalProperties logicalProperties = plan.getLogicalProperties(); return plan.withChildren(groupPlanChildren) .withLogicalProperties(Optional.of(logicalProperties)); } + + private void moveParentExpressionsReference(Group fromGroup, Group toGroup) { + for (GroupExpression parentGroupExpression : fromGroup.getParentGroupExpressions()) { + /* + * the scenarios that 'parentGroupExpression == toGroup': eliminate the root group. + * the fromGroup is group 1, the toGroup is group 2, we can not replace group2's + * groupExpressions reference the child group which is group 2 (reference itself). + * + * A(group 2) B(group 2) + * | | + * B(group 1) => C(group 0) + * | + * C(group 0) + */ + if (parentGroupExpression.getOwnerGroup() != toGroup) { + parentGroupExpression.replaceChild(fromGroup, toGroup); Review Comment: since group expression's equals and hashCode include children, if we update children list, we need to re-add it to groupExpressions map. ########## fe/fe-core/src/main/java/org/apache/doris/nereids/memo/GroupExpression.java: ########## @@ -181,13 +208,14 @@ public boolean equals(Object o) { return false; } GroupExpression that = (GroupExpression) o; - // if the plan is LogicalRelation or PhysicalRelation, this == that should be true, + // if the plan is UnboundRelation or LogicalRelation or PhysicalRelation, this == that should be true, // when if one relation appear in plan more than once, // we cannot distinguish them throw equals function, since equals function cannot use output info. - if (plan instanceof LogicalRelation || plan instanceof PhysicalRelation) { + if (plan instanceof UnboundRelation || plan instanceof LogicalRelation || plan instanceof PhysicalRelation) { return false; } - return children.equals(that.children) && plan.equals(that.plan); + return children.equals(that.children) && plan.equals(that.plan) + && plan.getLogicalProperties().equals(that.plan.getLogicalProperties()); Review Comment: if we could compare logical properties, Logical and Physical Relation do not need to compare with equal operator ########## fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/Plan.java: ########## @@ -43,13 +44,26 @@ public interface Plan extends TreeNode<Plan> { LogicalProperties getLogicalProperties(); - default LogicalProperties computeLogicalProperties(Plan... inputs) { + boolean canResolve(); Review Comment: should we use `bind` uniformly. i.e. `canBind()`, `bound()`, `childrenBound()` ########## fe/fe-core/src/test/java/org/apache/doris/nereids/util/PlanChecker.java: ########## @@ -69,36 +79,145 @@ public PlanChecker analyze(String sql) { public PlanChecker analyze(Plan plan) { this.cascadesContext = MemoTestUtils.createCascadesContext(connectContext, plan); this.cascadesContext.newAnalyzer().analyze(); + MemoValidator.validate(cascadesContext.getMemo()); return this; } public PlanChecker applyTopDown(RuleFactory rule) { cascadesContext.topDownRewrite(rule); + MemoValidator.validate(cascadesContext.getMemo()); + return this; + } + + + public PlanChecker applyTopDown(PatternMatcher patternMatcher) { + cascadesContext.topDownRewrite(new OneRewriteRuleFactory() { + @Override + public Rule build() { + return patternMatcher.toRule(RuleType.TEST_REWRITE); + } + }); + MemoValidator.validate(cascadesContext.getMemo()); return this; } public PlanChecker applyBottomUp(RuleFactory rule) { cascadesContext.bottomUpRewrite(rule); + MemoValidator.validate(cascadesContext.getMemo()); return this; } - public void matchesFromRoot(PatternDescriptor<? extends Plan> patternDesc) { + public PlanChecker applyBottomUp(PatternMatcher patternMatcher) { Review Comment: please add some use example or comment on these methods to explain what it is and how to use it ########## fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Memo.java: ########## @@ -277,12 +346,172 @@ public void addEnforcerPlan(GroupExpression groupExpression, Group group) { groupExpression.setOwnerGroup(group); } + private CopyInResult rewriteByExistsPlan(Group targetGroup, Plan existsPlan) { + GroupExpression existedLogicalExpression = existsPlan instanceof GroupPlan + ? ((GroupPlan) existsPlan).getGroup().getLogicalExpression() // get first logicalGroupExpression + : existsPlan.getGroupExpression().get(); + if (targetGroup != null) { + Group existedGroup = existedLogicalExpression.getOwnerGroup(); + // clear targetGroup, from exist group move all logical groupExpression + // and logicalProperties to target group + eliminateFromGroupAndMoveToTargetGroup(existedGroup, targetGroup, existsPlan.getLogicalProperties()); + } + return CopyInResult.of(false, existedLogicalExpression); + } + + private CopyInResult rewriteByNewGroupExpression(Group targetGroup, Plan newPlan, + GroupExpression newGroupExpression) { + if (targetGroup == null) { + // case 2: + // if not exist target group and not exist the same group expression, + // then create new group with the newGroupExpression + Group newGroup = new Group(groupIdGenerator.getNextId(), newGroupExpression, + newPlan.getLogicalProperties()); + groups.put(newGroup.getGroupId(), newGroup); + groupExpressions.put(newGroupExpression, newGroupExpression); + } else { + // case 3: + // if exist the target group, clear all origin group expressions in the + // existedExpression's owner group and reset logical properties, the + // newGroupExpression is the init logical group expression + reInitGroup(targetGroup, newGroupExpression, newPlan.getLogicalProperties()); + } + return CopyInResult.of(true, newGroupExpression); + } + + private CopyInResult rewriteByExistedGroupExpression(Group targetGroup, Plan existedPlan, + GroupExpression existedExpression, GroupExpression newExpression) { + if (targetGroup != null && !targetGroup.equals(existedExpression.getOwnerGroup())) { + // case 4: + existedExpression.propagateApplied(newExpression); + moveParentExpressionsReference(existedExpression.getOwnerGroup(), targetGroup); + recycleGroup(existedExpression.getOwnerGroup()); + reInitGroup(targetGroup, newExpression, existedPlan.getLogicalProperties()); + return CopyInResult.of(true, newExpression); + } else { + // case 5: + // if targetGroup is null or targetGroup equal to the existedExpression's ownerGroup, + // then recycle the temporary new group expression + recycleExpression(newExpression); + return CopyInResult.of(false, existedExpression); + } + } + + /** + * eliminate fromGroup, clear targetGroup, then move the logical group expressions in the fromGroup to the toGroup. + * + * the scenario is: + * ``` + * Group 1(project, the targetGroup) Group 1(logicalOlapScan, the targetGroup) + * | => + * Group 0(logicalOlapScan, the fromGroup) + * ``` + * + * we should recycle the group 0, and recycle all group expressions in group 1, then move the logicalOlapScan to + * the group 1, and reset logical properties of the group 1. + */ + private void eliminateFromGroupAndMoveToTargetGroup(Group fromGroup, Group targetGroup, + LogicalProperties logicalProperties) { + if (fromGroup == targetGroup) { + return; + } + // simple check targetGroup is the ancestors of the fromGroup, not check completely because of performance + if (fromGroup == root) { + throw new IllegalStateException( + "TargetGroup should be ancestors of fromGroup, but fromGroup is root. Maybe a bug"); + } + + List<GroupExpression> logicalExpressions = fromGroup.clearLogicalExpressions(); + recycleGroup(fromGroup); Review Comment: i do not really understand this. If we recycle from group, then all its logical group expression's children is recycled. Then we add this logical group expression to target. do we get a logical group expression with illegal children in target? ########## fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Memo.java: ########## @@ -277,12 +346,172 @@ public void addEnforcerPlan(GroupExpression groupExpression, Group group) { groupExpression.setOwnerGroup(group); } + private CopyInResult rewriteByExistsPlan(Group targetGroup, Plan existsPlan) { + GroupExpression existedLogicalExpression = existsPlan instanceof GroupPlan + ? ((GroupPlan) existsPlan).getGroup().getLogicalExpression() // get first logicalGroupExpression + : existsPlan.getGroupExpression().get(); + if (targetGroup != null) { + Group existedGroup = existedLogicalExpression.getOwnerGroup(); + // clear targetGroup, from exist group move all logical groupExpression + // and logicalProperties to target group + eliminateFromGroupAndMoveToTargetGroup(existedGroup, targetGroup, existsPlan.getLogicalProperties()); + } + return CopyInResult.of(false, existedLogicalExpression); + } + + private CopyInResult rewriteByNewGroupExpression(Group targetGroup, Plan newPlan, + GroupExpression newGroupExpression) { + if (targetGroup == null) { + // case 2: + // if not exist target group and not exist the same group expression, + // then create new group with the newGroupExpression + Group newGroup = new Group(groupIdGenerator.getNextId(), newGroupExpression, + newPlan.getLogicalProperties()); + groups.put(newGroup.getGroupId(), newGroup); + groupExpressions.put(newGroupExpression, newGroupExpression); + } else { + // case 3: + // if exist the target group, clear all origin group expressions in the + // existedExpression's owner group and reset logical properties, the + // newGroupExpression is the init logical group expression + reInitGroup(targetGroup, newGroupExpression, newPlan.getLogicalProperties()); + } + return CopyInResult.of(true, newGroupExpression); + } + + private CopyInResult rewriteByExistedGroupExpression(Group targetGroup, Plan existedPlan, Review Comment: existedPlan -> newPlan? ########## fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/JobContext.java: ########## @@ -19,22 +19,29 @@ import org.apache.doris.nereids.CascadesContext; import org.apache.doris.nereids.properties.PhysicalProperties; +import org.apache.doris.nereids.rules.RuleType; + +import com.google.common.collect.Maps; + +import java.util.Map; /** * Context for one job in Nereids' cascades framework. */ public class JobContext { - private final CascadesContext cascadesContext; - private final PhysicalProperties requiredProperties; - private double costUpperBound; + protected final CascadesContext cascadesContext; + protected final PhysicalProperties requiredProperties; + protected double costUpperBound; + + protected Map<RuleType, Integer> ruleInvokeTimes = Maps.newLinkedHashMap(); Review Comment: trace? good🚀 -- 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-unsubscr...@doris.apache.org For queries about this service, please contact Infrastructure at: us...@infra.apache.org --------------------------------------------------------------------- To unsubscribe, e-mail: commits-unsubscr...@doris.apache.org For additional commands, e-mail: commits-h...@doris.apache.org
