calcite-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jh...@apache.org
Subject [2/2] calcite git commit: [CALCITE-890] Register all combinations of materialization substitutions (Maryann Xue)
Date Tue, 03 Nov 2015 01:49:40 GMT
[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 <wei.xue@intel.com>
Authored: Mon Nov 2 17:05:12 2015 -0800
Committer: Julian Hyde <jhyde@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


Mime
View raw message