You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@calcite.apache.org by jh...@apache.org on 2014/09/16 08:22:10 UTC
git commit: [OPTIQ-410] Allow lattice tiles to satisfy a query by
rolling up
Repository: incubator-optiq
Updated Branches:
refs/heads/master 235e66cca -> 7938e10d5
[OPTIQ-410] Allow lattice tiles to satisfy a query by rolling up
Project: http://git-wip-us.apache.org/repos/asf/incubator-optiq/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-optiq/commit/7938e10d
Tree: http://git-wip-us.apache.org/repos/asf/incubator-optiq/tree/7938e10d
Diff: http://git-wip-us.apache.org/repos/asf/incubator-optiq/diff/7938e10d
Branch: refs/heads/master
Commit: 7938e10d53ea9f7f0ebd1217a7ded9523e1613f9
Parents: 235e66c
Author: Julian Hyde <jh...@apache.org>
Authored: Mon Sep 15 17:59:52 2014 -0700
Committer: Julian Hyde <jh...@apache.org>
Committed: Mon Sep 15 20:38:27 2014 -0700
----------------------------------------------------------------------
.../optiq/impl/MaterializedViewTable.java | 2 +-
.../hydromatic/optiq/materialize/Lattice.java | 78 +++++++---
.../optiq/materialize/MaterializationActor.java | 4 +-
.../materialize/MaterializationService.java | 72 +++++++--
.../java/org/eigenbase/rel/AggregateCall.java | 7 +
.../rel/rules/AggregateStarTableRule.java | 149 ++++++++++++++++++-
.../org/eigenbase/relopt/RelOptLattice.java | 13 +-
core/src/main/java/org/eigenbase/util/Util.java | 57 +++++++
.../util/mapping/AbstractSourceMapping.java | 99 ++++++++++++
.../util/mapping/AbstractTargetMapping.java | 99 ++++++++++++
.../org/eigenbase/util/mapping/Mappings.java | 31 ++++
.../net/hydromatic/optiq/test/LatticeTest.java | 79 +++++++++-
.../test/java/org/eigenbase/util/UtilTest.java | 18 +++
13 files changed, 662 insertions(+), 46 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/7938e10d/core/src/main/java/net/hydromatic/optiq/impl/MaterializedViewTable.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/net/hydromatic/optiq/impl/MaterializedViewTable.java b/core/src/main/java/net/hydromatic/optiq/impl/MaterializedViewTable.java
index a01c9d1..8ba6a13 100644
--- a/core/src/main/java/net/hydromatic/optiq/impl/MaterializedViewTable.java
+++ b/core/src/main/java/net/hydromatic/optiq/impl/MaterializedViewTable.java
@@ -106,7 +106,7 @@ public class MaterializedViewTable extends ViewTable {
super(schema, viewSql, viewSchemaPath);
this.key = Preconditions.checkNotNull(
MaterializationService.instance().defineMaterialization(
- schema, viewSql, schemaPath, tableName, true));
+ schema, null, viewSql, schemaPath, tableName, true));
}
@Override
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/7938e10d/core/src/main/java/net/hydromatic/optiq/materialize/Lattice.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/net/hydromatic/optiq/materialize/Lattice.java b/core/src/main/java/net/hydromatic/optiq/materialize/Lattice.java
index 66b459e..167afbf 100644
--- a/core/src/main/java/net/hydromatic/optiq/materialize/Lattice.java
+++ b/core/src/main/java/net/hydromatic/optiq/materialize/Lattice.java
@@ -60,6 +60,13 @@ public class Lattice {
}
};
+ private static final Function<Column, Integer> GET_ORDINAL =
+ new Function<Column, Integer>() {
+ public Integer apply(Column input) {
+ return input.ordinal;
+ }
+ };
+
public final ImmutableList<Node> nodes;
public final ImmutableList<Column> columns;
public final boolean auto;
@@ -206,21 +213,50 @@ public class Lattice {
}
}
final SqlDialect dialect = SqlDialect.DatabaseProduct.OPTIQ.getDialect();
- final StringBuilder buf = new StringBuilder();
- buf.append("SELECT DISTINCT ");
+ final StringBuilder buf = new StringBuilder("SELECT ");
+ final StringBuilder groupBuf = new StringBuilder("\nGROUP BY ");
int k = 0;
+ final Set<String> columnNames = Sets.newHashSet();
for (int i : BitSets.toIter(groupSet)) {
if (k++ > 0) {
buf.append(", ");
+ 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)) {
buf.append(" AS ");
dialect.quoteIdentifier(buf, fieldName);
}
}
+ int m = 0;
+ for (Measure measure : aggCallList) {
+ if (k++ > 0) {
+ buf.append(", ");
+ }
+ buf.append(measure.agg.getName())
+ .append("(");
+ if (measure.args.isEmpty()) {
+ buf.append("*");
+ } else {
+ int z = 0;
+ for (Column arg : measure.args) {
+ if (z++ > 0) {
+ buf.append(", ");
+ }
+ dialect.quoteIdentifier(buf, arg.identifiers());
+ }
+ }
+ buf.append(") AS ");
+ String measureName;
+ while (!columnNames.add(measureName = "m" + m)) {
+ ++m;
+ }
+ dialect.quoteIdentifier(buf, measureName);
+ }
buf.append("\nFROM ");
for (Node node : usedNodes) {
if (node.parent != null) {
@@ -247,6 +283,7 @@ public class Lattice {
if (OptiqPrepareImpl.DEBUG) {
System.out.println("Lattice SQL:\n" + buf);
}
+ buf.append(groupBuf);
return buf.toString();
}
@@ -356,6 +393,20 @@ public class Lattice {
&& this.args.equals(((Measure) obj).args);
}
+ /** Returns the set of distinct argument ordinals. */
+ public BitSet argBitSet() {
+ final BitSet bitSet = new BitSet();
+ for (Column arg : args) {
+ bitSet.set(arg.ordinal);
+ }
+ return bitSet;
+ }
+
+ /** Returns a list of argument ordinals. */
+ public List<Integer> argOrdinals() {
+ return Lists.transform(args, GET_ORDINAL);
+ }
+
private static int compare(List<Column> list0, List<Column> list1) {
final int size = Math.min(list0.size(), list1.size());
for (int i = 0; i < size; i++) {
@@ -613,22 +664,17 @@ public class Lattice {
public static class Tile {
public final ImmutableList<Measure> measures;
public final ImmutableList<Column> dimensions;
+ public final BitSet bitSet = new BitSet();
public Tile(ImmutableList<Measure> measures,
ImmutableList<Column> dimensions) {
this.measures = measures;
this.dimensions = dimensions;
- assert isSorted(dimensions);
- assert isSorted(measures);
- }
-
- private static <T extends Comparable<T>> boolean isSorted(List<T> list) {
- for (int i = 1; i < list.size(); i++) {
- if (list.get(i - 1).compareTo(list.get(i)) >= 0) {
- return false;
- }
+ assert Util.isStrictlySorted(dimensions);
+ assert Util.isStrictlySorted(measures);
+ for (Column dimension : dimensions) {
+ bitSet.set(dimension.ordinal);
}
- return true;
}
public static TileBuilder builder() {
@@ -636,10 +682,6 @@ public class Lattice {
}
public BitSet bitSet() {
- final BitSet bitSet = new BitSet();
- for (Column dimension : dimensions) {
- bitSet.set(dimension.ordinal);
- }
return bitSet;
}
}
@@ -652,7 +694,9 @@ public class Lattice {
ImmutableList.builder();
public Tile build() {
- return new Tile(measureBuilder.build(), dimensionListBuilder.build());
+ return new Tile(
+ ImmutableList.copyOf(Util.sort(measureBuilder.build())),
+ ImmutableList.copyOf(Util.sort(dimensionListBuilder.build())));
}
public void addMeasure(Measure measure) {
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/7938e10d/core/src/main/java/net/hydromatic/optiq/materialize/MaterializationActor.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/net/hydromatic/optiq/materialize/MaterializationActor.java b/core/src/main/java/net/hydromatic/optiq/materialize/MaterializationActor.java
index 9ac009f..2a02a37 100644
--- a/core/src/main/java/net/hydromatic/optiq/materialize/MaterializationActor.java
+++ b/core/src/main/java/net/hydromatic/optiq/materialize/MaterializationActor.java
@@ -22,7 +22,7 @@ import net.hydromatic.optiq.jdbc.OptiqSchema;
import org.eigenbase.reltype.RelDataType;
import org.eigenbase.util.Util;
-import com.google.common.collect.Maps;
+import com.google.common.collect.*;
import java.util.*;
@@ -37,6 +37,8 @@ class MaterializationActor {
final Map<QueryKey, MaterializationKey> keyBySql = Maps.newHashMap();
+ final List<MaterializationService.TileKey> tileKeys = Lists.newArrayList();
+
/** A query materialized in a table, so that reading from the table gives the
* same results as executing the query. */
static class Materialization {
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/7938e10d/core/src/main/java/net/hydromatic/optiq/materialize/MaterializationService.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/net/hydromatic/optiq/materialize/MaterializationService.java b/core/src/main/java/net/hydromatic/optiq/materialize/MaterializationService.java
index 26fbfb0..d608810 100644
--- a/core/src/main/java/net/hydromatic/optiq/materialize/MaterializationService.java
+++ b/core/src/main/java/net/hydromatic/optiq/materialize/MaterializationService.java
@@ -24,18 +24,20 @@ import net.hydromatic.linq4j.function.Function1;
import net.hydromatic.linq4j.function.Functions;
import net.hydromatic.optiq.*;
+import net.hydromatic.optiq.Table;
import net.hydromatic.optiq.config.OptiqConnectionProperty;
import net.hydromatic.optiq.impl.clone.CloneSchema;
import net.hydromatic.optiq.impl.java.JavaTypeFactory;
import net.hydromatic.optiq.jdbc.*;
import net.hydromatic.optiq.prepare.Prepare;
import net.hydromatic.optiq.runtime.Hook;
+import net.hydromatic.optiq.util.BitSets;
import org.eigenbase.reltype.RelDataType;
import org.eigenbase.reltype.RelDataTypeImpl;
import org.eigenbase.util.Pair;
-import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.*;
import java.lang.reflect.Type;
import java.util.*;
@@ -64,8 +66,8 @@ public class MaterializationService {
/** Defines a new materialization. Returns its key. */
public MaterializationKey defineMaterialization(final OptiqSchema schema,
- String viewSql, List<String> viewSchemaPath, String tableName,
- boolean create) {
+ TileKey tileKey, String viewSql, List<String> viewSchemaPath,
+ String tableName, boolean create) {
final MaterializationActor.QueryKey queryKey =
new MaterializationActor.QueryKey(viewSql, schema, viewSchemaPath);
final MaterializationKey existingKey = actor.keyBySql.get(queryKey);
@@ -145,6 +147,9 @@ public class MaterializationService {
tableEntry, viewSql, rowType);
actor.keyMap.put(materialization.key, materialization);
actor.keyBySql.put(queryKey, materialization.key);
+ if (tileKey != null) {
+ actor.tileKeys.add(tileKey);
+ }
return key;
}
@@ -167,8 +172,9 @@ public class MaterializationService {
* during the recursive SQL that populates a materialization. Otherwise a
* materialization would try to create itself to populate itself!
*/
- public OptiqSchema.TableEntry defineTile(Lattice lattice, BitSet groupSet,
- List<Lattice.Measure> measureList, OptiqSchema schema, boolean create) {
+ public Pair<OptiqSchema.TableEntry, TileKey> defineTile(Lattice lattice,
+ BitSet groupSet, List<Lattice.Measure> measureList, OptiqSchema schema,
+ boolean create) {
// FIXME This is all upside down. We are looking for a materialization
// first. But we should define a tile first, then find out whether an
// exact materialization exists, then find out whether an acceptable
@@ -181,18 +187,48 @@ public class MaterializationService {
// materializations that we can roll up. (Maybe the SQL on the fact table
// gets optimized to use those materializations.)
String sql = lattice.sql(groupSet, measureList);
- final MaterializationKey materializationKey =
- defineMaterialization(schema, sql, schema.path(null), "m" + groupSet,
- create);
+ final TileKey tileKey =
+ new TileKey(lattice, groupSet, ImmutableList.copyOf(measureList));
+ MaterializationKey materializationKey =
+ defineMaterialization(schema, tileKey, sql, schema.path(null),
+ "m" + groupSet, create);
if (materializationKey != null) {
final OptiqSchema.TableEntry tableEntry = checkValid(materializationKey);
if (tableEntry != null) {
- return tableEntry;
+ return Pair.of(tableEntry, tileKey);
+ }
+ }
+ // No direct hit. Look for roll-ups.
+ for (TileKey tileKey2 : actor.tileKeys) {
+ if (BitSets.contains(tileKey2.dimensions, groupSet)
+ && allSatisfiable(measureList, tileKey2)) {
+ sql = lattice.sql(tileKey2.dimensions, tileKey2.measures);
+ materializationKey =
+ defineMaterialization(schema, tileKey2, sql, schema.path(null),
+ "m" + tileKey2.dimensions, create);
+ final OptiqSchema.TableEntry tableEntry =
+ checkValid(materializationKey);
+ if (tableEntry != null) {
+ return Pair.of(tableEntry, tileKey2);
+ }
}
}
return null;
}
+ private boolean allSatisfiable(List<Lattice.Measure> measureList,
+ TileKey tileKey) {
+ // A measure can be satisfied if it is contained in the measure list, or,
+ // less obviously, if it is composed of grouping columns.
+ for (Lattice.Measure measure : measureList) {
+ if (!(tileKey.measures.contains(measure)
+ || BitSets.contains(tileKey.dimensions, measure.argBitSet()))) {
+ return false;
+ }
+ }
+ return true;
+ }
+
/** Gathers a list of all materialized tables known within a given root
* schema. (Each root schema defines a disconnected namespace, with no overlap
* with the current schema. Especially in a test run, the contents of two
@@ -232,6 +268,24 @@ public class MaterializationService {
}
return INSTANCE;
}
+
+ /** Definition of a particular combination of dimensions and measures of a
+ * lattice that is the basis of a materialization.
+ *
+ * <p>Holds similar information to a {@link Lattice.Tile} but a lattice is
+ * immutable and tiles are not added after their creation. */
+ public static class TileKey {
+ public final Lattice lattice;
+ public final BitSet dimensions;
+ public final ImmutableList<Lattice.Measure> measures;
+
+ public TileKey(Lattice lattice, BitSet dimensions,
+ ImmutableList<Lattice.Measure> measures) {
+ this.lattice = lattice;
+ this.dimensions = dimensions;
+ this.measures = measures;
+ }
+ }
}
// End MaterializationService.java
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/7938e10d/core/src/main/java/org/eigenbase/rel/AggregateCall.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/rel/AggregateCall.java b/core/src/main/java/org/eigenbase/rel/AggregateCall.java
index 93a69ef..3edfa47 100644
--- a/core/src/main/java/org/eigenbase/rel/AggregateCall.java
+++ b/core/src/main/java/org/eigenbase/rel/AggregateCall.java
@@ -21,6 +21,7 @@ import java.util.*;
import org.eigenbase.reltype.*;
import org.eigenbase.sql.*;
import org.eigenbase.sql.type.SqlTypeUtil;
+import org.eigenbase.util.mapping.Mappings;
import com.google.common.collect.ImmutableList;
@@ -221,6 +222,12 @@ public class AggregateCall {
newReturnType,
getName());
}
+
+ /** Creates a copy of this aggregate call, applying a mapping to its
+ * arguments. */
+ public AggregateCall transform(Mappings.TargetMapping mapping) {
+ return copy(Mappings.permute(argList, mapping));
+ }
}
// End AggregateCall.java
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/7938e10d/core/src/main/java/org/eigenbase/rel/rules/AggregateStarTableRule.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/rel/rules/AggregateStarTableRule.java b/core/src/main/java/org/eigenbase/rel/rules/AggregateStarTableRule.java
index 5f61fd6..ac659ea 100644
--- a/core/src/main/java/org/eigenbase/rel/rules/AggregateStarTableRule.java
+++ b/core/src/main/java/org/eigenbase/rel/rules/AggregateStarTableRule.java
@@ -16,7 +16,12 @@
*/
package org.eigenbase.rel.rules;
+import java.util.BitSet;
+import java.util.List;
+
+import org.eigenbase.rel.AggregateCall;
import org.eigenbase.rel.AggregateRelBase;
+import org.eigenbase.rel.Aggregation;
import org.eigenbase.rel.ProjectRelBase;
import org.eigenbase.rel.RelNode;
import org.eigenbase.relopt.RelOptCluster;
@@ -26,12 +31,22 @@ import org.eigenbase.relopt.RelOptRuleCall;
import org.eigenbase.relopt.RelOptRuleOperand;
import org.eigenbase.relopt.RelOptTable;
import org.eigenbase.relopt.RelOptUtil;
+import org.eigenbase.reltype.RelDataType;
+import org.eigenbase.sql.fun.SqlStdOperatorTable;
+import org.eigenbase.util.Pair;
+import org.eigenbase.util.mapping.AbstractSourceMapping;
+import net.hydromatic.optiq.Table;
import net.hydromatic.optiq.impl.StarTable;
import net.hydromatic.optiq.jdbc.OptiqSchema;
+import net.hydromatic.optiq.materialize.Lattice;
+import net.hydromatic.optiq.materialize.MaterializationService;
+import net.hydromatic.optiq.prepare.OptiqPrepareImpl;
import net.hydromatic.optiq.prepare.RelOptTableImpl;
+import net.hydromatic.optiq.util.BitSets;
import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Lists;
/**
* Planner rule that matches an {@link org.eigenbase.rel.AggregateRelBase} on
@@ -88,27 +103,147 @@ public class AggregateStarTableRule extends RelOptRule {
}
protected void apply(RelOptRuleCall call, ProjectRelBase postProject,
- AggregateRelBase aggregate, StarTable.StarTableScan scan) {
+ final AggregateRelBase aggregate, StarTable.StarTableScan scan) {
final RelOptCluster cluster = scan.getCluster();
final RelOptTable table = scan.getTable();
final RelOptLattice lattice = call.getPlanner().getLattice(table);
- OptiqSchema.TableEntry aggregateTable =
+ final List<Lattice.Measure> measures =
+ lattice.lattice.toMeasures(aggregate.getAggCallList());
+ Pair<OptiqSchema.TableEntry, MaterializationService.TileKey> pair =
lattice.getAggregate(call.getPlanner(), aggregate.getGroupSet(),
- aggregate.getAggCallList());
- if (aggregateTable == null) {
+ measures);
+ if (pair == null) {
return;
}
+ final OptiqSchema.TableEntry tableEntry = pair.left;
+ final MaterializationService.TileKey tileKey = pair.right;
final double rowCount = aggregate.getRows();
+ final Table aggregateTable = tableEntry.getTable();
+ final RelDataType aggregateTableRowType =
+ aggregateTable.getRowType(cluster.getTypeFactory());
final RelOptTable aggregateRelOptTable =
- RelOptTableImpl.create(table.getRelOptSchema(),
- aggregateTable.getTable().getRowType(cluster.getTypeFactory()),
- aggregateTable, rowCount);
+ RelOptTableImpl.create(table.getRelOptSchema(), aggregateTableRowType,
+ tableEntry, rowCount);
RelNode rel = aggregateRelOptTable.toRel(RelOptUtil.getContext(cluster));
+ if (tileKey == null) {
+ if (OptiqPrepareImpl.DEBUG) {
+ System.out.println("Using materialization "
+ + aggregateRelOptTable.getQualifiedName()
+ + " (exact match)");
+ }
+ } else if (!tileKey.dimensions.equals(aggregate.getGroupSet())) {
+ // Aggregate has finer granularity than we need. Roll up.
+ if (OptiqPrepareImpl.DEBUG) {
+ System.out.println("Using materialization "
+ + aggregateRelOptTable.getQualifiedName()
+ + ", rolling up " + tileKey.dimensions + " to "
+ + aggregate.getGroupSet());
+ }
+ assert BitSets.contains(tileKey.dimensions, aggregate.getGroupSet());
+ final List<AggregateCall> aggCalls = Lists.newArrayList();
+ for (AggregateCall aggCall : aggregate.getAggCallList()) {
+ final AggregateCall copy = rollUp(aggCall, tileKey);
+ if (copy == null) {
+ return;
+ }
+ aggCalls.add(copy);
+ }
+ BitSet groupSet = new BitSet();
+ for (int key : BitSets.toIter(aggregate.getGroupSet())) {
+ groupSet.set(BitSets.toList(tileKey.dimensions).indexOf(key));
+ }
+ rel = aggregate.copy(aggregate.getTraitSet(), rel, groupSet, aggCalls);
+ } else if (!tileKey.measures.equals(measures)) {
+ System.out.println("Using materialization "
+ + aggregateRelOptTable.getQualifiedName()
+ + ", right granularity, but different measures "
+ + aggregate.getAggCallList());
+ rel = RelOptUtil.project(rel,
+ new AbstractSourceMapping(
+ tileKey.dimensions.cardinality() + tileKey.measures.size(),
+ aggregate.getRowType().getFieldCount()) {
+ public int getSourceOpt(int source) {
+ if (source < aggregate.getGroupCount()) {
+ int in = BitSets.toList(tileKey.dimensions).get(source);
+ return BitSets.toList(aggregate.getGroupSet()).indexOf(in);
+ }
+ Lattice.Measure measure =
+ measures.get(source - aggregate.getGroupCount());
+ int i = tileKey.measures.indexOf(measure);
+ assert i >= 0;
+ return tileKey.dimensions.cardinality() + i;
+ }
+ });
+ }
if (postProject != null) {
rel = postProject.copy(postProject.getTraitSet(), ImmutableList.of(rel));
}
call.transformTo(rel);
}
+
+ private static AggregateCall rollUp(AggregateCall aggregateCall,
+ MaterializationService.TileKey tileKey) {
+ final Aggregation aggregation = aggregateCall.getAggregation();
+ final Pair<Aggregation, List<Integer>> seek =
+ Pair.of(aggregation, aggregateCall.getArgList());
+ final int offset = tileKey.dimensions.cardinality();
+ final ImmutableList<Lattice.Measure> measures = tileKey.measures;
+
+ // First, try to satisfy the aggregation by rolling up an aggregate in the
+ // materialization.
+ final int i = find(measures, seek);
+ tryRoll:
+ if (i >= 0) {
+ final Aggregation roll = getRollup(aggregation);
+ if (roll == null) {
+ break tryRoll;
+ }
+ return new AggregateCall(roll, false, ImmutableList.of(offset + i),
+ aggregateCall.type, aggregateCall.name);
+ }
+
+ // Second, try to satisfy the aggregation based on group set columns.
+ tryGroup:
+ {
+ List<Integer> newArgs = Lists.newArrayList();
+ for (Integer arg : aggregateCall.getArgList()) {
+ int z = BitSets.toList(tileKey.dimensions).indexOf(arg);
+ if (z < 0) {
+ break tryGroup;
+ }
+ newArgs.add(z);
+ }
+ return new AggregateCall(aggregation, false, newArgs, aggregateCall.type,
+ aggregateCall.name);
+ }
+
+ // No roll up possible.
+ return null;
+ }
+
+ private static Aggregation getRollup(Aggregation aggregation) {
+ if (aggregation == SqlStdOperatorTable.SUM
+ || aggregation == SqlStdOperatorTable.MIN
+ || aggregation == SqlStdOperatorTable.MAX) {
+ return aggregation;
+ } else if (aggregation == SqlStdOperatorTable.COUNT) {
+ return SqlStdOperatorTable.SUM;
+ } else {
+ return null;
+ }
+ }
+
+ private static int find(ImmutableList<Lattice.Measure> measures,
+ Pair<Aggregation, List<Integer>> seek) {
+ for (int i = 0; i < measures.size(); i++) {
+ Lattice.Measure measure = measures.get(i);
+ if (measure.agg.equals(seek.left)
+ && measure.argOrdinals().equals(seek.right)) {
+ return i;
+ }
+ }
+ return -1;
+ }
}
// End AggregateStarTableRule.java
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/7938e10d/core/src/main/java/org/eigenbase/relopt/RelOptLattice.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/relopt/RelOptLattice.java b/core/src/main/java/org/eigenbase/relopt/RelOptLattice.java
index b458574..a03d273 100644
--- a/core/src/main/java/org/eigenbase/relopt/RelOptLattice.java
+++ b/core/src/main/java/org/eigenbase/relopt/RelOptLattice.java
@@ -19,8 +19,8 @@ package org.eigenbase.relopt;
import java.util.BitSet;
import java.util.List;
-import org.eigenbase.rel.AggregateCall;
import org.eigenbase.rel.RelNode;
+import org.eigenbase.util.Pair;
import net.hydromatic.optiq.config.OptiqConnectionConfig;
import net.hydromatic.optiq.jdbc.OptiqSchema;
@@ -31,7 +31,7 @@ import net.hydromatic.optiq.materialize.MaterializationService;
* Use of a lattice by the query optimizer.
*/
public class RelOptLattice {
- private final Lattice lattice;
+ public final Lattice lattice;
public final RelOptTable starRelOptTable;
public RelOptLattice(Lattice lattice, RelOptTable starRelOptTable) {
@@ -66,11 +66,13 @@ public class RelOptLattice {
*
* @param planner Current planner
* @param groupSet Grouping key
- * @param aggCallList Aggregate functions
+ * @param measureList Calls to aggregate functions
* @return Materialized table
*/
- public OptiqSchema.TableEntry getAggregate(RelOptPlanner planner,
- BitSet groupSet, List<AggregateCall> aggCallList) {
+ public
+ Pair<OptiqSchema.TableEntry, MaterializationService.TileKey> getAggregate(
+ RelOptPlanner planner, BitSet groupSet,
+ List<Lattice.Measure> measureList) {
final OptiqConnectionConfig config =
planner.getContext().unwrap(OptiqConnectionConfig.class);
if (config == null) {
@@ -79,7 +81,6 @@ public class RelOptLattice {
final MaterializationService service = MaterializationService.instance();
boolean create = lattice.auto && config.createMaterializations();
final OptiqSchema schema = starRelOptTable.unwrap(OptiqSchema.class);
- final List<Lattice.Measure> measureList = lattice.toMeasures(aggCallList);
return service.defineTile(lattice, groupSet, measureList, schema, create);
}
}
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/7938e10d/core/src/main/java/org/eigenbase/util/Util.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/util/Util.java b/core/src/main/java/org/eigenbase/util/Util.java
index 5f98ba2..25b5837 100644
--- a/core/src/main/java/org/eigenbase/util/Util.java
+++ b/core/src/main/java/org/eigenbase/util/Util.java
@@ -1759,6 +1759,63 @@ public class Util {
}
/**
+ * Sorts a collection.
+ */
+ public static <E extends Comparable<E>>
+ List<E> sort(Collection<? extends E> collection) {
+ if (collection instanceof List
+ && isSorted((List) collection)) {
+ // Avoid creating a copy of a list that is already sorted.
+ //noinspection unchecked
+ return (List) collection;
+ }
+ final Object[] elements = collection.toArray();
+ Arrays.sort(elements);
+ //noinspection unchecked
+ return (ImmutableList) ImmutableList.copyOf(elements);
+ }
+
+ /** Returns whether an iterable is in non-descending order. */
+ public static <E extends Comparable<E>>
+ boolean isSorted(Iterable<? extends E> list) {
+ final Iterator<? extends E> iterator = list.iterator();
+ if (!iterator.hasNext()) {
+ return true;
+ }
+ E e = iterator.next();
+ for (;;) {
+ if (!iterator.hasNext()) {
+ return true;
+ }
+ E next = iterator.next();
+ if (e.compareTo(next) > 0) {
+ return false;
+ }
+ e = next;
+ }
+ }
+
+ /** Returns whether an iterable is in ascending order. */
+ public static <E extends Comparable<E>>
+ boolean isStrictlySorted(Iterable<? extends E> list) {
+ final Iterator<? extends E> iterator = list.iterator();
+ if (!iterator.hasNext()) {
+ return true;
+ }
+ E e = iterator.next();
+ for (;;) {
+ if (!iterator.hasNext()) {
+ return true;
+ }
+ E next = iterator.next();
+ if (e.compareTo(next) >= 0) {
+ return false;
+ }
+ e = next;
+ }
+ }
+
+ /**
* Converts a {@link Properties} object to a <code>{@link Map}<String,
* String></code>.
*
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/7938e10d/core/src/main/java/org/eigenbase/util/mapping/AbstractSourceMapping.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/util/mapping/AbstractSourceMapping.java b/core/src/main/java/org/eigenbase/util/mapping/AbstractSourceMapping.java
new file mode 100644
index 0000000..2737362
--- /dev/null
+++ b/core/src/main/java/org/eigenbase/util/mapping/AbstractSourceMapping.java
@@ -0,0 +1,99 @@
+/*
+ * 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.eigenbase.util.mapping;
+
+import java.util.Iterator;
+
+/**
+ * Simple implementation of
+ * {@link org.eigenbase.util.mapping.Mappings.TargetMapping} where the number
+ * of sources and targets are specified as constructor parameters and you
+ * just need to implement one method,
+ */
+public abstract class AbstractSourceMapping
+ extends Mappings.AbstractMapping
+ implements Mapping {
+ private final int sourceCount;
+ private final int targetCount;
+
+ public AbstractSourceMapping(int sourceCount, int targetCount) {
+ this.sourceCount = sourceCount;
+ this.targetCount = targetCount;
+ }
+
+ @Override public int getSourceCount() {
+ return sourceCount;
+ }
+
+ @Override public int getTargetCount() {
+ return targetCount;
+ }
+
+ public Mapping inverse() {
+ return Mappings.invert(this);
+ }
+
+ public int size() {
+ return targetCount;
+ }
+
+ public void clear() {
+ throw new UnsupportedOperationException();
+ }
+
+ public MappingType getMappingType() {
+ return MappingType.INVERSE_PARTIAL_FUNCTION;
+ }
+
+ public Iterator<IntPair> iterator() {
+ return new Iterator<IntPair>() {
+ int source;
+ int target = -1;
+
+ {
+ moveToNext();
+ }
+
+ private void moveToNext() {
+ while (++target < targetCount) {
+ source = getSourceOpt(target);
+ if (source >= 0) {
+ break;
+ }
+ }
+ }
+
+ public boolean hasNext() {
+ return target < targetCount;
+ }
+
+ public IntPair next() {
+ IntPair p = new IntPair(source, target);
+ moveToNext();
+ return p;
+ }
+
+ public void remove() {
+ throw new UnsupportedOperationException("remove");
+ }
+ };
+ }
+
+ public abstract int getSourceOpt(int source);
+}
+
+// End AbstractTargetMapping.java
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/7938e10d/core/src/main/java/org/eigenbase/util/mapping/AbstractTargetMapping.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/util/mapping/AbstractTargetMapping.java b/core/src/main/java/org/eigenbase/util/mapping/AbstractTargetMapping.java
new file mode 100644
index 0000000..3048601
--- /dev/null
+++ b/core/src/main/java/org/eigenbase/util/mapping/AbstractTargetMapping.java
@@ -0,0 +1,99 @@
+/*
+ * 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.eigenbase.util.mapping;
+
+import java.util.Iterator;
+
+/**
+ * Simple implementation of
+ * {@link org.eigenbase.util.mapping.Mappings.TargetMapping} where the number
+ * of sources and targets are specified as constructor parameters and you
+ * just need to implement one method,
+ */
+public abstract class AbstractTargetMapping
+ extends Mappings.AbstractMapping
+ implements Mapping {
+ private final int sourceCount;
+ private final int targetCount;
+
+ public AbstractTargetMapping(int sourceCount, int targetCount) {
+ this.sourceCount = sourceCount;
+ this.targetCount = targetCount;
+ }
+
+ @Override public int getSourceCount() {
+ return sourceCount;
+ }
+
+ @Override public int getTargetCount() {
+ return targetCount;
+ }
+
+ public Mapping inverse() {
+ return Mappings.invert(this);
+ }
+
+ public int size() {
+ return sourceCount;
+ }
+
+ public void clear() {
+ throw new UnsupportedOperationException();
+ }
+
+ public MappingType getMappingType() {
+ return MappingType.PARTIAL_FUNCTION;
+ }
+
+ public Iterator<IntPair> iterator() {
+ return new Iterator<IntPair>() {
+ int source = -1;
+ int target;
+
+ {
+ moveToNext();
+ }
+
+ private void moveToNext() {
+ while (++source < sourceCount) {
+ target = getTargetOpt(source);
+ if (target >= 0) {
+ break;
+ }
+ }
+ }
+
+ public boolean hasNext() {
+ return source < sourceCount;
+ }
+
+ public IntPair next() {
+ IntPair p = new IntPair(source, target);
+ moveToNext();
+ return p;
+ }
+
+ public void remove() {
+ throw new UnsupportedOperationException("remove");
+ }
+ };
+ }
+
+ public abstract int getTargetOpt(int source);
+}
+
+// End AbstractTargetMapping.java
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/7938e10d/core/src/main/java/org/eigenbase/util/mapping/Mappings.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/util/mapping/Mappings.java b/core/src/main/java/org/eigenbase/util/mapping/Mappings.java
index ea5a6fd..071fdb4 100644
--- a/core/src/main/java/org/eigenbase/util/mapping/Mappings.java
+++ b/core/src/main/java/org/eigenbase/util/mapping/Mappings.java
@@ -91,6 +91,16 @@ public abstract class Mappings {
}
/**
+ * Converts a mapping to its inverse.
+ */
+ public static Mapping invert(Mapping mapping) {
+ if (mapping instanceof InverseMapping) {
+ return ((InverseMapping) mapping).parent;
+ }
+ return new InverseMapping(mapping);
+ }
+
+ /**
* Divides one mapping by another.
*
* <p>{@code divide(A, B)} returns a mapping C such that B . C (the mapping
@@ -234,6 +244,27 @@ public abstract class Mappings {
}
/**
+ * Creates a view of a list, permuting according to a target mapping.
+ *
+ * @param mapping Mapping
+ * @param list List
+ * @param <T> Element type
+ * @return Permuted view of list
+ */
+ public static <T> List<T> permute(final List<T> list,
+ final TargetMapping mapping) {
+ return new AbstractList<T>() {
+ public T get(int index) {
+ return list.get(mapping.getTarget(index));
+ }
+
+ public int size() {
+ return mapping.getSourceCount();
+ }
+ };
+ }
+
+ /**
* Returns a mapping as a list such that {@code list.get(source)} is
* {@code mapping.getTarget(source)} and {@code list.size()} is
* {@code mapping.getSourceCount()}.
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/7938e10d/core/src/test/java/net/hydromatic/optiq/test/LatticeTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/net/hydromatic/optiq/test/LatticeTest.java b/core/src/test/java/net/hydromatic/optiq/test/LatticeTest.java
index fa2f16a..162992b 100644
--- a/core/src/test/java/net/hydromatic/optiq/test/LatticeTest.java
+++ b/core/src/test/java/net/hydromatic/optiq/test/LatticeTest.java
@@ -249,21 +249,90 @@ public class LatticeTest {
+ " } ],\n"
+ " tiles: [ {\n"
+ " dimensions: [ 'the_year', ['t', 'quarter'] ],\n"
+ + " measures: [ ]\n"
+ + " } ]\n")
+ .query(
+ "select distinct t.\"the_year\", t.\"quarter\"\n"
+ + "from \"foodmart\".\"sales_fact_1997\" as s\n"
+ + "join \"foodmart\".\"time_by_day\" as t using (\"time_id\")\n")
+ .enableMaterializations(true)
+ .explainContains(
+ "EnumerableTableAccessRel(table=[[adhoc, m{27, 31}")
+ .returnsCount(4);
+ }
+
+ /** A query that uses a pre-defined aggregate table, at the same
+ * granularity but fewer calls to aggregate functions. */
+ @Test public void testLatticeWithPreDefinedTilesFewerMeasures() {
+ foodmartModel(
+ " auto: false,\n"
+ + " defaultMeasures: [ {\n"
+ + " agg: 'count'\n"
+ + " } ],\n"
+ + " tiles: [ {\n"
+ + " dimensions: [ 'the_year', ['t', 'quarter'] ],\n"
+ " measures: [ {\n"
- + " agg: 'count'\n"
+ + " agg: 'sum',\n"
+ + " args: 'unit_sales'\n"
+ " }, {\n"
+ " agg: 'sum',\n"
+ + " args: 'store_sales'\n"
+ + " }, {\n"
+ + " agg: 'count'\n"
+ + " } ]\n"
+ + " } ]\n")
+ .query(
+ "select t.\"the_year\", t.\"quarter\", count(*) as c\n"
+ + "from \"foodmart\".\"sales_fact_1997\" as s\n"
+ + "join \"foodmart\".\"time_by_day\" as t using (\"time_id\")\n"
+ + "group by t.\"the_year\", t.\"quarter\"")
+ .enableMaterializations(true)
+ .explainContains(
+ "EnumerableCalcRel(expr#0..4=[{inputs}], proj#0..2=[{exprs}])\n"
+ + " EnumerableTableAccessRel(table=[[adhoc, m{27, 31}")
+ .returnsUnordered("the_year=1997; quarter=Q1; C=21588",
+ "the_year=1997; quarter=Q2; C=20368",
+ "the_year=1997; quarter=Q3; C=21453",
+ "the_year=1997; quarter=Q4; C=23428")
+ .sameResultWithMaterializationsDisabled();
+ }
+
+ /** Tests a query that uses a pre-defined aggregate table at a lower
+ * granularity. Includes a measure computed from a grouping column, a measure
+ * based on COUNT rolled up using SUM, and an expression on a measure. */
+ @Test public void testLatticeWithPreDefinedTilesRollUp() {
+ foodmartModel(
+ " auto: false,\n"
+ + " defaultMeasures: [ {\n"
+ + " agg: 'count'\n"
+ + " } ],\n"
+ + " tiles: [ {\n"
+ + " dimensions: [ 'the_year', ['t', 'quarter'] ],\n"
+ + " measures: [ {\n"
+ + " agg: 'sum',\n"
+ " args: 'unit_sales'\n"
+ + " }, {\n"
+ + " agg: 'sum',\n"
+ + " args: 'store_sales'\n"
+ + " }, {\n"
+ + " agg: 'count'\n"
+ " } ]\n"
+ " } ]\n")
.query(
- "select distinct t.\"the_year\", t.\"quarter\"\n"
+ "select t.\"the_year\",\n"
+ + " count(*) as c,\n"
+ + " min(\"quarter\") as q,\n"
+ + " sum(\"unit_sales\") * 10 as us\n"
+ "from \"foodmart\".\"sales_fact_1997\" as s\n"
- + "join \"foodmart\".\"time_by_day\" as t using (\"time_id\")\n")
+ + "join \"foodmart\".\"time_by_day\" as t using (\"time_id\")\n"
+ + "group by t.\"the_year\"")
.enableMaterializations(true)
.explainContains(
- "EnumerableTableAccessRel(table=[[adhoc, m{27, 31}")
- .returnsCount(4);
+ "EnumerableCalcRel(expr#0..3=[{inputs}], expr#4=[10], expr#5=[*($t3, $t4)], proj#0..2=[{exprs}], US=[$t5])\n"
+ + " EnumerableAggregateRel(group=[{0}], agg#0=[$SUM0($2)], Q=[MIN($1)], agg#2=[$SUM0($4)])\n"
+ + " EnumerableTableAccessRel(table=[[adhoc, m{27, 31}")
+ .returnsUnordered("the_year=1997; C=86837; Q=Q1; US=2667730.0000")
+ .sameResultWithMaterializationsDisabled();
}
/** A tile with no measures should inherit default measure list from the
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/7938e10d/core/src/test/java/org/eigenbase/util/UtilTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/eigenbase/util/UtilTest.java b/core/src/test/java/org/eigenbase/util/UtilTest.java
index 7328bc5..b6bcf00 100644
--- a/core/src/test/java/org/eigenbase/util/UtilTest.java
+++ b/core/src/test/java/org/eigenbase/util/UtilTest.java
@@ -1332,6 +1332,24 @@ public class UtilTest {
assertThat(map.get("X"), is((String) null));
assertThat(map.get("Y"), equalTo("y"));
}
+
+ /** Unit test for {@link Util#isSorted(Iterable)}. */
+ @Test public void testIsSorted() {
+ final List<String> empty = Collections.emptyList();
+ assertThat(Util.isSorted(empty), is(true));
+
+ final List<String> listA = Arrays.asList("a");
+ assertThat(Util.isSorted(listA), is(true));
+
+ final List<String> listAB = Arrays.asList("a", "b");
+ assertThat(Util.isSorted(listAB), is(true));
+
+ final List<String> listAA = Arrays.asList("a", "a");
+ assertThat(Util.isSorted(listAA), is(true));
+
+ final List<String> listABA = Arrays.asList("a", "b", "a");
+ assertThat(Util.isSorted(listABA), is(false));
+ }
}
// End UtilTest.java