[CALCITE-1870] Lattice suggester Don't add a query graph if it is cyclic.
More concise descriptions of join graphs, and add FoodMart test case. Add a test based on TPC-DS. Make FoodMartQueryTest a top-level class, and add a test that runs through all of its queries and suggests lattices. API changes to Lattice. Rename class Lattice.Node to LatticeNode, add sub-class LatticeRootNode that is immutable and has state that was previously in Lattice. LatticeSuggester makes heavy use of LatticeNode. Move column unique name into Column, and remove the Lattice.uniqueColumnNames field. DirectedGraph.toString sorts lists of vertices and edges. Add materialized views to documentation menu; tweak SQL formatting. In HepPlanner, rename noDAG to noDag. SqlImplementor: Translate simple RexNode to SQL without requiring RelBuilder; SqlImplementor.Context is now static, but not all derived classes are. Fix a typo in UdfTest. Project: http://git-wip-us.apache.org/repos/asf/calcite/repo Commit: http://git-wip-us.apache.org/repos/asf/calcite/commit/b47413a1 Tree: http://git-wip-us.apache.org/repos/asf/calcite/tree/b47413a1 Diff: http://git-wip-us.apache.org/repos/asf/calcite/diff/b47413a1 Branch: refs/heads/master Commit: b47413a1d648455c43dbe8d51df926ebd68b3a36 Parents: 6284d3c Author: Julian Hyde <[email protected]> Authored: Thu Jul 6 15:19:58 2017 -0700 Committer: Julian Hyde <[email protected]> Committed: Mon Oct 29 16:51:43 2018 -0700 ---------------------------------------------------------------------- .../org/apache/calcite/materialize/Lattice.java | 594 +++++++++++---- .../calcite/materialize/LatticeChildNode.java | 46 ++ .../apache/calcite/materialize/LatticeNode.java | 116 +++ .../calcite/materialize/LatticeRootNode.java | 86 +++ .../calcite/materialize/LatticeSpace.java | 135 ++++ .../calcite/materialize/LatticeSuggester.java | 755 +++++++++++++++++++ .../calcite/materialize/LatticeTable.java | 56 ++ .../materialize/MapSqlStatisticProvider.java | 88 +++ .../apache/calcite/materialize/MutableNode.java | 127 ++++ .../org/apache/calcite/materialize/Path.java | 45 ++ .../materialize/SqlStatisticProvider.java | 31 + .../org/apache/calcite/materialize/Step.java | 113 +++ .../org/apache/calcite/model/JsonSchema.java | 4 + .../org/apache/calcite/model/ModelHandler.java | 4 +- .../org/apache/calcite/plan/RelOptLattice.java | 2 +- .../org/apache/calcite/plan/hep/HepPlanner.java | 34 +- .../calcite/rel/rel2sql/SqlImplementor.java | 84 ++- .../apache/calcite/schema/impl/StarTable.java | 2 +- .../calcite/sql/validate/SqlValidatorUtil.java | 7 + .../apache/calcite/tools/FrameworkConfig.java | 15 + .../org/apache/calcite/tools/Frameworks.java | 91 ++- .../util/graph/AttributedDirectedGraph.java | 113 +++ .../util/graph/DefaultDirectedGraph.java | 34 +- .../apache/calcite/util/graph/DefaultEdge.java | 6 +- .../apache/calcite/util/mapping/IntPair.java | 53 ++ .../materialize/LatticeSuggesterTest.java | 626 +++++++++++++++ .../org/apache/calcite/test/CalciteSuite.java | 2 + .../apache/calcite/test/FoodMartQuerySet.java | 85 +++ .../org/apache/calcite/test/FoodmartTest.java | 69 +- .../java/org/apache/calcite/test/JdbcTest.java | 10 +- .../org/apache/calcite/test/LatticeTest.java | 139 +++- .../java/org/apache/calcite/test/UdfTest.java | 4 +- .../calcite/util/graph/DirectedGraphTest.java | 70 ++ .../hsqldb-foodmart-auto-lattice-model.json | 31 + .../materialize/TpcdsLatticeSuggesterTest.java | 206 +++++ site/_data/docs.yml | 1 + site/_docs/lattice.md | 232 +++++- site/_docs/materialized_views.md | 40 +- 38 files changed, 3811 insertions(+), 345 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/calcite/blob/b47413a1/core/src/main/java/org/apache/calcite/materialize/Lattice.java ---------------------------------------------------------------------- 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 3b56008..a4724eb 100644 --- a/core/src/main/java/org/apache/calcite/materialize/Lattice.java +++ b/core/src/main/java/org/apache/calcite/materialize/Lattice.java @@ -19,6 +19,7 @@ package org.apache.calcite.materialize; import org.apache.calcite.avatica.AvaticaUtils; import org.apache.calcite.jdbc.CalcitePrepare; import org.apache.calcite.jdbc.CalciteSchema; +import org.apache.calcite.linq4j.Ord; import org.apache.calcite.linq4j.tree.Primitive; import org.apache.calcite.plan.RelOptUtil; import org.apache.calcite.prepare.CalcitePrepareImpl; @@ -28,6 +29,7 @@ import org.apache.calcite.rel.core.JoinRelType; import org.apache.calcite.rel.core.TableScan; import org.apache.calcite.rel.logical.LogicalJoin; import org.apache.calcite.rel.logical.LogicalProject; +import org.apache.calcite.rel.rel2sql.SqlImplementor; import org.apache.calcite.rex.RexCall; import org.apache.calcite.rex.RexInputRef; import org.apache.calcite.rex.RexNode; @@ -46,6 +48,9 @@ import org.apache.calcite.sql.SqlUtil; import org.apache.calcite.sql.fun.SqlStdOperatorTable; import org.apache.calcite.sql.validate.SqlValidatorUtil; import org.apache.calcite.util.ImmutableBitSet; +import org.apache.calcite.util.Litmus; +import org.apache.calcite.util.Pair; +import org.apache.calcite.util.Util; import org.apache.calcite.util.graph.DefaultDirectedGraph; import org.apache.calcite.util.graph.DefaultEdge; import org.apache.calcite.util.graph.DirectedGraph; @@ -55,24 +60,37 @@ import org.apache.calcite.util.mapping.IntPair; import com.google.common.base.Preconditions; import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableListMultimap; +import com.google.common.collect.ImmutableSortedSet; import com.google.common.collect.Lists; import com.google.common.collect.Ordering; import java.util.ArrayList; +import java.util.Arrays; import java.util.HashSet; import java.util.IdentityHashMap; +import java.util.LinkedHashMap; +import java.util.LinkedHashSet; import java.util.List; import java.util.Map; import java.util.Objects; import java.util.Set; +import java.util.SortedSet; +import java.util.TreeSet; +import java.util.function.Function; +import java.util.function.IntFunction; +import java.util.stream.Collectors; +import javax.annotation.Nonnull; +import javax.annotation.Nullable; +import javax.annotation.ParametersAreNonnullByDefault; /** * Structure that allows materialized views based upon a star schema to be * recognized and recommended. */ +@ParametersAreNonnullByDefault public class Lattice { public final CalciteSchema rootSchema; - public final ImmutableList<Node> nodes; + public final LatticeRootNode rootNode; public final ImmutableList<Column> columns; public final boolean auto; public final boolean algorithm; @@ -80,38 +98,24 @@ public class Lattice { public final double rowCountEstimate; public final ImmutableList<Measure> defaultMeasures; public final ImmutableList<Tile> tiles; - public final ImmutableList<String> uniqueColumnNames; public final LatticeStatisticProvider statisticProvider; - private Lattice(CalciteSchema rootSchema, ImmutableList<Node> nodes, + private Lattice(CalciteSchema rootSchema, LatticeRootNode rootNode, boolean auto, boolean algorithm, long algorithmMaxMillis, LatticeStatisticProvider.Factory statisticProviderFactory, - Double rowCountEstimate, ImmutableList<Column> columns, - ImmutableList<Measure> defaultMeasures, ImmutableList<Tile> tiles) { + @Nullable Double rowCountEstimate, ImmutableList<Column> columns, + ImmutableSortedSet<Measure> defaultMeasures, ImmutableList<Tile> tiles) { this.rootSchema = rootSchema; - this.nodes = Objects.requireNonNull(nodes); + this.rootNode = Objects.requireNonNull(rootNode); this.columns = Objects.requireNonNull(columns); this.auto = auto; this.algorithm = algorithm; this.algorithmMaxMillis = algorithmMaxMillis; - this.defaultMeasures = Objects.requireNonNull(defaultMeasures); + this.defaultMeasures = defaultMeasures.asList(); // unique and sorted this.tiles = Objects.requireNonNull(tiles); - // Validate that nodes form a tree; each node except the first references - // a predecessor. - for (int i = 0; i < nodes.size(); i++) { - Node node = nodes.get(i); - if (i == 0) { - assert node.parent == null; - } else { - assert nodes.subList(0, i).contains(node.parent); - } - } + assert isValid(Litmus.THROW); - uniqueColumnNames = - ImmutableList.copyOf( - SqlValidatorUtil.uniquify( - Lists.transform(columns, input -> input.alias), true)); if (rowCountEstimate == null) { // We could improve this when we fix // [CALCITE-429] Add statistics SPI for lattice optimization algorithm @@ -128,8 +132,23 @@ public class Lattice { return builder(schema, sql).auto(auto).build(); } + private boolean isValid(Litmus litmus) { + if (!rootNode.isValid(litmus)) { + return false; + } + for (Measure measure : defaultMeasures) { + for (Column arg : measure.args) { + if (columns.get(arg.ordinal) != arg) { + return litmus.fail("measure argument must be a column registered in" + + " this lattice: {}", measure); + } + } + } + return litmus.succeed(); + } + private static void populateAliases(SqlNode from, List<String> aliases, - String current) { + @Nullable String current) { if (from instanceof SqlJoin) { SqlJoin join = (SqlJoin) from; populateAliases(join.getLeft(), aliases, null); @@ -203,6 +222,10 @@ public class Lattice { throw new AssertionError("input not found"); } + @Override public String toString() { + return rootNode + ":" + defaultMeasures; + } + /** Generates a SQL query to populate a tile of the lattice specified by a * given set of columns and measures. */ public String sql(ImmutableBitSet groupSet, List<Measure> aggCallList) { @@ -213,7 +236,7 @@ public class Lattice { * given set of columns and measures, optionally grouping. */ public String sql(ImmutableBitSet groupSet, boolean group, List<Measure> aggCallList) { - final List<Node> usedNodes = new ArrayList<>(); + final List<LatticeNode> usedNodes = new ArrayList<>(); if (group) { final ImmutableBitSet.Builder columnSetBuilder = groupSet.rebuild(); for (Measure call : aggCallList) { @@ -225,17 +248,18 @@ public class Lattice { // Figure out which nodes are needed. Use a node if its columns are used // or if has a child whose columns are used. - for (Node node : nodes) { + for (LatticeNode node : rootNode.descendants) { if (ImmutableBitSet.range(node.startCol, node.endCol) .intersects(columnSet)) { - use(usedNodes, node); + node.use(usedNodes); + } + + if (usedNodes.isEmpty()) { + usedNodes.add(rootNode); } - } - if (usedNodes.isEmpty()) { - usedNodes.add(nodes.get(0)); } } else { - usedNodes.addAll(nodes); + usedNodes.addAll(rootNode.descendants); } final SqlDialect dialect = SqlDialect.DatabaseProduct.CALCITE.getDialect(); @@ -243,6 +267,9 @@ public class Lattice { final StringBuilder groupBuf = new StringBuilder("\nGROUP BY "); int k = 0; final Set<String> columnNames = new HashSet<>(); + final SqlWriter w = createSqlWriter(dialect, buf, f -> { + throw new UnsupportedOperationException(); + }); if (groupSet != null) { for (int i : groupSet) { if (k++ > 0) { @@ -250,18 +277,16 @@ public class Lattice { groupBuf.append(", "); } final Column column = columns.get(i); - dialect.quoteIdentifier(buf, column.identifiers()); - dialect.quoteIdentifier(groupBuf, column.identifiers()); - final String fieldName = uniqueColumnNames.get(i); - columnNames.add(fieldName); - if (!column.alias.equals(fieldName)) { + column.toSql(w); + column.toSql(w.with(groupBuf)); + if (column instanceof BaseColumn) { + columnNames.add(((BaseColumn) column).column); + } + if (!column.alias.equals(column.defaultAlias())) { buf.append(" AS "); - dialect.quoteIdentifier(buf, fieldName); + dialect.quoteIdentifier(buf, column.alias); } } - if (groupSet.isEmpty()) { - groupBuf.append("()"); - } int m = 0; for (Measure measure : aggCallList) { if (k++ > 0) { @@ -277,7 +302,7 @@ public class Lattice { if (z++ > 0) { buf.append(", "); } - dialect.quoteIdentifier(buf, arg.identifiers()); + arg.toSql(w); } } buf.append(") AS "); @@ -291,25 +316,26 @@ public class Lattice { buf.append("*"); } buf.append("\nFROM "); - for (Node node : usedNodes) { - if (node.parent != null) { + for (LatticeNode node : usedNodes) { + if (node instanceof LatticeChildNode) { buf.append("\nJOIN "); } - dialect.quoteIdentifier(buf, node.scan.getTable().getQualifiedName()); + dialect.quoteIdentifier(buf, node.table.t.getQualifiedName()); buf.append(" AS "); dialect.quoteIdentifier(buf, node.alias); - if (node.parent != null) { + if (node instanceof LatticeChildNode) { + final LatticeChildNode node1 = (LatticeChildNode) node; buf.append(" ON "); k = 0; - for (IntPair pair : node.link) { + for (IntPair pair : node1.link) { if (k++ > 0) { buf.append(" AND "); } - final Column left = columns.get(node.parent.startCol + pair.source); - dialect.quoteIdentifier(buf, left.identifiers()); + final Column left = columns.get(node1.parent.startCol + pair.source); + left.toSql(w); buf.append(" = "); final Column right = columns.get(node.startCol + pair.target); - dialect.quoteIdentifier(buf, right.identifiers()); + right.toSql(w); } } } @@ -318,11 +344,21 @@ public class Lattice { + buf); } if (group) { + if (groupSet.isEmpty()) { + groupBuf.append("()"); + } buf.append(groupBuf); } return buf.toString(); } + /** Creates a context to which SQL can be generated. */ + public SqlWriter createSqlWriter(SqlDialect dialect, StringBuilder buf, + IntFunction<SqlNode> field) { + return new SqlWriter(this, dialect, buf, + new SqlImplementor.SimpleContext(dialect, field)); + } + /** Returns a SQL query that counts the number of distinct values of the * attributes given in {@code groupSet}. */ public String countSql(ImmutableBitSet groupSet) { @@ -331,31 +367,31 @@ public class Lattice { + ")"; } - private static void use(List<Node> usedNodes, Node node) { - if (!usedNodes.contains(node)) { - if (node.parent != null) { - use(usedNodes, node.parent); - } - usedNodes.add(node); - } - } - public StarTable createStarTable() { final List<Table> tables = new ArrayList<>(); - for (Node node : nodes) { - tables.add(node.scan.getTable().unwrap(Table.class)); + for (LatticeNode node : rootNode.descendants) { + tables.add(node.table.t.unwrap(Table.class)); } return StarTable.of(this, tables); } public static Builder builder(CalciteSchema calciteSchema, String sql) { - return new Builder(calciteSchema, sql); + return builder(new LatticeSpace(MapSqlStatisticProvider.INSTANCE), + calciteSchema, sql); + } + + static Builder builder(LatticeSpace space, CalciteSchema calciteSchema, + String sql) { + return new Builder(space, calciteSchema, sql); } public List<Measure> toMeasures(List<AggregateCall> aggCallList) { - return Lists.transform(aggCallList, - call -> new Measure(call.getAggregation(), - Lists.transform(call.getArgList(), columns::get))); + return Lists.transform(aggCallList, this::toMeasure); + } + + private Measure toMeasure(AggregateCall aggCall) { + return new Measure(aggCall.getAggregation(), aggCall.isDistinct(), + aggCall.name, Lists.transform(aggCall.getArgList(), columns::get)); } public Iterable<? extends Tile> computeTiles() { @@ -409,73 +445,123 @@ public class Lattice { return Math.min(v, factCount); } - /** Source relation of a lattice. - * - * <p>Relations form a tree; all relations except the root relation - * (the fact table) have precisely one parent and an equi-join - * condition on one or more pairs of columns linking to it. */ - public static class Node { - public final TableScan scan; - public final Node parent; - public final ImmutableList<IntPair> link; - public final int startCol; - public final int endCol; - public final String alias; + public List<String> uniqueColumnNames() { + return Lists.transform(columns, column -> column.alias); + } - public Node(TableScan scan, Node parent, List<IntPair> link, - int startCol, int endCol, String alias) { - this.scan = Objects.requireNonNull(scan); - this.parent = parent; - this.link = link == null ? null : ImmutableList.copyOf(link); - assert (parent == null) == (link == null); - assert startCol >= 0; - assert endCol > startCol; - this.startCol = startCol; - this.endCol = endCol; - this.alias = alias; + Pair<Path, Integer> columnToPathOffset(BaseColumn c) { + for (Pair<LatticeNode, Path> p + : Pair.zip(rootNode.descendants, rootNode.paths)) { + if (p.left.alias.equals(c.table)) { + return Pair.of(p.right, c.ordinal - p.left.startCol); + } + } + throw new AssertionError("lattice column not found: " + c); + } + + /** Returns the set of tables in this lattice. */ + public Set<LatticeTable> tables() { + return rootNode.descendants.stream().map(n -> n.table) + .collect(Collectors.toCollection(LinkedHashSet::new)); + } + + /** Returns the ordinal, within all of the columns in this Lattice, of the + * first column in the table with a given alias. + * Returns -1 if the table is not found. */ + public int firstColumn(String tableAlias) { + for (Column column : columns) { + if (column instanceof BaseColumn + && ((BaseColumn) column).table.equals(tableAlias)) { + return column.ordinal; + } } + return -1; } /** Edge in the temporary graph. */ private static class Edge extends DefaultEdge { - public static final DirectedGraph.EdgeFactory<RelNode, Edge> FACTORY = + public static final DirectedGraph.EdgeFactory<Vertex, Edge> FACTORY = Edge::new; final List<IntPair> pairs = new ArrayList<>(); - Edge(RelNode source, RelNode target) { + Edge(Vertex source, Vertex target) { super(source, target); } - public RelNode getTarget() { - return (RelNode) target; + Vertex getTarget() { + return (Vertex) target; + } + + Vertex getSource() { + return (Vertex) source; } + } + + /** Vertex in the temporary graph. */ + private static class Vertex { + final LatticeTable table; + final String alias; - public RelNode getSource() { - return (RelNode) source; + private Vertex(LatticeTable table, String alias) { + this.table = table; + this.alias = alias; } } - /** Measure in a lattice. */ + /** A measure within a {@link Lattice}. + * + * <p>It is immutable. + * + * <p>Examples: SUM(products.weight), COUNT() (means "COUNT(*")), + * COUNT(DISTINCT customer.id). + */ public static class Measure implements Comparable<Measure> { public final SqlAggFunction agg; + public final boolean distinct; + @Nullable public final String name; public final ImmutableList<Column> args; + public final String digest; - public Measure(SqlAggFunction agg, Iterable<Column> args) { + public Measure(SqlAggFunction agg, boolean distinct, @Nullable String name, + Iterable<Column> args) { this.agg = Objects.requireNonNull(agg); + this.distinct = distinct; + this.name = name; this.args = ImmutableList.copyOf(args); + + final StringBuilder b = new StringBuilder() + .append(agg) + .append(distinct ? "(DISTINCT " : "("); + for (Ord<Column> arg : Ord.zip(this.args)) { + if (arg.i > 0) { + b.append(", "); + } + if (arg.e instanceof BaseColumn) { + b.append(((BaseColumn) arg.e).table); + b.append('.'); + b.append(((BaseColumn) arg.e).column); + } else { + b.append(arg.e.alias); + } + } + b.append(')'); + this.digest = b.toString(); } - public int compareTo(Measure measure) { - int c = agg.getName().compareTo(measure.agg.getName()); - if (c != 0) { - return c; + public int compareTo(@Nonnull Measure measure) { + int c = compare(args, measure.args); + if (c == 0) { + c = agg.getName().compareTo(measure.agg.getName()); + if (c == 0) { + c = Boolean.compare(distinct, measure.distinct); + } } - return compare(args, measure.args); + return c; } @Override public String toString() { - return "Measure: [agg: " + agg + ", args: " + args + "]"; + return digest; } @Override public int hashCode() { @@ -486,7 +572,8 @@ public class Lattice { return obj == this || obj instanceof Measure && this.agg.equals(((Measure) obj).agg) - && this.args.equals(((Measure) obj).args); + && this.args.equals(((Measure) obj).args) + && this.distinct == ((Measure) obj).distinct; } /** Returns the set of distinct argument ordinals. */ @@ -500,7 +587,7 @@ public class Lattice { /** Returns a list of argument ordinals. */ public List<Integer> argOrdinals() { - return Lists.transform(args, input -> input.ordinal); + return Lists.transform(args, column -> column.ordinal); } private static int compare(List<Column> list0, List<Column> list1) { @@ -515,21 +602,25 @@ public class Lattice { } return Utilities.compare(list0.size(), list1.size()); } + + /** Copies this measure, mapping its arguments using a given function. */ + Measure copy(Function<Column, Column> mapper) { + return new Measure(agg, distinct, name, Util.transform(args, mapper)); + } } - /** Column in a lattice. Columns are identified by table alias and - * column name, and may have an additional alias that is unique + /** Column in a lattice. May be an a base column or an expression, + * and may have an additional alias that is unique * within the entire lattice. */ - public static class Column implements Comparable<Column> { + public abstract static class Column implements Comparable<Column> { + /** Ordinal of the column within the lattice. */ public final int ordinal; - public final String table; - public final String column; + /** Alias of the column, unique within the lattice. Derived from the column + * name, automatically disambiguated if necessary. */ public final String alias; - private Column(int ordinal, String table, String column, String alias) { + private Column(int ordinal, String alias) { this.ordinal = ordinal; - this.table = Objects.requireNonNull(table); - this.column = Objects.requireNonNull(column); this.alias = Objects.requireNonNull(alias); } @@ -556,6 +647,29 @@ public class Lattice { && this.ordinal == ((Column) obj).ordinal; } + public abstract void toSql(SqlWriter writer); + + /** The alias that SQL would give to this expression. */ + public abstract String defaultAlias(); + } + + /** Column in a lattice. Columns are identified by table alias and + * column name, and may have an additional alias that is unique + * within the entire lattice. */ + public static class BaseColumn extends Column { + /** Alias of the table reference that the column belongs to. */ + public final String table; + + /** Name of the column. Unique within the table reference, but not + * necessarily within the lattice. */ + @Nonnull public final String column; + + private BaseColumn(int ordinal, String table, String column, String alias) { + super(ordinal, alias); + this.table = Objects.requireNonNull(table); + this.column = Objects.requireNonNull(column); + } + @Override public String toString() { return identifiers().toString(); } @@ -563,15 +677,77 @@ public class Lattice { public List<String> identifiers() { return ImmutableList.of(table, column); } + + public void toSql(SqlWriter writer) { + writer.dialect.quoteIdentifier(writer.buf, identifiers()); + } + + public String defaultAlias() { + return column; + } + } + + /** Column in a lattice that is based upon a SQL expression. */ + public static class DerivedColumn extends Column { + @Nonnull public final RexNode e; + @Nonnull final List<String> tables; + + private DerivedColumn(int ordinal, String alias, RexNode e, + List<String> tables) { + super(ordinal, alias); + this.e = e; + this.tables = ImmutableList.copyOf(tables); + } + + @Override public String toString() { + return Arrays.toString(new Object[] {e, alias}); + } + + public void toSql(SqlWriter writer) { + writer.write(e); + } + + public String defaultAlias() { + // there is no default alias for an expression + return null; + } + } + + /** The information necessary to convert a column to SQL. */ + public static class SqlWriter { + public final Lattice lattice; + public final StringBuilder buf; + public final SqlDialect dialect; + private final SqlImplementor.SimpleContext context; + + SqlWriter(Lattice lattice, SqlDialect dialect, StringBuilder buf, + SqlImplementor.SimpleContext context) { + this.lattice = lattice; + this.context = context; + this.buf = buf; + this.dialect = dialect; + } + + /** Re-binds this writer to a different {@link StringBuilder}. */ + public SqlWriter with(StringBuilder buf) { + return new SqlWriter(lattice, dialect, buf, context); + } + + /** Writes an expression. */ + public SqlWriter write(RexNode e) { + final SqlNode node = context.toSql(null, e); + buf.append(node.toSqlString(dialect)); + return this; + } } /** Lattice builder. */ public static class Builder { - private final List<Node> nodes = new ArrayList<>(); - private final ImmutableList<Column> columns; + private final LatticeRootNode rootNode; + private final ImmutableList<BaseColumn> baseColumns; private final ImmutableListMultimap<String, Column> columnsByAlias; - private final ImmutableList.Builder<Measure> defaultMeasureListBuilder = - ImmutableList.builder(); + private final SortedSet<Measure> defaultMeasureSet = + new TreeSet<>(); private final ImmutableList.Builder<Tile> tileListBuilder = ImmutableList.builder(); private final CalciteSchema rootSchema; @@ -580,8 +756,10 @@ public class Lattice { private boolean auto = true; private Double rowCountEstimate; private String statisticProvider; + private Map<String, DerivedColumn> derivedColumnsByName = + new LinkedHashMap<>(); - public Builder(CalciteSchema schema, String sql) { + public Builder(LatticeSpace space, CalciteSchema schema, String sql) { this.rootSchema = Objects.requireNonNull(schema.root()); Preconditions.checkArgument(rootSchema.isRoot(), "must be root schema"); CalcitePrepare.ConvertResult parsed = @@ -598,14 +776,18 @@ public class Lattice { populateAliases(((SqlSelect) parsed.sqlNode).getFrom(), aliases, null); // Build a graph. - final DirectedGraph<RelNode, Edge> graph = + final DirectedGraph<Vertex, Edge> graph = DefaultDirectedGraph.create(Edge.FACTORY); - for (RelNode node : relNodes) { - graph.addVertex(node); + final List<Vertex> vertices = new ArrayList<>(); + for (Pair<RelNode, String> p : Pair.zip(relNodes, aliases)) { + final LatticeTable table = space.register(p.left.getTable()); + final Vertex vertex = new Vertex(table, p.right); + graph.addVertex(vertex); + vertices.add(vertex); } for (int[][] tempLink : tempLinks) { - final RelNode source = relNodes.get(tempLink[0][0]); - final RelNode target = relNodes.get(tempLink[1][0]); + final Vertex source = vertices.get(tempLink[0][0]); + final Vertex target = vertices.get(tempLink[1][0]); Edge edge = graph.getEdge(source, target); if (edge == null) { edge = graph.addEdge(source, target); @@ -615,52 +797,62 @@ public class Lattice { // Convert the graph into a tree of nodes, each connected to a parent and // with a join condition to that parent. - Node previous = null; - final Map<RelNode, Node> map = new IdentityHashMap<>(); - int previousColumn = 0; - for (RelNode relNode : TopologicalOrderIterator.of(graph)) { - final List<Edge> edges = graph.getInwardEdges(relNode); - Node node; - final int column = previousColumn - + relNode.getRowType().getFieldCount(); - if (previous == null) { + MutableNode root = null; + final Map<LatticeTable, MutableNode> map = new IdentityHashMap<>(); + for (Vertex vertex : TopologicalOrderIterator.of(graph)) { + final List<Edge> edges = graph.getInwardEdges(vertex); + MutableNode node; + if (root == null) { if (!edges.isEmpty()) { throw new RuntimeException("root node must not have relationships: " - + relNode); + + vertex); } - node = new Node((TableScan) relNode, null, null, - previousColumn, column, aliases.get(nodes.size())); + root = node = new MutableNode(vertex.table); + node.alias = vertex.alias; } else { if (edges.size() != 1) { throw new RuntimeException( - "child node must have precisely one parent: " + relNode); + "child node must have precisely one parent: " + vertex); } final Edge edge = edges.get(0); - node = new Node((TableScan) relNode, - map.get(edge.getSource()), edge.pairs, previousColumn, column, - aliases.get(nodes.size())); + final MutableNode parent = map.get(edge.getSource().table); + final Step step = + new Step(edge.getSource().table, + edge.getTarget().table, edge.pairs); + node = new MutableNode(vertex.table, parent, step); + node.alias = vertex.alias; } - nodes.add(node); - map.put(relNode, node); - previous = node; - previousColumn = column; + map.put(vertex.table, node); } + assert root != null; + final Fixer fixer = new Fixer(); + fixer.fixUp(root); + baseColumns = fixer.columnList.build(); + columnsByAlias = fixer.columnAliasList.build(); + rootNode = new LatticeRootNode(space, root); + } - final ImmutableList.Builder<Column> builder = ImmutableList.builder(); - final ImmutableListMultimap.Builder<String, Column> aliasBuilder = - ImmutableListMultimap.builder(); - int c = 0; - for (Node node : nodes) { - if (node.scan != null) { - for (String name : node.scan.getRowType().getFieldNames()) { - final Column column = new Column(c++, node.alias, name, name); - builder.add(column); - aliasBuilder.put(column.alias, column); - } - } + /** Creates a Builder based upon a mutable node. */ + Builder(LatticeSpace space, CalciteSchema schema, + MutableNode mutableNode) { + this.rootSchema = schema; + + final Fixer fixer = new Fixer(); + fixer.fixUp(mutableNode); + + final LatticeRootNode node0 = new LatticeRootNode(space, mutableNode); + final LatticeRootNode node1 = space.nodeMap.get(node0.digest); + final LatticeRootNode node; + if (node1 != null) { + node = node1; + } else { + node = node0; + space.nodeMap.put(node0.digest, node0); } - columns = builder.build(); - columnsByAlias = aliasBuilder.build(); + + this.rootNode = node; + baseColumns = fixer.columnList.build(); + columnsByAlias = fixer.columnAliasList.build(); } /** Sets the "auto" attribute (default true). */ @@ -704,16 +896,21 @@ public class Lattice { this.statisticProvider) : Lattices.CACHED_SQL; Preconditions.checkArgument(rootSchema.isRoot(), "must be root schema"); - return new Lattice(rootSchema, ImmutableList.copyOf(nodes), auto, + final ImmutableList.Builder<Column> columnBuilder = + ImmutableList.<Column>builder() + .addAll(baseColumns) + .addAll(derivedColumnsByName.values()); + return new Lattice(rootSchema, rootNode, auto, algorithm, algorithmMaxMillis, statisticProvider, rowCountEstimate, - columns, defaultMeasureListBuilder.build(), tileListBuilder.build()); + columnBuilder.build(), ImmutableSortedSet.copyOf(defaultMeasureSet), + tileListBuilder.build()); } /** Resolves the arguments of a * {@link org.apache.calcite.model.JsonMeasure}. They must either be null, * a string, or a list of strings. Throws if the structure is invalid, or if * any of the columns do not exist in the lattice. */ - public ImmutableList<Column> resolveArgs(Object args) { + public ImmutableList<Column> resolveArgs(@Nullable Object args) { if (args == null) { return ImmutableList.of(); } else if (args instanceof String) { @@ -779,7 +976,7 @@ public class Lattice { } private Column resolveQualifiedColumn(String table, String column) { - for (Column column1 : columns) { + for (BaseColumn column1 : baseColumns) { if (column1.table.equals(table) && column1.column.equals(column)) { return column1; @@ -789,10 +986,11 @@ public class Lattice { + column + "]"); } - public Measure resolveMeasure(String aggName, Object args) { + public Measure resolveMeasure(String aggName, boolean distinct, + @Nullable Object args) { final SqlAggFunction agg = resolveAgg(aggName); final ImmutableList<Column> list = resolveArgs(args); - return new Measure(agg, list); + return new Measure(agg, distinct, aggName, list); } private SqlAggFunction resolveAgg(String aggName) { @@ -806,13 +1004,87 @@ public class Lattice { } } - public void addMeasure(Measure measure) { - defaultMeasureListBuilder.add(measure); + /** Adds a measure, if it does not already exist. + * Returns false if an identical measure already exists. */ + public boolean addMeasure(Measure measure) { + return defaultMeasureSet.add(measure); } public void addTile(Tile tile) { tileListBuilder.add(tile); } + + public Column column(int table, int column) { + int i = 0; + for (LatticeNode descendant : rootNode.descendants) { + if (table-- == 0) { + break; + } + i += descendant.table.t.getRowType().getFieldCount(); + } + return baseColumns.get(i + column); + } + + Column pathOffsetToColumn(Path path, int offset) { + final int i = rootNode.paths.indexOf(path); + final LatticeNode node = rootNode.descendants.get(i); + final int c = node.startCol + offset; + if (c >= node.endCol) { + throw new AssertionError(); + } + return baseColumns.get(c); + } + + /** Adds a lattice column based on a SQL expression, + * or returns a column based on the same expression seen previously. */ + public Column expression(RexNode e, String alias, + List<String> tableAliases) { + return derivedColumnsByName.computeIfAbsent(e.toString(), k -> { + final int derivedOrdinal = derivedColumnsByName.size(); + final int ordinal = baseColumns.size() + derivedOrdinal; + return new DerivedColumn(ordinal, + Util.first(alias, "e$" + derivedOrdinal), e, tableAliases); + }); + } + + /** Work space for fixing up a tree of mutable nodes. */ + private static class Fixer { + final Set<String> aliases = new HashSet<>(); + final Set<String> columnAliases = new HashSet<>(); + final Set<MutableNode> seen = new HashSet<>(); + final ImmutableList.Builder<BaseColumn> columnList = + ImmutableList.builder(); + final ImmutableListMultimap.Builder<String, Column> columnAliasList = + ImmutableListMultimap.builder(); + int c; + + void fixUp(MutableNode node) { + if (!seen.add(node)) { + throw new IllegalArgumentException("cyclic query graph"); + } + if (node.alias == null) { + node.alias = Util.last(node.table.t.getQualifiedName()); + } + node.alias = SqlValidatorUtil.uniquify(node.alias, aliases, + SqlValidatorUtil.ATTEMPT_SUGGESTER); + node.startCol = c; + for (String name : node.table.t.getRowType().getFieldNames()) { + final String alias = SqlValidatorUtil.uniquify(name, + columnAliases, SqlValidatorUtil.ATTEMPT_SUGGESTER); + final BaseColumn column = + new BaseColumn(c++, node.alias, name, alias); + columnList.add(column); + columnAliasList.put(name, column); // name before it is made unique + } + node.endCol = c; + + assert MutableNode.ORDERING.isStrictlyOrdered(node.children) + : node.children; + for (MutableNode child : node.children) { + fixUp(child); + } + } + } } /** Materialized aggregate within a lattice. */ http://git-wip-us.apache.org/repos/asf/calcite/blob/b47413a1/core/src/main/java/org/apache/calcite/materialize/LatticeChildNode.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/materialize/LatticeChildNode.java b/core/src/main/java/org/apache/calcite/materialize/LatticeChildNode.java new file mode 100644 index 0000000..0554f63 --- /dev/null +++ b/core/src/main/java/org/apache/calcite/materialize/LatticeChildNode.java @@ -0,0 +1,46 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to you under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.calcite.materialize; + +import org.apache.calcite.util.mapping.IntPair; + +import com.google.common.collect.ImmutableList; + +import java.util.List; +import java.util.Objects; + +/** Non-root node in a {@link Lattice}. */ +public class LatticeChildNode extends LatticeNode { + public final LatticeNode parent; + public final ImmutableList<IntPair> link; + + LatticeChildNode(LatticeSpace space, LatticeNode parent, + MutableNode mutableNode) { + super(space, parent, mutableNode); + this.parent = Objects.requireNonNull(parent); + this.link = ImmutableList.copyOf(mutableNode.step.keys); + } + + void use(List<LatticeNode> usedNodes) { + if (!usedNodes.contains(this)) { + parent.use(usedNodes); + usedNodes.add(this); + } + } +} + +// End LatticeChildNode.java http://git-wip-us.apache.org/repos/asf/calcite/blob/b47413a1/core/src/main/java/org/apache/calcite/materialize/LatticeNode.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/materialize/LatticeNode.java b/core/src/main/java/org/apache/calcite/materialize/LatticeNode.java new file mode 100644 index 0000000..d9afc3f --- /dev/null +++ b/core/src/main/java/org/apache/calcite/materialize/LatticeNode.java @@ -0,0 +1,116 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to you under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.calcite.materialize; + +import org.apache.calcite.plan.RelOptTable; +import org.apache.calcite.util.mapping.IntPair; + +import com.google.common.base.Preconditions; +import com.google.common.collect.ImmutableList; + +import java.util.List; +import java.util.Objects; + +/** Source relation of a lattice. + * + * <p>Relations form a tree; all relations except the root relation + * (the fact table) have precisely one parent and an equi-join + * condition on one or more pairs of columns linking to it. */ +public abstract class LatticeNode { + public final LatticeTable table; + final int startCol; + final int endCol; + public final String alias; + private final ImmutableList<LatticeChildNode> children; + public final String digest; + + /** Creates a LatticeNode. + * + * <p>The {@code parent} and {@code mutableNode} arguments are used only + * during construction. */ + LatticeNode(LatticeSpace space, LatticeNode parent, MutableNode mutableNode) { + this.table = Objects.requireNonNull(mutableNode.table); + this.startCol = mutableNode.startCol; + this.endCol = mutableNode.endCol; + this.alias = mutableNode.alias; + Preconditions.checkArgument(startCol >= 0); + Preconditions.checkArgument(endCol > startCol); + + final StringBuilder sb = new StringBuilder() + .append(space.simpleName(table)); + if (parent != null) { + sb.append(':'); + int i = 0; + for (IntPair p : mutableNode.step.keys) { + if (i++ > 0) { + sb.append(","); + } + sb.append(parent.table.field(p.source).getName()); + } + } + if (mutableNode.children.isEmpty()) { + this.children = ImmutableList.of(); + } else { + sb.append(" ("); + final ImmutableList.Builder<LatticeChildNode> b = ImmutableList.builder(); + int i = 0; + for (MutableNode mutableChild : mutableNode.children) { + if (i++ > 0) { + sb.append(' '); + } + final LatticeChildNode node = + new LatticeChildNode(space, this, mutableChild); + sb.append(node.digest); + b.add(node); + } + this.children = b.build(); + sb.append(")"); + } + this.digest = sb.toString(); + + } + + @Override public String toString() { + return digest; + } + + public RelOptTable relOptTable() { + return table.t; + } + + abstract void use(List<LatticeNode> usedNodes); + + void flattenTo(ImmutableList.Builder<LatticeNode> builder) { + builder.add(this); + for (LatticeChildNode child : children) { + child.flattenTo(builder); + } + } + + void createPathsRecurse(LatticeSpace space, List<Step> steps, + List<Path> paths) { + paths.add(space.addPath(steps)); + for (LatticeChildNode child : children) { + steps.add(space.addEdge(table, child.table, child.link)); + child.createPathsRecurse(space, steps, paths); + steps.remove(steps.size() - 1); + } + } + +} + +// End LatticeNode.java http://git-wip-us.apache.org/repos/asf/calcite/blob/b47413a1/core/src/main/java/org/apache/calcite/materialize/LatticeRootNode.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/materialize/LatticeRootNode.java b/core/src/main/java/org/apache/calcite/materialize/LatticeRootNode.java new file mode 100644 index 0000000..60f53ec --- /dev/null +++ b/core/src/main/java/org/apache/calcite/materialize/LatticeRootNode.java @@ -0,0 +1,86 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to you under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.calcite.materialize; + +import org.apache.calcite.util.Litmus; + +import com.google.common.collect.ImmutableList; + +import java.util.ArrayList; +import java.util.List; + +/** Root node in a {@link Lattice}. It has no parent. */ +public class LatticeRootNode extends LatticeNode { + /** Descendants, in prefix order. This root node is at position 0. */ + public final ImmutableList<LatticeNode> descendants; + final ImmutableList<Path> paths; + + LatticeRootNode(LatticeSpace space, MutableNode mutableNode) { + super(space, null, mutableNode); + + final ImmutableList.Builder<LatticeNode> b = ImmutableList.builder(); + flattenTo(b); + this.descendants = b.build(); + this.paths = createPaths(space); + } + + private ImmutableList<Path> createPaths(LatticeSpace space) { + final List<Step> steps = new ArrayList<>(); + final List<Path> paths = new ArrayList<>(); + createPathsRecurse(space, steps, paths); + assert steps.isEmpty(); + return ImmutableList.copyOf(paths); + } + + void use(List<LatticeNode> usedNodes) { + if (!usedNodes.contains(this)) { + usedNodes.add(this); + } + } + + /** Validates that nodes form a tree; each node except the first references + * a predecessor. */ + boolean isValid(Litmus litmus) { + for (int i = 0; i < descendants.size(); i++) { + LatticeNode node = descendants.get(i); + if (i == 0) { + if (node != this) { + return litmus.fail("node 0 should be root"); + } + } else { + if (!(node instanceof LatticeChildNode)) { + return litmus.fail("node after 0 should be child"); + } + final LatticeChildNode child = (LatticeChildNode) node; + if (!descendants.subList(0, i).contains(child.parent)) { + return litmus.fail("parent not in preceding list"); + } + } + } + return litmus.succeed(); + } + + + /** Whether this node's graph is a super-set of (or equal to) another node's + * graph. */ + public boolean contains(LatticeRootNode node) { + return paths.containsAll(node.paths); + } + +} + +// End LatticeRootNode.java http://git-wip-us.apache.org/repos/asf/calcite/blob/b47413a1/core/src/main/java/org/apache/calcite/materialize/LatticeSpace.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/materialize/LatticeSpace.java b/core/src/main/java/org/apache/calcite/materialize/LatticeSpace.java new file mode 100644 index 0000000..fa27cfb --- /dev/null +++ b/core/src/main/java/org/apache/calcite/materialize/LatticeSpace.java @@ -0,0 +1,135 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to you under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.calcite.materialize; + +import org.apache.calcite.plan.RelOptTable; +import org.apache.calcite.util.Util; +import org.apache.calcite.util.graph.AttributedDirectedGraph; +import org.apache.calcite.util.mapping.IntPair; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.Lists; + +import java.util.HashMap; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.Objects; +import java.util.Set; +import java.util.TreeSet; + +/** Space within which lattices exist. */ +class LatticeSpace { + final SqlStatisticProvider statisticProvider; + private final Map<List<String>, LatticeTable> tableMap = new HashMap<>(); + final AttributedDirectedGraph<LatticeTable, Step> g = + new AttributedDirectedGraph<>(new Step.Factory()); + 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<>(); + + LatticeSpace(SqlStatisticProvider statisticProvider) { + this.statisticProvider = Objects.requireNonNull(statisticProvider); + } + + /** Derives a unique name for a table, qualifying with schema name only if + * necessary. */ + String simpleName(LatticeTable table) { + return simpleName(table.t.getQualifiedName()); + } + + String simpleName(RelOptTable table) { + return simpleName(table.getQualifiedName()); + } + + String simpleName(List<String> table) { + final String name = simpleTableNames.get(table); + if (name != null) { + return name; + } + final String name2 = Util.last(table); + if (simpleNames.add(name2)) { + simpleTableNames.put(ImmutableList.copyOf(table), name2); + return name2; + } + final String name3 = table.toString(); + simpleTableNames.put(ImmutableList.copyOf(table), name3); + return name3; + } + + LatticeTable register(RelOptTable t) { + final LatticeTable table = tableMap.get(t.getQualifiedName()); + if (table != null) { + return table; + } + final LatticeTable table2 = new LatticeTable(t); + tableMap.put(t.getQualifiedName(), table2); + g.addVertex(table2); + return table2; + } + + Step addEdge(LatticeTable source, LatticeTable target, List<IntPair> keys) { + keys = sortUnique(keys); + final Step step = g.addEdge(source, target, keys); + if (step != null) { + return step; + } + for (Step step2 : g.getEdges(source, target)) { + if (step2.keys.equals(keys)) { + return step2; + } + } + throw new AssertionError("addEdge failed, yet no edge present"); + } + + /** Returns a list of {@link IntPair} that is sorted and unique. */ + static List<IntPair> sortUnique(List<IntPair> keys) { + if (keys.size() > 1) { + // list may not be sorted; sort it + keys = IntPair.ORDERING.immutableSortedCopy(keys); + if (!IntPair.ORDERING.isStrictlyOrdered(keys)) { + // list may contain duplicates; sort and eliminate duplicates + final Set<IntPair> set = new TreeSet<>(IntPair.ORDERING); + set.addAll(keys); + keys = ImmutableList.copyOf(set); + } + } + return keys; + } + + /** Returns a list of {@link IntPair}, transposing source and target fields, + * and ensuring the result is sorted and unique. */ + static List<IntPair> swap(List<IntPair> keys) { + return sortUnique(Lists.transform(keys, IntPair.SWAP)); + } + + Path addPath(List<Step> steps) { + final ImmutableList<Step> key = ImmutableList.copyOf(steps); + final Path path = pathMap.get(key); + if (path != null) { + return path; + } + final Path path2 = new Path(key, pathMap.size()); + pathMap.put(key, path2); + return path2; + } + +} + +// End LatticeSpace.java http://git-wip-us.apache.org/repos/asf/calcite/blob/b47413a1/core/src/main/java/org/apache/calcite/materialize/LatticeSuggester.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 new file mode 100644 index 0000000..c9c3658 --- /dev/null +++ b/core/src/main/java/org/apache/calcite/materialize/LatticeSuggester.java @@ -0,0 +1,755 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to you under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.calcite.materialize; + +import org.apache.calcite.jdbc.CalciteSchema; +import org.apache.calcite.plan.RelOptCostImpl; +import org.apache.calcite.plan.RelOptUtil; +import org.apache.calcite.plan.hep.HepPlanner; +import org.apache.calcite.plan.hep.HepProgram; +import org.apache.calcite.plan.hep.HepProgramBuilder; +import org.apache.calcite.rel.RelNode; +import org.apache.calcite.rel.core.Aggregate; +import org.apache.calcite.rel.core.AggregateCall; +import org.apache.calcite.rel.core.Filter; +import org.apache.calcite.rel.core.Join; +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.rex.RexInputRef; +import org.apache.calcite.rex.RexNode; +import org.apache.calcite.sql.SqlAggFunction; +import org.apache.calcite.tools.FrameworkConfig; +import org.apache.calcite.util.CompositeList; +import org.apache.calcite.util.ImmutableBitSet; +import org.apache.calcite.util.ImmutableNullableList; +import org.apache.calcite.util.Pair; +import org.apache.calcite.util.Util; +import org.apache.calcite.util.graph.AttributedDirectedGraph; +import org.apache.calcite.util.graph.CycleDetector; +import org.apache.calcite.util.graph.DefaultEdge; +import org.apache.calcite.util.graph.TopologicalOrderIterator; +import org.apache.calcite.util.mapping.IntPair; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.ImmutableSet; +import com.google.common.collect.LinkedListMultimap; +import com.google.common.collect.Lists; +import com.google.common.collect.Multimap; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.HashMap; +import java.util.IdentityHashMap; +import java.util.LinkedHashMap; +import java.util.LinkedHashSet; +import java.util.List; +import java.util.Locale; +import java.util.Map; +import java.util.Objects; +import java.util.Set; +import javax.annotation.Nonnull; +import javax.annotation.Nullable; + +/** + * Algorithm that suggests a set of lattices. + */ +public class LatticeSuggester { + final LatticeSpace space; + + private static final HepProgram PROGRAM = + new HepProgramBuilder() + .addRuleInstance(FilterJoinRule.FILTER_ON_JOIN) + .addRuleInstance(FilterJoinRule.JOIN) + .build(); + + /** Lattices, indexed by digest. Uses LinkedHashMap for determinacy. */ + final Map<String, Lattice> latticeMap = new LinkedHashMap<>(); + + /** Lattices that have been made obsolete. Key is the obsolete lattice, value + * is the lattice that superseded it. */ + private final Map<Lattice, Lattice> obsoleteLatticeMap = new HashMap<>(); + + /** Whether to try to extend an existing lattice when adding a lattice. */ + private final boolean evolve; + + /** Creates a LatticeSuggester. */ + public LatticeSuggester(FrameworkConfig config) { + this.evolve = config.isEvolveLattice(); + space = new LatticeSpace(config.getStatisticProvider()); + } + + /** Returns the minimal set of lattices necessary to cover all of the queries + * seen. Any lattices that are subsumed by other lattices are not included. */ + public Set<Lattice> getLatticeSet() { + final Set<Lattice> set = new LinkedHashSet<>(latticeMap.values()); + set.removeAll(obsoleteLatticeMap.keySet()); + return ImmutableSet.copyOf(set); + } + + /** Adds a query. + * + * <p>It may fit within an existing lattice (or lattices). Or it may need a + * new lattice, or an extension to an existing lattice. + * + * @param r Relational expression for a query + * + * @return A list of join graphs: usually 1; more if the query contains a + * cartesian product; zero if the query graph is cyclic + */ + public List<Lattice> addQuery(RelNode r) { + // Push filters into joins and towards leaves + final HepPlanner planner = + new HepPlanner(PROGRAM, null, true, null, RelOptCostImpl.FACTORY); + planner.setRoot(r); + final RelNode r2 = planner.findBestExp(); + + final Query q = new Query(space); + final Frame frame = frame(q, r2); + if (frame == null) { + return ImmutableList.of(); + } + final AttributedDirectedGraph<TableRef, StepRef> g = + AttributedDirectedGraph.create(new StepRef.Factory()); + final Multimap<Pair<TableRef, TableRef>, IntPair> map = + LinkedListMultimap.create(); + for (TableRef tableRef : frame.tableRefs) { + 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)); + } + for (Map.Entry<Pair<TableRef, TableRef>, Collection<IntPair>> e + : map.asMap().entrySet()) { + final TableRef source = e.getKey().left; + final TableRef target = e.getKey().right; + final StepRef stepRef = + q.stepRef(source, target, ImmutableList.copyOf(e.getValue())); + g.addVertex(stepRef.source()); + g.addVertex(stepRef.target()); + g.addEdge(stepRef.source(), stepRef.target(), stepRef.step, + stepRef.ordinalInQuery); + } + + // If the join graph is cyclic, we can't use it. + final Set<TableRef> cycles = new CycleDetector<>(g).findCycles(); + if (!cycles.isEmpty()) { + return ImmutableList.of(); + } + + // Translate the query graph to mutable nodes + final Map<TableRef, MutableNode> nodes = new IdentityHashMap<>(); + final Map<List, MutableNode> nodesByParent = new HashMap<>(); + final List<MutableNode> rootNodes = new ArrayList<>(); + for (TableRef tableRef : TopologicalOrderIterator.of(g)) { + final List<StepRef> edges = g.getInwardEdges(tableRef); + final MutableNode node; + switch (edges.size()) { + case 0: + node = new MutableNode(tableRef.table); + rootNodes.add(node); + break; + case 1: + final StepRef edge = edges.get(0); + final MutableNode parent = nodes.get(edge.source()); + final List key = + ImmutableList.of(parent, tableRef.table, edge.step.keys); + final MutableNode existingNode = nodesByParent.get(key); + if (existingNode == null) { + node = new MutableNode(tableRef.table, parent, edge.step); + nodesByParent.put(key, node); + } else { + node = existingNode; + } + break; + default: + for (StepRef edge2 : edges) { + final MutableNode parent2 = nodes.get(edge2.source()); + final MutableNode node2 = + new MutableNode(tableRef.table, parent2, edge2.step); + parent2.children.add(node2); + } + node = null; + break; + } + nodes.put(tableRef, node); + } + + // Transcribe the hierarchy of mutable nodes to immutable nodes + final List<Lattice> lattices = new ArrayList<>(); + for (MutableNode rootNode : rootNodes) { + if (rootNode.isCyclic()) { + continue; + } + final CalciteSchema rootSchema = CalciteSchema.createRootSchema(false); + final Lattice.Builder latticeBuilder = + new Lattice.Builder(space, rootSchema, rootNode); + + final List<MutableNode> flatNodes = new ArrayList<>(); + rootNode.flatten(flatNodes); + + for (MutableMeasure measure : frame.measures) { + for (ColRef arg : measure.arguments) { + if (arg == null) { + // Cannot handle expressions, e.g. "sum(x + 1)" yet + return ImmutableList.of(); + } + } + latticeBuilder.addMeasure( + new Lattice.Measure(measure.aggregate, measure.distinct, + measure.name, + Lists.transform(measure.arguments, colRef -> { + if (colRef instanceof BaseColRef) { + final BaseColRef baseColRef = (BaseColRef) colRef; + final MutableNode node = nodes.get(baseColRef.t); + final int table = flatNodes.indexOf(node); + return latticeBuilder.column(table, baseColRef.c); + } else if (colRef instanceof DerivedColRef) { + final DerivedColRef derivedColRef = + (DerivedColRef) colRef; + final String alias = deriveAlias(measure, derivedColRef); + return latticeBuilder.expression(derivedColRef.e, alias, + derivedColRef.tableAliases()); + } else { + throw new AssertionError("expression in measure"); + } + }))); + } + + for (int i = 0; i < frame.columnCount; i++) { + final ColRef c = frame.column(i); + if (c instanceof DerivedColRef) { + final DerivedColRef derivedColRef = (DerivedColRef) c; + final Lattice.Column expression = + latticeBuilder.expression(derivedColRef.e, + derivedColRef.alias, derivedColRef.tableAliases()); + } + } + + final Lattice lattice0 = latticeBuilder.build(); + final Lattice lattice1 = findMatch(lattice0, rootNode); + lattices.add(lattice1); + } + return ImmutableList.copyOf(lattices); + } + + /** Derives the alias of an expression that is the argument to a measure. + * + * <p>For example, if the measure is called "sum_profit" and the aggregate + * function is "sum", returns "profit". + */ + private static String deriveAlias(MutableMeasure measure, + DerivedColRef derivedColRef) { + if (!derivedColRef.alias.contains("$")) { + // User specified an alias. Use that. + return derivedColRef.alias; + } + String alias = measure.name; + if (alias.contains("$")) { + // User did not specify an alias for the aggregate function, and it got a + // system-generated name like 'EXPR$2'. Don't try to derive anything from + // it. + return derivedColRef.alias; + } + final String aggUpper = + measure.aggregate.getName().toUpperCase(Locale.ROOT); + final String aliasUpper = alias.toUpperCase(Locale.ROOT); + if (aliasUpper.startsWith(aggUpper + "_")) { + // Convert "sum_profit" to "profit" + return alias.substring((aggUpper + "_").length()); + } else if (aliasUpper.startsWith(aggUpper)) { + // Convert "sumprofit" to "profit" + return alias.substring(aggUpper.length()); + } else if (aliasUpper.endsWith("_" + aggUpper)) { + // Convert "profit_sum" to "profit" + return alias.substring(0, alias.length() - ("_" + aggUpper).length()); + } else if (aliasUpper.endsWith(aggUpper)) { + // Convert "profitsum" to "profit" + return alias.substring(0, alias.length() - aggUpper.length()); + } else { + return alias; + } + } + + /** Returns the best match for a lattice. If no match, registers the lattice + * and returns it. Never returns null. */ + private Lattice findMatch(final Lattice lattice, MutableNode mutableNode) { + final Lattice lattice1 = latticeMap.get(lattice.toString()); + if (lattice1 != null) { + // Exact match for an existing lattice + return lattice1; + } + + if (evolve) { + // No exact match. Scan existing lattices for a sub-set. + int bestMatchQuality = 0; + Lattice bestMatch = null; + for (Lattice lattice2 : latticeMap.values()) { + int q = matchQuality(lattice2, lattice); + if (q > bestMatchQuality) { + bestMatch = lattice2; + bestMatchQuality = q; + } else if (q == bestMatchQuality + && bestMatch != null + && !lattice2.rootNode.paths.equals(bestMatch.rootNode.paths) + && lattice2.rootNode.paths.containsAll(bestMatch.rootNode.paths)) { + bestMatch = lattice2; + } + } + + if (bestMatch != null) { + // Fix up the best batch + for (Path path + : minus(bestMatch.rootNode.paths, lattice.rootNode.paths)) { + // TODO: assign alias based on node in bestMatch + mutableNode.addPath(path, null); + } + final CalciteSchema rootSchema = CalciteSchema.createRootSchema(false); + final Lattice.Builder builder = + new Lattice.Builder(space, rootSchema, mutableNode); + for (Lattice.Measure measure : bestMatch.defaultMeasures) { + builder.addMeasure(measure.copy(mapper(bestMatch, builder))); + } + for (Lattice.Measure measure : lattice.defaultMeasures) { + builder.addMeasure(measure.copy(mapper(lattice, builder))); + } + final Lattice lattice2 = builder.build(); + latticeMap.remove(bestMatch.toString()); + obsoleteLatticeMap.put(bestMatch, lattice2); + latticeMap.put(lattice2.toString(), lattice2); + return lattice2; + } + } + + // No suitable existing lattice. Register this one. + latticeMap.put(lattice.toString(), lattice); + return lattice; + } + + private java.util.function.Function<Lattice.Column, Lattice.Column> mapper( + final Lattice lattice, final Lattice.Builder builder) { + return (Lattice.Column c) -> { + if (c instanceof Lattice.BaseColumn) { + Lattice.BaseColumn baseColumn = (Lattice.BaseColumn) c; + Pair<Path, Integer> p = lattice.columnToPathOffset(baseColumn); + return builder.pathOffsetToColumn(p.left, p.right); + } else { + final Lattice.DerivedColumn derivedColumn = (Lattice.DerivedColumn) c; + return builder.expression(derivedColumn.e, derivedColumn.alias, + derivedColumn.tables); + } + }; + } + + private int matchQuality(Lattice lattice, Lattice target) { + if (!lattice.rootNode.table.equals(target.rootNode.table)) { + return 0; + } + if (lattice.rootNode.paths.equals(target.rootNode.paths)) { + return 3; + } + if (lattice.rootNode.paths.containsAll(target.rootNode.paths)) { + return 2; + } + return 1; + } + + private static <E> Set<E> minus(Collection<E> c, Collection<E> c2) { + final LinkedHashSet<E> c3 = new LinkedHashSet<>(c); + c3.removeAll(c2); + return c3; + } + + private Frame frame(final Query q, RelNode r) { + if (r instanceof Sort) { + final Sort sort = (Sort) r; + return frame(q, sort.getInput()); + } else if (r instanceof Filter) { + final Filter filter = (Filter) r; + return frame(q, filter.getInput()); + } else if (r instanceof Aggregate) { + final Aggregate aggregate = (Aggregate) r; + final Frame h = frame(q, aggregate.getInput()); + if (h == null) { + return null; + } + final List<MutableMeasure> measures = new ArrayList<>(); + for (AggregateCall call : aggregate.getAggCallList()) { + measures.add( + new MutableMeasure(call.getAggregation(), call.isDistinct(), + Util.transform(call.getArgList(), h::column), call.name)); + } + final int fieldCount = r.getRowType().getFieldCount(); + return new Frame(fieldCount, h.hops, measures, ImmutableList.of(h)) { + ColRef column(int offset) { + if (offset < aggregate.getGroupSet().cardinality()) { + return h.column(aggregate.getGroupSet().nth(offset)); + } + return null; // an aggregate function; no direct mapping + } + }; + } else if (r instanceof Project) { + final Project project = (Project) r; + final Frame h = frame(q, project.getInput()); + if (h == null) { + return null; + } + final int fieldCount = r.getRowType().getFieldCount(); + return new Frame(fieldCount, h.hops, h.measures, ImmutableList.of(h)) { + final List<ColRef> columns; + + { + final ImmutableNullableList.Builder<ColRef> columnBuilder = + ImmutableNullableList.builder(); + for (Pair<RexNode, String> p : project.getNamedProjects()) { + columnBuilder.add(toColRef(p.left, p.right)); + } + columns = columnBuilder.build(); + } + + ColRef column(int offset) { + return columns.get(offset); + } + + /** Converts an expression to a base or derived column reference. + * The alias is optional, but if the derived column reference becomes + * a dimension or measure, the alias will be used to choose a name. */ + private ColRef toColRef(RexNode e, String alias) { + if (e instanceof RexInputRef) { + return h.column(((RexInputRef) e).getIndex()); + } + + final ImmutableBitSet bits = RelOptUtil.InputFinder.bits(e); + final ImmutableList.Builder<TableRef> tableRefs = + ImmutableList.builder(); + int c = 0; // offset within lattice of first column in a table + for (TableRef tableRef : h.tableRefs) { + final int prev = c; + c += tableRef.table.t.getRowType().getFieldCount(); + if (bits.intersects(ImmutableBitSet.range(prev, c))) { + tableRefs.add(tableRef); + } + } + return new DerivedColRef(tableRefs.build(), e, alias); + } + }; + } else if (r instanceof Join) { + final Join join = (Join) r; + final int leftCount = join.getLeft().getRowType().getFieldCount(); + final Frame left = frame(q, join.getLeft()); + final Frame right = frame(q, join.getRight()); + if (left == null || right == null) { + return null; + } + final ImmutableList.Builder<Hop> builder = ImmutableList.builder(); + builder.addAll(left.hops); + 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)); + } + builder.addAll(right.hops); + final int fieldCount = r.getRowType().getFieldCount(); + return new Frame(fieldCount, builder.build(), + CompositeList.of(left.measures, right.measures), + ImmutableList.of(left, right)) { + ColRef column(int offset) { + if (offset < leftCount) { + return left.column(offset); + } else { + return right.column(offset - leftCount); + } + } + }; + } else if (r instanceof TableScan) { + final TableScan scan = (TableScan) r; + final TableRef tableRef = q.tableRef(scan); + final int fieldCount = r.getRowType().getFieldCount(); + return new Frame(fieldCount, ImmutableList.of(), + ImmutableList.of(), ImmutableSet.of(tableRef)) { + ColRef column(int offset) { + if (offset >= scan.getTable().getRowType().getFieldCount()) { + throw new IndexOutOfBoundsException("field " + offset + + " out of range in " + scan.getTable().getRowType()); + } + return new BaseColRef(tableRef, offset); + } + }; + } else { + return null; + } + } + + /** Holds state for a particular query graph. In particular table and step + * references count from zero each query. */ + private static class Query { + final LatticeSpace space; + final Map<Integer, TableRef> tableRefs = new HashMap<>(); + int stepRefCount = 0; + + Query(LatticeSpace space) { + this.space = space; + } + + TableRef tableRef(TableScan scan) { + final TableRef r = tableRefs.get(scan.getId()); + if (r != null) { + return r; + } + final LatticeTable t = space.register(scan.getTable()); + final TableRef r2 = new TableRef(t, tableRefs.size()); + tableRefs.put(scan.getId(), r2); + return r2; + } + + StepRef stepRef(TableRef source, TableRef target, List<IntPair> keys) { + keys = LatticeSpace.sortUnique(keys); + final Step h = new Step(source.table, target.table, keys); + if (h.isBackwards(space.statisticProvider)) { + final List<IntPair> keys1 = LatticeSpace.swap(h.keys); + final Step h2 = space.addEdge(h.target(), h.source(), keys1); + return new StepRef(target, source, h2, stepRefCount++); + } else { + final Step h2 = space.addEdge(h.source(), h.target(), h.keys); + return new StepRef(source, target, h2, stepRefCount++); + } + } + } + + /** Information about the parent of fields from a relational expression. */ + abstract static class Frame { + final List<Hop> hops; + final List<MutableMeasure> measures; + final Set<TableRef> tableRefs; + final int columnCount; + + Frame(int columnCount, List<Hop> hops, List<MutableMeasure> measures, + Collection<TableRef> tableRefs) { + this.hops = ImmutableList.copyOf(hops); + this.measures = ImmutableList.copyOf(measures); + this.tableRefs = ImmutableSet.copyOf(tableRefs); + this.columnCount = columnCount; + } + + Frame(int columnCount, List<Hop> hops, List<MutableMeasure> measures, + List<Frame> inputs) { + this(columnCount, hops, measures, collectTableRefs(inputs, hops)); + } + + abstract ColRef column(int offset); + + @Override public String toString() { + return "Frame(" + hops + ")"; + } + + 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); + } + for (Frame frame : inputs) { + set.addAll(frame.tableRefs); + } + return set; + } + } + + /** Use of a table within a query. A table can be used more than once. */ + private static class TableRef { + final LatticeTable table; + private final int ordinalInQuery; + + private TableRef(LatticeTable table, int ordinalInQuery) { + this.table = Objects.requireNonNull(table); + this.ordinalInQuery = ordinalInQuery; + } + + public int hashCode() { + return ordinalInQuery; + } + + public boolean equals(Object obj) { + return this == obj + || obj instanceof TableRef + && ordinalInQuery == ((TableRef) obj).ordinalInQuery; + } + + public String toString() { + return table + ":" + ordinalInQuery; + } + } + + /** Use of a step within a query. A step can be used more than once. */ + private static class StepRef extends DefaultEdge { + final Step step; + private final int ordinalInQuery; + + StepRef(TableRef source, TableRef target, Step step, int ordinalInQuery) { + super(source, target); + this.step = Objects.requireNonNull(step); + this.ordinalInQuery = ordinalInQuery; + } + + @Override public int hashCode() { + return ordinalInQuery; + } + + @Override public boolean equals(Object obj) { + return this == obj + || obj instanceof StepRef + && ((StepRef) obj).ordinalInQuery == ordinalInQuery; + } + + @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(); + } + + TableRef source() { + return (TableRef) source; + } + + TableRef target() { + return (TableRef) target; + } + + /** Creates {@link StepRef} instances. */ + private static class Factory + implements AttributedDirectedGraph.AttributedEdgeFactory< + TableRef, StepRef> { + public StepRef createEdge(TableRef source, TableRef target) { + throw new UnsupportedOperationException(); + } + + public StepRef createEdge(TableRef source, TableRef target, + Object... attributes) { + final Step step = (Step) attributes[0]; + final Integer ordinalInQuery = (Integer) attributes[1]; + return new StepRef(source, target, step, ordinalInQuery); + } + } + } + + /** A hop is a join condition. One or more hops between the same source and + * target combine to form a {@link Step}. + * + * <p>The tables are registered but the step is not. After we have gathered + * several join conditions we may discover that the keys are composite: e.g. + * + * <blockquote> + * <pre> + * x.a = y.a + * AND x.b = z.b + * AND x.c = y.c + * </pre> + * </blockquote> + * + * <p>has 3 semi-hops: + * + * <ul> + * <li>x.a = y.a + * <li>x.b = z.b + * <li>x.c = y.c + * </ul> + * + * <p>which turn into 2 steps, the first of which is composite: + * + * <ul> + * <li>x.[a, c] = y.[a, c] + * <li>x.b = z.b + * </ul> + */ + private static class Hop { + final BaseColRef source; + final BaseColRef target; + + private Hop(BaseColRef source, BaseColRef target) { + this.source = source; + this.target = target; + } + } + + /** Column reference. */ + private abstract static class ColRef { + } + + /** Reference to a base column. */ + private static class BaseColRef extends ColRef { + final TableRef t; + final int c; + + private BaseColRef(TableRef t, int c) { + this.t = t; + this.c = c; + } + } + + /** Reference to a derived column (that is, an expression). */ + private static class DerivedColRef extends ColRef { + @Nonnull final List<TableRef> tableRefs; + @Nonnull final RexNode e; + final String alias; + + private DerivedColRef(Iterable<TableRef> tableRefs, RexNode e, + String alias) { + this.tableRefs = ImmutableList.copyOf(tableRefs); + this.e = e; + this.alias = alias; + } + + List<String> tableAliases() { + return Util.transform(tableRefs, tableRef -> tableRef.table.alias); + } + } + + /** An aggregate call. Becomes a measure in the final lattice. */ + private static class MutableMeasure { + final SqlAggFunction aggregate; + final boolean distinct; + final List<ColRef> arguments; + final String name; + + private MutableMeasure(SqlAggFunction aggregate, boolean distinct, + List<ColRef> arguments, @Nullable String name) { + this.aggregate = aggregate; + this.arguments = arguments; + this.distinct = distinct; + this.name = name; + } + } + +} + +// End LatticeSuggester.java http://git-wip-us.apache.org/repos/asf/calcite/blob/b47413a1/core/src/main/java/org/apache/calcite/materialize/LatticeTable.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/materialize/LatticeTable.java b/core/src/main/java/org/apache/calcite/materialize/LatticeTable.java new file mode 100644 index 0000000..c7ae68a --- /dev/null +++ b/core/src/main/java/org/apache/calcite/materialize/LatticeTable.java @@ -0,0 +1,56 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to you under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.calcite.materialize; + +import org.apache.calcite.plan.RelOptTable; +import org.apache.calcite.rel.type.RelDataTypeField; +import org.apache.calcite.util.Util; + +import java.util.Objects; +import javax.annotation.Nonnull; + +/** Table registered in the graph. */ +public class LatticeTable { + @Nonnull public final RelOptTable t; + @Nonnull public final String alias; + + LatticeTable(RelOptTable table) { + t = Objects.requireNonNull(table); + alias = Objects.requireNonNull(Util.last(table.getQualifiedName())); + } + + @Override public int hashCode() { + return t.getQualifiedName().hashCode(); + } + + @Override public boolean equals(Object obj) { + return this == obj + || obj instanceof LatticeTable + && t.getQualifiedName().equals( + ((LatticeTable) obj).t.getQualifiedName()); + } + + @Override public String toString() { + return t.getQualifiedName().toString(); + } + + RelDataTypeField field(int i) { + return t.getRowType().getFieldList().get(i); + } +} + +// End LatticeTable.java http://git-wip-us.apache.org/repos/asf/calcite/blob/b47413a1/core/src/main/java/org/apache/calcite/materialize/MapSqlStatisticProvider.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/materialize/MapSqlStatisticProvider.java b/core/src/main/java/org/apache/calcite/materialize/MapSqlStatisticProvider.java new file mode 100644 index 0000000..92dac0d --- /dev/null +++ b/core/src/main/java/org/apache/calcite/materialize/MapSqlStatisticProvider.java @@ -0,0 +1,88 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to you under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.calcite.materialize; + +import com.google.common.collect.ImmutableMap; + +import java.util.List; +import java.util.Map; + +/** + * Implementation of {@link SqlStatisticProvider} that looks up values in a + * table. + * + * <p>Only for testing. + */ +public enum MapSqlStatisticProvider implements SqlStatisticProvider { + INSTANCE; + + private static final Map<String, Double> CARDINALITY_MAP = + ImmutableMap.<String, Double>builder() + .put("[foodmart, agg_c_14_sales_fact_1997]", 86_805d) + .put("[foodmart, customer]", 10_281d) + .put("[foodmart, employee]", 1_155d) + .put("[foodmart, employee_closure]", 7_179d) + .put("[foodmart, department]", 10_281d) + .put("[foodmart, inventory_fact_1997]", 4_070d) + .put("[foodmart, position]", 18d) + .put("[foodmart, product]", 1560d) + .put("[foodmart, product_class]", 110d) + .put("[foodmart, promotion]", 1_864d) + // region really has 110 rows; made it smaller than store to trick FK + .put("[foodmart, region]", 24d) + .put("[foodmart, salary]", 21_252d) + .put("[foodmart, sales_fact_1997]", 86_837d) + .put("[foodmart, store]", 25d) + .put("[foodmart, store_ragged]", 25d) + .put("[foodmart, time_by_day]", 730d) + .put("[foodmart, warehouse]", 24d) + .put("[foodmart, warehouse_class]", 6d) + .put("[scott, EMP]", 10d) + .put("[scott, DEPT]", 4d) + .put("[tpcds, CALL_CENTER]", 8d) + .put("[tpcds, CATALOG_PAGE]", 11_718d) + .put("[tpcds, CATALOG_RETURNS]", 144_067d) + .put("[tpcds, CATALOG_SALES]", 1_441_548d) + .put("[tpcds, CUSTOMER]", 100_000d) + .put("[tpcds, CUSTOMER_ADDRESS]", 50_000d) + .put("[tpcds, CUSTOMER_DEMOGRAPHICS]", 1_920_800d) + .put("[tpcds, DATE_DIM]", 73049d) + .put("[tpcds, DBGEN_VERSION]", 1d) + .put("[tpcds, HOUSEHOLD_DEMOGRAPHICS]", 7200d) + .put("[tpcds, INCOME_BAND]", 20d) + .put("[tpcds, INVENTORY]", 11_745_000d) + .put("[tpcds, ITEM]", 18_000d) + .put("[tpcds, PROMOTION]", 300d) + .put("[tpcds, REASON]", 35d) + .put("[tpcds, SHIP_MODE]", 20d) + .put("[tpcds, STORE]", 12d) + .put("[tpcds, STORE_RETURNS]", 287_514d) + .put("[tpcds, STORE_SALES]", 2_880_404d) + .put("[tpcds, TIME_DIM]", 86_400d) + .put("[tpcds, WAREHOUSE]", 5d) + .put("[tpcds, WEB_PAGE]", 60d) + .put("[tpcds, WEB_RETURNS]", 71_763d) + .put("[tpcds, WEB_SALES]", 719_384d) + .put("[tpcds, WEB_SITE]", 1d) + .build(); + + public double tableCardinality(List<String> qualifiedTableName) { + return CARDINALITY_MAP.get(qualifiedTableName.toString()); + } +} + +// End MapSqlStatisticProvider.java
