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 <[email protected]> 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) {
