You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@calcite.apache.org by jc...@apache.org on 2015/11/11 13:25:45 UTC
[39/50] [abbrv] calcite git commit: [CALCITE-890] Register all
combinations of materialization substitutions (Maryann Xue)
[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/branch-release
Commit: 5149568ce948f7ef2b2951ae99f1bd32c4cef07f
Parents: b94f4d7
Author: maryannxue <we...@intel.com>
Authored: Mon Nov 2 17:05:12 2015 -0800
Committer: Julian Hyde <jh...@apache.org>
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