Repository: calcite Updated Branches: refs/heads/master 3f89e037c -> 81a9bd783
[CALCITE-2668] Support for left/right outer join in RelMdExpressionLineage Project: http://git-wip-us.apache.org/repos/asf/calcite/repo Commit: http://git-wip-us.apache.org/repos/asf/calcite/commit/81a9bd78 Tree: http://git-wip-us.apache.org/repos/asf/calcite/tree/81a9bd78 Diff: http://git-wip-us.apache.org/repos/asf/calcite/diff/81a9bd78 Branch: refs/heads/master Commit: 81a9bd783e2cc8a34e7a175b09cfd0b77dbf334a Parents: 3f89e03 Author: Jesus Camacho Rodriguez <[email protected]> Authored: Tue Nov 13 08:42:35 2018 -0800 Committer: Jesus Camacho Rodriguez <[email protected]> Committed: Tue Nov 13 08:42:52 2018 -0800 ---------------------------------------------------------------------- .../rel/metadata/RelMdExpressionLineage.java | 149 +++++++++++-------- .../rel/metadata/RelMdTableReferences.java | 2 +- .../rel/rules/AbstractMaterializedViewRule.java | 13 +- .../apache/calcite/test/RelMetadataTest.java | 46 ++++-- 4 files changed, 136 insertions(+), 74 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/calcite/blob/81a9bd78/core/src/main/java/org/apache/calcite/rel/metadata/RelMdExpressionLineage.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdExpressionLineage.java b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdExpressionLineage.java index d456c81..fcbf571 100644 --- a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdExpressionLineage.java +++ b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdExpressionLineage.java @@ -44,7 +44,6 @@ import org.apache.calcite.util.Util; import com.google.common.collect.HashMultimap; 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 java.util.ArrayList; @@ -80,7 +79,7 @@ public class RelMdExpressionLineage //~ Constructors ----------------------------------------------------------- - private RelMdExpressionLineage() {} + protected RelMdExpressionLineage() {} //~ Methods ---------------------------------------------------------------- @@ -116,10 +115,7 @@ public class RelMdExpressionLineage final RexBuilder rexBuilder = rel.getCluster().getRexBuilder(); // Extract input fields referenced by expression - final Set<RelDataTypeField> inputExtraFields = new LinkedHashSet<>(); - final RelOptUtil.InputFinder inputFinder = new RelOptUtil.InputFinder(inputExtraFields); - outputExpression.accept(inputFinder); - final ImmutableBitSet inputFieldsUsed = inputFinder.inputBitSet.build(); + final ImmutableBitSet inputFieldsUsed = extractInputRefs(outputExpression); // Infer column origin expressions for given references final Map<RexInputRef, Set<RexNode>> mapping = new LinkedHashMap<>(); @@ -147,10 +143,7 @@ public class RelMdExpressionLineage final RexBuilder rexBuilder = rel.getCluster().getRexBuilder(); // Extract input fields referenced by expression - final Set<RelDataTypeField> inputExtraFields = new LinkedHashSet<>(); - final RelOptUtil.InputFinder inputFinder = new RelOptUtil.InputFinder(inputExtraFields); - outputExpression.accept(inputFinder); - final ImmutableBitSet inputFieldsUsed = inputFinder.inputBitSet.build(); + final ImmutableBitSet inputFieldsUsed = extractInputRefs(outputExpression); for (int idx : inputFieldsUsed) { if (idx >= rel.getGroupCount()) { @@ -184,21 +177,66 @@ public class RelMdExpressionLineage */ public Set<RexNode> getExpressionLineage(Join rel, RelMetadataQuery mq, RexNode outputExpression) { - if (rel.getJoinType() != JoinRelType.INNER) { - // We cannot map origin of this expression. - return null; - } - final RexBuilder rexBuilder = rel.getCluster().getRexBuilder(); final RelNode leftInput = rel.getLeft(); final RelNode rightInput = rel.getRight(); final int nLeftColumns = leftInput.getRowType().getFieldList().size(); - // Infer column origin expressions for given references + // Extract input fields referenced by expression + final ImmutableBitSet inputFieldsUsed = extractInputRefs(outputExpression); + + if (rel.getJoinType() != JoinRelType.INNER) { + // If we reference the inner side, we will bail out + if (rel.getJoinType() == JoinRelType.LEFT) { + ImmutableBitSet rightFields = ImmutableBitSet.range( + nLeftColumns, rel.getRowType().getFieldCount()); + if (inputFieldsUsed.intersects(rightFields)) { + // We cannot map origin of this expression. + return null; + } + } else if (rel.getJoinType() == JoinRelType.RIGHT) { + ImmutableBitSet leftFields = ImmutableBitSet.range( + 0, nLeftColumns); + if (inputFieldsUsed.intersects(leftFields)) { + // We cannot map origin of this expression. + return null; + } + } else { + // We cannot map origin of this expression. + return null; + } + } + + // Gather table references + final Set<RelTableRef> leftTableRefs = mq.getTableReferences(leftInput); + if (leftTableRefs == null) { + // Bail out + return null; + } + final Set<RelTableRef> rightTableRefs = mq.getTableReferences(rightInput); + if (rightTableRefs == null) { + // Bail out + return null; + } final Multimap<List<String>, RelTableRef> qualifiedNamesToRefs = HashMultimap.create(); final Map<RelTableRef, RelTableRef> currentTablesMapping = new HashMap<>(); + for (RelTableRef leftRef : leftTableRefs) { + qualifiedNamesToRefs.put(leftRef.getQualifiedName(), leftRef); + } + for (RelTableRef rightRef : rightTableRefs) { + 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())); + } + + // Infer column origin expressions for given references final Map<RexInputRef, Set<RexNode>> mapping = new LinkedHashMap<>(); - for (int idx = 0; idx < rel.getRowType().getFieldList().size(); idx++) { + for (int idx : inputFieldsUsed) { if (idx < nLeftColumns) { final RexInputRef inputRef = RexInputRef.of(idx, leftInput.getRowType().getFieldList()); final Set<RexNode> originalExprs = mq.getExpressionLineage(leftInput, inputRef); @@ -206,12 +244,7 @@ public class RelMdExpressionLineage // Bail out return null; } - // Gather table references, left input references remain unchanged - final Set<RelTableRef> tableRefs = - RexUtil.gatherTableReferences(Lists.newArrayList(originalExprs)); - for (RelTableRef leftRef : tableRefs) { - qualifiedNamesToRefs.put(leftRef.getQualifiedName(), leftRef); - } + // Left input references remain unchanged mapping.put(RexInputRef.of(idx, rel.getRowType().getFieldList()), originalExprs); } else { // Right input. @@ -222,20 +255,8 @@ public class RelMdExpressionLineage // Bail out return null; } - // Gather table references, right input references might need to be - // updated if there are table names clashes with left input - final Set<RelTableRef> tableRefs = - RexUtil.gatherTableReferences(Lists.newArrayList(originalExprs)); - 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())); - } + // Right input references might need to be updated if there are + // table names clashes with left input final Set<RexNode> updatedExprs = ImmutableSet.copyOf( Iterables.transform(originalExprs, e -> RexUtil.swapTableReferences(rexBuilder, e, @@ -258,34 +279,40 @@ public class RelMdExpressionLineage RexNode outputExpression) { final RexBuilder rexBuilder = rel.getCluster().getRexBuilder(); + // Extract input fields referenced by expression + final ImmutableBitSet inputFieldsUsed = extractInputRefs(outputExpression); + // Infer column origin expressions for given references final Multimap<List<String>, RelTableRef> qualifiedNamesToRefs = HashMultimap.create(); final Map<RexInputRef, Set<RexNode>> mapping = new LinkedHashMap<>(); for (RelNode input : rel.getInputs()) { + // Gather table references final Map<RelTableRef, RelTableRef> currentTablesMapping = new HashMap<>(); - for (int idx = 0; idx < input.getRowType().getFieldList().size(); idx++) { + final Set<RelTableRef> tableRefs = mq.getTableReferences(input); + if (tableRefs == null) { + // Bail out + return null; + } + for (RelTableRef tableRef : tableRefs) { + int shift = 0; + Collection<RelTableRef> lRefs = qualifiedNamesToRefs.get( + tableRef.getQualifiedName()); + if (lRefs != null) { + shift = lRefs.size(); + } + currentTablesMapping.put(tableRef, + RelTableRef.of(tableRef.getTable(), shift + tableRef.getEntityNumber())); + } + // Map references + for (int idx : inputFieldsUsed) { final RexInputRef inputRef = RexInputRef.of(idx, input.getRowType().getFieldList()); final Set<RexNode> originalExprs = mq.getExpressionLineage(input, inputRef); if (originalExprs == null) { // Bail out return null; } - + // References might need to be updated final RexInputRef ref = RexInputRef.of(idx, rel.getRowType().getFieldList()); - // Gather table references, references might need to be - // updated - final Set<RelTableRef> tableRefs = - RexUtil.gatherTableReferences(Lists.newArrayList(originalExprs)); - for (RelTableRef tableRef : tableRefs) { - int shift = 0; - Collection<RelTableRef> lRefs = qualifiedNamesToRefs.get( - tableRef.getQualifiedName()); - if (lRefs != null) { - shift = lRefs.size(); - } - currentTablesMapping.put(tableRef, - RelTableRef.of(tableRef.getTable(), shift + tableRef.getEntityNumber())); - } final Set<RexNode> updatedExprs = originalExprs.stream() .map(e -> @@ -318,10 +345,7 @@ public class RelMdExpressionLineage final RexBuilder rexBuilder = rel.getCluster().getRexBuilder(); // Extract input fields referenced by expression - final Set<RelDataTypeField> inputExtraFields = new LinkedHashSet<>(); - final RelOptUtil.InputFinder inputFinder = new RelOptUtil.InputFinder(inputExtraFields); - outputExpression.accept(inputFinder); - final ImmutableBitSet inputFieldsUsed = inputFinder.inputBitSet.build(); + final ImmutableBitSet inputFieldsUsed = extractInputRefs(outputExpression); // Infer column origin expressions for given references final Map<RexInputRef, Set<RexNode>> mapping = new LinkedHashMap<>(); @@ -377,10 +401,7 @@ public class RelMdExpressionLineage protected static Set<RexNode> createAllPossibleExpressions(RexBuilder rexBuilder, RexNode expr, Map<RexInputRef, Set<RexNode>> mapping) { // Extract input fields referenced by expression - final Set<RelDataTypeField> inputExtraFields = new LinkedHashSet<>(); - final RelOptUtil.InputFinder inputFinder = new RelOptUtil.InputFinder(inputExtraFields); - expr.accept(inputFinder); - final ImmutableBitSet predFieldsUsed = inputFinder.inputBitSet.build(); + final ImmutableBitSet predFieldsUsed = extractInputRefs(expr); if (predFieldsUsed.isEmpty()) { // The unique expression is the input expression @@ -444,6 +465,12 @@ public class RelMdExpressionLineage } } + private static ImmutableBitSet extractInputRefs(RexNode expr) { + final Set<RelDataTypeField> inputExtraFields = new LinkedHashSet<>(); + final RelOptUtil.InputFinder inputFinder = new RelOptUtil.InputFinder(inputExtraFields); + expr.accept(inputFinder); + return inputFinder.inputBitSet.build(); + } } // End RelMdExpressionLineage.java http://git-wip-us.apache.org/repos/asf/calcite/blob/81a9bd78/core/src/main/java/org/apache/calcite/rel/metadata/RelMdTableReferences.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdTableReferences.java b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdTableReferences.java index 38b1ca2..6c2395f 100644 --- a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdTableReferences.java +++ b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdTableReferences.java @@ -63,7 +63,7 @@ public class RelMdTableReferences //~ Constructors ----------------------------------------------------------- - private RelMdTableReferences() {} + protected RelMdTableReferences() {} //~ Methods ---------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/calcite/blob/81a9bd78/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 b164fe0..89e444a 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 @@ -1863,11 +1863,12 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule { return result; } - /** Currently we only support TableScan - Project - Filter - Join */ + /** Currently we only support TableScan - Project - Filter - Inner Join */ private static boolean isValidRelNodePlan(RelNode node, RelMetadataQuery mq) { final Multimap<Class<? extends RelNode>, RelNode> m = mq.getNodeTypes(node); - for (Class<? extends RelNode> c : m.keySet()) { + for (Entry<Class<? extends RelNode>, Collection<RelNode>> e : m.asMap().entrySet()) { + Class<? extends RelNode> c = e.getKey(); if (!TableScan.class.isAssignableFrom(c) && !Project.class.isAssignableFrom(c) && !Filter.class.isAssignableFrom(c) @@ -1876,6 +1877,14 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule { // Skip it return false; } + if (Join.class.isAssignableFrom(c)) { + for (RelNode n : e.getValue()) { + if (((Join) n).getJoinType() != JoinRelType.INNER) { + // Skip it + return false; + } + } + } } return true; } http://git-wip-us.apache.org/repos/asf/calcite/blob/81a9bd78/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 0c216b3..1c5140f 100644 --- a/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java +++ b/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java @@ -1630,14 +1630,14 @@ public class RelMetadataTest extends SqlToRelTestBase { final Set<RexNode> r1 = mq.getExpressionLineage(rel, ref1); assertThat(r1.size(), is(1)); final RexTableInputRef result1 = (RexTableInputRef) r1.iterator().next(); - assertTrue(result1.getQualifiedName().equals(EMP_QNAME)); + assertEquals(result1.getQualifiedName(), EMP_QNAME); assertThat(result1.getIndex(), is(3)); final RexNode ref2 = RexInputRef.of(1, rel.getRowType().getFieldList()); final Set<RexNode> r2 = mq.getExpressionLineage(rel, ref2); assertThat(r2.size(), is(1)); final RexTableInputRef result2 = (RexTableInputRef) r2.iterator().next(); - assertTrue(result2.getQualifiedName().equals(EMP_QNAME)); + assertEquals(result2.getQualifiedName(), EMP_QNAME); assertThat(result2.getIndex(), is(7)); assertThat(result1.getIdentifier(), is(result2.getIdentifier())); @@ -1653,14 +1653,14 @@ public class RelMetadataTest extends SqlToRelTestBase { final Set<RexNode> r1 = mq.getExpressionLineage(rel, ref1); assertThat(r1.size(), is(1)); final RexTableInputRef result1 = (RexTableInputRef) r1.iterator().next(); - assertTrue(result1.getQualifiedName().equals(EMP_QNAME)); + assertEquals(result1.getQualifiedName(), EMP_QNAME); assertThat(result1.getIndex(), is(7)); final RexNode ref2 = RexInputRef.of(1, rel.getRowType().getFieldList()); final Set<RexNode> r2 = mq.getExpressionLineage(rel, ref2); assertThat(r2.size(), is(1)); final RexTableInputRef result2 = (RexTableInputRef) r2.iterator().next(); - assertTrue(result2.getQualifiedName().equals(EMP_QNAME)); + assertEquals(result2.getQualifiedName(), EMP_QNAME); assertThat(result2.getIndex(), is(3)); assertThat(result1.getIdentifier(), is(result2.getIdentifier())); @@ -1681,10 +1681,10 @@ public class RelMetadataTest extends SqlToRelTestBase { final RexCall call = (RexCall) result; assertThat(call.getOperands().size(), is(2)); final RexTableInputRef inputRef1 = (RexTableInputRef) call.getOperands().get(0); - assertTrue(inputRef1.getQualifiedName().equals(EMP_QNAME)); + assertEquals(inputRef1.getQualifiedName(), EMP_QNAME); assertThat(inputRef1.getIndex(), is(0)); final RexTableInputRef inputRef2 = (RexTableInputRef) call.getOperands().get(1); - assertTrue(inputRef2.getQualifiedName().equals(EMP_QNAME)); + assertEquals(inputRef2.getQualifiedName(), EMP_QNAME); assertThat(inputRef2.getIndex(), is(7)); assertThat(inputRef1.getIdentifier(), is(inputRef2.getIdentifier())); } @@ -1698,7 +1698,7 @@ public class RelMetadataTest extends SqlToRelTestBase { final Set<RexNode> r = mq.getExpressionLineage(rel, ref); assertThat(r.size(), is(1)); final RexTableInputRef result = (RexTableInputRef) r.iterator().next(); - assertTrue(result.getQualifiedName().equals(EMP_QNAME)); + assertEquals(result.getQualifiedName(), EMP_QNAME); assertThat(result.getIndex(), is(1)); } @@ -1711,7 +1711,33 @@ public class RelMetadataTest extends SqlToRelTestBase { final Set<RexNode> r = mq.getExpressionLineage(rel, ref); assertThat(r.size(), is(1)); final RexTableInputRef result = (RexTableInputRef) r.iterator().next(); - assertTrue(result.getQualifiedName().equals(ImmutableList.of("CATALOG", "SALES", "BONUS"))); + assertEquals(result.getQualifiedName(), ImmutableList.of("CATALOG", "SALES", "BONUS")); + assertThat(result.getIndex(), is(0)); + } + + @Test public void testExpressionLineageLeftJoinLeft() { + // ename is column 1 in catalog.sales.emp + final RelNode rel = convertSql("select ename from emp left join dept using (deptno)"); + final RelMetadataQuery mq = RelMetadataQuery.instance(); + + final RexNode ref = RexInputRef.of(0, rel.getRowType().getFieldList()); + final Set<RexNode> r = mq.getExpressionLineage(rel, ref); + assertThat(r.size(), is(1)); + final RexTableInputRef result = (RexTableInputRef) r.iterator().next(); + assertEquals(result.getQualifiedName(), EMP_QNAME); + assertThat(result.getIndex(), is(1)); + } + + @Test public void testExpressionLineageRightJoinRight() { + // ename is column 0 in catalog.sales.bonus + final RelNode rel = convertSql("select bonus.ename from emp right join bonus using (ename)"); + final RelMetadataQuery mq = RelMetadataQuery.instance(); + + final RexNode ref = RexInputRef.of(0, rel.getRowType().getFieldList()); + final Set<RexNode> r = mq.getExpressionLineage(rel, ref); + assertThat(r.size(), is(1)); + final RexTableInputRef result = (RexTableInputRef) r.iterator().next(); + assertEquals(result.getQualifiedName(), ImmutableList.of("CATALOG", "SALES", "BONUS")); assertThat(result.getIndex(), is(0)); } @@ -1843,12 +1869,12 @@ public class RelMetadataTest extends SqlToRelTestBase { final RexCall call = (RexCall) result; assertThat(call.getOperands().size(), is(2)); final RexTableInputRef inputRef1 = (RexTableInputRef) call.getOperands().get(0); - assertTrue(inputRef1.getQualifiedName().equals(EMP_QNAME)); + assertEquals(inputRef1.getQualifiedName(), EMP_QNAME); // Add join alpha to set set.add(inputRef1.getQualifiedName()); assertThat(inputRef1.getIndex(), is(0)); final RexTableInputRef inputRef2 = (RexTableInputRef) call.getOperands().get(1); - assertTrue(inputRef2.getQualifiedName().equals(EMP_QNAME)); + assertEquals(inputRef2.getQualifiedName(), EMP_QNAME); assertThat(inputRef2.getIndex(), is(5)); assertThat(inputRef1.getIdentifier(), not(inputRef2.getIdentifier())); }
