[CALCITE-890] Register all combinations of materialization substitutions (Maryann Xue)
Project: http://git-wip-us.apache.org/repos/asf/calcite/repo Commit: http://git-wip-us.apache.org/repos/asf/calcite/commit/5149568c Tree: http://git-wip-us.apache.org/repos/asf/calcite/tree/5149568c Diff: http://git-wip-us.apache.org/repos/asf/calcite/diff/5149568c Branch: refs/heads/master Commit: 5149568ce948f7ef2b2951ae99f1bd32c4cef07f Parents: b94f4d7 Author: maryannxue <[email protected]> Authored: Mon Nov 2 17:05:12 2015 -0800 Committer: Julian Hyde <[email protected]> Committed: Mon Nov 2 17:05:12 2015 -0800 ---------------------------------------------------------------------- .../MaterializedViewSubstitutionVisitor.java | 2 +- .../calcite/plan/SubstitutionVisitor.java | 239 +++++++++++++++++-- .../calcite/plan/volcano/VolcanoPlanner.java | 42 ++-- .../calcite/test/MaterializationTest.java | 77 ++++++ 4 files changed, 311 insertions(+), 49 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/calcite/blob/5149568c/core/src/main/java/org/apache/calcite/plan/MaterializedViewSubstitutionVisitor.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/plan/MaterializedViewSubstitutionVisitor.java b/core/src/main/java/org/apache/calcite/plan/MaterializedViewSubstitutionVisitor.java index 5c4ccdd..9a95c49 100644 --- a/core/src/main/java/org/apache/calcite/plan/MaterializedViewSubstitutionVisitor.java +++ b/core/src/main/java/org/apache/calcite/plan/MaterializedViewSubstitutionVisitor.java @@ -40,7 +40,7 @@ public class MaterializedViewSubstitutionVisitor extends SubstitutionVisitor { super(target_, query_, EXTENDED_RULES); } - public RelNode go(RelNode replacement_) { + public List<RelNode> go(RelNode replacement_) { return super.go(replacement_); } http://git-wip-us.apache.org/repos/asf/calcite/blob/5149568c/core/src/main/java/org/apache/calcite/plan/SubstitutionVisitor.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/plan/SubstitutionVisitor.java b/core/src/main/java/org/apache/calcite/plan/SubstitutionVisitor.java index b52dc8a..739c6ba 100644 --- a/core/src/main/java/org/apache/calcite/plan/SubstitutionVisitor.java +++ b/core/src/main/java/org/apache/calcite/plan/SubstitutionVisitor.java @@ -431,8 +431,33 @@ public class SubstitutionVisitor { return fromMutable(node); } - public RelNode go(RelNode replacement_) { - MutableRel replacement = toMutable(replacement_); + /** + * Returns a list of all possible rels that result from substituting the + * matched RelNode with the replacement RelNode within the query. + * + * <p>For example, the substitution result of A join B, while A and B + * are both a qualified match for replacement R, is R join B, R join R, + * A join R. + */ + public List<RelNode> go(RelNode replacement_) { + List<List<Replacement>> matches = go(toMutable(replacement_)); + if (matches.isEmpty()) { + return ImmutableList.of(); + } + List<RelNode> sub = Lists.newArrayList(); + sub.add(fromMutable(query.input)); + reverseSubstitute(query, matches, sub, 0, matches.size()); + return sub; + } + + /** + * Substitutes the query with replacement whenever possible but meanwhile + * keeps track of all the substitutions and their original rel before + * replacement, so that in later processing stage, the replacement can be + * recovered individually to produce a list of all possible rels with + * substitution in different places. + */ + private List<List<Replacement>> go(MutableRel replacement) { assert MutableRels.equalType( "target", target, "replacement", replacement, true); final List<MutableRel> queryDescendants = MutableRels.descendants(query); @@ -453,10 +478,27 @@ public class SubstitutionVisitor { } map.clear(); + final List<Replacement> attempted = Lists.newArrayList(); + List<List<Replacement>> substitutions = Lists.newArrayList(); + for (;;) { int count = 0; + MutableRel queryDescendant = query; outer: - for (MutableRel queryDescendant : queryDescendants) { + while (queryDescendant != null) { + for (Replacement r : attempted) { + if (queryDescendant == r.after) { + // This node has been replaced by previous iterations in the + // hope to match its ancestors, so the node itself should not + // be matched again. + queryDescendant = MutableRels.preOrderTraverseNext(queryDescendant); + continue outer; + } + } + final MutableRel next = MutableRels.preOrderTraverseNext(queryDescendant); + final MutableRel childOrNext = + queryDescendant.getInputs().isEmpty() + ? next : queryDescendant.getInputs().get(0); for (MutableRel targetDescendant : targetDescendants) { for (UnifyRule rule : applicableRules(queryDescendant, targetDescendant)) { @@ -466,6 +508,7 @@ public class SubstitutionVisitor { final UnifyResult result = rule.apply(call); if (result != null) { ++count; + attempted.add(new Replacement(result.call.query, result.result)); MutableRel parent = result.call.query.replaceInParent(result.result); // Replace previous equivalents with new equivalents, higher up @@ -477,19 +520,93 @@ public class SubstitutionVisitor { : Pair.of(result.result, result.call.query); equivalents.put(result.result, result.call.query); if (targetDescendant == target) { - MutableRels.replace(query, target, replacement); - return fromMutable(query.input); + // A real substitution happens. We purge the attempted + // replacement list and add them into substitution list. + // Meanwhile we stop matching the descendants and jump + // to the next subtree in pre-order traversal. + if (!target.equals(replacement)) { + Replacement r = MutableRels.replace( + query.input, target, copyMutable(replacement)); + assert r != null + : rule + "should have returned a result containing the target."; + attempted.add(r); + } + substitutions.add(ImmutableList.copyOf(attempted)); + attempted.clear(); + queryDescendant = next; + continue outer; } + // We will try walking the query tree all over again to see + // if there can be any substitutions after the replacement + // attempt. break outer; } } } } - } - if (count == 0) { - return null; - } + queryDescendant = childOrNext; + } + // Quit the entire loop if: + // 1) we have walked the entire query tree with one or more successful + // substitutions, thus count != 0 && attempted.isEmpty(); + // 2) we have walked the entire query tree but have made no replacement + // attempt, thus count == 0 && attempted.isEmpty(); + // 3) we had done some replacement attempt in a previous walk, but in + // this one we have not found any potential matches or substitutions, + // thus count == 0 && !attempted.isEmpty(). + if (count == 0 || attempted.isEmpty()) { + break; + } + } + if (!attempted.isEmpty()) { + // We had done some replacement attempt in the previous walk, but that + // did not lead to any substitutions in this walk, so we need to recover + // the replacement. + undoReplacement(attempted); + } + return substitutions; + } + + /** + * Represents a replacement action: before => after. + */ + private static class Replacement { + final MutableRel before; + final MutableRel after; + + Replacement(MutableRel before, MutableRel after) { + this.before = before; + this.after = after; + } + } + + private static void undoReplacement(List<Replacement> replacement) { + for (int i = replacement.size() - 1; i >= 0; i--) { + Replacement r = replacement.get(i); + r.after.replaceInParent(r.before); + } + } + + private static void redoReplacement(List<Replacement> replacement) { + for (Replacement r : replacement) { + r.before.replaceInParent(r.after); + } + } + + private static void reverseSubstitute(Holder query, + List<List<Replacement>> matches, List<RelNode> sub, + int replaceCount, int maxCount) { + if (matches.isEmpty()) { + return; } + final List<List<Replacement>> rem = matches.subList(1, matches.size()); + reverseSubstitute(query, rem, sub, replaceCount, maxCount); + undoReplacement(matches.get(0)); + if (++replaceCount < maxCount) { + sub.add(fromMutable(query.input)); + } + reverseSubstitute(query, rem, sub, replaceCount, maxCount); + redoReplacement(matches.get(0)); } private static List<RelNode> fromMutables(List<MutableRel> nodes) { @@ -535,6 +652,50 @@ public class SubstitutionVisitor { } } + private static List<MutableRel> copyMutables(List<MutableRel> nodes) { + return Lists.transform(nodes, + new Function<MutableRel, MutableRel>() { + public MutableRel apply(MutableRel mutableRel) { + return copyMutable(mutableRel); + } + }); + } + + private static MutableRel copyMutable(MutableRel node) { + switch (node.type) { + case SCAN: + return MutableScan.of((TableScan) ((MutableScan) node).rel); + case VALUES: + return MutableValues.of((Values) ((MutableValues) node).rel); + case PROJECT: + final MutableProject project = (MutableProject) node; + return MutableProject.of(project.rowType, + copyMutable(project.input), project.projects); + case FILTER: + final MutableFilter filter = (MutableFilter) node; + return MutableFilter.of(copyMutable(filter.input), filter.condition); + case AGGREGATE: + final MutableAggregate aggregate = (MutableAggregate) node; + return MutableAggregate.of(copyMutable(aggregate.input), + aggregate.indicator, aggregate.groupSet, aggregate.groupSets, + aggregate.aggCalls); + case SORT: + final MutableSort sort = (MutableSort) node; + return MutableSort.of(copyMutable(sort.input), sort.collation, + sort.offset, sort.fetch); + case UNION: + final MutableUnion union = (MutableUnion) node; + return MutableUnion.of(copyMutables(union.inputs), union.all); + case JOIN: + final MutableJoin join = (MutableJoin) node; + return MutableJoin.of(join.cluster, copyMutable(join.getLeft()), + copyMutable(join.getRight()), join.getCondition(), join.getJoinType(), + join.getVariablesStopped()); + default: + throw new AssertionError(node.deep()); + } + } + private UnifyResult matchRecurse(MutableRel target) { assert false; // not called final List<MutableRel> targetInputs = target.getInputs(); @@ -1711,6 +1872,10 @@ public class SubstitutionVisitor { @Override public void setInput(int ordinalInParent, MutableRel input) { inputs.set(ordinalInParent, input); + if (input != null) { + input.parent = this; + input.ordinalInParent = ordinalInParent; + } } @Override public List<MutableRel> getInputs() { @@ -1784,7 +1949,7 @@ public class SubstitutionVisitor { } if (input != null) { input.parent = this; - input.ordinalInParent = 0; + input.ordinalInParent = ordinalInParent; } } @@ -1857,6 +2022,20 @@ public class SubstitutionVisitor { variablesStopped); } + @Override public boolean equals(Object obj) { + return obj == this + || obj instanceof MutableJoin + && joinType == ((MutableJoin) obj).joinType + && condition.toString().equals( + ((MutableJoin) obj).condition.toString()) + && left.equals(((MutableJoin) obj).left) + && right.equals(((MutableJoin) obj).right); + } + + @Override public int hashCode() { + return Objects.hashCode(left, right, condition.toString(), joinType); + } + @Override public StringBuilder digest(StringBuilder buf) { return buf.append("Join(left: ").append(left) .append(", right:").append(right) @@ -1888,6 +2067,20 @@ public class SubstitutionVisitor { } } + public static MutableRel preOrderTraverseNext(MutableRel node) { + MutableRel parent = node.getParent(); + int ordinal = node.ordinalInParent + 1; + while (parent != null) { + if (parent.getInputs().size() > ordinal) { + return parent.getInputs().get(ordinal); + } + node = parent; + parent = node.getParent(); + ordinal = node.ordinalInParent + 1; + } + return null; + } + private static List<MutableRel> descendants(MutableRel query) { final List<MutableRel> list = new ArrayList<>(); descendantsRecurse(list, query); @@ -1914,28 +2107,30 @@ public class SubstitutionVisitor { * * <p>Assumes relational expressions (and their descendants) are not null. * Does not handle cycles. */ - public static void replace(MutableRel query, MutableRel find, + public static Replacement replace(MutableRel query, MutableRel find, MutableRel replace) { if (find.equals(replace)) { // Short-cut common case. - return; + return null; } assert equalType("find", find, "replace", replace, true); - replaceRecurse(query, find, replace); + return replaceRecurse(query, find, replace); } /** Helper for {@link #replace}. */ - private static void replaceRecurse(MutableRel query, MutableRel find, - MutableRel replace) { - final List<MutableRel> inputs = query.getInputs(); - for (int i = 0; i < inputs.size(); i++) { - MutableRel input = inputs.get(i); - if (input.equals(find)) { - query.setInput(i, replace); - } else { - replaceRecurse(input, find, replace); + private static Replacement replaceRecurse(MutableRel query, + MutableRel find, MutableRel replace) { + if (find.equals(query)) { + query.replaceInParent(replace); + return new Replacement(query, replace); + } + for (MutableRel input : query.getInputs()) { + Replacement r = replaceRecurse(input, find, replace); + if (r != null) { + return r; } } + return null; } /** Based on http://git-wip-us.apache.org/repos/asf/calcite/blob/5149568c/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoPlanner.java ---------------------------------------------------------------------- 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 4cc513a..53d6160 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 @@ -360,7 +360,7 @@ public class VolcanoPlanner extends AbstractRelOptPlanner { registerImpl(rel, root.set); } - private RelNode useMaterialization(RelNode root, + private List<RelNode> useMaterialization(RelNode root, RelOptMaterialization materialization, boolean firstRun) { // Try to rewrite the original root query in terms of the materialized // query. If that is possible, register the remnant query as equivalent @@ -369,10 +369,12 @@ public class VolcanoPlanner extends AbstractRelOptPlanner { // This call modifies originalRoot. Doesn't look like originalRoot should be mutable though. // Need to check. - RelNode sub = substitute(root, materialization); - if (sub != null) { - Hook.SUB.run(sub); - registerImpl(sub, this.root.set); + List<RelNode> sub = substitute(root, materialization); + if (!sub.isEmpty()) { + for (RelNode rel : sub) { + Hook.SUB.run(rel); + registerImpl(rel, this.root.set); + } return sub; } @@ -385,10 +387,10 @@ public class VolcanoPlanner extends AbstractRelOptPlanner { true); registerImpl(tableRel2, subset.set); } - return null; + return ImmutableList.of(); } - private RelNode substitute( + private List<RelNode> substitute( RelNode root, RelOptMaterialization materialization) { // First, if the materialization is in terms of a star table, rewrite // the query in terms of the star table. @@ -423,25 +425,13 @@ public class VolcanoPlanner extends AbstractRelOptPlanner { // Useful for big queries, e.g. // (t1 group by c1) join (t2 group by c2). private void useMaterializations(RelNode root, - List<RelOptMaterialization> materializations, boolean firstRun) { + List<RelOptMaterialization> materializations) { + List<RelNode> applied = Lists.newArrayList(root); for (RelOptMaterialization m : materializations) { - RelNode sub = useMaterialization(root, m, firstRun); - if (sub != null) { - useMaterializations(sub, materializations, false); - } else { - // Based on the assumption that a substitution itself won't trigger another - // substitution, if a materialization is not matched here it won't be useful - // in any subsequent matching for the current level of recursion or this level - // down. So we can safely remove the unmatched materialization from the remnant - // list for the current root. - List<RelOptMaterialization> newList = - Lists.newArrayListWithExpectedSize(materializations.size() - 1); - for (RelOptMaterialization elem : materializations) { - if (elem != m) { - newList.add(elem); - } - } - materializations = newList; + int count = applied.size(); + for (int i = 0; i < count; i++) { + List<RelNode> sub = useMaterialization(applied.get(i), m, i == 0); + applied.addAll(sub); } } } @@ -495,7 +485,7 @@ public class VolcanoPlanner extends AbstractRelOptPlanner { } } } - useMaterializations(originalRoot, applicableMaterializations, true); + useMaterializations(originalRoot, applicableMaterializations); // Use a lattice if the query uses at least the central (fact) table of the // lattice. http://git-wip-us.apache.org/repos/asf/calcite/blob/5149568c/core/src/test/java/org/apache/calcite/test/MaterializationTest.java ---------------------------------------------------------------------- diff --git a/core/src/test/java/org/apache/calcite/test/MaterializationTest.java b/core/src/test/java/org/apache/calcite/test/MaterializationTest.java index d65804e..b8c1442 100644 --- a/core/src/test/java/org/apache/calcite/test/MaterializationTest.java +++ b/core/src/test/java/org/apache/calcite/test/MaterializationTest.java @@ -18,8 +18,12 @@ package org.apache.calcite.test; import org.apache.calcite.jdbc.JavaTypeFactoryImpl; import org.apache.calcite.materialize.MaterializationService; +import org.apache.calcite.plan.RelOptTable; import org.apache.calcite.plan.SubstitutionVisitor; import org.apache.calcite.prepare.Prepare; +import org.apache.calcite.rel.RelNode; +import org.apache.calcite.rel.RelVisitor; +import org.apache.calcite.rel.core.TableScan; import org.apache.calcite.rel.type.RelDataType; import org.apache.calcite.rel.type.RelDataTypeSystem; import org.apache.calcite.rex.RexBuilder; @@ -27,14 +31,17 @@ import org.apache.calcite.rex.RexInputRef; import org.apache.calcite.rex.RexLiteral; import org.apache.calcite.rex.RexNode; import org.apache.calcite.rex.RexUtil; +import org.apache.calcite.runtime.Hook; import org.apache.calcite.sql.fun.SqlStdOperatorTable; import org.apache.calcite.util.JsonBuilder; +import org.apache.calcite.util.Pair; import org.apache.calcite.util.Util; import org.apache.commons.lang3.StringUtils; import com.google.common.base.Function; import com.google.common.collect.ImmutableList; +import com.google.common.collect.Lists; import org.junit.Ignore; import org.junit.Test; @@ -42,10 +49,12 @@ import org.junit.Test; import java.math.BigDecimal; import java.sql.ResultSet; import java.sql.SQLException; +import java.util.Collections; import java.util.List; import java.util.Map; import static org.hamcrest.CoreMatchers.equalTo; +import static org.hamcrest.CoreMatchers.is; import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertFalse; import static org.junit.Assert.assertThat; @@ -884,6 +893,74 @@ public class MaterializationTest { Prepare.THREAD_TRIM.set(false); } } + + @Test public void testMaterializationSubstitution() { + String q = "select *\n" + + "from (select * from \"emps\" where \"empid\" < 300)\n" + + "join (select * from \"emps\" where \"empid\" < 200) using (\"empid\")"; + + final List<Pair<String, String>> expectedNames = Lists.newArrayList(); + expectedNames.add(Pair.of("emps", "m0")); + expectedNames.add(Pair.of("emps", "m1")); + expectedNames.add(Pair.of("m0", "emps")); + expectedNames.add(Pair.of("m0", "m0")); + expectedNames.add(Pair.of("m0", "m1")); + expectedNames.add(Pair.of("m1", "emps")); + expectedNames.add(Pair.of("m1", "m0")); + expectedNames.add(Pair.of("m1", "m1")); + + /** + * Implementation of RelVisitor to extract substituted table names. + */ + class SubstitutionVisitor extends RelVisitor { + private String first; + private String second; + + Pair<String, String> run(RelNode input) { + go(input); + return Pair.of(first, second); + } + + @Override public void visit( + RelNode node, int ordinal, RelNode parent) { + if (node instanceof TableScan) { + RelOptTable table = node.getTable(); + List<String> qName = table.getQualifiedName(); + String name = qName.get(qName.size() - 1); + if (first == null) { + first = name; + } else { + second = name; + } + } + super.visit(node, ordinal, parent); + } + } + + try { + Prepare.THREAD_TRIM.set(true); + MaterializationService.setThreadLocal(); + final List<Pair<String, String>> substitutedNames = Lists.newArrayList(); + CalciteAssert.that() + .withMaterializations(JdbcTest.HR_MODEL, + "m0", "select * from \"emps\" where \"empid\" < 300", + "m1", "select * from \"emps\" where \"empid\" < 600") + .query(q) + .withHook(Hook.SUB, + new Function<RelNode, Void>() { + public Void apply(RelNode input) { + substitutedNames.add(new SubstitutionVisitor().run(input)); + return null; + } + }) + .enableMaterializations(true) + .sameResultWithMaterializationsDisabled(); + Collections.sort(substitutedNames); + assertThat(substitutedNames, is(expectedNames)); + } finally { + Prepare.THREAD_TRIM.set(false); + } + } } // End MaterializationTest.java
