You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@calcite.apache.org by vl...@apache.org on 2019/02/13 19:27:42 UTC
[calcite] branch master updated: [CALCITE-2817] Make
CannotPlanException great
This is an automated email from the ASF dual-hosted git repository.
vladimirsitnikov 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 d64f60c [CALCITE-2817] Make CannotPlanException great
d64f60c is described below
commit d64f60cc513370cd409098f8ec997463329c1d6c
Author: Vladimir Sitnikov <si...@gmail.com>
AuthorDate: Fri Feb 1 20:40:00 2019 +0300
[CALCITE-2817] Make CannotPlanException great
This addresses the common cases for CannotPlanException: VolcanoPlanner would
try to identify and print explanations like "the convertsion from LogicalAggregate to enumerable is missing".
The change also adds VolcanoPlanner#toDot() method to dump planner state in a Graphviz-compatible format.
The state includes sets, subsets, rels. It prints active rule with references to the matched rels.
Color coding:
red subset means it has no rels (besides AbstractConverter) yet
blue (subset, rel) means it is best for its subset
dashed lines connect VolcanoRule with its operands
---
.../org/apache/calcite/plan/volcano/RelSubset.java | 154 +++++++++++++++-
.../calcite/plan/volcano/VolcanoPlanner.java | 204 +++++++++++++++++++--
.../calcite/plan/volcano/VolcanoRuleCall.java | 7 +-
3 files changed, 348 insertions(+), 17 deletions(-)
diff --git a/core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java b/core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java
index a2b185e..6accad3 100644
--- a/core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java
+++ b/core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java
@@ -28,9 +28,12 @@ import org.apache.calcite.rel.AbstractRelNode;
import org.apache.calcite.rel.RelNode;
import org.apache.calcite.rel.RelWriter;
import org.apache.calcite.rel.core.CorrelationId;
+import org.apache.calcite.rel.externalize.RelWriterImpl;
import org.apache.calcite.rel.metadata.RelMetadataQuery;
import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.sql.SqlExplainLevel;
import org.apache.calcite.util.Litmus;
+import org.apache.calcite.util.Pair;
import org.apache.calcite.util.Util;
import org.apache.calcite.util.trace.CalciteTrace;
@@ -40,9 +43,14 @@ import java.io.PrintWriter;
import java.io.StringWriter;
import java.util.ArrayList;
import java.util.Collection;
+import java.util.Comparator;
+import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
+import java.util.Map;
import java.util.Set;
+import java.util.function.Function;
+import java.util.stream.Collectors;
/**
* Subset of an equivalence class where all relational expressions have the
@@ -406,6 +414,75 @@ public class RelSubset extends AbstractRelNode {
//~ Inner Classes ----------------------------------------------------------
/**
+ * Identifies the leaf-most non-implementable nodes.
+ */
+ static class DeadEndFinder {
+ final Set<RelSubset> deadEnds = new HashSet<>();
+ // To save time
+ private final Set<RelNode> visitedNodes = new HashSet<>();
+ // For cycle detection
+ private final Set<RelNode> activeNodes = new HashSet<>();
+
+ private boolean visit(RelNode p) {
+ if (p instanceof RelSubset) {
+ visitSubset((RelSubset) p);
+ return false;
+ }
+ return visitRel(p);
+ }
+
+ private void visitSubset(RelSubset subset) {
+ RelNode cheapest = subset.getBest();
+ if (cheapest != null) {
+ // Subset is implementable, and we are looking for bad ones, so stop here
+ return;
+ }
+
+ boolean isEmpty = true;
+ for (RelNode rel : subset.getRels()) {
+ if (rel instanceof AbstractConverter) {
+ // Converters are not implementable
+ continue;
+ }
+ if (!activeNodes.add(rel)) {
+ continue;
+ }
+ boolean res = visit(rel);
+ isEmpty &= res;
+ activeNodes.remove(rel);
+ }
+ if (isEmpty) {
+ deadEnds.add(subset);
+ }
+ }
+
+ /**
+ * Returns true when input {@code RelNode} is cyclic.
+ */
+ private boolean visitRel(RelNode p) {
+ // If one of the inputs is in "active" set, that means the rel forms a cycle,
+ // then we just ignore it. Cyclic rels are not implementable.
+ for (RelNode oldInput : p.getInputs()) {
+ if (activeNodes.contains(oldInput)) {
+ return true;
+ }
+ }
+ // The same subset can be used multiple times (e.g. union all with the same inputs),
+ // so it is important to perform "contains" and "add" in different loops
+ activeNodes.addAll(p.getInputs());
+ for (RelNode oldInput : p.getInputs()) {
+ if (!visitedNodes.add(oldInput)) {
+ // We don't want to explore the same subset twice
+ continue;
+ }
+ visit(oldInput);
+ }
+ activeNodes.removeAll(p.getInputs());
+ return false;
+ }
+ }
+
+ /**
* Visitor which walks over a tree of {@link RelSet}s, replacing each node
* with the cheapest implementation of the expression.
*/
@@ -417,6 +494,14 @@ public class RelSubset extends AbstractRelNode {
this.planner = planner;
}
+ private static String traitDiff(RelTraitSet original, RelTraitSet desired) {
+ return Pair.zip(original, desired)
+ .stream()
+ .filter(p -> !p.left.satisfies(p.right))
+ .map(p -> p.left.getTraitDef().getSimpleName() + ": " + p.left + " -> " + p.right)
+ .collect(Collectors.joining(", ", "[", "]"));
+ }
+
public RelNode visit(
RelNode p,
int ordinal,
@@ -429,8 +514,73 @@ public class RelSubset extends AbstractRelNode {
// out why we reached impasse.
StringWriter sw = new StringWriter();
final PrintWriter pw = new PrintWriter(sw);
- pw.println("Node [" + subset.getDescription()
- + "] could not be implemented; planner state:\n");
+
+ pw.print("There are not enough rules to produce a node with desired properties");
+ RelTraitSet desiredTraits = subset.getTraitSet();
+ String sep = ": ";
+ for (RelTrait trait : desiredTraits) {
+ pw.print(sep);
+ pw.print(trait.getTraitDef().getSimpleName());
+ pw.print("=");
+ pw.print(trait);
+ sep = ", ";
+ }
+ pw.print(".");
+ DeadEndFinder finder = new DeadEndFinder();
+ finder.visit(subset);
+ if (finder.deadEnds.isEmpty()) {
+ pw.print(" All the inputs have relevant nodes, however the cost is still infinite.");
+ } else {
+ Map<String, Long> problemCounts =
+ finder.deadEnds.stream()
+ .filter(deadSubset -> deadSubset.getOriginal() != null)
+ .map(x -> x.getOriginal().getClass().getSimpleName()
+ + traitDiff(x.getOriginal().getTraitSet(), x.getTraitSet()))
+ .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
+ // Sort problems from most often to less often ones
+ String problems = problemCounts.entrySet().stream()
+ .sorted(Comparator.comparingLong(Map.Entry<String, Long>::getValue).reversed())
+ .map(e -> e.getKey() + (e.getValue() > 1 ? " (" + e.getValue() + " cases)" : ""))
+ .collect(Collectors.joining(", "));
+ pw.println();
+ pw.print("Missing conversion");
+ pw.print(finder.deadEnds.size() == 1 ? " is " : "s are ");
+ pw.print(problems);
+ pw.println();
+ if (finder.deadEnds.size() == 1) {
+ pw.print("There is 1 empty subset: ");
+ }
+ if (finder.deadEnds.size() > 1) {
+ pw.println("There are " + finder.deadEnds.size() + " empty subsets:");
+ }
+ int i = 0;
+ int rest = finder.deadEnds.size();
+ for (RelSubset deadEnd : finder.deadEnds) {
+ if (finder.deadEnds.size() > 1) {
+ pw.print("Empty subset ");
+ pw.print(i);
+ pw.print(": ");
+ }
+ pw.print(deadEnd);
+ pw.println(", the relevant part of the original plan is as follows");
+ RelNode original = deadEnd.getOriginal();
+ original.explain(
+ new RelWriterImpl(pw, SqlExplainLevel.EXPPLAN_ATTRIBUTES, true));
+ i++;
+ rest--;
+ if (rest > 0) {
+ pw.println();
+ }
+ if (i >= 10 && rest > 1) {
+ pw.print("The rest ");
+ pw.print(rest);
+ pw.println(" leafs are omitted.");
+ break;
+ }
+ }
+ }
+ pw.println();
+
planner.dump(pw);
pw.flush();
final String dump = sw.toString();
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 3a9d04d..cb88de3 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
@@ -44,6 +44,7 @@ import org.apache.calcite.rel.RelNode;
import org.apache.calcite.rel.RelVisitor;
import org.apache.calcite.rel.convert.Converter;
import org.apache.calcite.rel.convert.ConverterRule;
+import org.apache.calcite.rel.externalize.RelWriterImpl;
import org.apache.calcite.rel.metadata.JaninoRelMetadataProvider;
import org.apache.calcite.rel.metadata.RelMetadataProvider;
import org.apache.calcite.rel.metadata.RelMetadataQuery;
@@ -62,6 +63,7 @@ import org.apache.calcite.runtime.Hook;
import org.apache.calcite.sql.SqlExplainLevel;
import org.apache.calcite.util.Litmus;
import org.apache.calcite.util.Pair;
+import org.apache.calcite.util.PartiallyOrderedSet;
import org.apache.calcite.util.SaffronProperties;
import org.apache.calcite.util.Util;
@@ -76,6 +78,7 @@ import java.io.PrintWriter;
import java.io.StringWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
+import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
@@ -97,6 +100,10 @@ import java.util.regex.Pattern;
*/
public class VolcanoPlanner extends AbstractRelOptPlanner {
//~ Static fields/initializers ---------------------------------------------
+ private static final boolean DUMP_GRAPHVIZ =
+ Util.getBooleanProperty("calcite.volcano.dump.graphviz", true);
+ private static final boolean DUMP_SETS =
+ Util.getBooleanProperty("calcite.volcano.dump.sets", true);
protected static final double COST_IMPROVEMENT = .5;
@@ -213,12 +220,6 @@ public class VolcanoPlanner extends AbstractRelOptPlanner {
*/
RelOptListener listener;
- /**
- * Dump of the root relational expression, as it was before any rules were
- * applied. For debugging.
- */
- private String originalRootString;
-
private RelNode originalRoot;
/**
@@ -237,7 +238,7 @@ public class VolcanoPlanner extends AbstractRelOptPlanner {
final Map<RelNode, Provenance> provenanceMap = new HashMap<>();
- private final Deque<VolcanoRuleCall> ruleCallStack = new ArrayDeque<>();
+ final Deque<VolcanoRuleCall> ruleCallStack = new ArrayDeque<>();
/** Zero cost, according to {@link #costFactory}. Not necessarily a
* {@link org.apache.calcite.plan.volcano.VolcanoCost}. */
@@ -305,8 +306,6 @@ public class VolcanoPlanner extends AbstractRelOptPlanner {
if (this.originalRoot == null) {
this.originalRoot = rel;
}
- this.originalRootString =
- RelOptUtil.toString(root, SqlExplainLevel.ALL_ATTRIBUTES);
// Making a node the root changes its importance.
this.ruleQueue.recompute(this.root);
@@ -1157,8 +1156,32 @@ public class VolcanoPlanner extends AbstractRelOptPlanner {
public void dump(PrintWriter pw) {
pw.println("Root: " + root.getDescription());
pw.println("Original rel:");
- pw.println(originalRootString);
- pw.println("Sets:");
+
+ if (originalRoot != null) {
+ originalRoot.explain(
+ new RelWriterImpl(pw, SqlExplainLevel.ALL_ATTRIBUTES, false));
+ }
+ if (DUMP_SETS) {
+ pw.println();
+ pw.println("Sets:");
+ dumpSets(pw);
+ }
+ if (DUMP_GRAPHVIZ) {
+ pw.println();
+ pw.println("Graphviz:");
+ dumpGraphviz(pw);
+ }
+ }
+
+ public String toDot() {
+ StringWriter sw = new StringWriter();
+ PrintWriter pw = new PrintWriter(sw);
+ dumpGraphviz(pw);
+ pw.flush();
+ return sw.toString();
+ }
+
+ private void dumpSets(PrintWriter pw) {
Ordering<RelSet> ordering = Ordering.from(Comparator.comparingInt(o -> o.id));
for (RelSet set : ordering.immutableSortedCopy(allSets)) {
pw.println("Set#" + set.id
@@ -1206,7 +1229,162 @@ public class VolcanoPlanner extends AbstractRelOptPlanner {
}
}
}
- pw.println();
+ }
+
+ private void dumpGraphviz(PrintWriter pw) {
+ Ordering<RelSet> ordering = Ordering.from(Comparator.comparingInt(o -> o.id));
+ Set<RelNode> activeRels = new HashSet<>();
+ for (VolcanoRuleCall volcanoRuleCall : ruleCallStack) {
+ activeRels.addAll(Arrays.asList(volcanoRuleCall.rels));
+ }
+ pw.println("digraph G {");
+ pw.println("\troot [style=filled,label=\"Root\"];");
+ PartiallyOrderedSet<RelSubset> subsetPoset = new PartiallyOrderedSet<>(
+ (e1, e2) -> e1.getTraitSet().satisfies(e2.getTraitSet()));
+ Set<RelSubset> nonEmptySubsets = new HashSet<>();
+ for (RelSet set : ordering.immutableSortedCopy(allSets)) {
+ pw.print("\tsubgraph cluster");
+ pw.print(set.id);
+ pw.println("{");
+ pw.print("\t\tlabel=");
+ Util.printJavaString(pw, "Set " + set.id + " " + set.subsets.get(0).getRowType(), false);
+ pw.print(";\n");
+ for (RelNode rel : set.rels) {
+ String traits = "." + rel.getTraitSet().toString();
+ pw.print("\t\trel");
+ pw.print(rel.getId());
+ pw.print(" [label=");
+ RelMetadataQuery mq = rel.getCluster().getMetadataQuery();
+ Util.printJavaString(pw,
+ rel.getDescription().replace(traits, "")
+ + "\nrows=" + mq.getRowCount(rel) + ", cost=" + getCost(rel, mq), false);
+ RelSubset relSubset = getSubset(rel);
+ if (!(rel instanceof AbstractConverter)) {
+ nonEmptySubsets.add(relSubset);
+ }
+ if (relSubset.best == rel) {
+ pw.print(",color=blue");
+ }
+ if (activeRels.contains(rel)) {
+ pw.print(",style=dashed");
+ }
+ pw.print(",shape=box");
+ pw.println("]");
+ }
+
+ subsetPoset.clear();
+ for (RelSubset subset : set.subsets) {
+ subsetPoset.add(subset);
+ pw.print("\t\tsubset");
+ pw.print(subset.getId());
+ pw.print(" [label=");
+ Util.printJavaString(pw, subset.getDescription(), false);
+ boolean empty = !nonEmptySubsets.contains(subset);
+ if (empty) {
+ // We don't want to iterate over rels when we know the set is not empty
+ for (RelNode rel : subset.getRels()) {
+ if (!(rel instanceof AbstractConverter)) {
+ empty = false;
+ break;
+ }
+ }
+ if (empty) {
+ pw.print(",color=red");
+ }
+ }
+ if (activeRels.contains(subset)) {
+ pw.print(",style=dashed");
+ }
+ pw.print("]\n");
+ }
+
+ for (RelSubset subset : subsetPoset) {
+ for (RelSubset parent : subsetPoset.getChildren(subset)) {
+ pw.print("\t\tsubset");
+ pw.print(subset.getId());
+ pw.print(" -> subset");
+ pw.print(parent.getId());
+ pw.print(";");
+ }
+ }
+
+ pw.print("\t}\n");
+ }
+ // Note: it is important that all the links are declared AFTER declaration of the nodes
+ // Otherwise Graphviz creates nodes implicitly, and puts them into a wrong cluster
+ pw.print("\troot -> subset");
+ pw.print(root.getId());
+ pw.println(";");
+ for (RelSet set : ordering.immutableSortedCopy(allSets)) {
+ for (RelNode rel : set.rels) {
+ RelSubset relSubset = getSubset(rel);
+ pw.print("\tsubset");
+ pw.print(relSubset.getId());
+ pw.print(" -> rel");
+ pw.print(rel.getId());
+ if (relSubset.best == rel) {
+ pw.print("[color=blue]");
+ }
+ pw.print(";");
+ List<RelNode> inputs = rel.getInputs();
+ for (int i = 0; i < inputs.size(); i++) {
+ RelNode input = inputs.get(i);
+ pw.print(" rel");
+ pw.print(rel.getId());
+ pw.print(" -> ");
+ pw.print(input instanceof RelSubset ? "subset" : "rel");
+ pw.print(input.getId());
+ if (relSubset.best == rel || inputs.size() > 1) {
+ char sep = '[';
+ if (relSubset.best == rel) {
+ pw.print(sep);
+ pw.print("color=blue");
+ sep = ',';
+ }
+ if (inputs.size() > 1) {
+ pw.print(sep);
+ pw.print("label=\"");
+ pw.print(i);
+ pw.print("\"");
+ // sep = ',';
+ }
+ pw.print(']');
+ }
+ pw.print(";");
+ }
+ pw.println();
+ }
+ }
+
+ // Draw lines for current rules
+ for (VolcanoRuleCall ruleCall : ruleCallStack) {
+ pw.print("rule");
+ pw.print(ruleCall.id);
+ pw.print(" [style=dashed,label=");
+ Util.printJavaString(pw, ruleCall.rule.toString(), false);
+ pw.print("]");
+
+ RelNode[] rels = ruleCall.rels;
+ for (int i = 0; i < rels.length; i++) {
+ RelNode rel = rels[i];
+ pw.print(" rule");
+ pw.print(ruleCall.id);
+ pw.print(" -> ");
+ pw.print(rel instanceof RelSubset ? "subset" : "rel");
+ pw.print(rel.getId());
+ pw.print(" [style=dashed");
+ if (rels.length > 1) {
+ pw.print(",label=\"");
+ pw.print(i);
+ pw.print("\"");
+ }
+ pw.print("]");
+ pw.print(";");
+ }
+ pw.println();
+ }
+
+ pw.print("}");
}
/**
@@ -1754,9 +1932,7 @@ public class VolcanoPlanner extends AbstractRelOptPlanner {
RelNode rel,
RelNode equivRel,
VolcanoRuleCall ruleCall) {
- ruleCallStack.push(ruleCall);
ensureRegistered(rel, equivRel);
- ruleCallStack.pop();
}
//~ Inner Classes ----------------------------------------------------------
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 ac883f0..184b9f7 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
@@ -209,7 +209,12 @@ public class VolcanoRuleCall extends RelOptRuleCall {
this.generatedRelList = new ArrayList<>();
}
- getRule().onMatch(this);
+ volcanoPlanner.ruleCallStack.push(this);
+ try {
+ getRule().onMatch(this);
+ } finally {
+ volcanoPlanner.ruleCallStack.pop();
+ }
if (LOGGER.isDebugEnabled()) {
if (generatedRelList.isEmpty()) {