You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@calcite.apache.org by jh...@apache.org on 2019/09/20 19:44:03 UTC
[calcite] 02/02: [CALCITE-3286] In LatticeSuggester,
allow join conditions that use expressions
This is an automated email from the ASF dual-hosted git repository.
jhyde pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/calcite.git
commit 29d8508f591be79683d0efeb3541dc3bdbc36d44
Author: Julian Hyde <jh...@apache.org>
AuthorDate: Thu Aug 22 21:51:47 2019 -0700
[CALCITE-3286] In LatticeSuggester, allow join conditions that use expressions
Skip expressions when deducing primary and foreign keys.
---
.../org/apache/calcite/materialize/Lattice.java | 4 +-
.../apache/calcite/materialize/LatticeNode.java | 2 +-
.../apache/calcite/materialize/LatticeSpace.java | 40 ++++++++-
.../calcite/materialize/LatticeSuggester.java | 98 +++++++++++++++-------
.../java/org/apache/calcite/materialize/Step.java | 64 +++++++++-----
.../apache/calcite/rex/RexToSqlNodeConverter.java | 4 +
.../calcite/materialize/LatticeSuggesterTest.java | 62 ++++++++++++++
7 files changed, 218 insertions(+), 56 deletions(-)
diff --git a/core/src/main/java/org/apache/calcite/materialize/Lattice.java b/core/src/main/java/org/apache/calcite/materialize/Lattice.java
index f729bf7..b1af5f3 100644
--- a/core/src/main/java/org/apache/calcite/materialize/Lattice.java
+++ b/core/src/main/java/org/apache/calcite/materialize/Lattice.java
@@ -842,8 +842,8 @@ public class Lattice {
final Edge edge = edges.get(0);
final MutableNode parent = map.get(edge.getSource().table);
final Step step =
- new Step(edge.getSource().table,
- edge.getTarget().table, edge.pairs);
+ Step.create(edge.getSource().table,
+ edge.getTarget().table, edge.pairs, space);
node = new MutableNode(vertex.table, parent, step);
node.alias = vertex.alias;
}
diff --git a/core/src/main/java/org/apache/calcite/materialize/LatticeNode.java b/core/src/main/java/org/apache/calcite/materialize/LatticeNode.java
index d9afc3f..092453e 100644
--- a/core/src/main/java/org/apache/calcite/materialize/LatticeNode.java
+++ b/core/src/main/java/org/apache/calcite/materialize/LatticeNode.java
@@ -59,7 +59,7 @@ public abstract class LatticeNode {
if (i++ > 0) {
sb.append(",");
}
- sb.append(parent.table.field(p.source).getName());
+ sb.append(space.fieldName(parent.table, p.source));
}
}
if (mutableNode.children.isEmpty()) {
diff --git a/core/src/main/java/org/apache/calcite/materialize/LatticeSpace.java b/core/src/main/java/org/apache/calcite/materialize/LatticeSpace.java
index fa27cfb..8fa87db 100644
--- a/core/src/main/java/org/apache/calcite/materialize/LatticeSpace.java
+++ b/core/src/main/java/org/apache/calcite/materialize/LatticeSpace.java
@@ -17,6 +17,8 @@
package org.apache.calcite.materialize;
import org.apache.calcite.plan.RelOptTable;
+import org.apache.calcite.rel.type.RelDataTypeField;
+import org.apache.calcite.rex.RexNode;
import org.apache.calcite.util.Util;
import org.apache.calcite.util.graph.AttributedDirectedGraph;
import org.apache.calcite.util.mapping.IntPair;
@@ -24,6 +26,7 @@ import org.apache.calcite.util.mapping.IntPair;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Lists;
+import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
@@ -37,12 +40,13 @@ class LatticeSpace {
final SqlStatisticProvider statisticProvider;
private final Map<List<String>, LatticeTable> tableMap = new HashMap<>();
final AttributedDirectedGraph<LatticeTable, Step> g =
- new AttributedDirectedGraph<>(new Step.Factory());
+ new AttributedDirectedGraph<>(new Step.Factory(this));
private final Map<List<String>, String> simpleTableNames = new HashMap<>();
private final Set<String> simpleNames = new HashSet<>();
/** Root nodes, indexed by digest. */
final Map<String, LatticeRootNode> nodeMap = new HashMap<>();
final Map<ImmutableList<Step>, Path> pathMap = new HashMap<>();
+ final Map<LatticeTable, List<RexNode>> tableExpressions = new HashMap<>();
LatticeSpace(SqlStatisticProvider statisticProvider) {
this.statisticProvider = Objects.requireNonNull(statisticProvider);
@@ -130,6 +134,40 @@ class LatticeSpace {
return path2;
}
+ /** Registers an expression as a derived column of a given table.
+ *
+ * <p>Its ordinal is the number of fields in the row type plus the ordinal
+ * of the extended expression. For example, if a table has 10 fields then its
+ * derived columns will have ordinals 10, 11, 12 etc. */
+ int registerExpression(LatticeTable table, RexNode e) {
+ final List<RexNode> expressions =
+ tableExpressions.computeIfAbsent(table, t -> new ArrayList<>());
+ final int fieldCount = table.t.getRowType().getFieldCount();
+ for (int i = 0; i < expressions.size(); i++) {
+ if (expressions.get(i).toString().equals(e.toString())) {
+ return fieldCount + i;
+ }
+ }
+ final int result = fieldCount + expressions.size();
+ expressions.add(e);
+ return result;
+ }
+
+ /** Returns the name of field {@code field} of {@code table}.
+ *
+ * <p>If the field is derived (see
+ * {@link #registerExpression(LatticeTable, RexNode)}) its name is its
+ * {@link RexNode#toString()}. */
+ public String fieldName(LatticeTable table, int field) {
+ final List<RelDataTypeField> fieldList =
+ table.t.getRowType().getFieldList();
+ final int fieldCount = fieldList.size();
+ if (field < fieldCount) {
+ return fieldList.get(field).getName();
+ } else {
+ return tableExpressions.get(table).get(field - fieldCount).toString();
+ }
+ }
}
// End LatticeSpace.java
diff --git a/core/src/main/java/org/apache/calcite/materialize/LatticeSuggester.java b/core/src/main/java/org/apache/calcite/materialize/LatticeSuggester.java
index f532eb3..30f337e 100644
--- a/core/src/main/java/org/apache/calcite/materialize/LatticeSuggester.java
+++ b/core/src/main/java/org/apache/calcite/materialize/LatticeSuggester.java
@@ -31,6 +31,7 @@ import org.apache.calcite.rel.core.Project;
import org.apache.calcite.rel.core.Sort;
import org.apache.calcite.rel.core.TableScan;
import org.apache.calcite.rel.rules.FilterJoinRule;
+import org.apache.calcite.rel.type.RelDataTypeField;
import org.apache.calcite.rex.RexInputRef;
import org.apache.calcite.rex.RexNode;
import org.apache.calcite.sql.SqlAggFunction;
@@ -103,6 +104,17 @@ public class LatticeSuggester {
return ImmutableSet.copyOf(set);
}
+ /** Converts a column reference to an expression. */
+ public RexNode toRex(LatticeTable table, int column) {
+ final List<RelDataTypeField> fieldList =
+ table.t.getRowType().getFieldList();
+ if (column < fieldList.size()) {
+ return new RexInputRef(column, fieldList.get(column).getType());
+ } else {
+ return space.tableExpressions.get(table).get(column - fieldList.size());
+ }
+ }
+
/** Adds a query.
*
* <p>It may fit within an existing lattice (or lattices). Or it may need a
@@ -133,8 +145,8 @@ public class LatticeSuggester {
g.addVertex(tableRef);
}
for (Hop hop : frame.hops) {
- map.put(Pair.of(hop.source.t, hop.target.t),
- IntPair.of(hop.source.c, hop.target.c));
+ map.put(Pair.of(hop.source.tableRef(), hop.target.tableRef()),
+ IntPair.of(hop.source.col(space), hop.target.col(space)));
}
for (Map.Entry<Pair<TableRef, TableRef>, Collection<IntPair>> e
: map.asMap().entrySet()) {
@@ -457,7 +469,13 @@ public class LatticeSuggester {
tableRefs.add(tableRef);
}
}
- return new DerivedColRef(tableRefs.build(), e, alias);
+ final List<TableRef> tableRefList = tableRefs.build();
+ switch (tableRefList.size()) {
+ case 1:
+ return new SingleTableDerivedColRef(tableRefList.get(0), e, alias);
+ default:
+ return new DerivedColRef(tableRefList, e, alias);
+ }
}
};
} else if (r instanceof Join) {
@@ -473,9 +491,11 @@ public class LatticeSuggester {
for (IntPair p : join.analyzeCondition().pairs()) {
final ColRef source = left.column(p.source);
final ColRef target = right.column(p.target);
- assert source instanceof BaseColRef;
- assert target instanceof BaseColRef;
- builder.add(new Hop((BaseColRef) source, (BaseColRef) target));
+ assert source instanceof SingleTableColRef;
+ assert target instanceof SingleTableColRef;
+ builder.add(
+ new Hop((SingleTableColRef) source,
+ (SingleTableColRef) target));
}
builder.addAll(right.hops);
final int fieldCount = r.getRowType().getFieldCount();
@@ -533,7 +553,7 @@ public class LatticeSuggester {
StepRef stepRef(TableRef source, TableRef target, List<IntPair> keys) {
keys = LatticeSpace.sortUnique(keys);
- final Step h = new Step(source.table, target.table, keys);
+ final Step h = Step.create(source.table, target.table, keys, space);
if (h.isBackwards(space.statisticProvider)) {
final List<IntPair> keys1 = LatticeSpace.swap(h.keys);
final Step h2 = space.addEdge(h.target(), h.source(), keys1);
@@ -574,8 +594,8 @@ public class LatticeSuggester {
static Set<TableRef> collectTableRefs(List<Frame> inputs, List<Hop> hops) {
final LinkedHashSet<TableRef> set = new LinkedHashSet<>();
for (Hop hop : hops) {
- set.add(hop.source.t);
- set.add(hop.target.t);
+ set.add(hop.source.tableRef());
+ set.add(hop.target.tableRef());
}
for (Frame frame : inputs) {
set.addAll(frame.tableRefs);
@@ -631,21 +651,8 @@ public class LatticeSuggester {
}
@Override public String toString() {
- final StringBuilder b = new StringBuilder()
- .append("StepRef(")
- .append(source)
- .append(", ")
- .append(target)
- .append(",");
- for (IntPair key : step.keys) {
- b.append(' ')
- .append(step.source().field(key.source).getName())
- .append(':')
- .append(step.target().field(key.target).getName());
- }
- return b.append("):")
- .append(ordinalInQuery)
- .toString();
+ return "StepRef(" + source + ", " + target + "," + step.keyString + "):"
+ + ordinalInQuery;
}
TableRef source() {
@@ -703,10 +710,10 @@ public class LatticeSuggester {
* </ul>
*/
private static class Hop {
- final BaseColRef source;
- final BaseColRef target;
+ final SingleTableColRef source;
+ final SingleTableColRef target;
- private Hop(BaseColRef source, BaseColRef target) {
+ private Hop(SingleTableColRef source, SingleTableColRef target) {
this.source = source;
this.target = target;
}
@@ -716,8 +723,15 @@ public class LatticeSuggester {
private abstract static class ColRef {
}
+ /** Column reference that is within a single table. */
+ private interface SingleTableColRef {
+ TableRef tableRef();
+
+ int col(LatticeSpace space);
+ }
+
/** Reference to a base column. */
- private static class BaseColRef extends ColRef {
+ private static class BaseColRef extends ColRef implements SingleTableColRef {
final TableRef t;
final int c;
@@ -725,6 +739,14 @@ public class LatticeSuggester {
this.t = t;
this.c = c;
}
+
+ public TableRef tableRef() {
+ return t;
+ }
+
+ public int col(LatticeSpace space) {
+ return c;
+ }
}
/** Reference to a derived column (that is, an expression). */
@@ -733,8 +755,7 @@ public class LatticeSuggester {
@Nonnull final RexNode e;
final String alias;
- private DerivedColRef(Iterable<TableRef> tableRefs, RexNode e,
- String alias) {
+ DerivedColRef(Iterable<TableRef> tableRefs, RexNode e, String alias) {
this.tableRefs = ImmutableList.copyOf(tableRefs);
this.e = e;
this.alias = alias;
@@ -745,6 +766,23 @@ public class LatticeSuggester {
}
}
+ /** Variant of {@link DerivedColRef} where all referenced expressions are in
+ * the same table. */
+ private static class SingleTableDerivedColRef extends DerivedColRef
+ implements SingleTableColRef {
+ SingleTableDerivedColRef(TableRef tableRef, RexNode e, String alias) {
+ super(ImmutableList.of(tableRef), e, alias);
+ }
+
+ public TableRef tableRef() {
+ return tableRefs.get(0);
+ }
+
+ public int col(LatticeSpace space) {
+ return space.registerExpression(tableRef().table, e);
+ }
+ }
+
/** An aggregate call. Becomes a measure in the final lattice. */
private static class MutableMeasure {
final SqlAggFunction aggregate;
diff --git a/core/src/main/java/org/apache/calcite/materialize/Step.java b/core/src/main/java/org/apache/calcite/materialize/Step.java
index d28a8f9..2e75c65 100644
--- a/core/src/main/java/org/apache/calcite/materialize/Step.java
+++ b/core/src/main/java/org/apache/calcite/materialize/Step.java
@@ -39,12 +39,31 @@ import java.util.Objects;
class Step extends DefaultEdge {
final List<IntPair> keys;
- Step(LatticeTable source, LatticeTable target, List<IntPair> keys) {
+ /** String representation of {@link #keys}. Computing the string requires a
+ * {@link LatticeSpace}, so we pre-compute it before construction. */
+ final String keyString;
+
+ private Step(LatticeTable source, LatticeTable target,
+ List<IntPair> keys, String keyString) {
super(source, target);
this.keys = ImmutableList.copyOf(keys);
+ this.keyString = Objects.requireNonNull(keyString);
assert IntPair.ORDERING.isStrictlyOrdered(keys); // ordered and unique
}
+ /** Creates a Step. */
+ static Step create(LatticeTable source, LatticeTable target,
+ List<IntPair> keys, LatticeSpace space) {
+ final StringBuilder b = new StringBuilder();
+ for (IntPair key : keys) {
+ b.append(' ')
+ .append(space.fieldName(source, key.source))
+ .append(':')
+ .append(space.fieldName(target, key.target));
+ }
+ return new Step(source, target, keys, b.toString());
+ }
+
@Override public int hashCode() {
return Objects.hash(source, target, keys);
}
@@ -58,20 +77,7 @@ class Step extends DefaultEdge {
}
@Override public String toString() {
- final StringBuilder b = new StringBuilder()
- .append("Step(")
- .append(source)
- .append(", ")
- .append(target)
- .append(",");
- for (IntPair key : keys) {
- b.append(' ')
- .append(source().field(key.source).getName())
- .append(':')
- .append(target().field(key.target).getName());
- }
- return b.append(")")
- .toString();
+ return "Step(" + source + ", " + target + "," + keyString + ")";
}
LatticeTable source() {
@@ -87,13 +93,21 @@ class Step extends DefaultEdge {
final List<Integer> sourceColumns = IntPair.left(keys);
final RelOptTable targetTable = target().t;
final List<Integer> targetColumns = IntPair.right(keys);
- final boolean forwardForeignKey =
- statisticProvider.isForeignKey(sourceTable, sourceColumns, targetTable,
- targetColumns)
+ final boolean noDerivedSourceColumns =
+ sourceColumns.stream().allMatch(i ->
+ i < sourceTable.getRowType().getFieldCount());
+ final boolean noDerivedTargetColumns =
+ targetColumns.stream().allMatch(i ->
+ i < targetTable.getRowType().getFieldCount());
+ final boolean forwardForeignKey = noDerivedSourceColumns
+ && noDerivedTargetColumns
+ && statisticProvider.isForeignKey(sourceTable, sourceColumns,
+ targetTable, targetColumns)
&& statisticProvider.isKey(targetTable, targetColumns);
- final boolean backwardForeignKey =
- statisticProvider.isForeignKey(targetTable, targetColumns, sourceTable,
- sourceColumns)
+ final boolean backwardForeignKey = noDerivedSourceColumns
+ && noDerivedTargetColumns
+ && statisticProvider.isForeignKey(targetTable, targetColumns,
+ sourceTable, sourceColumns)
&& statisticProvider.isKey(sourceTable, sourceColumns);
if (backwardForeignKey != forwardForeignKey) {
return backwardForeignKey;
@@ -124,6 +138,12 @@ class Step extends DefaultEdge {
/** Creates {@link Step} instances. */
static class Factory implements AttributedDirectedGraph.AttributedEdgeFactory<
LatticeTable, Step> {
+ private final LatticeSpace space;
+
+ Factory(LatticeSpace space) {
+ this.space = Objects.requireNonNull(space);
+ }
+
public Step createEdge(LatticeTable source, LatticeTable target) {
throw new UnsupportedOperationException();
}
@@ -132,7 +152,7 @@ class Step extends DefaultEdge {
Object... attributes) {
@SuppressWarnings("unchecked") final List<IntPair> keys =
(List) attributes[0];
- return new Step(source, target, keys);
+ return Step.create(source, target, keys, space);
}
}
}
diff --git a/core/src/main/java/org/apache/calcite/rex/RexToSqlNodeConverter.java b/core/src/main/java/org/apache/calcite/rex/RexToSqlNodeConverter.java
index 3e2a966..460d8f9 100644
--- a/core/src/main/java/org/apache/calcite/rex/RexToSqlNodeConverter.java
+++ b/core/src/main/java/org/apache/calcite/rex/RexToSqlNodeConverter.java
@@ -22,6 +22,10 @@ import org.apache.calcite.sql.SqlNode;
/**
* Converts expressions from {@link RexNode} to {@link SqlNode}.
+ *
+ * <p>For most purposes, {@link org.apache.calcite.rel.rel2sql.SqlImplementor}
+ * is superior. See in particular
+ * {@link org.apache.calcite.rel.rel2sql.SqlImplementor.Context#toSql(RexProgram, RexNode)}.
*/
public interface RexToSqlNodeConverter {
//~ Methods ----------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/materialize/LatticeSuggesterTest.java b/core/src/test/java/org/apache/calcite/materialize/LatticeSuggesterTest.java
index 6043eda..8c691f2 100644
--- a/core/src/test/java/org/apache/calcite/materialize/LatticeSuggesterTest.java
+++ b/core/src/test/java/org/apache/calcite/materialize/LatticeSuggesterTest.java
@@ -27,6 +27,7 @@ import org.apache.calcite.sql.fun.SqlLibraryOperatorTableFactory;
import org.apache.calcite.sql.parser.SqlParseException;
import org.apache.calcite.sql.parser.SqlParser;
import org.apache.calcite.statistic.MapSqlStatisticProvider;
+import org.apache.calcite.statistic.QuerySqlStatisticProvider;
import org.apache.calcite.test.CalciteAssert;
import org.apache.calcite.test.FoodMartQuerySet;
import org.apache.calcite.test.SlowTests;
@@ -614,6 +615,67 @@ public class LatticeSuggesterTest {
assertThat(t.s.latticeMap.size(), is(1));
}
+ /** A tricky case involving a CTE (WITH), a join condition that references an
+ * expression, a complex WHERE clause, and some other queries. */
+ @Test public void testJoinUsingExpression() throws Exception {
+ final Tester t = new Tester().foodmart().withEvolve(true);
+
+ final String q0 = "with c as (select\n"
+ + " \"customer_id\" + 1 as \"customer_id\",\n"
+ + " \"fname\"\n"
+ + " from \"customer\")\n"
+ + "select\n"
+ + " COUNT(distinct c.\"customer_id\") as \"customer.count\"\n"
+ + "from c\n"
+ + "left join \"sales_fact_1997\" using (\"customer_id\")\n"
+ + "where case\n"
+ + " when lower(substring(\"fname\", 11, 1)) in (0, 1)\n"
+ + " then 'Amy Adams'\n"
+ + " when lower(substring(\"fname\", 11, 1)) in (2, 3)\n"
+ + " then 'Barry Manilow'\n"
+ + " when lower(substring(\"fname\", 11, 1)) in ('y', 'z')\n"
+ + " then 'Yvonne Zane'\n"
+ + " end = 'Barry Manilow'\n"
+ + "LIMIT 500";
+ final String q1 = "select * from \"customer\"";
+ final String q2 = "select sum(\"product_id\") from \"product\"";
+ // similar to q0, but "c" is a sub-select rather than CTE
+ final String q4 = "select\n"
+ + " COUNT(distinct c.\"customer_id\") as \"customer.count\"\n"
+ + "from (select \"customer_id\" + 1 as \"customer_id\", \"fname\"\n"
+ + " from \"customer\") as c\n"
+ + "left join \"sales_fact_1997\" using (\"customer_id\")\n";
+ t.addQuery(q1);
+ t.addQuery(q0);
+ t.addQuery(q1);
+ t.addQuery(q4);
+ t.addQuery(q2);
+ assertThat(t.s.latticeMap.size(), is(3));
+ }
+
+ @Test public void testDerivedColRef() throws Exception {
+ final FrameworkConfig config = Frameworks.newConfigBuilder()
+ .defaultSchema(Tester.schemaFrom(CalciteAssert.SchemaSpec.SCOTT))
+ .statisticProvider(QuerySqlStatisticProvider.SILENT_CACHING_INSTANCE)
+ .build();
+ final Tester t = new Tester(config).foodmart().withEvolve(true);
+
+ final String q0 = "select\n"
+ + " min(c.\"fname\") as \"customer.count\"\n"
+ + "from \"customer\" as c\n"
+ + "left join \"sales_fact_1997\" as s\n"
+ + "on c.\"customer_id\" + 1 = s.\"customer_id\" + 2";
+ t.addQuery(q0);
+ assertThat(t.s.latticeMap.size(), is(1));
+ assertThat(t.s.latticeMap.keySet().iterator().next(),
+ is("sales_fact_1997 (customer:+($2, 2)):[MIN(customer.fname)]"));
+ assertThat(t.s.space.g.toString(),
+ is("graph(vertices: [[foodmart, customer],"
+ + " [foodmart, sales_fact_1997]], "
+ + "edges: [Step([foodmart, sales_fact_1997],"
+ + " [foodmart, customer], +($2, 2):+($0, 1))])"));
+ }
+
/** Creates a matcher that matches query graphs to strings. */
private BaseMatcher<List<Lattice>> isGraphs(
String... strings) {