This is an automated email from the ASF dual-hosted git repository.
jhyde pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/calcite.git
The following commit(s) were added to refs/heads/master by this push:
new cd34e5d [CALCITE-4514] When merging RelSets, fine-tune which set is
merged into which, for efficiency (Botong Hunang)
cd34e5d is described below
commit cd34e5dacfa43e3442029a05085f669377863033
Author: Botong Huang <[email protected]>
AuthorDate: Thu Feb 25 22:26:25 2021 -0800
[CALCITE-4514] When merging RelSets, fine-tune which set is merged into
which, for efficiency (Botong Hunang)
If one set is the parent of the other, merge into the child.
If both sets are parents of the other, or if neither set is
parent of the other, merge into the set that is more popular
(is referenced as child of more relational expressions), or
has more children, or is older. The last condition ensures
determinism.
Close apache/calcite#2358
---
.../calcite/plan/volcano/VolcanoPlanner.java | 65 ++++++++++++++++------
.../calcite/plan/volcano/VolcanoPlannerTest.java | 32 +++++++++++
2 files changed, 79 insertions(+), 18 deletions(-)
diff --git
a/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoPlanner.java
b/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoPlanner.java
index 8ee6c20..f9cea4c 100644
--- a/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoPlanner.java
+++ b/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoPlanner.java
@@ -1136,32 +1136,48 @@ public class VolcanoPlanner extends
AbstractRelOptPlanner {
return false;
}
- private RelSet merge(RelSet set, RelSet set2) {
- assert set != set2 : "pre: set != set2";
+ private RelSet merge(RelSet set1, RelSet set2) {
+ assert set1 != set2 : "pre: set != set2";
- // Find the root of set2's equivalence tree.
- set = equivRoot(set);
+ // Find the root of each set's equivalence tree.
+ set1 = equivRoot(set1);
set2 = equivRoot(set2);
- // Looks like set2 was already marked as equivalent to set. Nothing
- // to do.
- if (set2 == set) {
- return set;
+ // If set1 and set2 are equivalent, there's nothing to do.
+ if (set2 == set1) {
+ return set1;
}
// If necessary, swap the sets, so we're always merging the newer set
// into the older or merging parent set into child set.
- if (set2.getChildSets(this).contains(set)) {
- // No-op
- } else if (set.getChildSets(this).contains(set2)
- || set.id > set2.id) {
- RelSet t = set;
- set = set2;
+ final boolean swap;
+ final Set<RelSet> childrenOf1 = set1.getChildSets(this);
+ final Set<RelSet> childrenOf2 = set2.getChildSets(this);
+ final boolean set2IsParentOfSet1 = childrenOf2.contains(set1);
+ final boolean set1IsParentOfSet2 = childrenOf1.contains(set2);
+ if (set2IsParentOfSet1 && set1IsParentOfSet2) {
+ // There is a cycle of length 1; each set is the (direct) parent of the
+ // other. Swap so that we are merging into the larger, older set.
+ swap = isSmaller(set1, set2);
+ } else if (set2IsParentOfSet1) {
+ // set2 is a parent of set1. Do not swap. We want to merge set2 into set.
+ swap = false;
+ } else if (set1IsParentOfSet2) {
+ // set1 is a parent of set2. Swap, so that we merge set into set2.
+ swap = true;
+ } else {
+ // Neither is a parent of the other.
+ // Swap so that we are merging into the larger, older set.
+ swap = isSmaller(set1, set2);
+ }
+ if (swap) {
+ RelSet t = set1;
+ set1 = set2;
set2 = t;
}
// Merge.
- set.mergeWith(this, set2);
+ set1.mergeWith(this, set2);
if (root == null) {
throw new IllegalStateException("root must not be null");
@@ -1170,15 +1186,28 @@ public class VolcanoPlanner extends
AbstractRelOptPlanner {
// Was the set we merged with the root? If so, the result is the new
// root.
if (set2 == getSet(root)) {
- root = set.getOrCreateSubset(
+ root = set1.getOrCreateSubset(
root.getCluster(), root.getTraitSet(), root.isRequired());
ensureRootConverters();
}
if (ruleDriver != null) {
- ruleDriver.onSetMerged(set);
+ ruleDriver.onSetMerged(set1);
+ }
+ return set1;
+ }
+
+ /** Returns whether {@code set1} is less popular than {@code set2}
+ * (or smaller, or younger). If so, it will be more efficient to merge set1
+ * into set2 than set2 into set1. */
+ private boolean isSmaller(RelSet set1, RelSet set2) {
+ if (set1.parents.size() < set2.parents.size()) {
+ return true; // set1 is less popular than set2
+ }
+ if (set1.rels.size() < set2.rels.size()) {
+ return true; // set1 is smaller than set2
}
- return set;
+ return set1.id > set2.id; // true if set1 is younger than set2
}
static RelSet equivRoot(RelSet s) {
diff --git
a/core/src/test/java/org/apache/calcite/plan/volcano/VolcanoPlannerTest.java
b/core/src/test/java/org/apache/calcite/plan/volcano/VolcanoPlannerTest.java
index 645a878..21a3c3f 100644
--- a/core/src/test/java/org/apache/calcite/plan/volcano/VolcanoPlannerTest.java
+++ b/core/src/test/java/org/apache/calcite/plan/volcano/VolcanoPlannerTest.java
@@ -73,6 +73,7 @@ import static org.apache.calcite.test.Matchers.isLinux;
import static org.hamcrest.CoreMatchers.equalTo;
import static org.hamcrest.CoreMatchers.instanceOf;
+import static org.hamcrest.CoreMatchers.sameInstance;
import static org.hamcrest.MatcherAssert.assertThat;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertNotSame;
@@ -692,6 +693,37 @@ class VolcanoPlannerTest {
null);
}
+ /** Test case for
+ * <a
href="https://issues.apache.org/jira/browse/CALCITE-4514";>[CALCITE-4514]
+ * Fine tune the merge order of two RelSets</a>. When the merging RelSets,
+ * if they are both parents of each other (that is, there is a 1-cycle), we
+ * should merge the less popular/smaller/younger set into the more
+ * popular/bigger/older one. */
+ @Test void testSetMergeWithCycle() {
+ VolcanoPlanner planner = new VolcanoPlanner();
+ planner.addRelTraitDef(ConventionTraitDef.INSTANCE);
+ RelOptCluster cluster = newCluster(planner);
+
+ NoneLeafRel leafRel = new NoneLeafRel(cluster, "a");
+ NoneSingleRel singleRelA = new NoneSingleRel(cluster, leafRel);
+ NoneSingleRel singleRelB = new NoneSingleRel(cluster, singleRelA);
+
+ planner.setRoot(singleRelA);
+ RelSet setA = planner.ensureRegistered(singleRelA, null).getSet();
+ RelSet setB = planner.ensureRegistered(leafRel, null).getSet();
+
+ // Create the relSet dependency cycle, so that both sets are parent of each
+ // other.
+ planner.ensureRegistered(singleRelB, leafRel);
+
+ // trigger the set merge
+ planner.ensureRegistered(singleRelB, singleRelA);
+
+ // setA and setB have the same popularity (parentRels.size()).
+ // Since setB is larger than setA, setA should be merged into setB.
+ assertThat(setA.equivalentSet, sameInstance(setB));
+ }
+
private void checkEvent(
List<RelOptListener.RelEvent> eventList,
int iEvent,
