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/07/28 20:56:30 UTC
[6/7] git commit: [OPTIQ-349] Add heuristic join-optimizer that can
generate bushy joins
[OPTIQ-349] Add heuristic join-optimizer that can generate bushy joins
Add Util.human(), to format numbers like 'du -h' does.
Try harder to estimate row-count from abstract RelNodes.
Implement Metadata.toString() in reflective metadata provider.
Add row-count estimates to TPC-DS schema, and run heuristic bushy join algorithm on TPC-DS query 17.
Project: http://git-wip-us.apache.org/repos/asf/incubator-optiq/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-optiq/commit/b0aff0df
Tree: http://git-wip-us.apache.org/repos/asf/incubator-optiq/tree/b0aff0df
Diff: http://git-wip-us.apache.org/repos/asf/incubator-optiq/diff/b0aff0df
Branch: refs/heads/master
Commit: b0aff0df60b4c1f2a3ba70a4e17b86142103b93f
Parents: 1b12738
Author: Julian Hyde <jh...@apache.org>
Authored: Tue Jul 22 11:33:08 2014 -0700
Committer: Julian Hyde <jh...@apache.org>
Committed: Mon Jul 28 11:16:19 2014 -0700
----------------------------------------------------------------------
.../net/hydromatic/optiq/prepare/Prepare.java | 81 ++---
.../java/net/hydromatic/optiq/runtime/Hook.java | 3 +
.../net/hydromatic/optiq/tools/Programs.java | 89 ++++-
.../java/net/hydromatic/optiq/util/BitSets.java | 25 +-
.../metadata/ReflectiveRelMetadataProvider.java | 9 +-
.../org/eigenbase/rel/rules/LoptJoinTree.java | 7 +
.../org/eigenbase/rel/rules/LoptMultiJoin.java | 151 +++++----
.../rel/rules/LoptOptimizeJoinRule.java | 40 +--
.../rel/rules/OptimizeBushyJoinRule.java | 328 ++++++++++++++++++-
.../org/eigenbase/rel/rules/SemiJoinRel.java | 4 +-
.../org/eigenbase/relopt/volcano/RelSubset.java | 6 +-
.../eigenbase/sql2rel/SqlToRelConverter.java | 14 +-
.../org/eigenbase/util/ImmutableIntList.java | 32 +-
core/src/main/java/org/eigenbase/util/Util.java | 47 +++
.../org/eigenbase/util/mapping/Mappings.java | 91 ++++-
.../net/hydromatic/optiq/tools/PlannerTest.java | 126 ++++---
.../test/java/org/eigenbase/util/UtilTest.java | 43 +++
.../optiq/impl/tpcds/TpcdsSchema.java | 42 ++-
.../hydromatic/optiq/impl/tpcds/TpcdsTest.java | 51 ++-
19 files changed, 941 insertions(+), 248 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b0aff0df/core/src/main/java/net/hydromatic/optiq/prepare/Prepare.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/net/hydromatic/optiq/prepare/Prepare.java b/core/src/main/java/net/hydromatic/optiq/prepare/Prepare.java
index c2d5dba..0fb3f14 100644
--- a/core/src/main/java/net/hydromatic/optiq/prepare/Prepare.java
+++ b/core/src/main/java/net/hydromatic/optiq/prepare/Prepare.java
@@ -21,7 +21,6 @@ import net.hydromatic.optiq.DataContext;
import net.hydromatic.optiq.impl.StarTable;
import net.hydromatic.optiq.jdbc.OptiqPrepare;
import net.hydromatic.optiq.jdbc.OptiqSchema;
-import net.hydromatic.optiq.rules.java.JavaRules;
import net.hydromatic.optiq.runtime.Bindable;
import net.hydromatic.optiq.runtime.Hook;
import net.hydromatic.optiq.runtime.Typed;
@@ -29,8 +28,6 @@ import net.hydromatic.optiq.tools.Program;
import net.hydromatic.optiq.tools.Programs;
import org.eigenbase.rel.*;
-import org.eigenbase.rel.metadata.*;
-import org.eigenbase.rel.rules.*;
import org.eigenbase.relopt.*;
import org.eigenbase.reltype.RelDataType;
import org.eigenbase.rex.RexBuilder;
@@ -40,6 +37,7 @@ import org.eigenbase.sql.validate.*;
import org.eigenbase.sql2rel.SqlToRelConverter;
import org.eigenbase.trace.EigenbaseTimingTracer;
import org.eigenbase.trace.EigenbaseTrace;
+import org.eigenbase.util.Pair;
import com.google.common.collect.ImmutableList;
@@ -55,24 +53,6 @@ import java.util.logging.Logger;
public abstract class Prepare {
protected static final Logger LOGGER = EigenbaseTrace.getStatementTracer();
- private static final ImmutableList<RelOptRule> CALC_RULES =
- ImmutableList.of(
- JavaRules.ENUMERABLE_CALC_RULE,
- JavaRules.ENUMERABLE_FILTER_TO_CALC_RULE,
- JavaRules.ENUMERABLE_PROJECT_TO_CALC_RULE,
- MergeCalcRule.INSTANCE,
- MergeFilterOntoCalcRule.INSTANCE,
- MergeProjectOntoCalcRule.INSTANCE,
- FilterToCalcRule.INSTANCE,
- ProjectToCalcRule.INSTANCE,
- MergeCalcRule.INSTANCE,
-
- // REVIEW jvs 9-Apr-2006: Do we still need these two? Doesn't the
- // combination of MergeCalcRule, FilterToCalcRule, and
- // ProjectToCalcRule have the same effect?
- MergeFilterOntoCalcRule.INSTANCE,
- MergeProjectOntoCalcRule.INSTANCE);
-
protected final OptiqPrepare.Context context;
protected final CatalogReader catalogReader;
protected String queryString = null;
@@ -124,39 +104,19 @@ public abstract class Prepare {
planner.setRoot(rootRel);
final RelTraitSet desiredTraits = getDesiredRootTraitSet(rootRel);
- final Program program1 =
- new Program() {
- public RelNode run(RelOptPlanner planner, RelNode rel,
- RelTraitSet requiredOutputTraits) {
- final DataContext dataContext = context.getDataContext();
- planner.setExecutor(new RexExecutorImpl(dataContext));
-
- for (Materialization materialization : materializations) {
- planner.addMaterialization(
- new RelOptMaterialization(materialization.tableRel,
- materialization.queryRel,
- materialization.starRelOptTable));
- }
-
- final RelNode rootRel2 =
- planner.changeTraits(rel, requiredOutputTraits);
- assert rootRel2 != null;
-
- planner.setRoot(rootRel2);
- final RelOptPlanner planner2 = planner.chooseDelegate();
- final RelNode rootRel3 = planner2.findBestExp();
- assert rootRel3 != null : "could not implement exp";
- return rootRel3;
- }
- };
-
- final RelNode rootRel3 = program1.run(planner, rootRel, desiredTraits);
-
- // Second planner pass to do physical "tweaks". This the first time that
- // EnumerableCalcRel is introduced.
- final Program program2 =
- Programs.hep(CALC_RULES, true, new DefaultRelMetadataProvider());
- final RelNode rootRel4 = program2.run(null, rootRel3, null);
+ final Program program = getProgram();
+
+ final DataContext dataContext = context.getDataContext();
+ planner.setExecutor(new RexExecutorImpl(dataContext));
+
+ for (Materialization materialization : materializations) {
+ planner.addMaterialization(
+ new RelOptMaterialization(materialization.tableRel,
+ materialization.queryRel,
+ materialization.starRelOptTable));
+ }
+
+ final RelNode rootRel4 = program.run(planner, rootRel, desiredTraits);
if (LOGGER.isLoggable(Level.FINE)) {
LOGGER.fine(
"Plan after physical tweaks: "
@@ -166,6 +126,19 @@ public abstract class Prepare {
return rootRel4;
}
+ private Program getProgram() {
+ // Allow a test to override the planner.
+ final List<Materialization> materializations = ImmutableList.of();
+ final Pair<List<Materialization>, Program[]> pair =
+ Pair.of(materializations, new Program[1]);
+ Hook.PROGRAM.run(pair);
+ if (pair.right[0] != null) {
+ return pair.right[0];
+ }
+
+ return Programs.standard();
+ }
+
protected RelTraitSet getDesiredRootTraitSet(RelNode rootRel) {
// Make sure non-CallingConvention traits, if any, are preserved
return rootRel.getTraitSet()
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b0aff0df/core/src/main/java/net/hydromatic/optiq/runtime/Hook.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/net/hydromatic/optiq/runtime/Hook.java b/core/src/main/java/net/hydromatic/optiq/runtime/Hook.java
index 442e4b5..653ad23 100644
--- a/core/src/main/java/net/hydromatic/optiq/runtime/Hook.java
+++ b/core/src/main/java/net/hydromatic/optiq/runtime/Hook.java
@@ -47,6 +47,9 @@ public enum Hook {
/** Called when a constant expression is being reduced. */
EXPRESSION_REDUCER,
+ /** Called to create a Program to optimize the statement. */
+ PROGRAM,
+
/** Called with a query that has been generated to send to a back-end system.
* The query might be a SQL string (for the JDBC adapter), a list of Mongo
* pipeline expressions (for the MongoDB adapter), et cetera. */
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b0aff0df/core/src/main/java/net/hydromatic/optiq/tools/Programs.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/net/hydromatic/optiq/tools/Programs.java b/core/src/main/java/net/hydromatic/optiq/tools/Programs.java
index 83c73cd..3e97c2f 100644
--- a/core/src/main/java/net/hydromatic/optiq/tools/Programs.java
+++ b/core/src/main/java/net/hydromatic/optiq/tools/Programs.java
@@ -17,8 +17,12 @@
*/
package net.hydromatic.optiq.tools;
+import net.hydromatic.optiq.prepare.OptiqPrepareImpl;
+import net.hydromatic.optiq.rules.java.JavaRules;
+
import org.eigenbase.rel.RelNode;
import org.eigenbase.rel.metadata.ChainedRelMetadataProvider;
+import org.eigenbase.rel.metadata.DefaultRelMetadataProvider;
import org.eigenbase.rel.metadata.RelMetadataProvider;
import org.eigenbase.rel.rules.*;
import org.eigenbase.relopt.*;
@@ -26,6 +30,7 @@ import org.eigenbase.relopt.hep.*;
import com.google.common.base.Function;
import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Lists;
import java.util.*;
@@ -41,6 +46,53 @@ public class Programs {
}
};
+ public static final ImmutableList<RelOptRule> CALC_RULES =
+ ImmutableList.of(
+ JavaRules.ENUMERABLE_CALC_RULE,
+ JavaRules.ENUMERABLE_FILTER_TO_CALC_RULE,
+ JavaRules.ENUMERABLE_PROJECT_TO_CALC_RULE,
+ MergeCalcRule.INSTANCE,
+ MergeFilterOntoCalcRule.INSTANCE,
+ MergeProjectOntoCalcRule.INSTANCE,
+ FilterToCalcRule.INSTANCE,
+ ProjectToCalcRule.INSTANCE,
+ MergeCalcRule.INSTANCE,
+
+ // REVIEW jvs 9-Apr-2006: Do we still need these two? Doesn't the
+ // combination of MergeCalcRule, FilterToCalcRule, and
+ // ProjectToCalcRule have the same effect?
+ MergeFilterOntoCalcRule.INSTANCE,
+ MergeProjectOntoCalcRule.INSTANCE);
+
+ public static final ImmutableSet<RelOptRule> RULE_SET =
+ ImmutableSet.of(
+ JavaRules.ENUMERABLE_JOIN_RULE,
+ JavaRules.ENUMERABLE_PROJECT_RULE,
+ JavaRules.ENUMERABLE_FILTER_RULE,
+ JavaRules.ENUMERABLE_AGGREGATE_RULE,
+ JavaRules.ENUMERABLE_SORT_RULE,
+ JavaRules.ENUMERABLE_LIMIT_RULE,
+ JavaRules.ENUMERABLE_UNION_RULE,
+ JavaRules.ENUMERABLE_INTERSECT_RULE,
+ JavaRules.ENUMERABLE_MINUS_RULE,
+ JavaRules.ENUMERABLE_TABLE_MODIFICATION_RULE,
+ JavaRules.ENUMERABLE_VALUES_RULE,
+ JavaRules.ENUMERABLE_WINDOW_RULE,
+ JavaRules.ENUMERABLE_ONE_ROW_RULE,
+ JavaRules.ENUMERABLE_EMPTY_RULE,
+ TableAccessRule.INSTANCE,
+ OptiqPrepareImpl.COMMUTE
+ ? CommutativeJoinRule.INSTANCE
+ : MergeProjectRule.INSTANCE,
+ PushFilterPastProjectRule.INSTANCE,
+ PushFilterPastJoinRule.FILTER_ON_JOIN,
+ RemoveDistinctAggregateRule.INSTANCE,
+ ReduceAggregatesRule.INSTANCE,
+ SwapJoinRule.INSTANCE,
+ PushJoinThroughJoinRule.RIGHT,
+ PushJoinThroughJoinRule.LEFT,
+ PushSortPastProjectRule.INSTANCE);
+
// private constructor for utility class
private Programs() {}
@@ -120,7 +172,7 @@ public class Programs {
RelTraitSet requiredOutputTraits) {
final int joinCount = RelOptUtil.countJoins(rel);
final Program program;
- if (joinCount < 6) {
+ if (joinCount < (bushy ? 2 : 6)) {
program = ofRules(rules);
} else {
// Create a program that gathers together joins as a MultiJoinRel.
@@ -153,6 +205,41 @@ public class Programs {
};
}
+ public static Program getProgram() {
+ return new Program() {
+ public RelNode run(RelOptPlanner planner, RelNode rel,
+ RelTraitSet requiredOutputTraits) {
+ return null;
+ }
+ };
+ }
+
+ /** Returns the standard program used by Prepare. */
+ public static Program standard() {
+ final Program program1 =
+ new Program() {
+ public RelNode run(RelOptPlanner planner, RelNode rel,
+ RelTraitSet requiredOutputTraits) {
+ final RelNode rootRel2 =
+ planner.changeTraits(rel, requiredOutputTraits);
+ assert rootRel2 != null;
+
+ planner.setRoot(rootRel2);
+ final RelOptPlanner planner2 = planner.chooseDelegate();
+ final RelNode rootRel3 = planner2.findBestExp();
+ assert rootRel3 != null : "could not implement exp";
+ return rootRel3;
+ }
+ };
+
+ // Second planner pass to do physical "tweaks". This the first time that
+ // EnumerableCalcRel is introduced.
+ final Program program2 =
+ hep(CALC_RULES, true, new DefaultRelMetadataProvider());
+
+ return sequence(program1, program2);
+ }
+
/** Program backed by a {@link RuleSet}. */
static class RuleSetProgram implements Program {
final RuleSet ruleSet;
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b0aff0df/core/src/main/java/net/hydromatic/optiq/util/BitSets.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/net/hydromatic/optiq/util/BitSets.java b/core/src/main/java/net/hydromatic/optiq/util/BitSets.java
index f0dbd4f..78394db 100644
--- a/core/src/main/java/net/hydromatic/optiq/util/BitSets.java
+++ b/core/src/main/java/net/hydromatic/optiq/util/BitSets.java
@@ -17,6 +17,7 @@
*/
package net.hydromatic.optiq.util;
+import org.eigenbase.util.ImmutableIntList;
import org.eigenbase.util.IntList;
import java.util.*;
@@ -136,7 +137,7 @@ public final class BitSets {
}
/**
- * Creates a bitset with given bits set.
+ * Creates a BitSet with given bits set.
*
* <p>For example, {@code of(new Integer[] {0, 3})} returns a bit set
* with bits {0, 3} set.
@@ -153,7 +154,7 @@ public final class BitSets {
}
/**
- * Creates a bitset with given bits set.
+ * Creates a BitSet with given bits set.
*
* <p>For example, {@code of(Arrays.asList(0, 3)) } returns a bit set
* with bits {0, 3} set.
@@ -161,7 +162,7 @@ public final class BitSets {
* @param bits Collection of bits to set
* @return Bit set
*/
- public static BitSet of(Collection<? extends Number> bits) {
+ public static BitSet of(Iterable<? extends Number> bits) {
final BitSet bitSet = new BitSet();
for (Number bit : bits) {
bitSet.set(bit.intValue());
@@ -170,6 +171,23 @@ public final class BitSets {
}
/**
+ * Creates a BitSet with given bits set.
+ *
+ * <p>For example, {@code of(ImmutableIntList.of(0, 3))} returns a bit set
+ * with bits {0, 3} set.
+ *
+ * @param bits Collection of bits to set
+ * @return Bit set
+ */
+ public static BitSet of(ImmutableIntList bits) {
+ final BitSet bitSet = new BitSet();
+ for (int i = 0, n = bits.size(); i < n; i++) {
+ bitSet.set(bits.getInt(i));
+ }
+ return bitSet;
+ }
+
+ /**
* Creates a bitset with bits from {@code fromIndex} (inclusive) to
* specified {@code toIndex} (exclusive) set to {@code true}.
*
@@ -190,6 +208,7 @@ public final class BitSets {
return bitSet;
}
+ /** Creates a BitSet with bits between 0 and {@code toIndex} set. */
public static BitSet range(int toIndex) {
return range(0, toIndex);
}
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b0aff0df/core/src/main/java/org/eigenbase/rel/metadata/ReflectiveRelMetadataProvider.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/rel/metadata/ReflectiveRelMetadataProvider.java b/core/src/main/java/org/eigenbase/rel/metadata/ReflectiveRelMetadataProvider.java
index a0c25c7..20e6ec2 100644
--- a/core/src/main/java/org/eigenbase/rel/metadata/ReflectiveRelMetadataProvider.java
+++ b/core/src/main/java/org/eigenbase/rel/metadata/ReflectiveRelMetadataProvider.java
@@ -120,10 +120,15 @@ public class ReflectiveRelMetadataProvider
// Selectivity.selectivity(rex)
// by calling method
// new SelectivityImpl().selectivity(filter, rex)
- if (method.equals(BuiltinMethod.METADATA_REL.method))
- {
+ if (method.equals(
+ BuiltinMethod.METADATA_REL.method)) {
return rel;
}
+ if (method.equals(
+ BuiltinMethod.OBJECT_TO_STRING.method)) {
+ return metadataClass0.getSimpleName() + "(" + rel
+ + ")";
+ }
final Object[] args1;
if (args == null) {
args1 = new Object[]{rel};
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b0aff0df/core/src/main/java/org/eigenbase/rel/rules/LoptJoinTree.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/rel/rules/LoptJoinTree.java b/core/src/main/java/org/eigenbase/rel/rules/LoptJoinTree.java
index 0e32b0e..5f277a9 100644
--- a/core/src/main/java/org/eigenbase/rel/rules/LoptJoinTree.java
+++ b/core/src/main/java/org/eigenbase/rel/rules/LoptJoinTree.java
@@ -22,6 +22,7 @@ import java.util.*;
import org.eigenbase.rel.*;
import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
/**
* Utility class used to store a {@link JoinRelBase} tree and the factors that
@@ -132,6 +133,12 @@ public class LoptJoinTree {
return factorTree;
}
+ public List<Integer> getTreeOrder() {
+ List<Integer> treeOrder = Lists.newArrayList();
+ getTreeOrder(treeOrder);
+ return treeOrder;
+ }
+
public void getTreeOrder(List<Integer> treeOrder) {
factorTree.getTreeOrder(treeOrder);
}
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b0aff0df/core/src/main/java/org/eigenbase/rel/rules/LoptMultiJoin.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/rel/rules/LoptMultiJoin.java b/core/src/main/java/org/eigenbase/rel/rules/LoptMultiJoin.java
index 4a79da0..6579674 100644
--- a/core/src/main/java/org/eigenbase/rel/rules/LoptMultiJoin.java
+++ b/core/src/main/java/org/eigenbase/rel/rules/LoptMultiJoin.java
@@ -29,6 +29,9 @@ import org.eigenbase.util.IntList;
import net.hydromatic.optiq.util.BitSets;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Lists;
+
/**
* Utility class that keeps track of the join factors that
* make up a {@link MultiJoinRel}.
@@ -56,7 +59,7 @@ public class LoptMultiJoin {
/**
* Number of factors into the MultiJoinRel
*/
- private int nJoinFactors;
+ private final int nJoinFactors;
/**
* Total number of fields in the MultiJoinRel
@@ -66,21 +69,21 @@ public class LoptMultiJoin {
/**
* Original inputs into the MultiJoinRel
*/
- private List<RelNode> joinFactors;
+ private final ImmutableList<RelNode> joinFactors;
/**
* If a join factor is null generating in a left or right outer join,
* joinTypes indicates the join type corresponding to the factor. Otherwise,
* it is set to INNER.
*/
- private List<JoinRelType> joinTypes;
+ private final ImmutableList<JoinRelType> joinTypes;
/**
* If a join factor is null generating in a left or right outer join, the
* bitmap contains the non-null generating factors that the null generating
* factor is dependent upon
*/
- private BitSet [] outerJoinFactors;
+ private final BitSet [] outerJoinFactors;
/**
* Bitmap corresponding to the fields projected from each join factor, after
@@ -134,7 +137,7 @@ public class LoptMultiJoin {
/**
* Type factory
*/
- RelDataTypeFactory factory;
+ final RelDataTypeFactory factory;
/**
* Indicates for each factor whether its join can be removed because it is
@@ -168,22 +171,18 @@ public class LoptMultiJoin {
public LoptMultiJoin(MultiJoinRel multiJoin) {
this.multiJoin = multiJoin;
- joinFactors = multiJoin.getInputs();
+ joinFactors = ImmutableList.copyOf(multiJoin.getInputs());
nJoinFactors = joinFactors.size();
projFields = multiJoin.getProjFields();
joinFieldRefCountsMap = multiJoin.getCopyJoinFieldRefCountsMap();
- joinFilters = new ArrayList<RexNode>();
- RelOptUtil.decomposeConjunction(
- multiJoin.getJoinFilter(),
- joinFilters);
+ joinFilters =
+ Lists.newArrayList(RelOptUtil.conjunctions(multiJoin.getJoinFilter()));
allJoinFilters = new ArrayList<RexNode>(joinFilters);
List<RexNode> outerJoinFilters = multiJoin.getOuterJoinConditions();
for (int i = 0; i < nJoinFactors; i++) {
- List<RexNode> ojFilters = new ArrayList<RexNode>();
- RelOptUtil.decomposeConjunction(outerJoinFilters.get(i), ojFilters);
- allJoinFilters.addAll(ojFilters);
+ allJoinFilters.addAll(RelOptUtil.conjunctions(outerJoinFilters.get(i)));
}
int start = 0;
@@ -197,7 +196,23 @@ public class LoptMultiJoin {
start += nFieldsInJoinFactor[i];
}
- setOuterJoinInfo();
+ // Extract outer join information from the join factors, including the type
+ // of outer join and the factors that a null-generating factor is dependent
+ // upon.
+ joinTypes = ImmutableList.copyOf(multiJoin.getJoinTypes());
+ List<RexNode> outerJoinConds = this.multiJoin.getOuterJoinConditions();
+ outerJoinFactors = new BitSet[nJoinFactors];
+ for (int i = 0; i < nJoinFactors; i++) {
+ if (outerJoinConds.get(i) != null) {
+ // set a bitmap containing the factors referenced in the
+ // ON condition of the outer join; mask off the factor
+ // corresponding to the factor itself
+ BitSet dependentFactors =
+ getJoinFilterFactorBitmap(outerJoinConds.get(i), false);
+ dependentFactors.clear(i);
+ outerJoinFactors[i] = dependentFactors;
+ }
+ }
// determine which join factors each join filter references
setJoinFilterRefs();
@@ -404,28 +419,6 @@ public class LoptMultiJoin {
}
/**
- * Extracts outer join information from the join factors, including the type
- * of outer join and the factors that a null-generating factor is dependent
- * upon.
- */
- private void setOuterJoinInfo() {
- joinTypes = multiJoin.getJoinTypes();
- List<RexNode> outerJoinConds = multiJoin.getOuterJoinConditions();
- outerJoinFactors = new BitSet[nJoinFactors];
- for (int i = 0; i < nJoinFactors; i++) {
- if (outerJoinConds.get(i) != null) {
- // set a bitmap containing the factors referenced in the
- // ON condition of the outer join; mask off the factor
- // corresponding to the factor itself
- BitSet dependentFactors =
- getJoinFilterFactorBitmap(outerJoinConds.get(i), false);
- dependentFactors.clear(i);
- outerJoinFactors[i] = dependentFactors;
- }
- }
- }
-
- /**
* Returns a bitmap representing the factors referenced in a join filter
*
* @param joinFilter the join filter
@@ -434,18 +427,21 @@ public class LoptMultiJoin {
*
* @return the bitmap containing the factor references
*/
- private BitSet getJoinFilterFactorBitmap(
+ BitSet getJoinFilterFactorBitmap(
RexNode joinFilter,
boolean setFields) {
- BitSet fieldRefBitmap = new BitSet(nTotalFields);
- joinFilter.accept(new RelOptUtil.InputFinder(fieldRefBitmap));
+ BitSet fieldRefBitmap = fieldBitmap(joinFilter);
if (setFields) {
fieldsRefByJoinFilter.put(joinFilter, fieldRefBitmap);
}
- BitSet factorRefBitmap = new BitSet(nJoinFactors);
- setFactorBitmap(factorRefBitmap, fieldRefBitmap);
- return factorRefBitmap;
+ return factorBitmap(fieldRefBitmap);
+ }
+
+ private BitSet fieldBitmap(RexNode joinFilter) {
+ BitSet fieldRefBitmap = new BitSet(nTotalFields);
+ joinFilter.accept(new RelOptUtil.InputFinder(fieldRefBitmap));
+ return fieldRefBitmap;
}
/**
@@ -474,17 +470,17 @@ public class LoptMultiJoin {
* Sets the bitmap indicating which factors a filter references based on
* which fields it references
*
- * @param factorRefBitmap bitmap representing factors referenced that will
- * be set by this method
* @param fieldRefBitmap bitmap representing fields referenced
+ * @return bitmap representing factors referenced that will
+ * be set by this method
*/
- private void setFactorBitmap(
- BitSet factorRefBitmap,
- BitSet fieldRefBitmap) {
+ private BitSet factorBitmap(BitSet fieldRefBitmap) {
+ BitSet factorRefBitmap = new BitSet(nJoinFactors);
for (int field : BitSets.toIter(fieldRefBitmap)) {
int factor = findRef(field);
factorRefBitmap.set(factor);
}
+ return factorRefBitmap;
}
/**
@@ -540,11 +536,9 @@ public class LoptMultiJoin {
int leftFactor = factorRefs.nextSetBit(0);
int rightFactor = factorRefs.nextSetBit(leftFactor + 1);
- BitSet leftFields = new BitSet(nTotalFields);
- List<RexNode> operands = ((RexCall) joinFilter).getOperands();
- operands.get(0).accept(new RelOptUtil.InputFinder(leftFields));
- BitSet leftBitmap = new BitSet(nJoinFactors);
- setFactorBitmap(leftBitmap, leftFields);
+ final RexCall call = (RexCall) joinFilter;
+ BitSet leftFields = fieldBitmap(call.getOperands().get(0));
+ BitSet leftBitmap = factorBitmap(leftFields);
// filter contains only two factor references, one on each
// side of the operator
@@ -604,29 +598,7 @@ public class LoptMultiJoin {
public boolean hasAllFactors(
LoptJoinTree joinTree,
BitSet factorsNeeded) {
- BitSet childFactors = new BitSet(nJoinFactors);
- getChildFactors(joinTree, childFactors);
- return BitSets.contains(childFactors, factorsNeeded);
- }
-
- /**
- * Sets a bitmap representing all fields corresponding to a RelNode
- *
- * @param rel Relational expression for which fields will be set
- * @param fields bitmap containing set bits for each field in a RelNode
- */
- public void setFieldBitmap(LoptJoinTree rel, BitSet fields) {
- // iterate through all factors within the RelNode
- BitSet factors = new BitSet(nJoinFactors);
- getChildFactors(rel, factors);
- for (int factor = factors.nextSetBit(0);
- factor >= 0;
- factor = factors.nextSetBit(factor + 1)) {
- // set a bit for each field
- for (int i = 0; i < nFieldsInJoinFactor[factor]; i++) {
- fields.set(joinStart[factor] + i);
- }
- }
+ return BitSets.contains(BitSets.of(joinTree.getTreeOrder()), factorsNeeded);
}
/**
@@ -636,9 +608,7 @@ public class LoptMultiJoin {
* @param childFactors bitmap to be set
*/
public void getChildFactors(LoptJoinTree joinTree, BitSet childFactors) {
- List<Integer> children = new ArrayList<Integer>();
- joinTree.getTreeOrder(children);
- for (int child : children) {
+ for (int child : joinTree.getTreeOrder()) {
childFactors.set(child);
}
}
@@ -809,6 +779,31 @@ public class LoptMultiJoin {
return selfJoin.getColumnMapping().get(rightOffset);
}
+ public Edge createEdge(RexNode condition) {
+ BitSet fieldRefBitmap = fieldBitmap(condition);
+ BitSet factorRefBitmap = factorBitmap(fieldRefBitmap);
+ return new Edge(condition, factorRefBitmap, fieldRefBitmap);
+ }
+
+ /** Information about a join-condition. */
+ static class Edge {
+ final BitSet factors;
+ final BitSet columns;
+ final RexNode condition;
+
+ Edge(RexNode condition, BitSet factors, BitSet columns) {
+ this.condition = condition;
+ this.factors = factors;
+ this.columns = columns;
+ }
+
+ @Override public String toString() {
+ return "Edge(condition: " + condition
+ + ", factors: " + factors
+ + ", columns: " + columns + ")";
+ }
+ }
+
//~ Inner Classes ----------------------------------------------------------
/**
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b0aff0df/core/src/main/java/org/eigenbase/rel/rules/LoptOptimizeJoinRule.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/rel/rules/LoptOptimizeJoinRule.java b/core/src/main/java/org/eigenbase/rel/rules/LoptOptimizeJoinRule.java
index e758ee1..6e13a25 100644
--- a/core/src/main/java/org/eigenbase/rel/rules/LoptOptimizeJoinRule.java
+++ b/core/src/main/java/org/eigenbase/rel/rules/LoptOptimizeJoinRule.java
@@ -25,6 +25,7 @@ import org.eigenbase.relopt.*;
import org.eigenbase.reltype.*;
import org.eigenbase.rex.*;
import org.eigenbase.sql.fun.*;
+import org.eigenbase.util.ImmutableIntList;
import org.eigenbase.util.Pair;
import org.eigenbase.util.mapping.IntPair;
@@ -445,7 +446,7 @@ public class LoptOptimizeJoinRule extends RelOptRule {
*
* @param multiJoin join factors being optimized
* @param joinTree selected join ordering
- * @param fieldNames fieldnames corresponding to the projection expressions
+ * @param fieldNames field names corresponding to the projection expressions
*
* @return created projection
*/
@@ -459,8 +460,7 @@ public class LoptOptimizeJoinRule extends RelOptRule {
// create a projection on top of the joins, matching the original
// join order
- List<Integer> newJoinOrder = new ArrayList<Integer>();
- joinTree.getTreeOrder(newJoinOrder);
+ final List<Integer> newJoinOrder = joinTree.getTreeOrder();
int nJoinFactors = multiJoin.getNumJoinFactors();
List<RelDataTypeField> fields = multiJoin.getMultiJoinFields();
@@ -536,9 +536,7 @@ public class LoptOptimizeJoinRule extends RelOptRule {
LoptJoinTree joinTree,
List<RexNode> filters,
int factor) {
- int nJoinFactors = multiJoin.getNumJoinFactors();
- BitSet childFactors = new BitSet(nJoinFactors);
- multiJoin.getChildFactors(joinTree, childFactors);
+ BitSet childFactors = BitSets.of(joinTree.getTreeOrder());
childFactors.set(factor);
int factorStart = multiJoin.getJoinStart(factor);
@@ -558,12 +556,9 @@ public class LoptOptimizeJoinRule extends RelOptRule {
// then loop through the outer join filters where the factor being
// added is the null generating factor in the outer join
- RexNode outerJoinCond = multiJoin.getOuterJoinCond(factor);
- List<RexNode> outerJoinFilters = new ArrayList<RexNode>();
- RelOptUtil.decomposeConjunction(outerJoinCond, outerJoinFilters);
setFactorJoinKeys(
multiJoin,
- outerJoinFilters,
+ RelOptUtil.conjunctions(multiJoin.getOuterJoinCond(factor)),
childFactors,
factorStart,
nFields,
@@ -845,7 +840,7 @@ public class LoptOptimizeJoinRule extends RelOptRule {
joinTree,
-1,
factorToAdd,
- new ArrayList<Integer>(),
+ ImmutableIntList.of(),
null,
filtersToAdd);
}
@@ -1038,8 +1033,7 @@ public class LoptOptimizeJoinRule extends RelOptRule {
// remember the original join order before the pushdown so we can
// appropriately adjust any filters already attached to the join
// node
- List<Integer> origJoinOrder = new ArrayList<Integer>();
- joinTree.getTreeOrder(origJoinOrder);
+ final List<Integer> origJoinOrder = joinTree.getTreeOrder();
// recursively pushdown the factor
LoptJoinTree subTree = (childNo == 0) ? left : right;
@@ -1212,19 +1206,18 @@ public class LoptOptimizeJoinRule extends RelOptRule {
boolean adjust) {
// loop through the remaining filters to be added and pick out the
// ones that reference only the factors in the new join tree
- RexNode condition = null;
- ListIterator<RexNode> filterIter = filtersToAdd.listIterator();
- int nJoinFactors = multiJoin.getNumJoinFactors();
- RexBuilder rexBuilder =
+ final RexBuilder rexBuilder =
multiJoin.getMultiJoinRel().getCluster().getRexBuilder();
- BitSet childFactors = new BitSet(nJoinFactors);
+ final BitSet childFactors = BitSets.of(rightTree.getTreeOrder());
if (leftIdx >= 0) {
childFactors.set(leftIdx);
} else {
- multiJoin.getChildFactors(leftTree, childFactors);
+ BitSets.setAll(childFactors, leftTree.getTreeOrder());
}
multiJoin.getChildFactors(rightTree, childFactors);
+ RexNode condition = null;
+ final ListIterator<RexNode> filterIter = filtersToAdd.listIterator();
while (filterIter.hasNext()) {
RexNode joinFilter = filterIter.next();
BitSet filterBitmap =
@@ -1491,8 +1484,7 @@ public class LoptOptimizeJoinRule extends RelOptRule {
}
int factIdx = multiJoin.getJoinRemovalFactor(dimIdx);
- List<Integer> joinOrder = new ArrayList<Integer>();
- factTree.getTreeOrder(joinOrder);
+ final List<Integer> joinOrder = factTree.getTreeOrder();
assert joinOrder.contains(factIdx);
// figure out the position of the fact table in the current jointree
@@ -1511,8 +1503,8 @@ public class LoptOptimizeJoinRule extends RelOptRule {
int nDimFields = dimFields.size();
Integer [] replacementKeys = new Integer[nDimFields];
SemiJoinRel semiJoin = multiJoin.getJoinRemovalSemiJoin(dimIdx);
- List<Integer> dimKeys = semiJoin.getRightKeys();
- List<Integer> factKeys = semiJoin.getLeftKeys();
+ ImmutableIntList dimKeys = semiJoin.getRightKeys();
+ ImmutableIntList factKeys = semiJoin.getLeftKeys();
for (int i = 0; i < dimKeys.size(); i++) {
replacementKeys[dimKeys.get(i)] = factKeys.get(i) + adjustment;
}
@@ -1554,7 +1546,7 @@ public class LoptOptimizeJoinRule extends RelOptRule {
LoptJoinTree currJoinTree,
int leftIdx,
int factorToAdd,
- List<Integer> newKeys,
+ ImmutableIntList newKeys,
Integer [] replacementKeys,
List<RexNode> filtersToAdd) {
// create a projection, projecting the fields from the join tree
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b0aff0df/core/src/main/java/org/eigenbase/rel/rules/OptimizeBushyJoinRule.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/rel/rules/OptimizeBushyJoinRule.java b/core/src/main/java/org/eigenbase/rel/rules/OptimizeBushyJoinRule.java
index 297ce9c..1c6c4fa 100644
--- a/core/src/main/java/org/eigenbase/rel/rules/OptimizeBushyJoinRule.java
+++ b/core/src/main/java/org/eigenbase/rel/rules/OptimizeBushyJoinRule.java
@@ -17,12 +17,28 @@
*/
package org.eigenbase.rel.rules;
-import java.util.*;
+import java.io.PrintWriter;
+import java.util.BitSet;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
import org.eigenbase.rel.*;
+import org.eigenbase.rel.metadata.RelMdUtil;
+import org.eigenbase.rel.metadata.RelMetadataQuery;
import org.eigenbase.relopt.*;
import org.eigenbase.rex.*;
+import org.eigenbase.util.Pair;
import org.eigenbase.util.Util;
+import org.eigenbase.util.mapping.Mappings;
+
+import net.hydromatic.optiq.prepare.OptiqPrepareImpl;
+import net.hydromatic.optiq.util.BitSets;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Lists;
/**
* Planner rule that finds an approximately optimal ordering for join operators
@@ -33,25 +49,327 @@ import org.eigenbase.util.Util;
* <p>It is similar to {@link org.eigenbase.rel.rules.LoptOptimizeJoinRule}.
* {@code LoptOptimizeJoinRule} is only capable of producing left-deep joins;
* this rule is capable of producing bushy joins.
+ *
+ * <p>TODO:
+ * <ol>
+ * <li>Join conditions that touch 1 factor.
+ * <li>Join conditions that touch 3 factors.
+ * <li>More than 1 join conditions that touch the same pair of factors,
+ * e.g. {@code t0.c1 = t1.c1 and t1.c2 = t0.c3}
+ * </ol>
*/
public class OptimizeBushyJoinRule extends RelOptRule {
public static final OptimizeBushyJoinRule INSTANCE =
- new OptimizeBushyJoinRule(RelFactories.DEFAULT_JOIN_FACTORY);
+ new OptimizeBushyJoinRule(RelFactories.DEFAULT_JOIN_FACTORY,
+ RelFactories.DEFAULT_PROJECT_FACTORY);
private final RelFactories.JoinFactory joinFactory;
+ private final RelFactories.ProjectFactory projectFactory;
+ private final PrintWriter pw =
+ OptiqPrepareImpl.DEBUG ? new PrintWriter(System.out, true) : null;
/** Creates an OptimizeBushyJoinRule. */
- public OptimizeBushyJoinRule(RelFactories.JoinFactory joinFactory) {
+ public OptimizeBushyJoinRule(RelFactories.JoinFactory joinFactory,
+ RelFactories.ProjectFactory projectFactory) {
super(operand(MultiJoinRel.class, any()));
this.joinFactory = joinFactory;
+ this.projectFactory = projectFactory;
}
@Override public void onMatch(RelOptRuleCall call) {
final MultiJoinRel multiJoinRel = call.rel(0);
+ final RexBuilder rexBuilder = multiJoinRel.getCluster().getRexBuilder();
+
final LoptMultiJoin multiJoin = new LoptMultiJoin(multiJoinRel);
- final RexBuilder rexBuilder = multiJoinRel.getCluster().getRexBuilder();
- Util.discard(multiJoin);
+ final List<Vertex> vertexes = Lists.newArrayList();
+ int x = 0;
+ for (int i = 0; i < multiJoin.getNumJoinFactors(); i++) {
+ final RelNode rel = multiJoin.getJoinFactor(i);
+ double cost = RelMetadataQuery.getRowCount(rel);
+ vertexes.add(new LeafVertex(i, rel, cost, x));
+ x += rel.getRowType().getFieldCount();
+ }
+ assert x == multiJoin.getNumTotalFields();
+
+ final List<LoptMultiJoin.Edge> unusedEdges = Lists.newArrayList();
+ for (RexNode node : multiJoin.getJoinFilters()) {
+ unusedEdges.add(multiJoin.createEdge(node));
+ }
+
+ // Comparator that chooses the best edge. A "good edge" is one that has
+ // a large difference in the number of rows on LHS and RHS.
+ final Comparator<LoptMultiJoin.Edge> edgeComparator =
+ new Comparator<LoptMultiJoin.Edge>() {
+ public int compare(LoptMultiJoin.Edge e0, LoptMultiJoin.Edge e1) {
+ return Double.compare(rowCountDiff(e0), rowCountDiff(e1));
+ }
+
+ private double rowCountDiff(LoptMultiJoin.Edge edge) {
+ assert edge.factors.cardinality() == 2 : edge.factors;
+ final int factor0 = edge.factors.nextSetBit(0);
+ final int factor1 = edge.factors.nextSetBit(factor0 + 1);
+ return Math.abs(vertexes.get(factor0).cost
+ - vertexes.get(factor1).cost);
+ }
+ };
+
+ final List<LoptMultiJoin.Edge> usedEdges = Lists.newArrayList();
+ while (!unusedEdges.isEmpty()) {
+ final int edgeOrdinal = chooseBestEdge(unusedEdges, edgeComparator);
+ if (pw != null) {
+ trace(vertexes, unusedEdges, usedEdges, edgeOrdinal, pw);
+ }
+ final LoptMultiJoin.Edge bestEdge = remove(unusedEdges, edgeOrdinal);
+ usedEdges.add(bestEdge);
+
+ // For now, assume that the edge is between precisely two factors.
+ // 1-factor conditions have probably been pushed down,
+ // and 3-or-more-factor conditions are advanced. (TODO:)
+ // Therefore, for now, the factors that are merged are exactly the factors
+ // on this edge.
+ BitSet merged = bestEdge.factors;
+ assert merged.cardinality() == 2;
+ final int[] factors = BitSets.toArray(merged);
+
+ // Determine which factor is to be on the LHS of the join.
+ final int majorFactor;
+ final int minorFactor;
+ if (vertexes.get(factors[0]).cost <= vertexes.get(factors[1]).cost) {
+ majorFactor = factors[0];
+ minorFactor = factors[1];
+ } else {
+ majorFactor = factors[1];
+ minorFactor = factors[0];
+ }
+ final Vertex majorVertex = vertexes.get(majorFactor);
+ final Vertex minorVertex = vertexes.get(minorFactor);
+
+ // Find the join conditions. All conditions whose factors are now all in
+ // the join can now be used.
+ final BitSet newFactors =
+ BitSets.union(majorVertex.factors, minorVertex.factors);
+ final List<RexNode> conditions = Lists.newArrayList(bestEdge.condition);
+ final Iterator<LoptMultiJoin.Edge> edgeIterator = unusedEdges.iterator();
+ while (edgeIterator.hasNext()) {
+ LoptMultiJoin.Edge edge = edgeIterator.next();
+ if (BitSets.contains(newFactors, edge.factors)) {
+ conditions.add(edge.condition);
+ edgeIterator.remove();
+ usedEdges.add(edge);
+ }
+ }
+
+ final int v = vertexes.size();
+ double cost =
+ majorVertex.cost
+ * minorVertex.cost
+ * RelMdUtil.guessSelectivity(
+ RexUtil.composeConjunction(rexBuilder, conditions, false));
+ newFactors.set(v);
+ final Vertex newVertex =
+ new JoinVertex(v, majorFactor, minorFactor, newFactors,
+ cost, ImmutableList.copyOf(conditions));
+ vertexes.add(newVertex);
+
+ // Re-compute selectivity of edges above the one just chosen.
+ // Suppose that we just chose the edge between "product" (10k rows) and
+ // "product_class" (10 rows).
+ // Both of those vertices are now replaced by a new vertex "P-PC".
+ // This vertex has fewer rows (1k rows) -- a fact that is critical to
+ // decisions made later. (Hence "greedy" algorithm not "simple".)
+ // The adjacent edges are modified.
+ for (int i = 0; i < unusedEdges.size(); i++) {
+ final LoptMultiJoin.Edge edge = unusedEdges.get(i);
+ if (edge.factors.intersects(merged)) {
+ BitSet newEdgeFactors = (BitSet) edge.factors.clone();
+ newEdgeFactors.andNot(newFactors);
+ newEdgeFactors.set(v);
+ assert newEdgeFactors.cardinality() == 2;
+ final LoptMultiJoin.Edge newEdge =
+ new LoptMultiJoin.Edge(edge.condition, newEdgeFactors,
+ edge.columns);
+ unusedEdges.set(i, newEdge);
+ }
+ }
+ }
+
+ // We have a winner!
+ List<Pair<RelNode, Mappings.TargetMapping>> relNodes = Lists.newArrayList();
+ for (Vertex vertex : vertexes) {
+ if (vertex instanceof LeafVertex) {
+ LeafVertex leafVertex = (LeafVertex) vertex;
+ final Mappings.TargetMapping mapping =
+ Mappings.offsetSource(
+ Mappings.createIdentity(
+ leafVertex.rel.getRowType().getFieldCount()),
+ leafVertex.fieldOffset,
+ multiJoin.getNumTotalFields());
+ relNodes.add(Pair.of(leafVertex.rel, mapping));
+ } else {
+ JoinVertex joinVertex = (JoinVertex) vertex;
+ final Pair<RelNode, Mappings.TargetMapping> leftPair =
+ relNodes.get(joinVertex.leftFactor);
+ RelNode left = leftPair.left;
+ final Mappings.TargetMapping leftMapping = leftPair.right;
+ final Pair<RelNode, Mappings.TargetMapping> rightPair =
+ relNodes.get(joinVertex.rightFactor);
+ RelNode right = rightPair.left;
+ final Mappings.TargetMapping rightMapping = rightPair.right;
+ final Mappings.TargetMapping mapping =
+ Mappings.merge(leftMapping,
+ Mappings.offsetTarget(rightMapping,
+ left.getRowType().getFieldCount()));
+ if (pw != null) {
+ pw.println("left: " + leftMapping);
+ pw.println("right: " + rightMapping);
+ pw.println("combined: " + mapping);
+ pw.println();
+ }
+ final RexVisitor<RexNode> shuttle =
+ new RexPermuteInputsShuttle(mapping, left, right);
+ final RexNode condition =
+ RexUtil.composeConjunction(rexBuilder, joinVertex.conditions,
+ false);
+ relNodes.add(
+ Pair.of(
+ joinFactory.createJoin(left, right, condition.accept(shuttle),
+ JoinRelType.INNER, ImmutableSet.<String>of(), false),
+ mapping));
+ }
+ if (pw != null) {
+ pw.println(Util.last(relNodes));
+ }
+ }
+
+ final Pair<RelNode, Mappings.TargetMapping> top = Util.last(relNodes);
+ final RelNode project =
+ RelFactories.createProject(projectFactory, top.left,
+ Mappings.asList(top.right));
+
+ call.transformTo(project);
+ }
+
+ private void trace(List<Vertex> vertexes,
+ List<LoptMultiJoin.Edge> unusedEdges, List<LoptMultiJoin.Edge> usedEdges,
+ int edgeOrdinal, PrintWriter pw) {
+ pw.println("bestEdge: " + edgeOrdinal);
+ pw.println("vertexes:");
+ for (Vertex vertex : vertexes) {
+ pw.println(vertex);
+ }
+ pw.println("unused edges:");
+ for (LoptMultiJoin.Edge edge : unusedEdges) {
+ pw.println(edge);
+ }
+ pw.println("edges:");
+ for (LoptMultiJoin.Edge edge : usedEdges) {
+ pw.println(edge);
+ }
+ pw.println();
+ pw.flush();
+ }
+
+ /** Removes the element of a list at a given ordinal, moving the last element
+ * into its place. This is an efficient means of removing an element from an
+ * array list if you do not mind the order of the list changing. */
+ private static <E> E remove(List<E> list, int ordinal) {
+ final int lastOrdinal = list.size() - 1;
+ final E last = list.remove(lastOrdinal);
+ if (ordinal == lastOrdinal) {
+ return last;
+ }
+ final E e = list.get(ordinal);
+ list.set(ordinal, last);
+ return e;
+ }
+
+ int chooseBestEdge(List<LoptMultiJoin.Edge> edges,
+ Comparator<LoptMultiJoin.Edge> comparator) {
+ return minPos(edges, comparator);
+ }
+
+ /** Returns the index within a list at which compares least according to a
+ * comparator.
+ *
+ * <p>In the case of a tie, returns the earliest such element.</p>
+ *
+ * <p>If the list is empty, returns -1.</p>
+ */
+ static <E> int minPos(List<E> list, Comparator<E> fn) {
+ if (list.isEmpty()) {
+ return -1;
+ }
+ E eBest = list.get(0);
+ int iBest = 0;
+ for (int i = 1; i < list.size(); i++) {
+ E e = list.get(i);
+ if (fn.compare(e, eBest) < 0) {
+ eBest = e;
+ iBest = i;
+ }
+ }
+ return iBest;
+ }
+
+ /** Participant in a join (relation or join). */
+ abstract static class Vertex {
+ final int id;
+
+ protected final BitSet factors;
+ final double cost;
+
+ Vertex(int id, BitSet factors, double cost) {
+ this.id = id;
+ this.factors = factors;
+ this.cost = cost;
+ }
+ }
+
+ /** Relation participating in a join. */
+ static class LeafVertex extends Vertex {
+ private final RelNode rel;
+ final int fieldOffset;
+
+ LeafVertex(int id, RelNode rel, double cost, int fieldOffset) {
+ super(id, BitSets.of(id), cost);
+ this.rel = rel;
+ this.fieldOffset = fieldOffset;
+ }
+
+ @Override public String toString() {
+ return "LeafVertex(id: " + id
+ + ", cost: " + Util.human(cost)
+ + ", factors: " + factors
+ + ", fieldOffset: " + fieldOffset
+ + ")";
+ }
+ }
+
+ /** Participant in a join which is itself a join. */
+ static class JoinVertex extends Vertex {
+ private final int leftFactor;
+ private final int rightFactor;
+ /** Zero or more join conditions. All are in terms of the original input
+ * columns (not in terms of the outputs of left and right input factors). */
+ final ImmutableList<RexNode> conditions;
+
+ JoinVertex(int id, int leftFactor, int rightFactor,
+ BitSet factors, double cost, ImmutableList<RexNode> conditions) {
+ super(id, factors, cost);
+ this.leftFactor = leftFactor;
+ this.rightFactor = rightFactor;
+ this.conditions = Preconditions.checkNotNull(conditions);
+ }
+
+ @Override public String toString() {
+ return "JoinVertex(id: " + id
+ + ", cost: " + Util.human(cost)
+ + ", factors: " + factors
+ + ", leftFactor: " + leftFactor
+ + ", rightFactor: " + rightFactor
+ + ")";
+ }
}
}
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b0aff0df/core/src/main/java/org/eigenbase/rel/rules/SemiJoinRel.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/rel/rules/SemiJoinRel.java b/core/src/main/java/org/eigenbase/rel/rules/SemiJoinRel.java
index 8dfa4fa..e9a9c6d 100644
--- a/core/src/main/java/org/eigenbase/rel/rules/SemiJoinRel.java
+++ b/core/src/main/java/org/eigenbase/rel/rules/SemiJoinRel.java
@@ -109,11 +109,11 @@ public final class SemiJoinRel extends JoinRelBase {
Collections.<RelDataTypeField>emptyList());
}
- public List<Integer> getLeftKeys() {
+ public ImmutableIntList getLeftKeys() {
return leftKeys;
}
- public List<Integer> getRightKeys() {
+ public ImmutableIntList getRightKeys() {
return rightKeys;
}
}
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b0aff0df/core/src/main/java/org/eigenbase/relopt/volcano/RelSubset.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/relopt/volcano/RelSubset.java b/core/src/main/java/org/eigenbase/relopt/volcano/RelSubset.java
index dd83915..add6c4a 100644
--- a/core/src/main/java/org/eigenbase/relopt/volcano/RelSubset.java
+++ b/core/src/main/java/org/eigenbase/relopt/volcano/RelSubset.java
@@ -129,10 +129,10 @@ public class RelSubset extends AbstractRelNode {
}
public double getRows() {
- if (best == null) {
- return Double.POSITIVE_INFINITY;
- } else {
+ if (best != null) {
return RelMetadataQuery.getRowCount(best);
+ } else {
+ return RelMetadataQuery.getRowCount(set.rel);
}
}
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b0aff0df/core/src/main/java/org/eigenbase/sql2rel/SqlToRelConverter.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/sql2rel/SqlToRelConverter.java b/core/src/main/java/org/eigenbase/sql2rel/SqlToRelConverter.java
index cbd52f1..ec8fcf4 100644
--- a/core/src/main/java/org/eigenbase/sql2rel/SqlToRelConverter.java
+++ b/core/src/main/java/org/eigenbase/sql2rel/SqlToRelConverter.java
@@ -571,11 +571,9 @@ public class SqlToRelConverter {
return;
}
- Map<Integer, Integer> squished = new HashMap<Integer, Integer>();
- final List<RelDataTypeField> fields =
- rel.getRowType().getFieldList();
- List<Pair<RexNode, String>> newProjects =
- new ArrayList<Pair<RexNode, String>>();
+ final Map<Integer, Integer> squished = Maps.newHashMap();
+ final List<RelDataTypeField> fields = rel.getRowType().getFieldList();
+ final List<Pair<RexNode, String>> newProjects = Lists.newArrayList();
for (int i = 0; i < fields.size(); i++) {
if (origins.get(i) == i) {
squished.put(i, newProjects.size());
@@ -596,8 +594,7 @@ public class SqlToRelConverter {
// Create the expressions to reverse the mapping.
// Project($0, $1, $0, $2).
- List<Pair<RexNode, String>> undoProjects =
- new ArrayList<Pair<RexNode, String>>();
+ final List<Pair<RexNode, String>> undoProjects = Lists.newArrayList();
for (int i = 0; i < fields.size(); i++) {
final int origin = origins.get(i);
RelDataTypeField field = fields.get(i);
@@ -625,12 +622,11 @@ public class SqlToRelConverter {
// Usual case: all of the expressions in the SELECT clause are
// different.
- List<AggregateCall> aggCalls = Collections.emptyList();
rel =
createAggregate(
bb,
BitSets.range(rel.getRowType().getFieldCount()),
- aggCalls);
+ ImmutableList.<AggregateCall>of());
bb.setRoot(
rel,
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b0aff0df/core/src/main/java/org/eigenbase/util/ImmutableIntList.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/util/ImmutableIntList.java b/core/src/main/java/org/eigenbase/util/ImmutableIntList.java
index 18dd530..aa1a35e 100644
--- a/core/src/main/java/org/eigenbase/util/ImmutableIntList.java
+++ b/core/src/main/java/org/eigenbase/util/ImmutableIntList.java
@@ -144,13 +144,21 @@ public class ImmutableIntList extends FlatLists.AbstractFlatList<Integer> {
return ints[index];
}
+ public int getInt(int index) {
+ return ints[index];
+ }
+
public int indexOf(Object o) {
if (o instanceof Integer) {
- final int seek = (Integer) o;
- for (int i = 0; i < ints.length; i++) {
- if (ints[i] == seek) {
- return i;
- }
+ return indexOf((int) (Integer) o);
+ }
+ return -1;
+ }
+
+ public int indexOf(int seek) {
+ for (int i = 0; i < ints.length; i++) {
+ if (ints[i] == seek) {
+ return i;
}
}
return -1;
@@ -158,11 +166,15 @@ public class ImmutableIntList extends FlatLists.AbstractFlatList<Integer> {
public int lastIndexOf(Object o) {
if (o instanceof Integer) {
- final int seek = (Integer) o;
- for (int i = ints.length - 1; i >= 0; --i) {
- if (ints[i] == seek) {
- return i;
- }
+ return lastIndexOf((int) (Integer) o);
+ }
+ return -1;
+ }
+
+ public int lastIndexOf(int seek) {
+ for (int i = ints.length - 1; i >= 0; --i) {
+ if (ints[i] == seek) {
+ return i;
}
}
return -1;
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b0aff0df/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 fd85b78..9672c0c 100644
--- a/core/src/main/java/org/eigenbase/util/Util.java
+++ b/core/src/main/java/org/eigenbase/util/Util.java
@@ -2056,6 +2056,53 @@ public class Util {
&& list0.subList(0, list1.size()).equals(list1);
}
+ /** Converts a number into human-readable form, with 3 digits and a "K", "M"
+ * or "G" multiplier for thousands, millions or billions.
+ *
+ * <p>Examples: -2, 0, 1, 999, 1.00K, 1.99K, 3.45M, 4.56B.</p>
+ */
+ public static String human(double d) {
+ if (d == 0d) {
+ return "0";
+ }
+ if (d < 0d) {
+ return "-" + human(-d);
+ }
+ final int digitCount = (int) Math.floor(Math.log10(d));
+ switch (digitCount) {
+ case 0:
+ case 1:
+ case 2:
+ return Integer.toString((int) d);
+ case 3:
+ case 4:
+ case 5:
+ return digits3(Math.round(d / 10D), digitCount % 3) + "K";
+ case 6:
+ case 7:
+ case 8:
+ return digits3(Math.round(d / 10000D), digitCount % 3) + "M";
+ case 9:
+ case 10:
+ case 11:
+ return digits3(Math.round(d / 10000000D), digitCount % 3) + "G";
+ default:
+ return Double.toString(d);
+ }
+ }
+
+ private static String digits3(long x, int z) {
+ final String s = Long.toString(x);
+ switch (z) {
+ case 0:
+ return s.charAt(0) + "." + s.substring(1, 3);
+ case 1:
+ return s.substring(0, 2) + "." + s.substring(2, 3);
+ default:
+ return s.substring(0, 3);
+ }
+ }
+
//~ Inner Classes ----------------------------------------------------------
/**
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b0aff0df/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 a727231..3e9a657 100644
--- a/core/src/main/java/org/eigenbase/util/mapping/Mappings.java
+++ b/core/src/main/java/org/eigenbase/util/mapping/Mappings.java
@@ -396,6 +396,13 @@ public abstract class Mappings {
/**
* Creates a mapping by appending two mappings.
+ *
+ * <p>Sources and targets of the second mapping are shifted to the right.</p>
+ *
+ * <p>For example, <pre>append({0:0, 1:1}, {0:0, 1:1, 2:2})</pre> yields
+ * <pre>{0:0, 1:1, 2:2, 3:3, 4:4}</pre>.
+ *
+ * @see #merge
*/
public static TargetMapping append(
TargetMapping mapping0,
@@ -423,18 +430,27 @@ public abstract class Mappings {
/**
* Creates a mapping by merging two mappings. There must be no clashes.
+ *
+ * <p>Unlike {@link #append}, sources and targets are not shifted.
+ *
+ * <p>For example, <code>merge({0:0, 1:1}, {2:2, 3:3, 4:4})</code> yields
+ * <code>{0:0, 1:1, 2:2, 3:3, 4:4}</code>.
+ * <code>merge({0:0, 1:1}, {1:2, 2:3})</code> throws, because there are
+ * two entries with source=1.
*/
public static TargetMapping merge(
TargetMapping mapping0,
TargetMapping mapping1) {
final int s0 = mapping0.getSourceCount();
final int s1 = mapping1.getSourceCount();
- assert s0 == s1;
+ final int sMin = Math.min(s0, s1);
+ final int sMax = Math.max(s0, s1);
final int t0 = mapping0.getTargetCount();
final int t1 = mapping1.getTargetCount();
+ final int tMax = Math.max(t0, t1);
final TargetMapping mapping =
- create(MappingType.INVERSE_SURJECTION, s0, Math.max(t0, t1));
- for (int s = 0; s < s0; s++) {
+ create(MappingType.INVERSE_SURJECTION, sMax, tMax);
+ for (int s = 0; s < sMin; s++) {
int t = mapping0.getTargetOpt(s);
if (t >= 0) {
mapping.set(s, t);
@@ -446,11 +462,36 @@ public abstract class Mappings {
}
}
}
+ for (int s = sMin; s < sMax; s++) {
+ int t = s < s0 ? mapping0.getTargetOpt(s) : -1;
+ if (t >= 0) {
+ mapping.set(s, t);
+ assert mapping1.getTargetOpt(s) < 0;
+ } else {
+ t = s < s1 ? mapping1.getTargetOpt(s) : -1;
+ if (t >= 0) {
+ mapping.set(s, t);
+ }
+ }
+ }
return mapping;
}
/**
* Returns a mapping that shifts a given mapping's source by a given
+ * offset, incrementing the number of sources by the minimum possible.
+ *
+ * @param mapping Input mapping
+ * @param offset Offset to be applied to each source
+ * @return Shifted mapping
+ */
+ public static TargetMapping offsetSource(
+ final TargetMapping mapping, final int offset) {
+ return offsetSource(mapping, offset, mapping.getSourceCount() + offset);
+ }
+
+ /**
+ * Returns a mapping that shifts a given mapping's source by a given
* offset.
*
* <p>For example, given {@code mapping} with sourceCount=2, targetCount=8,
@@ -483,6 +524,50 @@ public abstract class Mappings {
}
/**
+ * Returns a mapping that shifts a given mapping's target by a given
+ * offset, incrementing the number of targets by the minimum possible.
+ *
+ * @param mapping Input mapping
+ * @param offset Offset to be applied to each target
+ * @return Shifted mapping
+ */
+ public static TargetMapping offsetTarget(
+ final TargetMapping mapping, final int offset) {
+ return offsetTarget(mapping, offset, mapping.getTargetCount() + offset);
+ }
+
+ /**
+ * Returns a mapping that shifts a given mapping's target by a given
+ * offset.
+ *
+ * <p>For example, given {@code mapping} with sourceCount=2, targetCount=8,
+ * and (source, target) entries {[0: 5], [1: 7]}, offsetTarget(mapping, 3)
+ * returns a mapping with sourceCount=2, targetCount=11,
+ * and (source, target) entries {[0: 8], [1: 10]}.
+ *
+ * @param mapping Input mapping
+ * @param offset Offset to be applied to each target
+ * @param targetCount New target count; must be at least {@code mapping}'s
+ * target count plus {@code offset}
+ * @return Shifted mapping
+ */
+ public static TargetMapping offsetTarget(
+ final TargetMapping mapping, final int offset, final int targetCount) {
+ if (targetCount < mapping.getTargetCount() + offset) {
+ throw new IllegalArgumentException("new target count too low");
+ }
+ return target(
+ new Function1<Integer, Integer>() {
+ public Integer apply(Integer source) {
+ int target = mapping.getTargetOpt(source);
+ return target < 0 ? null : target + offset;
+ }
+ },
+ mapping.getSourceCount(),
+ targetCount);
+ }
+
+ /**
* Returns a mapping that shifts a given mapping's source and target by a
* given offset.
*
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b0aff0df/core/src/test/java/net/hydromatic/optiq/tools/PlannerTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/net/hydromatic/optiq/tools/PlannerTest.java b/core/src/test/java/net/hydromatic/optiq/tools/PlannerTest.java
index 77e734e..d544858 100644
--- a/core/src/test/java/net/hydromatic/optiq/tools/PlannerTest.java
+++ b/core/src/test/java/net/hydromatic/optiq/tools/PlannerTest.java
@@ -22,7 +22,6 @@ import net.hydromatic.optiq.config.Lex;
import net.hydromatic.optiq.impl.java.ReflectiveSchema;
import net.hydromatic.optiq.impl.jdbc.*;
import net.hydromatic.optiq.impl.jdbc.JdbcRules.JdbcProjectRel;
-import net.hydromatic.optiq.prepare.OptiqPrepareImpl;
import net.hydromatic.optiq.rules.java.EnumerableConvention;
import net.hydromatic.optiq.rules.java.JavaRules;
import net.hydromatic.optiq.rules.java.JavaRules.EnumerableProjectRel;
@@ -45,7 +44,6 @@ import org.eigenbase.sql.validate.SqlValidatorScope;
import org.eigenbase.util.Util;
import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableSet;
import org.junit.Test;
@@ -444,7 +442,7 @@ public class PlannerTest {
.append(i - 1).append(".\"deptno\"");
}
Planner planner =
- getPlanner(null, Programs.heuristicJoinOrder(RULE_SET, false));
+ getPlanner(null, Programs.heuristicJoinOrder(Programs.RULE_SET, false));
SqlNode parse = planner.parse(buf.toString());
SqlNode validate = planner.validate(parse);
@@ -456,23 +454,81 @@ public class PlannerTest {
"EnumerableJoinRel(condition=[=($3, $0)], joinType=[inner])"));
}
- /** Plans a 4-table join query on the FoodMart schema. The ideal plan is not
+ /** Plans a 3-table join query on the FoodMart schema. The ideal plan is not
* bushy, but nevertheless exercises the bushy-join heuristic optimizer. */
@Test public void testAlmostBushy() throws Exception {
- final String sql = "select *\n"
+ checkBushy("select *\n"
+ "from \"sales_fact_1997\" as s\n"
+ " join \"customer\" as c using (\"customer_id\")\n"
+ " join \"product\" as p using (\"product_id\")\n"
+ "where c.\"city\" = 'San Francisco'\n"
- + "and p.\"brand_name\" = 'Washington'";
- final String expected = ""
- + "EnumerableJoinRel(condition=[=($0, $38)], joinType=[inner])\n"
- + " EnumerableJoinRel(condition=[=($2, $8)], joinType=[inner])\n"
- + " EnumerableTableAccessRel(table=[[foodmart2, sales_fact_1997]])\n"
- + " EnumerableFilterRel(condition=[=($9, 'San Francisco')])\n"
- + " EnumerableTableAccessRel(table=[[foodmart2, customer]])\n"
- + " EnumerableFilterRel(condition=[=($2, 'Washington')])\n"
- + " EnumerableTableAccessRel(table=[[foodmart2, product]])\n";
+ + "and p.\"brand_name\" = 'Washington'",
+ "EnumerableProjectRel(product_id=[$0], time_id=[$1], customer_id=[$2], promotion_id=[$3], store_id=[$4], store_sales=[$5], store_cost=[$6], unit_sales=[$7], customer_id0=[$8], account_num=[$9], lname=[$10], fname=[$11], mi=[$12], address1=[$13], address2=[$14], address3=[$15], address4=[$16], city=[$17], state_province=[$18], postal_code=[$19], country=[$20], customer_region_id=[$21], phone1=[$22], phone2=[$23], birthdate=[$24], marital_status=[$25], yearly_income=[$26], gender=[$27], total_children=[$28], num_children_at_home=[$29], education=[$30], date_accnt_opened=[$31], member_card=[$32], occupation=[$33], houseowner=[$34], num_cars_owned=[$35], fullname=[$36], product_class_id=[$37], product_id0=[$38], brand_name=[$39], product_name=[$40], SKU=[$41], SRP=[$42], gross_weight=[$43], net_weight=[$44], recyclable_package=[$45], low_fat=[$46], units_per_case=[$47], cases_per_pallet=[$48], shelf_width=[$49], shelf_height=[$50], shelf_depth=[$51])\n"
+ + " EnumerableProjectRel($f0=[$44], $f1=[$45], $f2=[$46], $f3=[$47], $f4=[$48], $f5=[$49], $f6=[$50], $f7=[$51], $f8=[$15], $f9=[$16], $f10=[$17], $f11=[$18], $f12=[$19], $f13=[$20], $f14=[$21], $f15=[$22], $f16=[$23], $f17=[$24], $f18=[$25], $f19=[$26], $f20=[$27], $f21=[$28], $f22=[$29], $f23=[$30], $f24=[$31], $f25=[$32], $f26=[$33], $f27=[$34], $f28=[$35], $f29=[$36], $f30=[$37], $f31=[$38], $f32=[$39], $f33=[$40], $f34=[$41], $f35=[$42], $f36=[$43], $f37=[$0], $f38=[$1], $f39=[$2], $f40=[$3], $f41=[$4], $f42=[$5], $f43=[$6], $f44=[$7], $f45=[$8], $f46=[$9], $f47=[$10], $f48=[$11], $f49=[$12], $f50=[$13], $f51=[$14])\n"
+ + " EnumerableJoinRel(condition=[=($44, $1)], joinType=[inner])\n"
+ + " EnumerableFilterRel(condition=[=($2, 'Washington')])\n"
+ + " EnumerableTableAccessRel(table=[[foodmart2, product]])\n"
+ + " EnumerableJoinRel(condition=[=($31, $0)], joinType=[inner])\n"
+ + " EnumerableFilterRel(condition=[=($9, 'San Francisco')])\n"
+ + " EnumerableTableAccessRel(table=[[foodmart2, customer]])\n"
+ + " EnumerableTableAccessRel(table=[[foodmart2, sales_fact_1997]])\n");
+ }
+
+ /** Plans a 4-table join query on the FoodMart schema.
+ *
+ * <p>The ideal plan is bushy:
+ * customer x (product_class x product x sales)
+ * which would be written
+ * (customer x ((product_class x product) x sales))
+ * if you don't assume 'x' is left-associative. */
+ @Test public void testBushy() throws Exception {
+ checkBushy("select *\n"
+ + "from \"sales_fact_1997\" as s\n"
+ + " join \"customer\" as c using (\"customer_id\")\n"
+ + " join \"product\" as p using (\"product_id\")\n"
+ + " join \"product_class\" as pc using (\"product_class_id\")\n"
+ + "where c.\"city\" = 'San Francisco'\n"
+ + "and p.\"brand_name\" = 'Washington'",
+ "EnumerableProjectRel(product_id=[$0], time_id=[$1], customer_id=[$2], promotion_id=[$3], store_id=[$4], store_sales=[$5], store_cost=[$6], unit_sales=[$7], customer_id0=[$8], account_num=[$9], lname=[$10], fname=[$11], mi=[$12], address1=[$13], address2=[$14], address3=[$15], address4=[$16], city=[$17], state_province=[$18], postal_code=[$19], country=[$20], customer_region_id=[$21], phone1=[$22], phone2=[$23], birthdate=[$24], marital_status=[$25], yearly_income=[$26], gender=[$27], total_children=[$28], num_children_at_home=[$29], education=[$30], date_accnt_opened=[$31], member_card=[$32], occupation=[$33], houseowner=[$34], num_cars_owned=[$35], fullname=[$36], product_class_id=[$37], product_id0=[$38], brand_name=[$39], product_name=[$40], SKU=[$41], SRP=[$42], gross_weight=[$43], net_weight=[$44], recyclable_package=[$45], low_fat=[$46], units_per_case=[$47], cases_per_pallet=[$48], shelf_width=[$49], shelf_height=[$50], shelf_depth=[$51], product_class_id0=[$52], pro
duct_subcategory=[$53], product_category=[$54], product_department=[$55], product_family=[$56])\n"
+ + " EnumerableProjectRel($f0=[$49], $f1=[$50], $f2=[$51], $f3=[$52], $f4=[$53], $f5=[$54], $f6=[$55], $f7=[$56], $f8=[$0], $f9=[$1], $f10=[$2], $f11=[$3], $f12=[$4], $f13=[$5], $f14=[$6], $f15=[$7], $f16=[$8], $f17=[$9], $f18=[$10], $f19=[$11], $f20=[$12], $f21=[$13], $f22=[$14], $f23=[$15], $f24=[$16], $f25=[$17], $f26=[$18], $f27=[$19], $f28=[$20], $f29=[$21], $f30=[$22], $f31=[$23], $f32=[$24], $f33=[$25], $f34=[$26], $f35=[$27], $f36=[$28], $f37=[$34], $f38=[$35], $f39=[$36], $f40=[$37], $f41=[$38], $f42=[$39], $f43=[$40], $f44=[$41], $f45=[$42], $f46=[$43], $f47=[$44], $f48=[$45], $f49=[$46], $f50=[$47], $f51=[$48], $f52=[$29], $f53=[$30], $f54=[$31], $f55=[$32], $f56=[$33])\n"
+ + " EnumerableJoinRel(condition=[=($51, $0)], joinType=[inner])\n"
+ + " EnumerableFilterRel(condition=[=($9, 'San Francisco')])\n"
+ + " EnumerableTableAccessRel(table=[[foodmart2, customer]])\n"
+ + " EnumerableJoinRel(condition=[=($20, $6)], joinType=[inner])\n"
+ + " EnumerableJoinRel(condition=[=($5, $0)], joinType=[inner])\n"
+ + " EnumerableTableAccessRel(table=[[foodmart2, product_class]])\n"
+ + " EnumerableFilterRel(condition=[=($2, 'Washington')])\n"
+ + " EnumerableTableAccessRel(table=[[foodmart2, product]])\n"
+ + " EnumerableTableAccessRel(table=[[foodmart2, sales_fact_1997]])\n");
+ }
+
+ /** Plans a 5-table join query on the FoodMart schema. The ideal plan is
+ * bushy: store x (customer x (product_class x product x sales)). */
+ @Test public void testBushy5() throws Exception {
+ checkBushy("select *\n"
+ + "from \"sales_fact_1997\" as s\n"
+ + " join \"customer\" as c using (\"customer_id\")\n"
+ + " join \"product\" as p using (\"product_id\")\n"
+ + " join \"product_class\" as pc using (\"product_class_id\")\n"
+ + " join \"store\" as st using (\"store_id\")\n"
+ + "where c.\"city\" = 'San Francisco'\n",
+ "EnumerableProjectRel(product_id=[$0], time_id=[$1], customer_id=[$2], promotion_id=[$3], store_id=[$4], store_sales=[$5], store_cost=[$6], unit_sales=[$7], customer_id0=[$8], account_num=[$9], lname=[$10], fname=[$11], mi=[$12], address1=[$13], address2=[$14], address3=[$15], address4=[$16], city=[$17], state_province=[$18], postal_code=[$19], country=[$20], customer_region_id=[$21], phone1=[$22], phone2=[$23], birthdate=[$24], marital_status=[$25], yearly_income=[$26], gender=[$27], total_children=[$28], num_children_at_home=[$29], education=[$30], date_accnt_opened=[$31], member_card=[$32], occupation=[$33], houseowner=[$34], num_cars_owned=[$35], fullname=[$36], product_class_id=[$37], product_id0=[$38], brand_name=[$39], product_name=[$40], SKU=[$41], SRP=[$42], gross_weight=[$43], net_weight=[$44], recyclable_package=[$45], low_fat=[$46], units_per_case=[$47], cases_per_pallet=[$48], shelf_width=[$49], shelf_height=[$50], shelf_depth=[$51], product_class_id0=[$52], pro
duct_subcategory=[$53], product_category=[$54], product_department=[$55], product_family=[$56], store_id0=[$57], store_type=[$58], region_id=[$59], store_name=[$60], store_number=[$61], store_street_address=[$62], store_city=[$63], store_state=[$64], store_postal_code=[$65], store_country=[$66], store_manager=[$67], store_phone=[$68], store_fax=[$69], first_opened_date=[$70], last_remodel_date=[$71], store_sqft=[$72], grocery_sqft=[$73], frozen_sqft=[$74], meat_sqft=[$75], coffee_bar=[$76], video_store=[$77], salad_bar=[$78], prepared_food=[$79], florist=[$80])\n"
+ + " EnumerableProjectRel($f0=[$73], $f1=[$74], $f2=[$75], $f3=[$76], $f4=[$77], $f5=[$78], $f6=[$79], $f7=[$80], $f8=[$24], $f9=[$25], $f10=[$26], $f11=[$27], $f12=[$28], $f13=[$29], $f14=[$30], $f15=[$31], $f16=[$32], $f17=[$33], $f18=[$34], $f19=[$35], $f20=[$36], $f21=[$37], $f22=[$38], $f23=[$39], $f24=[$40], $f25=[$41], $f26=[$42], $f27=[$43], $f28=[$44], $f29=[$45], $f30=[$46], $f31=[$47], $f32=[$48], $f33=[$49], $f34=[$50], $f35=[$51], $f36=[$52], $f37=[$58], $f38=[$59], $f39=[$60], $f40=[$61], $f41=[$62], $f42=[$63], $f43=[$64], $f44=[$65], $f45=[$66], $f46=[$67], $f47=[$68], $f48=[$69], $f49=[$70], $f50=[$71], $f51=[$72], $f52=[$53], $f53=[$54], $f54=[$55], $f55=[$56], $f56=[$57], $f57=[$0], $f58=[$1], $f59=[$2], $f60=[$3], $f61=[$4], $f62=[$5], $f63=[$6], $f64=[$7], $f65=[$8], $f66=[$9], $f67=[$10], $f68=[$11], $f69=[$12], $f70=[$13], $f71=[$14], $f72=[$15], $f73=[$16], $f74=[$17], $f75=[$18], $f76=[$19], $f77=[$20], $f78=[$21], $f79=[$22], $f80=[$23])\n"
+ + " EnumerableJoinRel(condition=[=($77, $0)], joinType=[inner])\n"
+ + " EnumerableTableAccessRel(table=[[foodmart2, store]])\n"
+ + " EnumerableJoinRel(condition=[=($51, $0)], joinType=[inner])\n"
+ + " EnumerableFilterRel(condition=[=($9, 'San Francisco')])\n"
+ + " EnumerableTableAccessRel(table=[[foodmart2, customer]])\n"
+ + " EnumerableJoinRel(condition=[=($20, $6)], joinType=[inner])\n"
+ + " EnumerableJoinRel(condition=[=($5, $0)], joinType=[inner])\n"
+ + " EnumerableTableAccessRel(table=[[foodmart2, product_class]])\n"
+ + " EnumerableTableAccessRel(table=[[foodmart2, product]])\n"
+ + " EnumerableTableAccessRel(table=[[foodmart2, sales_fact_1997]])\n");
+ }
+
+ /** Checks that a query returns a particular plan, using a planner with
+ * OptimizeBushyJoinRule enabled. */
+ private void checkBushy(String sql, String expected) throws Exception {
final SchemaPlus rootSchema = Frameworks.createRootSchema(true);
final FrameworkConfig config = Frameworks.newConfigBuilder()
.lex(Lex.ORACLE)
@@ -480,7 +536,7 @@ public class PlannerTest {
OptiqAssert.addSchema(rootSchema,
OptiqAssert.SchemaSpec.CLONE_FOODMART))
.traitDefs((List<RelTraitDef>) null)
- .programs(Programs.heuristicJoinOrder(RULE_SET, true))
+ .programs(Programs.heuristicJoinOrder(Programs.RULE_SET, true))
.build();
Planner planner = Frameworks.getPlanner(config);
SqlNode parse = planner.parse(sql);
@@ -565,35 +621,6 @@ public class PlannerTest {
}
}
- private static final ImmutableSet<RelOptRule> RULE_SET =
- ImmutableSet.of(
- JavaRules.ENUMERABLE_JOIN_RULE,
- JavaRules.ENUMERABLE_PROJECT_RULE,
- JavaRules.ENUMERABLE_FILTER_RULE,
- JavaRules.ENUMERABLE_AGGREGATE_RULE,
- JavaRules.ENUMERABLE_SORT_RULE,
- JavaRules.ENUMERABLE_LIMIT_RULE,
- JavaRules.ENUMERABLE_UNION_RULE,
- JavaRules.ENUMERABLE_INTERSECT_RULE,
- JavaRules.ENUMERABLE_MINUS_RULE,
- JavaRules.ENUMERABLE_TABLE_MODIFICATION_RULE,
- JavaRules.ENUMERABLE_VALUES_RULE,
- JavaRules.ENUMERABLE_WINDOW_RULE,
- JavaRules.ENUMERABLE_ONE_ROW_RULE,
- JavaRules.ENUMERABLE_EMPTY_RULE,
- TableAccessRule.INSTANCE,
- OptiqPrepareImpl.COMMUTE
- ? CommutativeJoinRule.INSTANCE
- : MergeProjectRule.INSTANCE,
- PushFilterPastProjectRule.INSTANCE,
- PushFilterPastJoinRule.FILTER_ON_JOIN,
- RemoveDistinctAggregateRule.INSTANCE,
- ReduceAggregatesRule.INSTANCE,
- SwapJoinRule.INSTANCE,
- PushJoinThroughJoinRule.RIGHT,
- PushJoinThroughJoinRule.LEFT,
- PushSortPastProjectRule.INSTANCE);
-
/**
* Test to determine whether de-correlation correctly removes CorrelatorRel.
*/
@@ -621,11 +648,12 @@ public class PlannerTest {
Frameworks.createRootSchema(true).add("tpch",
new ReflectiveSchema(new TpchSchema()));
- Planner p = Frameworks.getPlanner(Frameworks.newConfigBuilder() //
- .lex(Lex.MYSQL) //
- .defaultSchema(schema) //
- .programs(Programs.ofRules(RULE_SET)) //
- .build());
+ final FrameworkConfig config = Frameworks.newConfigBuilder()
+ .lex(Lex.MYSQL)
+ .defaultSchema(schema)
+ .programs(Programs.ofRules(Programs.RULE_SET))
+ .build();
+ Planner p = Frameworks.getPlanner(config);
SqlNode n = p.parse(tpchTestQuery);
n = p.validate(n);
RelNode r = p.convert(n);
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b0aff0df/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 8df1a1f..c621791 100644
--- a/core/src/test/java/org/eigenbase/util/UtilTest.java
+++ b/core/src/test/java/org/eigenbase/util/UtilTest.java
@@ -33,6 +33,7 @@ import net.hydromatic.linq4j.function.Function1;
import net.hydromatic.optiq.runtime.FlatLists;
import net.hydromatic.optiq.runtime.Spaces;
+import net.hydromatic.optiq.util.BitSets;
import net.hydromatic.optiq.util.CompositeMap;
import com.google.common.collect.ImmutableList;
@@ -848,6 +849,7 @@ public class UtilTest {
assertEquals(0, list.size());
assertEquals(list, Collections.<Integer>emptyList());
assertThat(list.toString(), equalTo("[]"));
+ assertThat(BitSets.of(list), equalTo(new BitSet()));
list = ImmutableIntList.of(1, 3, 5);
assertEquals(3, list.size());
@@ -1260,6 +1262,47 @@ public class UtilTest {
// ok
}
}
+
+ @Test public void testHuman() {
+ assertThat(Util.human(0D), equalTo("0"));
+ assertThat(Util.human(1D), equalTo("1"));
+ assertThat(Util.human(19D), equalTo("19"));
+ assertThat(Util.human(198D), equalTo("198"));
+ assertThat(Util.human(1000D), equalTo("1.00K"));
+ assertThat(Util.human(1002D), equalTo("1.00K"));
+ assertThat(Util.human(1009D), equalTo("1.01K"));
+ assertThat(Util.human(1234D), equalTo("1.23K"));
+ assertThat(Util.human(1987D), equalTo("1.99K"));
+ assertThat(Util.human(1999D), equalTo("2.00K"));
+ assertThat(Util.human(86837.2D), equalTo("86.8K"));
+ assertThat(Util.human(868372.8D), equalTo("868K"));
+ assertThat(Util.human(1009000D), equalTo("1.01M"));
+ assertThat(Util.human(1999999D), equalTo("2.00M"));
+ assertThat(Util.human(1009000000D), equalTo("1.01G"));
+ assertThat(Util.human(1999999000D), equalTo("2.00G"));
+
+ assertThat(Util.human(-1D), equalTo("-1"));
+ assertThat(Util.human(-19D), equalTo("-19"));
+ assertThat(Util.human(-198D), equalTo("-198"));
+ assertThat(Util.human(-1999999000D), equalTo("-2.00G"));
+
+ // not ideal - should use m (milli) and u (micro)
+ assertThat(Util.human(0.18D), equalTo("0.18"));
+ assertThat(Util.human(0.018D), equalTo("0.018"));
+ assertThat(Util.human(0.0018D), equalTo("0.0018"));
+ assertThat(Util.human(0.00018D), equalTo("1.8E-4"));
+ assertThat(Util.human(0.000018D), equalTo("1.8E-5"));
+ assertThat(Util.human(0.0000018D), equalTo("1.8E-6"));
+
+ // bad - should round to 3 digits
+ assertThat(Util.human(0.181111D), equalTo("0.181111"));
+ assertThat(Util.human(0.0181111D), equalTo("0.0181111"));
+ assertThat(Util.human(0.00181111D), equalTo("0.00181111"));
+ assertThat(Util.human(0.000181111D), equalTo("1.81111E-4"));
+ assertThat(Util.human(0.0000181111D), equalTo("1.81111E-5"));
+ assertThat(Util.human(0.00000181111D), equalTo("1.81111E-6"));
+
+ }
}
// End UtilTest.java
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b0aff0df/plus/src/main/java/net/hydromatic/optiq/impl/tpcds/TpcdsSchema.java
----------------------------------------------------------------------
diff --git a/plus/src/main/java/net/hydromatic/optiq/impl/tpcds/TpcdsSchema.java b/plus/src/main/java/net/hydromatic/optiq/impl/tpcds/TpcdsSchema.java
index ec3d0f7..ccfb7d3 100644
--- a/plus/src/main/java/net/hydromatic/optiq/impl/tpcds/TpcdsSchema.java
+++ b/plus/src/main/java/net/hydromatic/optiq/impl/tpcds/TpcdsSchema.java
@@ -23,6 +23,8 @@ import net.hydromatic.linq4j.QueryProvider;
import net.hydromatic.linq4j.Queryable;
import net.hydromatic.optiq.SchemaPlus;
+import net.hydromatic.optiq.Statistic;
+import net.hydromatic.optiq.Statistics;
import net.hydromatic.optiq.Table;
import net.hydromatic.optiq.impl.AbstractSchema;
import net.hydromatic.optiq.impl.AbstractTableQueryable;
@@ -30,10 +32,13 @@ import net.hydromatic.optiq.impl.java.AbstractQueryableTable;
import org.eigenbase.reltype.RelDataType;
import org.eigenbase.reltype.RelDataTypeFactory;
+import org.eigenbase.util.Bug;
import com.google.common.collect.ImmutableMap;
import java.sql.Date;
+import java.util.BitSet;
+import java.util.Collections;
import java.util.List;
import java.util.Map;
@@ -41,7 +46,7 @@ import net.hydromatic.tpcds.TpcdsColumn;
import net.hydromatic.tpcds.TpcdsEntity;
import net.hydromatic.tpcds.TpcdsTable;
-/** Schema that provides TPC-H tables, populated according to a
+/** Schema that provides TPC-DS tables, populated according to a
* particular scale factor. */
public class TpcdsSchema extends AbstractSchema {
private final double scaleFactor;
@@ -49,6 +54,34 @@ public class TpcdsSchema extends AbstractSchema {
private final int partCount;
private final ImmutableMap<String, Table> tableMap;
+ // From TPC-DS spec, table 3-2 "Database Row Counts", for 1G sizing.
+ private static final ImmutableMap<String, Integer> TABLE_ROW_COUNTS =
+ ImmutableMap.<String, Integer>builder()
+ .put("call_center", 8)
+ .put("catalog_page", 11718)
+ .put("catalog_returns", 144067)
+ .put("catalog_sales", 1441548)
+ .put("customer", 50000)
+ .put("demographics", 1920800)
+ .put("date_dim", 73049)
+ .put("household_demographics", 7200)
+ .put("income_band", 20)
+ .put("inventory", 11745000)
+ .put("item", 18000)
+ .put("promotions", 300)
+ .put("reason", 35)
+ .put("ship_mode", 20)
+ .put("store", 12)
+ .put("store_returns", 287514)
+ .put("store_sales", 2880404)
+ .put("time_dim", 86400)
+ .put("warehouse", 5)
+ .put("web_page", 60)
+ .put("web_returns", 71763)
+ .put("web_sales", 719384)
+ .put("web_site", 1)
+ .build();
+
public TpcdsSchema(double scaleFactor, int part, int partCount) {
this.scaleFactor = scaleFactor;
this.part = part;
@@ -56,6 +89,7 @@ public class TpcdsSchema extends AbstractSchema {
final ImmutableMap.Builder<String, Table> builder = ImmutableMap.builder();
for (TpcdsTable<?> tpcdsTable : TpcdsTable.getTables()) {
+ //noinspection unchecked
builder.put(tpcdsTable.getTableName().toUpperCase(),
new TpcdsQueryableTable(tpcdsTable));
}
@@ -77,6 +111,12 @@ public class TpcdsSchema extends AbstractSchema {
this.tpcdsTable = tpcdsTable;
}
+ @Override public Statistic getStatistic() {
+ Bug.upgrade("add row count estimate to TpcdsTable, and use it");
+ double rowCount = TABLE_ROW_COUNTS.get(tpcdsTable.name);
+ return Statistics.of(rowCount, Collections.<BitSet>emptyList());
+ }
+
public <T> Queryable<T> asQueryable(final QueryProvider queryProvider,
final SchemaPlus schema, final String tableName) {
//noinspection unchecked