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/19 00:44:22 UTC
git commit: [OPTIQ-346] Add commutative join rule
Repository: incubator-optiq
Updated Branches:
refs/heads/master 4b9fba42e -> b059c093d
[OPTIQ-346] Add commutative join rule
CommutativeJoinRule is currently disabled. Specifying "-Doptiq.enable.join.commute=true" enables CommutativeJoinRule and disables MergeProjectRule; the two together caused a planning-time explosion.
Tweak cost of joins, so that the left input contributes more to the cost than the right input (L log L vs. R). This reflects the cost of populating a hash table with the LHS. All else being equal, a join is more efficient if the smaller input is placed on the left.
Remove EnumerableJoinRel.getRows(), which was computing join row count assuming a many-to-one join. Fair enough, but it did not recognize that joining to a filtered dimension table reduces the row count of the fact-dimension join.
Fix display of a plan's provenance when one of the rule operands was a RelSubset.
Enable writing tests that provide arguments to EXPLAIN PLAN.
Project: http://git-wip-us.apache.org/repos/asf/incubator-optiq/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-optiq/commit/b059c093
Tree: http://git-wip-us.apache.org/repos/asf/incubator-optiq/tree/b059c093
Diff: http://git-wip-us.apache.org/repos/asf/incubator-optiq/diff/b059c093
Branch: refs/heads/master
Commit: b059c093d99ef18e74b0d4f873ef3c74b1e18517
Parents: 4b9fba4
Author: Julian Hyde <jh...@apache.org>
Authored: Fri Jul 18 15:25:41 2014 -0700
Committer: Julian Hyde <jh...@apache.org>
Committed: Fri Jul 18 15:25:41 2014 -0700
----------------------------------------------------------------------
.../optiq/prepare/OptiqPrepareImpl.java | 8 +-
.../hydromatic/optiq/rules/java/JavaRules.java | 34 ++--
.../net/hydromatic/optiq/tools/Programs.java | 1 +
.../rel/rules/CommutativeJoinRule.java | 155 +++++++++++++++++++
.../rel/rules/LoptOptimizeJoinRule.java | 3 +-
.../relopt/volcano/VolcanoPlanner.java | 13 +-
.../main/java/org/eigenbase/rex/RexUtil.java | 63 +++++---
.../net/hydromatic/optiq/test/JdbcTest.java | 75 +++++++--
.../optiq/test/MaterializationTest.java | 2 +-
.../net/hydromatic/optiq/test/OptiqAssert.java | 49 +++---
.../net/hydromatic/optiq/tools/PlannerTest.java | 5 +-
core/src/test/resources/sql/misc.oq | 46 ++++++
.../hydromatic/optiq/impl/tpcds/TpcdsTest.java | 21 +++
13 files changed, 389 insertions(+), 86 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b059c093/core/src/main/java/net/hydromatic/optiq/prepare/OptiqPrepareImpl.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/net/hydromatic/optiq/prepare/OptiqPrepareImpl.java b/core/src/main/java/net/hydromatic/optiq/prepare/OptiqPrepareImpl.java
index 41f6e58..87c172c 100644
--- a/core/src/main/java/net/hydromatic/optiq/prepare/OptiqPrepareImpl.java
+++ b/core/src/main/java/net/hydromatic/optiq/prepare/OptiqPrepareImpl.java
@@ -83,6 +83,10 @@ public class OptiqPrepareImpl implements OptiqPrepare {
public static final boolean DEBUG =
"true".equals(System.getProperties().getProperty("optiq.debug"));
+ public static final boolean COMMUTE =
+ "true".equals(
+ System.getProperties().getProperty("optiq.enable.join.commute"));
+
/** Whether to enable the collation trait. Some extra optimizations are
* possible if enabled, but queries should work either way. At some point
* this will become a preference, or we will run multiple phases: first
@@ -118,7 +122,9 @@ public class OptiqPrepareImpl implements OptiqPrepare {
JavaRules.ENUMERABLE_EMPTY_RULE,
JavaRules.ENUMERABLE_TABLE_FUNCTION_RULE,
TableAccessRule.INSTANCE,
- MergeProjectRule.INSTANCE,
+ COMMUTE
+ ? CommutativeJoinRule.INSTANCE
+ : MergeProjectRule.INSTANCE,
PushFilterPastProjectRule.INSTANCE,
PushFilterPastJoinRule.FILTER_ON_JOIN,
RemoveDistinctAggregateRule.INSTANCE,
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b059c093/core/src/main/java/net/hydromatic/optiq/rules/java/JavaRules.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/net/hydromatic/optiq/rules/java/JavaRules.java b/core/src/main/java/net/hydromatic/optiq/rules/java/JavaRules.java
index 2e4a69b..64ae4de 100644
--- a/core/src/main/java/net/hydromatic/optiq/rules/java/JavaRules.java
+++ b/core/src/main/java/net/hydromatic/optiq/rules/java/JavaRules.java
@@ -171,7 +171,6 @@ public class JavaRules {
@Override
public RelOptCost computeSelfCost(RelOptPlanner planner) {
- // We always "build" the
double rowCount = RelMetadataQuery.getRowCount(this);
// Joins can be flipped, and for many algorithms, both versions are viable
@@ -187,14 +186,19 @@ public class JavaRules {
}
}
- // Cheaper if the smaller number of rows is coming from the RHS.
+ // Cheaper if the smaller number of rows is coming from the LHS.
+ // Model this by adding L log L to the cost.
final double rightRowCount = right.getRows();
final double leftRowCount = left.getRows();
- if (rightRowCount > leftRowCount && !Double.isInfinite(rightRowCount)) {
- rowCount *= rightRowCount / (leftRowCount + 1d);
+ if (Double.isInfinite(leftRowCount)) {
+ rowCount = leftRowCount;
+ } else {
+ rowCount += Util.nLogN(leftRowCount);
}
- if (condition.isAlwaysTrue()) {
- rowCount *= 10d;
+ if (Double.isInfinite(rightRowCount)) {
+ rowCount = rightRowCount;
+ } else {
+ rowCount += rightRowCount;
}
return planner.getCostFactory().makeCost(rowCount, 0, 0);
}
@@ -220,24 +224,6 @@ public class JavaRules {
return d;
}
- @Override
- public double getRows() {
- final boolean leftKey = left.isKey(BitSets.of(leftKeys));
- final boolean rightKey = right.isKey(BitSets.of(rightKeys));
- final double leftRowCount = left.getRows();
- final double rightRowCount = right.getRows();
- if (leftKey && rightKey) {
- return Math.min(leftRowCount, rightRowCount);
- }
- if (leftKey) {
- return rightRowCount;
- }
- if (rightKey) {
- return leftRowCount;
- }
- return leftRowCount * rightRowCount;
- }
-
public Result implement(EnumerableRelImplementor implementor, Prefer pref) {
BlockBuilder builder = new BlockBuilder();
final Result leftResult =
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b059c093/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 788971f..53a6ac6 100644
--- a/core/src/main/java/net/hydromatic/optiq/tools/Programs.java
+++ b/core/src/main/java/net/hydromatic/optiq/tools/Programs.java
@@ -137,6 +137,7 @@ public class Programs {
final List<RelOptRule> list = new ArrayList<RelOptRule>(rules);
list.removeAll(
ImmutableList.of(SwapJoinRule.INSTANCE,
+ CommutativeJoinRule.INSTANCE,
PushJoinThroughJoinRule.LEFT,
PushJoinThroughJoinRule.RIGHT));
list.add(LoptOptimizeJoinRule.INSTANCE);
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b059c093/core/src/main/java/org/eigenbase/rel/rules/CommutativeJoinRule.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/rel/rules/CommutativeJoinRule.java b/core/src/main/java/org/eigenbase/rel/rules/CommutativeJoinRule.java
new file mode 100644
index 0000000..71afb8c
--- /dev/null
+++ b/core/src/main/java/org/eigenbase/rel/rules/CommutativeJoinRule.java
@@ -0,0 +1,155 @@
+/*
+// Licensed to Julian Hyde under one or more contributor license
+// agreements. See the NOTICE file distributed with this work for
+// additional information regarding copyright ownership.
+//
+// Julian Hyde 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.rel.rules;
+
+import java.util.BitSet;
+import java.util.List;
+
+import org.eigenbase.rel.JoinRelBase;
+import org.eigenbase.rel.JoinRelType;
+import org.eigenbase.rel.RelNode;
+import org.eigenbase.relopt.RelOptCluster;
+import org.eigenbase.relopt.RelOptRule;
+import org.eigenbase.relopt.RelOptRuleCall;
+import org.eigenbase.relopt.volcano.RelSubset;
+import org.eigenbase.rex.RexBuilder;
+import org.eigenbase.rex.RexNode;
+import org.eigenbase.rex.RexPermuteInputsShuttle;
+import org.eigenbase.rex.RexUtil;
+import org.eigenbase.util.mapping.Mappings;
+
+import net.hydromatic.optiq.util.BitSets;
+
+import com.google.common.collect.Lists;
+
+/**
+ * Planner rule that changes a join based on the commutativity rule.
+ *
+ * <p>((a JOIN b) JOIN c) → (a JOIN (b JOIN c))</p>
+ *
+ * <p>We do not need a rule to convert (a JOIN (b JOIN c)) →
+ * ((a JOIN b) JOIN c) because we have
+ * {@link org.eigenbase.rel.rules.SwapJoinRule}.
+ */
+public class CommutativeJoinRule extends RelOptRule {
+ //~ Static fields/initializers ---------------------------------------------
+
+ /** The singleton. */
+ public static final CommutativeJoinRule INSTANCE = new CommutativeJoinRule();
+
+ //~ Constructors -----------------------------------------------------------
+
+ /**
+ * Creates an CommutativeJoinRule.
+ */
+ private CommutativeJoinRule() {
+ super(
+ operand(JoinRelBase.class,
+ operand(JoinRelBase.class, any()),
+ operand(RelSubset.class, any())));
+ }
+
+ //~ Methods ----------------------------------------------------------------
+
+ public void onMatch(final RelOptRuleCall call) {
+ final JoinRelBase topJoin = call.rel(0);
+ final JoinRelBase bottomJoin = call.rel(1);
+ final RelNode relA = bottomJoin.getLeft();
+ final RelNode relB = bottomJoin.getRight();
+ final RelSubset relC = call.rel(2);
+ final RelOptCluster cluster = topJoin.getCluster();
+ final RexBuilder rexBuilder = cluster.getRexBuilder();
+
+ if (relC.getConvention() != relA.getConvention()) {
+ // relC could have any trait-set. But if we're matching say
+ // EnumerableConvention, we're only interested in enumerable subsets.
+ return;
+ }
+
+ // topJoin
+ // / \
+ // bottomJoin C
+ // / \
+ // A B
+
+ final int aCount = relA.getRowType().getFieldCount();
+ final int bCount = relB.getRowType().getFieldCount();
+ final int cCount = relC.getRowType().getFieldCount();
+ final BitSet aBitSet = BitSets.range(0, aCount);
+ final BitSet bBitSet = BitSets.range(aCount, aCount + bCount);
+
+ if (!topJoin.getSystemFieldList().isEmpty()) {
+ // FIXME Enable this rule for joins with system fields
+ return;
+ }
+
+ // If either join is not inner, we cannot proceed.
+ // (Is this too strict?)
+ if (topJoin.getJoinType() != JoinRelType.INNER
+ || bottomJoin.getJoinType() != JoinRelType.INNER) {
+ return;
+ }
+
+ // Goal is to transform to
+ //
+ // newTopJoin
+ // / \
+ // A newBottomJoin
+ // / \
+ // B C
+
+ // Split the condition of topJoin and bottomJoin into a conjunctions. A
+ // condition can be pushed down if it does not use columns from A.
+ final List<RexNode> top = Lists.newArrayList();
+ final List<RexNode> bottom = Lists.newArrayList();
+ PushJoinThroughJoinRule.split(topJoin.getCondition(), aBitSet, top, bottom);
+ PushJoinThroughJoinRule.split(bottomJoin.getCondition(), aBitSet, top,
+ bottom);
+
+ // Mapping for moving conditions from topJoin or bottomJoin to
+ // newBottomJoin.
+ // target: | B | C |
+ // source: | A | B | C |
+ final Mappings.TargetMapping bottomMapping =
+ Mappings.createShiftMapping(
+ aCount + bCount + cCount,
+ 0, aCount, bCount,
+ bCount, aCount + bCount, cCount);
+ final List<RexNode> newBottomList = Lists.newArrayList();
+ new RexPermuteInputsShuttle(bottomMapping, relB, relC)
+ .visitList(bottom, newBottomList);
+ RexNode newBottomCondition =
+ RexUtil.composeConjunction(rexBuilder, newBottomList, false);
+
+ final JoinRelBase newBottomJoin =
+ bottomJoin.copy(bottomJoin.getTraitSet(), newBottomCondition, relB,
+ relC, JoinRelType.INNER, false);
+
+ // Condition for newTopJoin consists of pieces from bottomJoin and topJoin.
+ // Field ordinals do not need to be changed.
+ RexNode newTopCondition =
+ RexUtil.composeConjunction(rexBuilder, top, false);
+ final JoinRelBase newTopJoin =
+ topJoin.copy(topJoin.getTraitSet(), newTopCondition, relA,
+ newBottomJoin, JoinRelType.INNER, false);
+
+ call.transformTo(newTopJoin);
+ }
+}
+
+// End CommutativeJoinRule.java
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b059c093/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 77437c1..9e3d122 100644
--- a/core/src/main/java/org/eigenbase/rel/rules/LoptOptimizeJoinRule.java
+++ b/core/src/main/java/org/eigenbase/rel/rules/LoptOptimizeJoinRule.java
@@ -643,9 +643,8 @@ public class LoptOptimizeJoinRule extends RelOptRule {
int firstFactor) {
LoptJoinTree joinTree = null;
int nJoinFactors = multiJoin.getNumJoinFactors();
- BitSet factorsToAdd = new BitSet(nJoinFactors);
+ BitSet factorsToAdd = BitSets.range(0, nJoinFactors);
BitSet factorsAdded = new BitSet(nJoinFactors);
- factorsToAdd.flip(0, nJoinFactors);
List<RexNode> filtersToAdd =
new ArrayList<RexNode>(multiJoin.getJoinFilters());
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b059c093/core/src/main/java/org/eigenbase/relopt/volcano/VolcanoPlanner.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/relopt/volcano/VolcanoPlanner.java b/core/src/main/java/org/eigenbase/relopt/volcano/VolcanoPlanner.java
index 7bb3d8d..edd6160 100644
--- a/core/src/main/java/org/eigenbase/relopt/volcano/VolcanoPlanner.java
+++ b/core/src/main/java/org/eigenbase/relopt/volcano/VolcanoPlanner.java
@@ -34,8 +34,8 @@ import org.eigenbase.util.*;
import net.hydromatic.linq4j.expressions.Expressions;
+import net.hydromatic.optiq.prepare.OptiqPrepareImpl;
import net.hydromatic.optiq.runtime.Spaces;
-
import net.hydromatic.optiq.util.graph.*;
import com.google.common.collect.*;
@@ -743,6 +743,12 @@ public class VolcanoPlanner extends AbstractRelOptPlanner {
for (RelNode rel : rule.rels) {
provenanceRecurse(pw, rel, i + 2, visited);
}
+ } else if (o == null && node instanceof RelSubset) {
+ // A few operands recognize subsets, not individual rels.
+ // The first rel in the subset is deemed to have created it.
+ final RelSubset subset = (RelSubset) node;
+ pw.println("subset " + subset);
+ provenanceRecurse(pw, subset.getRelList().get(0), i + 2, visited);
} else {
throw new AssertionError("bad type " + o);
}
@@ -892,8 +898,13 @@ public class VolcanoPlanner extends AbstractRelOptPlanner {
}
public void registerAbstractRelationalRules() {
+ addRule(PushFilterPastJoinRule.FILTER_ON_JOIN);
+ addRule(PushFilterPastJoinRule.JOIN);
addRule(AbstractConverter.ExpandConversionRule.INSTANCE);
addRule(SwapJoinRule.INSTANCE);
+ if (OptiqPrepareImpl.COMMUTE) {
+ addRule(CommutativeJoinRule.INSTANCE);
+ }
addRule(RemoveDistinctRule.INSTANCE);
addRule(UnionToDistinctRule.INSTANCE);
addRule(RemoveTrivialProjectRule.INSTANCE);
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b059c093/core/src/main/java/org/eigenbase/rex/RexUtil.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/rex/RexUtil.java b/core/src/main/java/org/eigenbase/rex/RexUtil.java
index b9e2a87..ad86fc8 100644
--- a/core/src/main/java/org/eigenbase/rex/RexUtil.java
+++ b/core/src/main/java/org/eigenbase/rex/RexUtil.java
@@ -30,19 +30,24 @@ import org.eigenbase.util.mapping.*;
import net.hydromatic.linq4j.function.*;
+import com.google.common.base.Predicate;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterators;
+import com.google.common.collect.UnmodifiableIterator;
+
/**
* Utility methods concerning row-expressions.
*/
public class RexUtil {
- private static final Predicate1<RexNode> NOT_ALWAYS_TRUE_PREDICATE =
- new Predicate1<RexNode>() {
+ private static final Predicate<RexNode> NOT_ALWAYS_TRUE_PREDICATE =
+ new Predicate<RexNode>() {
public boolean apply(RexNode e) {
return !e.isAlwaysTrue();
}
};
- private static final Predicate1<RexNode> NOT_ALWAYS_FALSE_PREDICATE =
- new Predicate1<RexNode>() {
+ private static final Predicate<RexNode> NOT_ALWAYS_FALSE_PREDICATE =
+ new Predicate<RexNode>() {
public boolean apply(RexNode e) {
return !e.isAlwaysFalse();
}
@@ -587,20 +592,25 @@ public class RexUtil {
* Returns null only if {@code nullOnEmpty} and expression is TRUE.
*/
public static RexNode composeConjunction(
- RexBuilder rexBuilder, List<RexNode> nodes, boolean nullOnEmpty) {
- List<RexNode> nodes2 =
- Functions.filter(nodes, NOT_ALWAYS_TRUE_PREDICATE);
- switch (nodes2.size()) {
- case 0:
+ RexBuilder rexBuilder, Iterable<RexNode> nodes, boolean nullOnEmpty) {
+ final UnmodifiableIterator<RexNode> iterator =
+ Iterators.filter(nodes.iterator(), NOT_ALWAYS_TRUE_PREDICATE);
+ if (!iterator.hasNext()) {
+ // Zero expressions
return nullOnEmpty
? null
: rexBuilder.makeLiteral(true);
- case 1:
- return nodes2.get(0);
- default:
- return rexBuilder.makeCall(
- SqlStdOperatorTable.AND, nodes2);
}
+ final RexNode node = iterator.next();
+ if (!iterator.hasNext()) {
+ // One expression
+ return node;
+ }
+ // More than one expression
+ final ImmutableList.Builder<RexNode> builder = ImmutableList.builder();
+ builder.add(node);
+ builder.addAll(iterator);
+ return rexBuilder.makeCall(SqlStdOperatorTable.AND, builder.build());
}
/**
@@ -610,20 +620,25 @@ public class RexUtil {
* Removes expressions that always evaluate to FALSE.
*/
public static RexNode composeDisjunction(
- RexBuilder rexBuilder, List<RexNode> nodes, boolean nullOnEmpty) {
- List<RexNode> nodes2 =
- Functions.filter(nodes, NOT_ALWAYS_FALSE_PREDICATE);
- switch (nodes2.size()) {
- case 0:
+ RexBuilder rexBuilder, Iterable<RexNode> nodes, boolean nullOnEmpty) {
+ final UnmodifiableIterator<RexNode> iterator =
+ Iterators.filter(nodes.iterator(), NOT_ALWAYS_FALSE_PREDICATE);
+ if (!iterator.hasNext()) {
+ // Zero expressions
return nullOnEmpty
? null
: rexBuilder.makeLiteral(false);
- case 1:
- return nodes2.get(0);
- default:
- return rexBuilder.makeCall(
- SqlStdOperatorTable.OR, nodes2);
}
+ final RexNode node = iterator.next();
+ if (!iterator.hasNext()) {
+ // One expression
+ return node;
+ }
+ // More than one expression
+ final ImmutableList.Builder<RexNode> builder = ImmutableList.builder();
+ builder.add(node);
+ builder.addAll(iterator);
+ return rexBuilder.makeCall(SqlStdOperatorTable.OR, builder.build());
}
/**
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b059c093/core/src/test/java/net/hydromatic/optiq/test/JdbcTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/net/hydromatic/optiq/test/JdbcTest.java b/core/src/test/java/net/hydromatic/optiq/test/JdbcTest.java
index b1a6cb8..3b0e6b9 100644
--- a/core/src/test/java/net/hydromatic/optiq/test/JdbcTest.java
+++ b/core/src/test/java/net/hydromatic/optiq/test/JdbcTest.java
@@ -406,8 +406,8 @@ public class JdbcTest {
+ "where n < 15");
// The call to "View('(10), (2)')" expands to 'values (1), (3), (10), (20)'.
assertThat(OptiqAssert.toString(resultSet),
- equalTo(
- "N=1\n"
+ equalTo(""
+ + "N=1\n"
+ "N=3\n"
+ "N=10\n"));
}
@@ -453,8 +453,8 @@ public class JdbcTest {
+ " }\n"
+ " ]\n"
+ "}").query("select * from table(\"adhoc\".\"View\"('(30)'))")
- .returns(
- "c=1\n"
+ .returns(""
+ + "c=1\n"
+ "c=3\n"
+ "c=30\n");
}
@@ -904,8 +904,8 @@ public class JdbcTest {
try {
Statement s = c.createStatement();
ResultSet rs =
- s.executeQuery(
- "SELECT 1 as \"a\", 2 as \"b\", 3 as \"a\", 4 as \"B\"\n"
+ s.executeQuery(""
+ + "SELECT 1 as \"a\", 2 as \"b\", 3 as \"a\", 4 as \"B\"\n"
+ "FROM (VALUES (0))");
assertTrue(rs.next());
assertEquals(1, rs.getInt("a"));
@@ -978,8 +978,8 @@ public class JdbcTest {
+ "from \"foodmart2\".\"time_by_day\"\n"
+ "group by \"the_year\"\n"
+ "order by 1, 2")
- .returns(
- "the_year=1997; C=365; M=April\n"
+ .returns(""
+ + "the_year=1997; C=365; M=April\n"
+ "the_year=1998; C=365; M=April\n");
}
@@ -1035,6 +1035,55 @@ public class JdbcTest {
+ "c0=1998\n");
}
+ /** Just short of bushy. */
+ @Test public void testAlmostBushy() {
+ OptiqAssert.that()
+ .with(OptiqAssert.Config.FOODMART_CLONE)
+ .query("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'")
+ .explainMatches("including all attributes ",
+ OptiqAssert.checkMaskedResultContains(""
+ + "EnumerableJoinRel(condition=[=($0, $38)], joinType=[inner]): rowcount = 7.050660528307499E8, cumulative cost = {1.0640240206183146E9 rows, 777302.0 cpu, 0.0 io}\n"
+ + " EnumerableJoinRel(condition=[=($2, $8)], joinType=[inner]): rowcount = 2.0087351932499997E7, cumulative cost = {2.117504619375143E7 rows, 724261.0 cpu, 0.0 io}\n"
+ + " EnumerableTableAccessRel(table=[[foodmart2, sales_fact_1997]]): rowcount = 86837.0, cumulative cost = {86837.0 rows, 86838.0 cpu, 0.0 io}\n"
+ + " EnumerableCalcRel(expr#0..28=[{inputs}], expr#29=['San Francisco'], expr#30=[=($t9, $t29)], proj#0..28=[{exprs}], $condition=[$t30]): rowcount = 1542.1499999999999, cumulative cost = {11823.15 rows, 637423.0 cpu, 0.0 io}\n"
+ + " EnumerableTableAccessRel(table=[[foodmart2, customer]]): rowcount = 10281.0, cumulative cost = {10281.0 rows, 10282.0 cpu, 0.0 io}\n"
+ + " EnumerableCalcRel(expr#0..14=[{inputs}], expr#15=['Washington'], expr#16=[=($t2, $t15)], proj#0..14=[{exprs}], $condition=[$t16]): rowcount = 234.0, cumulative cost = {1794.0 rows, 53041.0 cpu, 0.0 io}\n"
+ + " EnumerableTableAccessRel(table=[[foodmart2, product]]): rowcount = 1560.0, cumulative cost = {1560.0 rows, 1561.0 cpu, 0.0 io}\n"));
+ }
+
+ /** Tests a query whose best plan is a bushy join.
+ * First join sales_fact_1997 to customer;
+ * in parallel join product to product_class;
+ * then join the results. */
+ @Ignore("extremely slow - a bit better if you disable MergeProjectRule")
+ @Test public void testBushy() {
+ OptiqAssert.that()
+ .with(OptiqAssert.Config.FOODMART_CLONE)
+ .query(
+ "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 pc.\"product_department\" = 'Snacks'\n")
+ .explainMatches("including all attributes ",
+ OptiqAssert.checkMaskedResultContains(""
+ + "EnumerableCalcRel(expr#0..56=[{inputs}], expr#57=['San Francisco'], expr#58=[=($t9, $t57)], expr#59=['Snacks'], expr#60=[=($t32, $t59)], expr#61=[AND($t58, $t60)], product_id=[$t49], time_id=[$t50], customer_id=[$t51], promotion_id=[$t52], store_id=[$t53], store_sales=[$t54], store_cost=[$t55], unit_sales=[$t56], customer_id0=[$t0], account_num=[$t1], lname=[$t2], fname=[$t3], mi=[$t4], address1=[$t5], address2=[$t6], address3=[$t7], address4=[$t8], city=[$t9], state_province=[$t10], postal_code=[$t11], country=[$t12], customer_region_id=[$t13], phone1=[$t14], phone2=[$t15], birthdate=[$t16], marital_status=[$t17], yearly_income=[$t18], gender=[$t19], total_children=[$t20], num_children_at_home=[$t21], education=[$t22], date_accnt_opened=[$t23], member_card=[$t24], occupation=[$t25], houseowner=[$t26], num_cars_owned=[$t27], fullname=[$t28], product_class_id=[$t34], product_id0=[$t35], brand_name=[$t36], product_name=[$t37], SKU=[$t38], SRP=[$t39], gross_weight=[$
t40], net_weight=[$t41], recyclable_package=[$t42], low_fat=[$t43], units_per_case=[$t44], cases_per_pallet=[$t45], shelf_width=[$t46], shelf_height=[$t47], shelf_depth=[$t48], product_class_id0=[$t29], product_subcategory=[$t30], product_category=[$t31], product_department=[$t32], product_family=[$t33], $condition=[$t61]): rowcount = 1953.8325, cumulative cost = {728728.1144018068 rows, 1.0519232E7 cpu, 0.0 io}\n"
+ + " EnumerableJoinRel(condition=[=($51, $0)], joinType=[inner]): rowcount = 86837.0, cumulative cost = {726774.2819018068 rows, 98792.0 cpu, 0.0 io}\n"
+ + " EnumerableTableAccessRel(table=[[foodmart2, customer]]): rowcount = 10281.0, cumulative cost = {10281.0 rows, 10282.0 cpu, 0.0 io}\n"
+ + " EnumerableJoinRel(condition=[=($5, $0)], joinType=[inner]): rowcount = 86837.0, cumulative cost = {447842.86095661717 rows, 88510.0 cpu, 0.0 io}\n"
+ + " EnumerableTableAccessRel(table=[[foodmart2, product_class]]): rowcount = 110.0, cumulative cost = {110.0 rows, 111.0 cpu, 0.0 io}\n"
+ + " EnumerableJoinRel(condition=[=($15, $1)], joinType=[inner]): rowcount = 86837.0, cumulative cost = {273541.80811638 rows, 88399.0 cpu, 0.0 io}\n"
+ + " EnumerableTableAccessRel(table=[[foodmart2, product]]): rowcount = 1560.0, cumulative cost = {1560.0 rows, 1561.0 cpu, 0.0 io}\n"
+ + " EnumerableTableAccessRel(table=[[foodmart2, sales_fact_1997]]): rowcount = 86837.0, cumulative cost = {86837.0 rows, 86838.0 cpu, 0.0 io}\n"));
+ }
+
private static final String[] QUERIES = {
"select count(*) from (select 1 as \"c0\" from \"salary\" as \"salary\") as \"init\"",
"EXPR$0=21252\n",
@@ -2388,12 +2437,12 @@ public class JdbcTest {
.explainContains(
"EnumerableAggregateRel(group=[{0}], m0=[COUNT($1)])\n"
+ " EnumerableAggregateRel(group=[{0, 1}])\n"
- + " EnumerableCalcRel(expr#0..3=[{inputs}], c0=[$t3], unit_sales=[$t1])\n"
- + " EnumerableJoinRel(condition=[=($0, $2)], joinType=[inner])\n"
- + " EnumerableCalcRel(expr#0..7=[{inputs}], time_id=[$t1], unit_sales=[$t7])\n"
- + " EnumerableTableAccessRel(table=[[foodmart2, sales_fact_1997]])\n"
+ + " EnumerableCalcRel(expr#0..3=[{inputs}], c0=[$t1], unit_sales=[$t3])\n"
+ + " EnumerableJoinRel(condition=[=($2, $0)], joinType=[inner])\n"
+ " EnumerableCalcRel(expr#0..9=[{inputs}], expr#10=[CAST($t4):INTEGER], expr#11=[1997], expr#12=[=($t10, $t11)], time_id=[$t0], the_year=[$t4], $condition=[$t12])\n"
- + " EnumerableTableAccessRel(table=[[foodmart2, time_by_day]])")
+ + " EnumerableTableAccessRel(table=[[foodmart2, time_by_day]])\n"
+ + " EnumerableCalcRel(expr#0..7=[{inputs}], time_id=[$t1], unit_sales=[$t7])\n"
+ + " EnumerableTableAccessRel(table=[[foodmart2, sales_fact_1997]])")
.returns("c0=1997; m0=6\n");
}
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b059c093/core/src/test/java/net/hydromatic/optiq/test/MaterializationTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/net/hydromatic/optiq/test/MaterializationTest.java b/core/src/test/java/net/hydromatic/optiq/test/MaterializationTest.java
index 8c6ecd5..18bc8e3 100644
--- a/core/src/test/java/net/hydromatic/optiq/test/MaterializationTest.java
+++ b/core/src/test/java/net/hydromatic/optiq/test/MaterializationTest.java
@@ -104,7 +104,7 @@ public class MaterializationTest {
.withMaterializations(model, "m0", materialize)
.query(query)
.enableMaterializations(true)
- .explainMatches(explainChecker)
+ .explainMatches("", explainChecker)
.sameResultWithMaterializationsDisabled();
} finally {
Prepare.THREAD_TRIM.set(false);
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b059c093/core/src/test/java/net/hydromatic/optiq/test/OptiqAssert.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/net/hydromatic/optiq/test/OptiqAssert.java b/core/src/test/java/net/hydromatic/optiq/test/OptiqAssert.java
index a89523c..0a713c1 100644
--- a/core/src/test/java/net/hydromatic/optiq/test/OptiqAssert.java
+++ b/core/src/test/java/net/hydromatic/optiq/test/OptiqAssert.java
@@ -297,6 +297,25 @@ public class OptiqAssert {
};
}
+ public static Function1<ResultSet, Void> checkMaskedResultContains(
+ final String expected) {
+ return new Function1<ResultSet, Void>() {
+ public Void apply(ResultSet s) {
+ try {
+ final String actual = Util.toLinux(OptiqAssert.toString(s));
+ final String maskedActual =
+ actual.replaceAll(", id = [0-9]+", "");
+ if (!maskedActual.contains(expected)) {
+ assertEquals("contains", expected, maskedActual);
+ }
+ return null;
+ } catch (SQLException e) {
+ throw new RuntimeException(e);
+ }
+ }
+ };
+ }
+
public static Function1<ResultSet, Void> checkResultType(
final String expected) {
return new Function1<ResultSet, Void>() {
@@ -870,7 +889,12 @@ public class OptiqAssert {
return returns(checkResultCount(expectedCount));
}
- public AssertQuery returns(Function1<ResultSet, Void> checker) {
+ public final AssertQuery returns(Function1<ResultSet, Void> checker) {
+ return returns(sql, checker);
+ }
+
+ protected AssertQuery returns(String sql,
+ Function1<ResultSet, Void> checker) {
try {
assertQuery(createConnection(), sql, limit, materializationsEnabled,
checker, null);
@@ -944,20 +968,12 @@ public class OptiqAssert {
}
public AssertQuery explainContains(String expected) {
- return explainMatches(checkResultContains(expected));
+ return explainMatches("", checkResultContains(expected));
}
- public AssertQuery explainMatches(Function1<ResultSet, Void> checker) {
- String explainSql = "explain plan for " + sql;
- try {
- assertQuery(
- createConnection(), explainSql, limit, materializationsEnabled,
- checker, null);
- return this;
- } catch (Exception e) {
- throw new RuntimeException(
- "exception while executing [" + explainSql + "]", e);
- }
+ public final AssertQuery explainMatches(String extra,
+ Function1<ResultSet, Void> checker) {
+ return returns("explain plan " + extra + "for " + sql, checker);
}
public AssertQuery planContains(String expected) {
@@ -1105,7 +1121,7 @@ public class OptiqAssert {
}
@Override
- public AssertQuery returns(Function1<ResultSet, Void> checker) {
+ public AssertQuery returns(String sql, Function1<ResultSet, Void> checker) {
return this;
}
@@ -1125,11 +1141,6 @@ public class OptiqAssert {
}
@Override
- public AssertQuery explainMatches(Function1<ResultSet, Void> checker) {
- return this;
- }
-
- @Override
public AssertQuery planContains(String expected) {
return this;
}
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b059c093/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 9981696..75282c7 100644
--- a/core/src/test/java/net/hydromatic/optiq/tools/PlannerTest.java
+++ b/core/src/test/java/net/hydromatic/optiq/tools/PlannerTest.java
@@ -22,6 +22,7 @@ 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;
@@ -543,7 +544,9 @@ public class PlannerTest {
JavaRules.ENUMERABLE_ONE_ROW_RULE,
JavaRules.ENUMERABLE_EMPTY_RULE,
TableAccessRule.INSTANCE,
- MergeProjectRule.INSTANCE,
+ OptiqPrepareImpl.COMMUTE
+ ? CommutativeJoinRule.INSTANCE
+ : MergeProjectRule.INSTANCE,
PushFilterPastProjectRule.INSTANCE,
PushFilterPastJoinRule.FILTER_ON_JOIN,
RemoveDistinctAggregateRule.INSTANCE,
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b059c093/core/src/test/resources/sql/misc.oq
----------------------------------------------------------------------
diff --git a/core/src/test/resources/sql/misc.oq b/core/src/test/resources/sql/misc.oq
index 13b66c3..b8f72b0 100644
--- a/core/src/test/resources/sql/misc.oq
+++ b/core/src/test/resources/sql/misc.oq
@@ -181,4 +181,50 @@ select count(*) as c from "everyTypes" where "utilDate" = TIMESTAMP '1970-01-01
!ok
+# [OPTIQ-346] Add commutative join rule
+#
+# 3-way join that does not require bushy join. Best plan is: sales_fact_1997 as
+# left-most leaf, then customer (with filter), then product.
+!use foodmart
+select *
+from "sales_fact_1997" as s
+ join "customer" as c using ("customer_id")
+ join "product" as p using ("product_id")
+where c."city" = 'San Francisco';
+EnumerableJoinRel(condition=[=($0, $38)], joinType=[inner])
+ EnumerableJoinRel(condition=[=($2, $8)], joinType=[inner])
+ EnumerableTableAccessRel(table=[[foodmart2, sales_fact_1997]])
+ EnumerableCalcRel(expr#0..28=[{inputs}], expr#29=['San Francisco'], expr#30=[=($t9, $t29)], proj#0..28=[{exprs}], $condition=[$t30])
+ EnumerableTableAccessRel(table=[[foodmart2, customer]])
+ EnumerableTableAccessRel(table=[[foodmart2, product]])
+!plan
+
+# 4-way join whose optimal plan requires bushy join.
+#
+# In the plan, note that filters on customer.city and product_department are
+# pushed down. And the plan is a bushy join, with sub-joins (product_class,
+# product) and (sales_fact_1997, customer). However, scan(sales_fact_1997)
+# should be left-most leaf, but is not because CommutativeJoinRule is currently
+# disabled.
+!use foodmart
+select *
+from "sales_fact_1997" as s
+ join "customer" as c using ("customer_id")
+ join "product" as p using ("product_id")
+ join "product_class" as pc using ("product_class_id")
+where c."city" = 'San Francisco'
+ and pc."product_department" = 'Snacks';
+EnumerableCalcRel(expr#0..56=[{inputs}], $f0=[$t20], $f1=[$t21], $f2=[$t22], $f3=[$t23], $f4=[$t24], $f5=[$t25], $f6=[$t26], $f7=[$t27], $f8=[$t28], $f9=[$t29], $f10=[$t30], $f11=[$t31], $f12=[$t32], $f13=[$t33], $f14=[$t34], $f15=[$t35], $f16=[$t36], $f17=[$t37], $f18=[$t38], $f19=[$t39], $f20=[$t40], $f21=[$t41], $f22=[$t42], $f23=[$t43], $f24=[$t44], $f25=[$t45], $f26=[$t46], $f27=[$t47], $f28=[$t48], $f29=[$t49], $f30=[$t50], $f31=[$t51], $f32=[$t52], $f33=[$t53], $f34=[$t54], $f35=[$t55], $f36=[$t56], $f37=[$t5], $f38=[$t6], $f39=[$t7], $f40=[$t8], $f41=[$t9], $f42=[$t10], $f43=[$t11], $f44=[$t12], $f45=[$t13], $f46=[$t14], $f47=[$t15], $f48=[$t16], $f49=[$t17], $f50=[$t18], $f51=[$t19], $f52=[$t0], $f53=[$t1], $f54=[$t2], $f55=[$t3], $f56=[$t4])
+ EnumerableJoinRel(condition=[=($20, $6)], joinType=[inner])
+ EnumerableJoinRel(condition=[=($5, $0)], joinType=[inner])
+ EnumerableCalcRel(expr#0..4=[{inputs}], expr#5=['Snacks'], expr#6=[=($t3, $t5)], proj#0..4=[{exprs}], $condition=[$t6])
+ EnumerableTableAccessRel(table=[[foodmart2, product_class]])
+ EnumerableTableAccessRel(table=[[foodmart2, product]])
+ EnumerableJoinRel(condition=[=($2, $8)], joinType=[inner])
+ EnumerableTableAccessRel(table=[[foodmart2, sales_fact_1997]])
+ EnumerableCalcRel(expr#0..28=[{inputs}], expr#29=['San Francisco'], expr#30=[=($t9, $t29)], proj#0..28=[{exprs}], $condition=[$t30])
+ EnumerableTableAccessRel(table=[[foodmart2, customer]])
+!plan
+
+
# End misc.oq
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/b059c093/plus/src/test/java/net/hydromatic/optiq/impl/tpcds/TpcdsTest.java
----------------------------------------------------------------------
diff --git a/plus/src/test/java/net/hydromatic/optiq/impl/tpcds/TpcdsTest.java b/plus/src/test/java/net/hydromatic/optiq/impl/tpcds/TpcdsTest.java
index dbae507..713a1fe 100644
--- a/plus/src/test/java/net/hydromatic/optiq/impl/tpcds/TpcdsTest.java
+++ b/plus/src/test/java/net/hydromatic/optiq/impl/tpcds/TpcdsTest.java
@@ -19,6 +19,8 @@ package net.hydromatic.optiq.impl.tpcds;
import net.hydromatic.optiq.test.OptiqAssert;
+import org.eigenbase.util.Bug;
+
import org.junit.Ignore;
import org.junit.Test;
@@ -87,6 +89,14 @@ public class TpcdsTest {
checkQuery(1).runs();
}
+ @Test public void testQuery17() {
+ checkQuery(17).explainContains("xx");
+ }
+
+ @Test public void testQuery58() {
+ checkQuery(58).explainContains("xx").runs();
+ }
+
@Ignore("takes too long to optimize")
@Test public void testQuery72() {
checkQuery(72).runs();
@@ -101,9 +111,20 @@ public class TpcdsTest {
final Query query = Query.of(i);
String sql = query.sql(-1, new Random(0));
switch (i) {
+ case 58:
+ if (Bug.upgrade("new TPC-DS generator")) {
+ // Work around bug: Support '<DATE> = <character literal>'.
+ sql = sql.replace(" = '", " = DATE '");
+ } else {
+ // Until TPC-DS generator can handle date(...).
+ sql = sql.replace("'date([YEAR]+\"-01-01\",[YEAR]+\"-07-24\",sales)'",
+ "DATE '1998-08-18'");
+ }
+ break;
case 72:
// Work around OPTIQ-304: Support '<DATE> + <INTEGER>'.
sql = sql.replace("+ 5", "+ interval '5' day");
+ break;
}
return with()
.query(sql.replaceAll("tpcds\\.", "tpcds_01."));