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 2018/11/13 16:55:04 UTC
calcite git commit: [CALCITE-2668] Support for left/right outer join
in RelMdExpressionLineage
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 <jc...@apache.org>
Authored: Tue Nov 13 08:42:35 2018 -0800
Committer: Jesus Camacho Rodriguez <jc...@apache.org>
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()));
}