[CALCITE-952] Organize applicable materializations in reversed topological order (Maryann Xue)
Project: http://git-wip-us.apache.org/repos/asf/calcite/repo Commit: http://git-wip-us.apache.org/repos/asf/calcite/commit/c48c3413 Tree: http://git-wip-us.apache.org/repos/asf/calcite/tree/c48c3413 Diff: http://git-wip-us.apache.org/repos/asf/calcite/diff/c48c3413 Branch: refs/heads/master Commit: c48c341392032a652c40ce129157deb73ab949d7 Parents: b82704f Author: maryannxue <[email protected]> Authored: Wed Nov 4 11:52:03 2015 -0800 Committer: Julian Hyde <[email protected]> Committed: Wed Nov 4 11:52:32 2015 -0800 ---------------------------------------------------------------------- .../calcite/plan/volcano/VolcanoPlanner.java | 36 +++-- .../calcite/test/MaterializationTest.java | 150 +++++++++++++------ 2 files changed, 125 insertions(+), 61 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/calcite/blob/c48c3413/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 53d6160..b6ccd28 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 @@ -73,6 +73,7 @@ import org.apache.calcite.util.graph.DefaultDirectedGraph; import org.apache.calcite.util.graph.DefaultEdge; import org.apache.calcite.util.graph.DirectedGraph; import org.apache.calcite.util.graph.Graphs; +import org.apache.calcite.util.graph.TopologicalOrderIterator; import com.google.common.base.Function; import com.google.common.base.Supplier; @@ -452,17 +453,18 @@ public class VolcanoPlanner extends AbstractRelOptPlanner { // and therefore we can deduce T2 uses Emps. DirectedGraph<List<String>, DefaultEdge> usesGraph = DefaultDirectedGraph.create(); + final Map<List<String>, RelOptMaterialization> qnameMap = new HashMap<>(); for (RelOptMaterialization materialization : materializations) { - if (materialization.table != null) { + // If materialization is a tile in a lattice, we will deal with it shortly. + if (materialization.table != null + && materialization.starTable == null) { + final List<String> qname = materialization.table.getQualifiedName(); + qnameMap.put(qname, materialization); for (RelOptTable usedTable : findTables(materialization.queryRel)) { - usesGraph.addVertex( - materialization.table.getQualifiedName()); - usesGraph.addVertex( - usedTable.getQualifiedName()); - usesGraph.addEdge( - materialization.table.getQualifiedName(), - usedTable.getQualifiedName()); + usesGraph.addVertex(qname); + usesGraph.addVertex(usedTable.getQualifiedName()); + usesGraph.addEdge(usedTable.getQualifiedName(), qname); } } } @@ -474,15 +476,11 @@ public class VolcanoPlanner extends AbstractRelOptPlanner { Graphs.makeImmutable(usesGraph); final Set<RelOptTable> queryTables = findTables(originalRoot); final List<RelOptMaterialization> applicableMaterializations = Lists.newArrayList(); - for (RelOptMaterialization materialization : materializations) { - if (materialization.starTable != null) { - // Materialization is a tile in a lattice. We will deal with it shortly. - continue; - } - if (materialization.table != null) { - if (usesTable(materialization.table, queryTables, frozenGraph)) { - applicableMaterializations.add(materialization); - } + for (List<String> qname : TopologicalOrderIterator.of(usesGraph)) { + RelOptMaterialization materialization = qnameMap.get(qname); + if (materialization != null + && usesTable(materialization.table, queryTables, frozenGraph)) { + applicableMaterializations.add(materialization); } } useMaterializations(originalRoot, applicableMaterializations); @@ -525,8 +523,8 @@ public class VolcanoPlanner extends AbstractRelOptPlanner { Graphs.FrozenGraph<List<String>, DefaultEdge> usesGraph) { for (RelOptTable queryTable : usedTables) { if (usesGraph.getShortestPath( - table.getQualifiedName(), - queryTable.getQualifiedName()) != null) { + queryTable.getQualifiedName(), + table.getQualifiedName()) != null) { return true; } } http://git-wip-us.apache.org/repos/asf/calcite/blob/c48c3413/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 b8c1442..87b72bc 100644 --- a/core/src/test/java/org/apache/calcite/test/MaterializationTest.java +++ b/core/src/test/java/org/apache/calcite/test/MaterializationTest.java @@ -34,14 +34,13 @@ 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 com.google.common.collect.Ordering; import org.junit.Ignore; import org.junit.Test; @@ -49,6 +48,7 @@ import org.junit.Test; import java.math.BigDecimal; import java.sql.ResultSet; import java.sql.SQLException; +import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Map; @@ -74,6 +74,14 @@ public class MaterializationTest { CalciteAssert.checkResultContains( "EnumerableTableScan(table=[[hr, locations]])"); + private static final Ordering<Iterable<String>> + CASE_INSENSITIVE_LIST_COMPARATOR = + Ordering.from(String.CASE_INSENSITIVE_ORDER).lexicographical(); + + private static final Ordering<Iterable<List<String>>> + CASE_INSENSITIVE_LIST_LIST_COMPARATOR = + CASE_INSENSITIVE_LIST_COMPARATOR.lexicographical(); + final JavaTypeFactoryImpl typeFactory = new JavaTypeFactoryImpl(RelDataTypeSystem.DEFAULT); final RexBuilder rexBuilder = new RexBuilder(typeFactory); @@ -899,68 +907,126 @@ public class MaterializationTest { + "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); - } + final String[][][] expectedNames = { + {{"hr", "emps"}, {"hr", "m0"}}, + {{"hr", "emps"}, {"hr", "m1"}}, + {{"hr", "m0"}, {"hr", "emps"}}, + {{"hr", "m0"}, {"hr", "m0"}}, + {{"hr", "m0"}, {"hr", "m1"}}, + {{"hr", "m1"}, {"hr", "emps"}}, + {{"hr", "m1"}, {"hr", "m0"}}, + {{"hr", "m1"}, {"hr", "m1"}}}; - @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<List<List<String>>> substitutedNames = new ArrayList<>(); + 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 TableNameVisitor().run(input)); + return null; + } + }) + .enableMaterializations(true) + .sameResultWithMaterializationsDisabled(); + Collections.sort(substitutedNames, CASE_INSENSITIVE_LIST_LIST_COMPARATOR); + assertThat(substitutedNames, is(list3(expectedNames))); + } finally { + Prepare.THREAD_TRIM.set(false); } + } + + @Test public void testMaterializationSubstitution2() { + String q = "select *\n" + + "from (select * from \"emps\" where \"empid\" < 300)\n" + + "join (select * from \"emps\" where \"empid\" < 200) using (\"empid\")"; + + final String[][][] expectedNames = { + {{"hr", "emps"}, {"hr", "m0"}}, + {{"hr", "emps"}, {"hr", "m1"}}, + {{"hr", "emps"}, {"hr", "m2"}}, + {{"hr", "m0"}, {"hr", "emps"}}, + {{"hr", "m0"}, {"hr", "m0"}}, + {{"hr", "m0"}, {"hr", "m1"}}, + {{"hr", "m0"}, {"hr", "m2"}}, + {{"hr", "m1"}, {"hr", "emps"}}, + {{"hr", "m1"}, {"hr", "m0"}}, + {{"hr", "m1"}, {"hr", "m1"}}, + {{"hr", "m1"}, {"hr", "m2"}}, + {{"hr", "m2"}, {"hr", "emps"}}, + {{"hr", "m2"}, {"hr", "m0"}}, + {{"hr", "m2"}, {"hr", "m1"}}, + {{"hr", "m2"}, {"hr", "m2"}}}; try { Prepare.THREAD_TRIM.set(true); MaterializationService.setThreadLocal(); - final List<Pair<String, String>> substitutedNames = Lists.newArrayList(); + final List<List<List<String>>> substitutedNames = new ArrayList<>(); CalciteAssert.that() .withMaterializations(JdbcTest.HR_MODEL, "m0", "select * from \"emps\" where \"empid\" < 300", - "m1", "select * from \"emps\" where \"empid\" < 600") + "m1", "select * from \"emps\" where \"empid\" < 600", + "m2", "select * from \"m1\"") .query(q) .withHook(Hook.SUB, new Function<RelNode, Void>() { public Void apply(RelNode input) { - substitutedNames.add(new SubstitutionVisitor().run(input)); + substitutedNames.add(new TableNameVisitor().run(input)); return null; } }) .enableMaterializations(true) .sameResultWithMaterializationsDisabled(); - Collections.sort(substitutedNames); - assertThat(substitutedNames, is(expectedNames)); + Collections.sort(substitutedNames, CASE_INSENSITIVE_LIST_LIST_COMPARATOR); + assertThat(substitutedNames, is(list3(expectedNames))); } finally { Prepare.THREAD_TRIM.set(false); } } + + private static <E> List<List<List<E>>> list3(E[][][] as) { + final ImmutableList.Builder<List<List<E>>> builder = + ImmutableList.builder(); + for (E[][] a : as) { + builder.add(list2(a)); + } + return builder.build(); + } + + private static <E> List<List<E>> list2(E[][] as) { + final ImmutableList.Builder<List<E>> builder = ImmutableList.builder(); + for (E[] a : as) { + builder.add(ImmutableList.copyOf(a)); + } + return builder.build(); + } + + /** + * Implementation of RelVisitor to extract substituted table names. + */ + private static class TableNameVisitor extends RelVisitor { + private List<List<String>> names = new ArrayList<>(); + + List<List<String>> run(RelNode input) { + go(input); + return names; + } + + @Override public void visit(RelNode node, int ordinal, RelNode parent) { + if (node instanceof TableScan) { + RelOptTable table = node.getTable(); + List<String> qName = table.getQualifiedName(); + names.add(qName); + } + super.visit(node, ordinal, parent); + } + } } // End MaterializationTest.java
