This is an automated email from the ASF dual-hosted git repository.
hyuan 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 0f7dcfb [CALCITE-3819] Prune parent RelNode when merging child RelSet
with parent RelSet
0f7dcfb is described below
commit 0f7dcfbffdf2e2405c835d22af78dac7124a728f
Author: Haisheng Yuan <[email protected]>
AuthorDate: Tue Feb 25 14:05:37 2020 -0800
[CALCITE-3819] Prune parent RelNode when merging child RelSet with parent
RelSet
Suppose we have 2 RelSets:
RelSet A: rel1
RelSet B: rel2
rel1 is the parent of rel2.
If there is a transformation rule that transform rel1 to rel2, we will merge
RelSet A and B. During merge process, we can safely prune rel1 to avoid
further
rule apply on rel1 and reduce search space, more importantly, avoid cyclic
reference.
---
.../org/apache/calcite/plan/volcano/RelSet.java | 44 +++++++++++++++++++++-
.../calcite/plan/volcano/VolcanoPlanner.java | 20 ++++++----
.../calcite/plan/volcano/VolcanoRuleCall.java | 16 ++++++++
3 files changed, 72 insertions(+), 8 deletions(-)
diff --git a/core/src/main/java/org/apache/calcite/plan/volcano/RelSet.java
b/core/src/main/java/org/apache/calcite/plan/volcano/RelSet.java
index 974e331..1651219 100644
--- a/core/src/main/java/org/apache/calcite/plan/volcano/RelSet.java
+++ b/core/src/main/java/org/apache/calcite/plan/volcano/RelSet.java
@@ -23,6 +23,7 @@ import org.apache.calcite.plan.RelTrait;
import org.apache.calcite.plan.RelTraitDef;
import org.apache.calcite.plan.RelTraitSet;
import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.convert.Converter;
import org.apache.calcite.rel.core.CorrelationId;
import org.apache.calcite.rel.metadata.RelMetadataQuery;
import org.apache.calcite.util.trace.CalciteTrace;
@@ -108,6 +109,25 @@ class RelSet {
}
/**
+ * Returns the child Relset for current set
+ */
+ public Set<RelSet> getChildSets(VolcanoPlanner planner) {
+ Set<RelSet> childSets = new HashSet<>();
+ for (RelNode node : this.rels) {
+ if (node instanceof Converter) {
+ continue;
+ }
+ for (RelNode child : node.getInputs()) {
+ RelSet childSet = planner.equivRoot(((RelSubset) child).getSet());
+ if (childSet.id != this.id) {
+ childSets.add(childSet);
+ }
+ }
+ }
+ return childSets;
+ }
+
+ /**
* @return all of the {@link RelNode}s contained by any subset of this set
* (does not include the subset objects themselves)
*/
@@ -326,7 +346,29 @@ class RelSet {
if (otherSubset.bestCost.isLt(subset.bestCost)) {
changedSubsets.put(subset, otherSubset.best);
}
- for (RelNode otherRel : otherSubset.getRels()) {
+ }
+
+ Set<RelNode> parentRels = new HashSet<>(parents);
+ for (RelNode otherRel : otherSet.rels) {
+ Double importance = planner.getImportance(otherRel);
+ if (importance != null && importance == 0d) {
+ continue;
+ }
+
+ boolean pruned = false;
+ if (parentRels.contains(otherRel)) {
+ // if otherRel is a enforcing operator e.g.
+ // Sort, Exchange, do not prune it.
+ if (otherRel.getInputs().size() != 1
+ || otherRel.getInput(0).getTraitSet()
+ .satisfies(otherRel.getTraitSet())) {
+ pruned = true;
+ }
+ }
+
+ if (pruned) {
+ planner.setImportance(otherRel, 0d);
+ } else {
planner.reregister(this, otherRel);
}
}
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 d3bb2ec..7b2a6ac 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
@@ -856,7 +856,7 @@ public class VolcanoPlanner extends AbstractRelOptPlanner {
if (equivRel != null) {
final RelSubset equivSubset = getSubset(equivRel);
if (subset.set != equivSubset.set) {
- merge(equivSubset.set, subset.set);
+ merge(subset.set, equivSubset.set, !(rel instanceof RelSubset));
}
}
result = subset;
@@ -1073,6 +1073,11 @@ public class VolcanoPlanner extends
AbstractRelOptPlanner {
}
}
+ Double getImportance(RelNode rel) {
+ assert rel != null;
+ return relImportances.get(rel);
+ }
+
/**
* Dumps the internal state of this VolcanoPlanner to a writer.
*
@@ -1398,7 +1403,7 @@ public class VolcanoPlanner extends AbstractRelOptPlanner
{
assert equivSubset.getTraitSet().equals(
subset.getTraitSet());
assert equivSubset.set != subset.set;
- merge(equivSubset.set, subset.set);
+ merge(equivSubset.set, subset.set, true);
}
}
}
@@ -1499,7 +1504,7 @@ public class VolcanoPlanner extends AbstractRelOptPlanner
{
return changeCount > 0;
}
- private RelSet merge(RelSet set, RelSet set2) {
+ private RelSet merge(RelSet set, RelSet set2, boolean enableSwap) {
assert set != set2 : "pre: set != set2";
// Find the root of set2's equivalence tree.
@@ -1514,7 +1519,7 @@ public class VolcanoPlanner extends AbstractRelOptPlanner
{
// If necessary, swap the sets, so we're always merging the newer set
// into the older.
- if (set.id > set2.id) {
+ if (enableSwap && set.id > set2.id) {
RelSet t = set;
set = set2;
set2 = t;
@@ -1536,7 +1541,7 @@ public class VolcanoPlanner extends AbstractRelOptPlanner
{
return set;
}
- private static RelSet equivRoot(RelSet s) {
+ static RelSet equivRoot(RelSet s) {
RelSet p = s; // iterates at twice the rate, to detect cycles
while (s.equivalentSet != null) {
p = forward2(s, p);
@@ -1652,7 +1657,7 @@ public class VolcanoPlanner extends AbstractRelOptPlanner
{
LOGGER.trace(
"Register #{} {} (and merge sets, because it is a conversion)",
rel.getId(), rel.getDigest());
- merge(set, childSet);
+ merge(set, childSet, true);
registerCount++;
// During the mergers, the child set may have changed, and since
@@ -1774,7 +1779,8 @@ public class VolcanoPlanner extends AbstractRelOptPlanner
{
&& (set != null)
&& (set.equivalentSet == null)) {
LOGGER.trace("Register #{} {}, and merge sets", subset.getId(), subset);
- merge(set, subset.set);
+ boolean enableSwap = !set.getChildSets(this).contains(subset.set);
+ merge(subset.set, set, enableSwap);
registerCount++;
}
return subset;
diff --git
a/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoRuleCall.java
b/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoRuleCall.java
index af5d1ed..6256d3e 100644
--- a/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoRuleCall.java
+++ b/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoRuleCall.java
@@ -123,6 +123,22 @@ public class VolcanoRuleCall extends RelOptRuleCall {
volcanoPlanner.listener.ruleProductionSucceeded(event);
}
+ for (int i = 0; i < rels.length; i++) {
+ if (rel == rels[i]) {
+ if (i == 0) {
+ return;
+ }
+ volcanoPlanner.setImportance(rels[0], 0d);
+ break;
+ }
+
+ final RelNode relCopy = rel;
+ if (rels[i].getInputs().stream().anyMatch(n -> n == relCopy)) {
+ volcanoPlanner.setImportance(rels[0], 0d);
+ break;
+ }
+ }
+
// Registering the root relational expression implicitly registers
// its descendants. Register any explicit equivalences first, so we
// don't register twice and cause churn.
