You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@doris.apache.org by hu...@apache.org on 2022/07/22 10:31:39 UTC
[doris] branch master updated: [feature] (Nereids) Merge memo group recursively (#11043)
This is an automated email from the ASF dual-hosted git repository.
huajianlan 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 34f328aa57 [feature] (Nereids) Merge memo group recursively (#11043)
34f328aa57 is described below
commit 34f328aa575c3fb2ab6131a7ab0ca7838c6d3b9e
Author: minghong <mi...@163.com>
AuthorDate: Fri Jul 22 18:31:32 2022 +0800
[feature] (Nereids) Merge memo group recursively (#11043)
In Memo.copyIn( plan, group1, isRewrite), one branch is that the plan is already recorded in Memo, and owned by group 'group2'. In such case, 'group1' should be merged with 'group2', because they are equivalent.
After merge, the upper level of 'group1', saying 'p1 = group1.getLogicalExpression().getOwnerGroup()' of 'group1', and that of 'group2', saying 'p2', are equivalent. We need to merge 'p1' and 'p2'. And this process is recursive.
---
.../java/org/apache/doris/nereids/memo/Group.java | 31 +++++++++++
.../java/org/apache/doris/nereids/memo/Memo.java | 21 ++++----
.../org/apache/doris/nereids/memo/MemoTest.java | 62 ++++++++++++++++++++++
3 files changed, 104 insertions(+), 10 deletions(-)
diff --git a/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Group.java b/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Group.java
index aa681c1ac0..4a85acb0b2 100644
--- a/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Group.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Group.java
@@ -265,4 +265,35 @@ public class Group {
public String toString() {
return "Group[" + groupId + "]";
}
+
+ /**
+ * move the ownerGroup of all logical expressions to target group
+ * if this.equals(target), do nothing.
+ * @param target the new owner group of expressions
+ */
+ public void moveLogicalExpressionOwnership(Group target) {
+ if (equals(target)) {
+ return;
+ }
+ for (GroupExpression expression : logicalExpressions) {
+ target.addGroupExpression(expression);
+ }
+ logicalExpressions.clear();
+ }
+
+ /**
+ * move the ownerGroup of all physical expressions to target group
+ * if this.equals(target), do nothing.
+ * @param target the new owner group of expressions
+ */
+ public void movePhysicalExpressionOwnership(Group target) {
+ if (equals(target)) {
+ return;
+ }
+ for (GroupExpression expression : physicalExpressions) {
+ target.addGroupExpression(expression);
+ }
+ physicalExpressions.clear();
+ }
+
}
diff --git a/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Memo.java b/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Memo.java
index 55a8e5ebcd..c6a42dee0d 100644
--- a/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Memo.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/nereids/memo/Memo.java
@@ -188,22 +188,23 @@ public class Memo {
children.set(i, destination);
}
}
- if (groupExpressions.containsKey(groupExpression)) {
- // TODO: need to merge group recursively
+ GroupExpression that = groupExpressions.get(groupExpression);
+ if (that != null && that.getOwnerGroup() != null
+ && !that.getOwnerGroup().equals(groupExpression.getOwnerGroup())) {
+ // remove groupExpression from its owner group to avoid adding it to that.getOwnerGroup()
+ // that.getOwnerGroup() already has this groupExpression.
+ Group ownerGroup = groupExpression.getOwnerGroup();
groupExpression.getOwnerGroup().removeGroupExpression(groupExpression);
+ mergeGroup(ownerGroup, that.getOwnerGroup());
} else {
groupExpressions.put(groupExpression, groupExpression);
}
}
- for (GroupExpression groupExpression : source.getLogicalExpressions()) {
- source.removeGroupExpression(groupExpression);
- destination.addGroupExpression(groupExpression);
+ if (!source.equals(destination)) {
+ source.moveLogicalExpressionOwnership(destination);
+ source.movePhysicalExpressionOwnership(destination);
+ groups.remove(source);
}
- for (GroupExpression groupExpression : source.getPhysicalExpressions()) {
- source.removeGroupExpression(groupExpression);
- destination.addGroupExpression(groupExpression);
- }
- groups.remove(source);
}
/**
diff --git a/fe/fe-core/src/test/java/org/apache/doris/nereids/memo/MemoTest.java b/fe/fe-core/src/test/java/org/apache/doris/nereids/memo/MemoTest.java
index d84a864fdb..187eaea8f8 100644
--- a/fe/fe-core/src/test/java/org/apache/doris/nereids/memo/MemoTest.java
+++ b/fe/fe-core/src/test/java/org/apache/doris/nereids/memo/MemoTest.java
@@ -18,6 +18,7 @@
package org.apache.doris.nereids.memo;
import org.apache.doris.nereids.analyzer.UnboundRelation;
+import org.apache.doris.nereids.trees.expressions.ExprId;
import org.apache.doris.nereids.trees.expressions.SlotReference;
import org.apache.doris.nereids.trees.plans.PlanType;
import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
@@ -56,4 +57,65 @@ public class MemoTest {
rootGroup.logicalExpressionsAt(0).child(0).logicalExpressionsAt(0).child(0).logicalExpressionsAt(0)
.getPlan().getType());
}
+
+ /**
+ * initial Memo status:
+ * group#1(project1)-->group#0(relationA)
+ * group#3(project2)-->group#2(relationB)
+ * group#4(project3)-->group#2(relationB)
+ * copy relationA into group#2
+ * after merge:
+ * group#1(project1)-->group#0(relationA, relationB)
+ * group#4(project3)-->group#0
+ * merging group#2 and group#0 recursively invoke merging group#3 and group#1 and merging group#4 and group#1
+ */
+ @Test
+ public void testMergeGroup() {
+ UnboundRelation relation1 = new UnboundRelation(Lists.newArrayList("A"));
+ LogicalProject project1 = new LogicalProject(
+ ImmutableList.of(new SlotReference(new ExprId(1), "name", StringType.INSTANCE, true, ImmutableList.of("test"))),
+ relation1
+ );
+
+ Memo memo = new Memo(project1);
+
+ UnboundRelation relation2 = new UnboundRelation(Lists.newArrayList("B"));
+ LogicalProject project2 = new LogicalProject(
+ ImmutableList.of(new SlotReference(new ExprId(1), "name", StringType.INSTANCE, true, ImmutableList.of("test"))),
+ relation2
+ );
+ memo.copyIn(project2, null, false);
+ Assert.assertEquals(4, memo.getGroups().size());
+
+ LogicalProject project3 = new LogicalProject(
+ ImmutableList.of(new SlotReference(new ExprId(1), "other", StringType.INSTANCE, true, ImmutableList.of("other"))),
+ relation2
+ );
+
+ memo.copyIn(project3, null, false);
+
+ //after copyIn, group#2 contains relationA and relationB
+ memo.copyIn(relation1, memo.getGroups().get(2), true);
+
+
+ Assert.assertEquals(3, memo.getGroups().size());
+ Group root = memo.getRoot();
+ Assert.assertEquals(1, root.getLogicalExpressions().size());
+ Assert.assertEquals(PlanType.LOGICAL_PROJECT,
+ root.logicalExpressionsAt(0).getPlan().getType());
+ GroupExpression rootExpression = root.logicalExpressionsAt(0);
+ Assert.assertEquals(1, rootExpression.children().size());
+ //two expressions: relationA and relationB
+ Assert.assertEquals(2, rootExpression.child(0).getLogicalExpressions().size());
+ GroupExpression childExpression = rootExpression.child(0).logicalExpressionsAt(0);
+ Assert.assertEquals(PlanType.LOGICAL_UNBOUND_RELATION,
+ childExpression.getPlan().getType());
+
+ Group groupProjct3 = memo.getGroups().get(2); //group for project3
+ Group groupRelation = memo.getGroups().get(0); //group for relation
+ //group0 is child of group4
+ Assert.assertEquals(groupRelation, groupProjct3.logicalExpressionsAt(0).child(0));
+ Assert.assertEquals(1, groupProjct3.getLogicalExpressions().size());
+ Assert.assertEquals(1, groupProjct3.logicalExpressionsAt(0).children().size());
+ }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org