You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@calcite.apache.org by jh...@apache.org on 2021/03/01 00:42:09 UTC
[calcite] branch master updated (cd34e5d -> 52c1284)
This is an automated email from the ASF dual-hosted git repository.
jhyde pushed a change to branch master
in repository https://gitbox.apache.org/repos/asf/calcite.git.
discard cd34e5d [CALCITE-4514] When merging RelSets, fine-tune which set is merged into which, for efficiency (Botong Hunang)
new 52c1284 [CALCITE-4514] When merging RelSets, fine-tune which set is merged into which, for efficiency (Botong Huang)
This update added new revisions after undoing existing revisions.
That is to say, some revisions that were in the old version of the
branch are not in the new version. This situation occurs
when a user --force pushes a change and generates a repository
containing something like this:
* -- * -- B -- O -- O -- O (cd34e5d)
\
N -- N -- N refs/heads/master (52c1284)
You should already have received notification emails for all of the O
revisions, and so the following emails describe only the N revisions
from the common base, B.
Any revisions marked "omit" are not gone; other references still
refer to them. Any revisions marked "discard" are gone forever.
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
[calcite] 01/01: [CALCITE-4514] When merging RelSets,
fine-tune which set is merged into which, for efficiency (Botong Huang)
Posted by jh...@apache.org.
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
commit 52c1284d27f339303f341642f81fdf61852a2128
Author: Botong Huang <bo...@apache.org>
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 Huang)
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,