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 <sitnikov.vladi...@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()) {