Repository: calcite Updated Branches: refs/heads/master d2368327e -> 6f07293a3
[CALCITE-1767] Fix join/aggregate rewriting rule when same table is referenced more than once Project: http://git-wip-us.apache.org/repos/asf/calcite/repo Commit: http://git-wip-us.apache.org/repos/asf/calcite/commit/6f07293a Tree: http://git-wip-us.apache.org/repos/asf/calcite/tree/6f07293a Diff: http://git-wip-us.apache.org/repos/asf/calcite/diff/6f07293a Branch: refs/heads/master Commit: 6f07293a3843c8790af9c028b2962fd8a0512db9 Parents: d236832 Author: Jesus Camacho Rodriguez <[email protected]> Authored: Fri Apr 28 10:53:30 2017 +0100 Committer: Jesus Camacho Rodriguez <[email protected]> Committed: Fri Apr 28 10:53:50 2017 +0100 ---------------------------------------------------------------------- .../rel/metadata/RelMdAllPredicates.java | 131 +++++++++++++++---- .../rel/rules/AbstractMaterializedViewRule.java | 54 ++++---- .../apache/calcite/rex/RexTableInputRef.java | 6 +- .../java/org/apache/calcite/rex/RexUtil.java | 16 +++ .../calcite/test/MaterializationTest.java | 42 ++++++ .../apache/calcite/test/RelMetadataTest.java | 55 ++++++++ 6 files changed, 255 insertions(+), 49 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/calcite/blob/6f07293a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdAllPredicates.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdAllPredicates.java b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdAllPredicates.java index 616c429..f5520cb 100644 --- a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdAllPredicates.java +++ b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdAllPredicates.java @@ -35,12 +35,23 @@ import org.apache.calcite.rex.RexBuilder; import org.apache.calcite.rex.RexInputRef; import org.apache.calcite.rex.RexNode; import org.apache.calcite.rex.RexTableInputRef; +import org.apache.calcite.rex.RexTableInputRef.RelTableRef; +import org.apache.calcite.rex.RexUtil; import org.apache.calcite.util.BuiltInMethod; import org.apache.calcite.util.ImmutableBitSet; import org.apache.calcite.util.Util; +import com.google.common.base.Function; +import com.google.common.collect.HashMultimap; +import com.google.common.collect.Iterables; +import com.google.common.collect.Lists; +import com.google.common.collect.Multimap; + +import java.util.Collection; +import java.util.HashMap; import java.util.LinkedHashMap; import java.util.LinkedHashSet; +import java.util.List; import java.util.Map; import java.util.Set; @@ -152,10 +163,8 @@ public class RelMdAllPredicates final RexBuilder rexBuilder = join.getCluster().getRexBuilder(); final RexNode pred = join.getCondition(); - final RelNode leftInput = join.getLeft(); - final RelNode rightInput = join.getRight(); - final int nLeftColumns = leftInput.getRowType().getFieldList().size(); + final Multimap<List<String>, RelTableRef> qualifiedNamesToRefs = HashMultimap.create(); RelOptPredicateList newPreds = RelOptPredicateList.EMPTY; for (RelNode input : join.getInputs()) { final RelOptPredicateList inputPreds = mq.getAllPredicates(input); @@ -163,7 +172,45 @@ public class RelMdAllPredicates // Bail out return null; } - newPreds = newPreds.union(rexBuilder, inputPreds); + // If it does not contain table references, nothing needs to be done + if (!RexUtil.containsTableInputRef(inputPreds.pulledUpPredicates)) { + newPreds = newPreds.union(rexBuilder, inputPreds); + continue; + } + // Gather table references + final Set<RelTableRef> tableRefs = mq.getTableReferences(input); + if (input == join.getLeft()) { + // Left input references remain unchanged + for (RelTableRef leftRef : tableRefs) { + qualifiedNamesToRefs.put(leftRef.getQualifiedName(), leftRef); + } + newPreds = newPreds.union(rexBuilder, inputPreds); + } else { + // Right input references might need to be updated if there are table name + // clashes with left input + final Map<RelTableRef, RelTableRef> currentTablesMapping = new HashMap<>(); + for (RelTableRef rightRef : tableRefs) { + int shift = 0; + Collection<RelTableRef> lRefs = qualifiedNamesToRefs.get( + rightRef.getQualifiedName()); + if (lRefs != null) { + shift = lRefs.size(); + } + currentTablesMapping.put(rightRef, + RelTableRef.of(rightRef.getTable(), shift + rightRef.getEntityNumber())); + } + final List<RexNode> updatedPreds = Lists.newArrayList( + Iterables.transform( + inputPreds.pulledUpPredicates, + new Function<RexNode, RexNode>() { + @Override public RexNode apply(RexNode e) { + return RexUtil.swapTableReferences(rexBuilder, e, currentTablesMapping); + } + } + )); + newPreds = newPreds.union(rexBuilder, + RelOptPredicateList.of(rexBuilder, updatedPreds)); + } } // Extract input fields referenced by Join condition @@ -175,27 +222,14 @@ public class RelMdAllPredicates // Infer column origin expressions for given references final Map<RexInputRef, Set<RexNode>> mapping = new LinkedHashMap<>(); for (int idx : inputFieldsUsed) { - if (idx < nLeftColumns) { - final RexInputRef inputRef = RexInputRef.of(idx, leftInput.getRowType().getFieldList()); - final Set<RexNode> originalExprs = mq.getExpressionLineage(leftInput, inputRef); - if (originalExprs == null) { - // Bail out - return null; - } - final RexInputRef ref = RexInputRef.of(idx, join.getRowType().getFieldList()); - mapping.put(ref, originalExprs); - } else { - // Right input. - final RexInputRef inputRef = RexInputRef.of(idx - nLeftColumns, - rightInput.getRowType().getFieldList()); - final Set<RexNode> originalExprs = mq.getExpressionLineage(rightInput, inputRef); - if (originalExprs == null) { - // Bail out - return null; - } - final RexInputRef ref = RexInputRef.of(idx, join.getRowType().getFieldList()); - mapping.put(ref, originalExprs); + final RexInputRef inputRef = RexInputRef.of(idx, join.getRowType().getFieldList()); + final Set<RexNode> originalExprs = mq.getExpressionLineage(join, inputRef); + if (originalExprs == null) { + // Bail out + return null; } + final RexInputRef ref = RexInputRef.of(idx, join.getRowType().getFieldList()); + mapping.put(ref, originalExprs); } // Replace with new expressions and return union of predicates @@ -217,14 +251,59 @@ public class RelMdAllPredicates public RelOptPredicateList getAllPredicates(Union union, RelMetadataQuery mq) { final RexBuilder rexBuilder = union.getCluster().getRexBuilder(); + final Multimap<List<String>, RelTableRef> qualifiedNamesToRefs = HashMultimap.create(); RelOptPredicateList newPreds = RelOptPredicateList.EMPTY; - for (RelNode input : union.getInputs()) { + for (int i = 0; i < union.getInputs().size(); i++) { + final RelNode input = union.getInput(i); final RelOptPredicateList inputPreds = mq.getAllPredicates(input); if (inputPreds == null) { // Bail out return null; } - newPreds = newPreds.union(rexBuilder, inputPreds); + // If it does not contain table references, nothing needs to be done + if (!RexUtil.containsTableInputRef(inputPreds.pulledUpPredicates)) { + newPreds = newPreds.union(rexBuilder, inputPreds); + continue; + } + // Gather table references + final Set<RelTableRef> tableRefs = mq.getTableReferences(input); + if (i == 0) { + // Left input references remain unchanged + for (RelTableRef leftRef : tableRefs) { + qualifiedNamesToRefs.put(leftRef.getQualifiedName(), leftRef); + } + newPreds = newPreds.union(rexBuilder, inputPreds); + } else { + // Right input references might need to be updated if there are table name + // clashes with left input + final Map<RelTableRef, RelTableRef> currentTablesMapping = new HashMap<>(); + for (RelTableRef rightRef : tableRefs) { + int shift = 0; + Collection<RelTableRef> lRefs = qualifiedNamesToRefs.get( + rightRef.getQualifiedName()); + if (lRefs != null) { + shift = lRefs.size(); + } + currentTablesMapping.put(rightRef, + RelTableRef.of(rightRef.getTable(), shift + rightRef.getEntityNumber())); + } + // Add to existing qualified names + for (RelTableRef newRef : currentTablesMapping.values()) { + qualifiedNamesToRefs.put(newRef.getQualifiedName(), newRef); + } + // Update preds + final List<RexNode> updatedPreds = Lists.newArrayList( + Iterables.transform( + inputPreds.pulledUpPredicates, + new Function<RexNode, RexNode>() { + @Override public RexNode apply(RexNode e) { + return RexUtil.swapTableReferences(rexBuilder, e, currentTablesMapping); + } + } + )); + newPreds = newPreds.union(rexBuilder, + RelOptPredicateList.of(rexBuilder, updatedPreds)); + } } return newPreds; } http://git-wip-us.apache.org/repos/asf/calcite/blob/6f07293a/core/src/main/java/org/apache/calcite/rel/rules/AbstractMaterializedViewRule.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/rel/rules/AbstractMaterializedViewRule.java b/core/src/main/java/org/apache/calcite/rel/rules/AbstractMaterializedViewRule.java index 2893145..54586c7 100644 --- a/core/src/main/java/org/apache/calcite/rel/rules/AbstractMaterializedViewRule.java +++ b/core/src/main/java/org/apache/calcite/rel/rules/AbstractMaterializedViewRule.java @@ -298,14 +298,15 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule { matchModality = MatchModality.COMPLETE; } - // 4. We map every table in the query to a view table with the same qualified - // name. + // 4. We map every table in the query to a table with the same qualified + // name (all query tables are contained in the view, thus this is equivalent + // to mapping every table in the query to a view table). final Multimap<RelTableRef, RelTableRef> multiMapTables = ArrayListMultimap.create(); - for (RelTableRef queryTableRef : queryTableRefs) { - for (RelTableRef viewTableRef : viewTableRefs) { - if (queryTableRef.getQualifiedName().equals( - viewTableRef.getQualifiedName())) { - multiMapTables.put(queryTableRef, viewTableRef); + for (RelTableRef queryTableRef1 : queryTableRefs) { + for (RelTableRef queryTableRef2 : queryTableRefs) { + if (queryTableRef1.getQualifiedName().equals( + queryTableRef2.getQualifiedName())) { + multiMapTables.put(queryTableRef1, queryTableRef2); } } } @@ -938,30 +939,35 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule { */ private static List<BiMap<RelTableRef, RelTableRef>> generateTableMappings( Multimap<RelTableRef, RelTableRef> multiMapTables) { - final List<BiMap<RelTableRef, RelTableRef>> result = new ArrayList<>(); if (multiMapTables.isEmpty()) { - return result; + return ImmutableList.of(); } - result.add(HashBiMap.<RelTableRef, RelTableRef>create()); + List<BiMap<RelTableRef, RelTableRef>> result = + ImmutableList.<BiMap<RelTableRef, RelTableRef>>of( + HashBiMap.<RelTableRef, RelTableRef>create()); for (Entry<RelTableRef, Collection<RelTableRef>> e : multiMapTables.asMap().entrySet()) { - boolean added = false; + if (e.getValue().size() == 1) { + // Only one reference, we can just add it to every map + RelTableRef target = e.getValue().iterator().next(); + for (BiMap<RelTableRef, RelTableRef> m : result) { + m.put(e.getKey(), target); + } + continue; + } + // Multiple references: flatten + ImmutableList.Builder<BiMap<RelTableRef, RelTableRef>> newResult = + ImmutableList.builder(); for (RelTableRef target : e.getValue()) { - if (added) { - for (BiMap<RelTableRef, RelTableRef> m : result) { + for (BiMap<RelTableRef, RelTableRef> m : result) { + if (!m.containsValue(target)) { final BiMap<RelTableRef, RelTableRef> newM = HashBiMap.<RelTableRef, RelTableRef>create(m); newM.put(e.getKey(), target); - result.add(newM); + newResult.add(newM); } - } else { - for (BiMap<RelTableRef, RelTableRef> m : result) { - m.put(e.getKey(), target); - } - added = true; } } - // Mapping needs to exist - assert added; + result = newResult.build(); } return result; } @@ -1103,6 +1109,7 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule { RexTableInputRef uniqueKeyColumnRef = RexTableInputRef.of(parentTRef, uniqueKeyPos, parentTRef.getTable().getRowType().getFieldList().get(uniqueKeyPos).getType()); if (!foreignKeyColumnType.isNullable() + && vEC.getEquivalenceClassesMap().containsKey(uniqueKeyColumnRef) && vEC.getEquivalenceClassesMap().get(uniqueKeyColumnRef).contains( foreignKeyColumnRef)) { equiColumns.put(foreignKeyColumnRef, uniqueKeyColumnRef); @@ -1118,7 +1125,6 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule { edge = graph.addEdge(tRef, parentTRef); } edge.equiColumns.putAll(equiColumns); - break; } } } @@ -1508,6 +1514,10 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule { public Edge(RelTableRef source, RelTableRef target) { super(source, target); } + + public String toString() { + return "{" + source + " -> " + target + "}"; + } } /** Complete, view partial, or query partial. */ http://git-wip-us.apache.org/repos/asf/calcite/blob/6f07293a/core/src/main/java/org/apache/calcite/rex/RexTableInputRef.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/rex/RexTableInputRef.java b/core/src/main/java/org/apache/calcite/rex/RexTableInputRef.java index 83a3411..20762c1 100644 --- a/core/src/main/java/org/apache/calcite/rex/RexTableInputRef.java +++ b/core/src/main/java/org/apache/calcite/rex/RexTableInputRef.java @@ -95,7 +95,7 @@ public class RexTableInputRef extends RexInputRef { } /** Identifies uniquely a table by its qualified name and its entity number (occurrence) */ - public static class RelTableRef { + public static class RelTableRef implements Comparable<RelTableRef> { private final RelOptTable table; private final int entityNumber; @@ -139,6 +139,10 @@ public class RexTableInputRef extends RexInputRef { public static RelTableRef of(RelOptTable table, int entityNumber) { return new RelTableRef(table, entityNumber); } + + @Override public int compareTo(RelTableRef o) { + return digest.compareTo(o.digest); + } } } http://git-wip-us.apache.org/repos/asf/calcite/blob/6f07293a/core/src/main/java/org/apache/calcite/rex/RexUtil.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/rex/RexUtil.java b/core/src/main/java/org/apache/calcite/rex/RexUtil.java index 8b3c989..6ade754 100644 --- a/core/src/main/java/org/apache/calcite/rex/RexUtil.java +++ b/core/src/main/java/org/apache/calcite/rex/RexUtil.java @@ -828,6 +828,22 @@ public class RexUtil { } /** + * Returns whether any of the given expression trees contains a + * {link RexTableInputRef} node. + * + * @param nodes a list of RexNode trees + * @return true if at least one was found, otherwise false + */ + public static boolean containsTableInputRef(List<RexNode> nodes) { + for (RexNode e : nodes) { + if (containsTableInputRef(e) != null) { + return true; + } + } + return false; + } + + /** * Returns whether a given tree contains any {link RexTableInputRef} nodes. * * @param node a RexNode tree http://git-wip-us.apache.org/repos/asf/calcite/blob/6f07293a/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 49c88f5..eb15b5b 100644 --- a/core/src/test/java/org/apache/calcite/test/MaterializationTest.java +++ b/core/src/test/java/org/apache/calcite/test/MaterializationTest.java @@ -1451,6 +1451,48 @@ public class MaterializationTest { + " EnumerableTableScan(table=[[hr, m0]])")); } + @Test public void testJoinMaterializationUKFK6() { + checkMaterialize( + "select \"emps\".\"empid\", \"emps\".\"deptno\" from \"emps\"\n" + + "join \"depts\" \"a\" on (\"emps\".\"deptno\"=\"a\".\"deptno\")\n" + + "join \"depts\" \"b\" on (\"emps\".\"deptno\"=\"b\".\"deptno\")\n" + + "join \"dependents\" using (\"empid\")" + + "where \"emps\".\"empid\" = 1", + "select \"emps\".\"empid\" from \"emps\"\n" + + "join \"dependents\" using (\"empid\")\n" + + "where \"emps\".\"empid\" = 1", + HR_FKUK_MODEL, + CalciteAssert.checkResultContains( + "EnumerableCalc(expr#0..1=[{inputs}], empid=[$t0])\n" + + " EnumerableTableScan(table=[[hr, m0]])")); + } + + @Test public void testJoinMaterializationUKFK7() { + checkNoMaterialize( + "select \"emps\".\"empid\", \"emps\".\"deptno\" from \"emps\"\n" + + "join \"depts\" \"a\" on (\"emps\".\"name\"=\"a\".\"name\")\n" + + "join \"depts\" \"b\" on (\"emps\".\"name\"=\"b\".\"name\")\n" + + "join \"dependents\" using (\"empid\")" + + "where \"emps\".\"empid\" = 1", + "select \"emps\".\"empid\" from \"emps\"\n" + + "join \"dependents\" using (\"empid\")\n" + + "where \"emps\".\"empid\" = 1", + HR_FKUK_MODEL); + } + + @Test public void testJoinMaterializationUKFK8() { + checkNoMaterialize( + "select \"emps\".\"empid\", \"emps\".\"deptno\" from \"emps\"\n" + + "join \"depts\" \"a\" on (\"emps\".\"deptno\"=\"a\".\"deptno\")\n" + + "join \"depts\" \"b\" on (\"emps\".\"name\"=\"b\".\"name\")\n" + + "join \"dependents\" using (\"empid\")" + + "where \"emps\".\"empid\" = 1", + "select \"emps\".\"empid\" from \"emps\"\n" + + "join \"dependents\" using (\"empid\")\n" + + "where \"emps\".\"empid\" = 1", + HR_FKUK_MODEL); + } + @Test public void testSubQuery() { String q = "select \"empid\", \"deptno\", \"salary\" from \"emps\" e1\n" + "where \"empid\" = (\n" http://git-wip-us.apache.org/repos/asf/calcite/blob/6f07293a/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java ---------------------------------------------------------------------- diff --git a/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java b/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java index af25b30..79b985a 100644 --- a/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java +++ b/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java @@ -75,6 +75,7 @@ import org.apache.calcite.rex.RexInputRef; import org.apache.calcite.rex.RexLiteral; import org.apache.calcite.rex.RexNode; import org.apache.calcite.rex.RexTableInputRef; +import org.apache.calcite.rex.RexTableInputRef.RelTableRef; import org.apache.calcite.schema.SchemaPlus; import org.apache.calcite.sql.SqlKind; import org.apache.calcite.sql.fun.SqlStdOperatorTable; @@ -90,6 +91,7 @@ import com.google.common.collect.ImmutableSet; import com.google.common.collect.Iterables; import com.google.common.collect.Lists; import com.google.common.collect.Multimap; +import com.google.common.collect.Sets; import org.hamcrest.CoreMatchers; import org.hamcrest.CustomTypeSafeMatcher; @@ -1881,6 +1883,59 @@ public class RelMetadataTest extends SqlToRelTestBase { assertNull(inputSet); } + @Test public void testAllPredicatesAndTablesJoin() { + final String sql = "select x.sal, y.deptno from\n" + + "(select a.deptno, c.sal from (select * from emp limit 7) as a\n" + + "cross join (select * from dept limit 1) as b\n" + + "inner join (select * from emp limit 2) as c\n" + + "on a.deptno = c.deptno) as x\n" + + "inner join\n" + + "(select a.deptno, c.sal from (select * from emp limit 7) as a\n" + + "cross join (select * from dept limit 1) as b\n" + + "inner join (select * from emp limit 2) as c\n" + + "on a.deptno = c.deptno) as y\n" + + "on x.deptno = y.deptno"; + final RelNode rel = convertSql(sql); + final RelMetadataQuery mq = RelMetadataQuery.instance(); + final RelOptPredicateList inputSet = mq.getAllPredicates(rel); + assertThat(inputSet.pulledUpPredicates.toString(), + equalTo("[true, " + + "=([CATALOG, SALES, EMP].#0.$7, [CATALOG, SALES, EMP].#1.$7), " + + "true, " + + "=([CATALOG, SALES, EMP].#2.$7, [CATALOG, SALES, EMP].#3.$7), " + + "=([CATALOG, SALES, EMP].#0.$7, [CATALOG, SALES, EMP].#2.$7)]")); + final Set<RelTableRef> tableReferences = Sets.newTreeSet(mq.getTableReferences(rel)); + assertThat(tableReferences.toString(), + equalTo("[[CATALOG, SALES, DEPT].#0, [CATALOG, SALES, DEPT].#1, " + + "[CATALOG, SALES, EMP].#0, [CATALOG, SALES, EMP].#1, " + + "[CATALOG, SALES, EMP].#2, [CATALOG, SALES, EMP].#3]")); + } + + @Test public void testAllPredicatesAndTableUnion() { + final String sql = "select a.deptno, c.sal from (select * from emp limit 7) as a\n" + + "cross join (select * from dept limit 1) as b\n" + + "inner join (select * from emp limit 2) as c\n" + + "on a.deptno = c.deptno\n" + + "union all\n" + + "select a.deptno, c.sal from (select * from emp limit 7) as a\n" + + "cross join (select * from dept limit 1) as b\n" + + "inner join (select * from emp limit 2) as c\n" + + "on a.deptno = c.deptno"; + final RelNode rel = convertSql(sql); + final RelMetadataQuery mq = RelMetadataQuery.instance(); + final RelOptPredicateList inputSet = mq.getAllPredicates(rel); + assertThat(inputSet.pulledUpPredicates.toString(), + equalTo("[true, " + + "=([CATALOG, SALES, EMP].#0.$7, [CATALOG, SALES, EMP].#1.$7), " + + "true, " + + "=([CATALOG, SALES, EMP].#2.$7, [CATALOG, SALES, EMP].#3.$7)]")); + final Set<RelTableRef> tableReferences = Sets.newTreeSet(mq.getTableReferences(rel)); + assertThat(tableReferences.toString(), + equalTo("[[CATALOG, SALES, DEPT].#0, [CATALOG, SALES, DEPT].#1, " + + "[CATALOG, SALES, EMP].#0, [CATALOG, SALES, EMP].#1, " + + "[CATALOG, SALES, EMP].#2, [CATALOG, SALES, EMP].#3]")); + } + private void checkNodeTypeCount(String sql, Map<Class<? extends RelNode>, Integer> expected) { final RelNode rel = convertSql(sql); final RelMetadataQuery mq = RelMetadataQuery.instance();
