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/08/06 21:48:54 UTC
[1/2] git commit: Add FilterFactory.
Repository: incubator-optiq
Updated Branches:
refs/heads/master dde3c0133 -> c33e602fa
Add FilterFactory.
Project: http://git-wip-us.apache.org/repos/asf/incubator-optiq/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-optiq/commit/e6077659
Tree: http://git-wip-us.apache.org/repos/asf/incubator-optiq/tree/e6077659
Diff: http://git-wip-us.apache.org/repos/asf/incubator-optiq/diff/e6077659
Branch: refs/heads/master
Commit: e6077659dc4b3119cb9050abad6bd76dc445790d
Parents: dde3c01
Author: Julian Hyde <jh...@apache.org>
Authored: Wed Aug 6 12:33:00 2014 -0700
Committer: Julian Hyde <jh...@apache.org>
Committed: Wed Aug 6 12:34:15 2014 -0700
----------------------------------------------------------------------
.../java/org/eigenbase/rel/RelFactories.java | 25 ++++++++++++++++++++
1 file changed, 25 insertions(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/e6077659/core/src/main/java/org/eigenbase/rel/RelFactories.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/rel/RelFactories.java b/core/src/main/java/org/eigenbase/rel/RelFactories.java
index 64954ff..123731e 100644
--- a/core/src/main/java/org/eigenbase/rel/RelFactories.java
+++ b/core/src/main/java/org/eigenbase/rel/RelFactories.java
@@ -37,6 +37,9 @@ public class RelFactories {
public static final ProjectFactory DEFAULT_PROJECT_FACTORY =
new ProjectFactoryImpl();
+ public static final FilterFactory DEFAULT_FILTER_FACTORY =
+ new FilterFactoryImpl();
+
public static final JoinFactory DEFAULT_JOIN_FACTORY = new JoinFactoryImpl();
private RelFactories() {
@@ -67,6 +70,28 @@ public class RelFactories {
}
/**
+ * Can create a {@link org.eigenbase.rel.FilterRel} of the appropriate type
+ * for this rule's calling convention.
+ */
+ public interface FilterFactory {
+ /**
+ * Can create a {@link org.eigenbase.rel.FilterRel} of the appropriate type
+ * for this rule's calling convention.
+ */
+ RelNode createFilter(RelNode child, RexNode condition);
+ }
+
+ /**
+ * Implementation of {@link org.eigenbase.rel.RelFactories.FilterFactory} that
+ * returns vanilla {@link FilterRel}.
+ */
+ private static class FilterFactoryImpl implements FilterFactory {
+ public RelNode createFilter(RelNode child, RexNode condition) {
+ return new FilterRel(child.getCluster(), child, condition);
+ }
+ }
+
+ /**
* Can create a {@link org.eigenbase.rel.JoinRelBase} of the appropriate type
* for this rule's calling convention.
*/
[2/2] git commit: [OPTIQ-360] Introduce a rule to infer predicates
from equi-join conditions
Posted by jh...@apache.org.
[OPTIQ-360] Introduce a rule to infer predicates from equi-join conditions
Project: http://git-wip-us.apache.org/repos/asf/incubator-optiq/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-optiq/commit/c33e602f
Tree: http://git-wip-us.apache.org/repos/asf/incubator-optiq/tree/c33e602f
Diff: http://git-wip-us.apache.org/repos/asf/incubator-optiq/diff/c33e602f
Branch: refs/heads/master
Commit: c33e602fa0c215e8a9f426781f9bb445fd9e6e94
Parents: e607765
Author: Harish Butani <hb...@hortonworks.com>
Authored: Mon Aug 4 18:49:20 2014 -0700
Committer: Julian Hyde <jh...@apache.org>
Committed: Wed Aug 6 12:34:42 2014 -0700
----------------------------------------------------------------------
.../net/hydromatic/optiq/BuiltinMethod.java | 1 +
.../java/net/hydromatic/optiq/util/BitSets.java | 54 ++
.../eigenbase/rel/metadata/BuiltInMetadata.java | 17 +-
.../metadata/DefaultRelMetadataProvider.java | 3 +-
.../eigenbase/rel/metadata/RelMdPredicates.java | 667 +++++++++++++++++++
.../rel/metadata/RelMetadataQuery.java | 14 +
.../rules/TransitivePredicatesOnJoinRule.java | 86 +++
.../eigenbase/relopt/RelOptPredicateList.java | 74 ++
.../java/org/eigenbase/relopt/RelOptUtil.java | 3 +-
.../net/hydromatic/optiq/util/BitSetsTest.java | 33 +
.../org/eigenbase/test/RelOptRulesTest.java | 163 ++++-
.../org/eigenbase/test/RelOptRulesTest.xml | 509 ++++++++++++++
12 files changed, 1618 insertions(+), 6 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/c33e602f/core/src/main/java/net/hydromatic/optiq/BuiltinMethod.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/net/hydromatic/optiq/BuiltinMethod.java b/core/src/main/java/net/hydromatic/optiq/BuiltinMethod.java
index e435f24..4884822 100644
--- a/core/src/main/java/net/hydromatic/optiq/BuiltinMethod.java
+++ b/core/src/main/java/net/hydromatic/optiq/BuiltinMethod.java
@@ -221,6 +221,7 @@ public enum BuiltinMethod {
EXPLAIN_VISIBILITY(ExplainVisibility.class, "isVisibleInExplain",
SqlExplainLevel.class),
DATA_CONTEXT_GET_QUERY_PROVIDER(DataContext.class, "getQueryProvider"),
+ PREDICATES(Predicates.class, "getPredicates"),
METADATA_REL(Metadata.class, "rel");
public final Method method;
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/c33e602f/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 5936af3..869d1dc 100644
--- a/core/src/main/java/net/hydromatic/optiq/util/BitSets.java
+++ b/core/src/main/java/net/hydromatic/optiq/util/BitSets.java
@@ -245,6 +245,60 @@ public final class BitSets {
}
return -1;
}
+
+ /** Computes the closure of a map from integers to bits.
+ *
+ * <p>The input must have an entry for each position.
+ *
+ * <p>Does not modify the input map or its bit sets. */
+ public static SortedMap<Integer, BitSet> closure(
+ SortedMap<Integer, BitSet> equivalence) {
+ final Closure closure = new Closure(equivalence);
+ return closure.closure;
+ }
+
+ /**
+ * Setup equivalence Sets for each position. If i & j are equivalent then
+ * they will have the same equivalence Set. The algorithm computes the
+ * closure relation at each position for the position wrt to positions
+ * greater than it. Once a closure is computed for a position, the closure
+ * Set is set on all its descendants. So the closure computation bubbles up
+ * from lower positions and the final equivalence Set is propagated down
+ * from the lowest element in the Set.
+ */
+ private static class Closure {
+ private SortedMap<Integer, BitSet> equivalence;
+ private final SortedMap<Integer, BitSet> closure =
+ new TreeMap<Integer, BitSet>();
+
+ public Closure(SortedMap<Integer, BitSet> equivalence) {
+ this.equivalence = equivalence;
+ final ImmutableIntList keys =
+ ImmutableIntList.copyOf(equivalence.keySet());
+ for (int pos : keys) {
+ computeClosure(pos);
+ }
+ }
+
+ private BitSet computeClosure(int pos) {
+ BitSet o = closure.get(pos);
+ if (o != null) {
+ return o;
+ }
+ BitSet b = equivalence.get(pos);
+ o = (BitSet) b.clone();
+ int i = b.nextSetBit(pos + 1);
+ for (; i >= 0; i = b.nextSetBit(i + 1)) {
+ o.or(computeClosure(i));
+ }
+ closure.put(pos, o);
+ i = o.nextSetBit(pos + 1);
+ for (; i >= 0; i = b.nextSetBit(i + 1)) {
+ closure.put(i, o);
+ }
+ return o;
+ }
+ }
}
// End BitSets.java
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/c33e602f/core/src/main/java/org/eigenbase/rel/metadata/BuiltInMetadata.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/rel/metadata/BuiltInMetadata.java b/core/src/main/java/org/eigenbase/rel/metadata/BuiltInMetadata.java
index 863a712..eded7c9 100644
--- a/core/src/main/java/org/eigenbase/rel/metadata/BuiltInMetadata.java
+++ b/core/src/main/java/org/eigenbase/rel/metadata/BuiltInMetadata.java
@@ -20,6 +20,7 @@ import java.util.*;
import org.eigenbase.rel.*;
import org.eigenbase.relopt.RelOptCost;
+import org.eigenbase.relopt.RelOptPredicateList;
import org.eigenbase.rex.RexNode;
import org.eigenbase.sql.SqlExplainLevel;
@@ -207,9 +208,21 @@ public abstract class BuiltInMetadata {
Boolean isVisibleInExplain(SqlExplainLevel explainLevel);
}
+ /** Metadata about the predicates that hold in the rows emitted from a
+ * relational expression. */
+ public interface Predicates extends Metadata {
+ /**
+ * Derives the predicates that hold on rows emitted from a relational
+ * expression.
+ *
+ * @return Predicate list
+ */
+ RelOptPredicateList getPredicates();
+ }
+
/** The built-in forms of metadata. */
- interface All extends Selectivity, UniqueKeys, RowCount,
- DistinctRowCount, PercentageOriginalRows, ColumnUniqueness, ColumnOrigin {
+ interface All extends Selectivity, UniqueKeys, RowCount, DistinctRowCount,
+ PercentageOriginalRows, ColumnUniqueness, ColumnOrigin, Predicates {
}
}
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/c33e602f/core/src/main/java/org/eigenbase/rel/metadata/DefaultRelMetadataProvider.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/rel/metadata/DefaultRelMetadataProvider.java b/core/src/main/java/org/eigenbase/rel/metadata/DefaultRelMetadataProvider.java
index 8d58d88..0e7c8e6 100644
--- a/core/src/main/java/org/eigenbase/rel/metadata/DefaultRelMetadataProvider.java
+++ b/core/src/main/java/org/eigenbase/rel/metadata/DefaultRelMetadataProvider.java
@@ -43,7 +43,8 @@ public class DefaultRelMetadataProvider extends ChainedRelMetadataProvider {
RelMdPopulationSize.SOURCE,
RelMdDistinctRowCount.SOURCE,
RelMdSelectivity.SOURCE,
- RelMdExplainVisibility.SOURCE));
+ RelMdExplainVisibility.SOURCE,
+ RelMdPredicates.SOURCE));
}
}
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/c33e602f/core/src/main/java/org/eigenbase/rel/metadata/RelMdPredicates.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/rel/metadata/RelMdPredicates.java b/core/src/main/java/org/eigenbase/rel/metadata/RelMdPredicates.java
new file mode 100644
index 0000000..98fb483
--- /dev/null
+++ b/core/src/main/java/org/eigenbase/rel/metadata/RelMdPredicates.java
@@ -0,0 +1,667 @@
+/*
+// Licensed to the Apache Software Foundation (ASF) under one or more
+// contributor license agreements. See the NOTICE file distributed with
+// this work for additional information regarding copyright ownership.
+// The ASF licenses this file to you under the Apache License, Version 2.0
+// (the "License"); you may not use this file except in compliance with
+// the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+*/
+package org.eigenbase.rel.metadata;
+
+import java.util.ArrayList;
+import java.util.BitSet;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.SortedMap;
+import java.util.TreeMap;
+
+import org.eigenbase.rel.AggregateRelBase;
+import org.eigenbase.rel.FilterRelBase;
+import org.eigenbase.rel.JoinRelBase;
+import org.eigenbase.rel.JoinRelType;
+import org.eigenbase.rel.ProjectRelBase;
+import org.eigenbase.rel.RelNode;
+import org.eigenbase.rel.SortRel;
+import org.eigenbase.rel.TableAccessRelBase;
+import org.eigenbase.rel.UnionRelBase;
+import org.eigenbase.relopt.RelOptPredicateList;
+import org.eigenbase.relopt.RelOptUtil;
+import org.eigenbase.rex.RexBuilder;
+import org.eigenbase.rex.RexCall;
+import org.eigenbase.rex.RexInputRef;
+import org.eigenbase.rex.RexNode;
+import org.eigenbase.rex.RexPermuteInputsShuttle;
+import org.eigenbase.rex.RexUtil;
+import org.eigenbase.rex.RexVisitorImpl;
+import org.eigenbase.sql.SqlKind;
+import org.eigenbase.util.mapping.Mapping;
+import org.eigenbase.util.mapping.MappingType;
+import org.eigenbase.util.mapping.Mappings;
+
+import net.hydromatic.linq4j.Ord;
+
+import net.hydromatic.optiq.BuiltinMethod;
+import net.hydromatic.optiq.util.BitSets;
+
+import com.google.common.base.Function;
+import com.google.common.base.Predicate;
+import com.google.common.collect.FluentIterable;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Iterators;
+import com.google.common.collect.Lists;
+
+/**
+ * Utility to infer Predicates that are applicable above a RelNode.
+ *
+ * <p>This is currently used by
+ * {@link org.eigenbase.rel.rules.TransitivePredicatesOnJoinRule} to
+ * infer <em>Predicates</em> that can be inferred from one side of a Join
+ * to the other.
+ *
+ * <p>The PullUp Strategy is sound but not complete. Here are some of the
+ * limitations:
+ * <ol>
+ *
+ * <li> For Aggregations we only PullUp predicates that only contain
+ * Grouping Keys. This can be extended to infer predicates on Aggregation
+ * expressions from expressions on the aggregated columns. For e.g.
+ * <pre>
+ * select a, max(b) from R1 where b > 7 => max(b) > 7 or max(b) is null
+ * </pre>
+ *
+ * <li> For Projections we only look at columns that are projected without
+ * any function applied. So:
+ * <pre>
+ * select a from R1 where a > 7 -> a > 7 is pulledUp from the Projection.
+ * select a + 1 from R1 where a + 1 > 7 -> a + 1 > 7 is not pulledUp
+ * </pre>
+ *
+ * <li> There are several restrictions on Joins:
+ * <ul>
+ * <li> We only pullUp inferred predicates for now. Pulling up existing
+ * predicates causes an explosion of duplicates. The existing predicates
+ * are pushed back down as new predicates. Once we have rules to eliminate
+ * duplicate Filter conditions, we should pullUp all predicates.
+ *
+ * <li> For Left Outer: we infer new predicates from the left and set them
+ * as applicable on the Right side. No predicates are pulledUp.
+ *
+ * <li> Right Outer Joins are handled in an analogous manner.
+ *
+ * <li> For Full Outer Joins no predicates are pulledUp or inferred.
+ * </ul>
+ * </ol>
+ */
+public class RelMdPredicates {
+ public static final RelMetadataProvider SOURCE = ReflectiveRelMetadataProvider
+ .reflectiveSource(BuiltinMethod.PREDICATES.method, new RelMdPredicates());
+
+ private static final List<RexNode> EMPTY_LIST = ImmutableList.of();
+
+ // Catch-all rule when none of the others apply.
+ public RelOptPredicateList getPredicates(RelNode rel) {
+ return RelOptPredicateList.EMPTY;
+ }
+
+ /**
+ * Infers predicates for a table scan.
+ */
+ public RelOptPredicateList getPredicates(TableAccessRelBase table) {
+ return RelOptPredicateList.EMPTY;
+ }
+
+ /**
+ * Infers predicates for a project.
+ *
+ * <ol>
+ * <li>create a mapping from input to projection. Map only positions that
+ * directly reference an input column.
+ * <li>Expressions that only contain above columns are retained in the
+ * Project's pullExpressions list.
+ * <li>For e.g. expression 'a + e = 9' below will not be pulled up because 'e'
+ * is not in the projection list.
+ *
+ * <pre>
+ * childPullUpExprs: {a > 7, b + c < 10, a + e = 9}
+ * projectionExprs: {a, b, c, e / 2}
+ * projectionPullupExprs: {a > 7, b + c < 10}
+ * </pre>
+ *
+ * </ol>
+ */
+ public RelOptPredicateList getPredicates(ProjectRelBase project) {
+ RelNode child = project.getChild();
+ RelOptPredicateList childInfo =
+ RelMetadataQuery.getPulledUpPredicates(child);
+
+ List<RexNode> projectPullUpPredicates = new ArrayList<RexNode>();
+
+ BitSet columnsMapped = new BitSet(child.getRowType().getFieldCount());
+ Mapping m = Mappings.create(MappingType.PARTIAL_FUNCTION,
+ child.getRowType().getFieldCount(),
+ project.getRowType().getFieldCount());
+
+ for (Ord<RexNode> o : Ord.zip(project.getProjects())) {
+ if (o.e instanceof RexInputRef) {
+ int sIdx = ((RexInputRef) o.e).getIndex();
+ m.set(sIdx, o.i);
+ columnsMapped.set(sIdx);
+ }
+ }
+
+ // Go over childPullUpPredicates. If a predicate only contains columns in
+ // 'columnsMapped' construct a new predicate based on mapping.
+ for (RexNode r : childInfo.pulledUpPredicates) {
+ BitSet rCols = RelOptUtil.InputFinder.bits(r);
+ if (BitSets.contains(columnsMapped, rCols)) {
+ r = r.accept(new RexPermuteInputsShuttle(m, child));
+ projectPullUpPredicates.add(r);
+ }
+ }
+ return RelOptPredicateList.of(projectPullUpPredicates);
+ }
+
+ /**
+ * Add the Filter condition to the pulledPredicates list from the child.
+ */
+ public RelOptPredicateList getPredicates(FilterRelBase filter) {
+ RelNode child = filter.getChild();
+ RelOptPredicateList childInfo =
+ RelMetadataQuery.getPulledUpPredicates(child);
+
+ return RelOptPredicateList.of(
+ Iterables.concat(childInfo.pulledUpPredicates,
+ RelOptUtil.conjunctions(filter.getCondition())));
+ }
+
+ public RelOptPredicateList getPredicates(JoinRelBase join) {
+ RexBuilder rB = join.getCluster().getRexBuilder();
+ RelNode left = join.getInput(0);
+ RelNode right = join.getInput(1);
+
+ RelOptPredicateList leftInfo =
+ RelMetadataQuery.getPulledUpPredicates(left);
+ RelOptPredicateList rightInfo =
+ RelMetadataQuery.getPulledUpPredicates(right);
+
+ JoinConditionBasedPredicateInference jI =
+ new JoinConditionBasedPredicateInference(join,
+ RexUtil.composeConjunction(rB, leftInfo.pulledUpPredicates, false),
+ RexUtil.composeConjunction(rB, rightInfo.pulledUpPredicates,
+ false));
+
+ return jI.inferPredicates(false);
+ }
+
+ /**
+ * Infers predicates for an AggregateRel.
+ *
+ * <p>Pulls up predicates that only contains references to columns in the
+ * GroupSet. For e.g.
+ *
+ * <pre>
+ * childPullUpExprs : { a > 7, b + c < 10, a + e = 9}
+ * groupSet : { a, b}
+ * pulledUpExprs : { a > 7}
+ * </pre>
+ */
+ public RelOptPredicateList getPredicates(AggregateRelBase agg) {
+ RelNode child = agg.getChild();
+ RelOptPredicateList childInfo =
+ RelMetadataQuery.getPulledUpPredicates(child);
+
+ List<RexNode> aggPullUpPredicates = new ArrayList<RexNode>();
+
+ BitSet groupKeys = agg.getGroupSet();
+ Mapping m = Mappings.create(MappingType.PARTIAL_FUNCTION,
+ child.getRowType().getFieldCount(), agg.getRowType().getFieldCount());
+
+ int i = 0;
+ for (int j : BitSets.toIter(groupKeys)) {
+ m.set(j, i++);
+ }
+
+ for (RexNode r : childInfo.pulledUpPredicates) {
+ BitSet rCols = RelOptUtil.InputFinder.bits(r);
+ if (BitSets.contains(groupKeys, rCols)) {
+ r = r.accept(new RexPermuteInputsShuttle(m, child));
+ aggPullUpPredicates.add(r);
+ }
+ }
+ return RelOptPredicateList.of(aggPullUpPredicates);
+ }
+
+ /**
+ * Infers predicates for a UnionRelBase.
+ *
+ * <p>The pulled up expression is a disjunction of its children's predicates.
+ */
+ public RelOptPredicateList getPredicates(UnionRelBase union) {
+ RexBuilder rB = union.getCluster().getRexBuilder();
+ List<RexNode> orList = Lists.newArrayList();
+ for (RelNode input : union.getInputs()) {
+ RelOptPredicateList info = RelMetadataQuery.getPulledUpPredicates(input);
+ if (!info.pulledUpPredicates.isEmpty()) {
+ orList.addAll(
+ RelOptUtil.disjunctions(
+ RexUtil.composeConjunction(rB, info.pulledUpPredicates,
+ false)));
+ }
+ }
+
+ if (orList.isEmpty()) {
+ return RelOptPredicateList.EMPTY;
+ }
+ return RelOptPredicateList.of(
+ RelOptUtil.conjunctions(RexUtil.composeDisjunction(rB, orList, false)));
+ }
+
+ /**
+ * Infers predicates for a SortRel.
+ */
+ public RelOptPredicateList getPredicates(SortRel sort) {
+ RelNode child = sort.getInput(0);
+ return RelMetadataQuery.getPulledUpPredicates(child);
+ }
+
+ /**
+ * Utility to infer predicates from one side of the join that apply on the
+ * other side. Contract is: - initialize with a {@link JoinRelBase} and
+ * optional predicates applicable on its left and right subtrees. - you can
+ * then ask it for equivalentPredicate(s) given a predicate.
+ * <p>
+ * So for:
+ * <ol>
+ * <li>'<code>R1(x) join R2(y) on x = y</code>' a call for
+ * equivalentPredciates on '<code>x > 7</code>' will return '
+ * <code>[y > 7]</code>'
+ * <li>'<code>R1(x) join R2(y) on x = y join R3(z) on y = z</code>' a call for
+ * equivalentPredciates on the second join '<code>x > 7</code>' will return '
+ * <code>[y > 7, z > 7]</code>'
+ * </ol>
+ */
+ static class JoinConditionBasedPredicateInference {
+ final JoinRelBase joinRel;
+ final int nSysFields;
+ final int nFieldsLeft;
+ final int nFieldsRight;
+ final BitSet leftFieldsBitSet;
+ final BitSet rightFieldsBitSet;
+ final BitSet allFieldsBitSet;
+ SortedMap<Integer, BitSet> equivalence;
+ final Map<String, BitSet> exprFields;
+ final Set<String> allExprsDigests;
+ final Set<String> equalityPredicates;
+ final RexNode leftChildPredicates;
+ final RexNode rightChildPredicates;
+
+ public JoinConditionBasedPredicateInference(JoinRelBase joinRel,
+ RexNode lPreds, RexNode rPreds) {
+ super();
+ this.joinRel = joinRel;
+ nFieldsLeft = joinRel.getLeft().getRowType().getFieldList().size();
+ nFieldsRight = joinRel.getRight().getRowType().getFieldList().size();
+ nSysFields = joinRel.getSystemFieldList().size();
+ leftFieldsBitSet = BitSets.range(nSysFields, nSysFields + nFieldsLeft);
+ rightFieldsBitSet = BitSets.range(nSysFields + nFieldsLeft,
+ nSysFields + nFieldsLeft + nFieldsRight);
+ allFieldsBitSet = BitSets.range(0,
+ nSysFields + nFieldsLeft + nFieldsRight);
+
+ exprFields = new HashMap<String, BitSet>();
+ allExprsDigests = new HashSet<String>();
+
+ if (lPreds == null) {
+ leftChildPredicates = null;
+ } else {
+ Mappings.TargetMapping leftMapping = Mappings.createShiftMapping(
+ nSysFields + nFieldsLeft, nSysFields, 0, nFieldsLeft);
+ leftChildPredicates = lPreds.accept(
+ new RexPermuteInputsShuttle(leftMapping, joinRel.getInput(0)));
+
+ for (RexNode r : RelOptUtil.conjunctions(leftChildPredicates)) {
+ exprFields.put(r.toString(), RelOptUtil.InputFinder.bits(r));
+ allExprsDigests.add(r.toString());
+ }
+ }
+ if (rPreds == null) {
+ rightChildPredicates = null;
+ } else {
+ Mappings.TargetMapping rightMapping = Mappings.createShiftMapping(
+ nSysFields + nFieldsLeft + nFieldsRight,
+ nSysFields + nFieldsLeft, 0, nFieldsRight);
+ rightChildPredicates = rPreds.accept(
+ new RexPermuteInputsShuttle(rightMapping, joinRel.getInput(1)));
+
+ for (RexNode r : RelOptUtil.conjunctions(rightChildPredicates)) {
+ exprFields.put(r.toString(), RelOptUtil.InputFinder.bits(r));
+ allExprsDigests.add(r.toString());
+ }
+ }
+
+ equivalence = new TreeMap<Integer, BitSet>();
+ equalityPredicates = new HashSet<String>();
+ for (int i = 0; i < nSysFields + nFieldsLeft + nFieldsRight; i++) {
+ equivalence.put(i, BitSets.of(i));
+ }
+
+ // Only process equivalences found in the join conditions. Processing
+ // Equivalences from the left or right side infer predicates that are
+ // already present in the Tree below the join.
+ RexBuilder rexBuilder = joinRel.getCluster().getRexBuilder();
+ List<RexNode> exprs =
+ RelOptUtil.conjunctions(
+ compose(rexBuilder, ImmutableList.of(joinRel.getCondition())));
+
+ final EquivalenceFinder eF = new EquivalenceFinder();
+ new ArrayList<Void>(Lists.transform(exprs, new Function<RexNode, Void>() {
+ public Void apply(RexNode input) {
+ return input.accept(eF);
+ }
+ }));
+
+ equivalence = BitSets.closure(equivalence);
+ }
+
+ /**
+ * The PullUp Strategy is sound but not complete.
+ * <ol>
+ * <li>We only pullUp inferred predicates for now. Pulling up existing
+ * predicates causes an explosion of duplicates. The existing predicates are
+ * pushed back down as new predicates. Once we have rules to eliminate
+ * duplicate Filter conditions, we should pullUp all predicates.
+ * <li>For Left Outer: we infer new predicates from the left and set them as
+ * applicable on the Right side. No predicates are pulledUp.
+ * <li>Right Outer Joins are handled in an analogous manner.
+ * <li>For Full Outer Joins no predicates are pulledUp or inferred.
+ * </ol>
+ */
+ public RelOptPredicateList inferPredicates(
+ boolean includeEqualityInference) {
+ List<RexNode> inferredPredicates = new ArrayList<RexNode>();
+ Set<String> allExprsDigests = new HashSet<String>(this.allExprsDigests);
+ final JoinRelType joinType = joinRel.getJoinType();
+ switch (joinType) {
+ case INNER:
+ case LEFT:
+ infer(leftChildPredicates, allExprsDigests, inferredPredicates,
+ includeEqualityInference,
+ joinType == JoinRelType.LEFT ? rightFieldsBitSet
+ : allFieldsBitSet);
+ break;
+ }
+ switch (joinType) {
+ case INNER:
+ case RIGHT:
+ infer(rightChildPredicates, allExprsDigests, inferredPredicates,
+ includeEqualityInference,
+ joinType == JoinRelType.RIGHT ? leftFieldsBitSet
+ : allFieldsBitSet);
+ break;
+ }
+
+ Mappings.TargetMapping rightMapping = Mappings.createShiftMapping(
+ nSysFields + nFieldsLeft + nFieldsRight,
+ 0, nSysFields + nFieldsLeft, nFieldsRight);
+ final RexPermuteInputsShuttle rightPermute =
+ new RexPermuteInputsShuttle(rightMapping, joinRel);
+ Mappings.TargetMapping leftMapping = Mappings.createShiftMapping(
+ nSysFields + nFieldsLeft, 0, nSysFields, nFieldsLeft);
+ final RexPermuteInputsShuttle leftPermute =
+ new RexPermuteInputsShuttle(leftMapping, joinRel);
+ List<RexNode> leftInferredPredicates = new ArrayList<RexNode>();
+ List<RexNode> rightInferredPredicates = new ArrayList<RexNode>();
+
+ for (RexNode iP : inferredPredicates) {
+ BitSet iPBitSet = RelOptUtil.InputFinder.bits(iP);
+ if (BitSets.contains(leftFieldsBitSet, iPBitSet)) {
+ leftInferredPredicates.add(iP.accept(leftPermute));
+ } else if (BitSets.contains(rightFieldsBitSet, iPBitSet)) {
+ rightInferredPredicates.add(iP.accept(rightPermute));
+ }
+ }
+
+ switch (joinType) {
+ case INNER:
+ return RelOptPredicateList.of(
+ Iterables.concat(RelOptUtil.conjunctions(leftChildPredicates),
+ RelOptUtil.conjunctions(rightChildPredicates),
+ RelOptUtil.conjunctions(joinRel.getCondition()),
+ inferredPredicates),
+ leftInferredPredicates, rightInferredPredicates);
+ case LEFT:
+ return RelOptPredicateList.of(
+ RelOptUtil.conjunctions(leftChildPredicates),
+ leftInferredPredicates, rightInferredPredicates);
+ case RIGHT:
+ return RelOptPredicateList.of(
+ RelOptUtil.conjunctions(rightChildPredicates),
+ inferredPredicates, EMPTY_LIST);
+ default:
+ assert inferredPredicates.size() == 0;
+ return RelOptPredicateList.EMPTY;
+ }
+ }
+
+ public RexNode left() {
+ return leftChildPredicates;
+ }
+
+ public RexNode right() {
+ return rightChildPredicates;
+ }
+
+ private void infer(RexNode predicates, Set<String> allExprsDigests,
+ List<RexNode> inferedPredicates, boolean includeEqualityInference,
+ BitSet inferringFields) {
+ for (RexNode r : RelOptUtil.conjunctions(predicates)) {
+ if (!includeEqualityInference
+ && equalityPredicates.contains(r.toString())) {
+ continue;
+ }
+ for (Mapping m : mappings(r)) {
+ RexNode tr = r.accept(
+ new RexPermuteInputsShuttle(m, joinRel.getInput(0),
+ joinRel.getInput(1)));
+ if (BitSets.contains(inferringFields, RelOptUtil.InputFinder.bits(tr))
+ && !allExprsDigests.contains(tr.toString())
+ && !isAlwaysTrue(tr)) {
+ inferedPredicates.add(tr);
+ allExprsDigests.add(tr.toString());
+ }
+ }
+ }
+ }
+
+ Iterable<Mapping> mappings(final RexNode predicate) {
+ return new Iterable<Mapping>() {
+ public Iterator<Mapping> iterator() {
+ BitSet fields = exprFields.get(predicate.toString());
+ if (fields.cardinality() == 0) {
+ return Iterators.emptyIterator();
+ }
+ return new ExprsItr(fields);
+ }
+ };
+ }
+
+ private void equivalent(int p1, int p2) {
+ BitSet b = equivalence.get(p1);
+ b.set(p2);
+
+ b = equivalence.get(p2);
+ b.set(p1);
+ }
+
+ RexNode compose(RexBuilder rexBuilder, Iterable<RexNode> exprs) {
+ exprs = FluentIterable.from(exprs).filter(new Predicate<RexNode>() {
+ public boolean apply(RexNode expr) {
+ return expr != null;
+ }
+ });
+ return RexUtil.composeConjunction(rexBuilder, exprs, false);
+ }
+
+ /**
+ * Find expressions of the form 'col_x = col_y'.
+ */
+ class EquivalenceFinder extends RexVisitorImpl<Void> {
+ protected EquivalenceFinder() {
+ super(true);
+ }
+
+ @Override
+ public Void visitCall(RexCall call) {
+ if (call.getOperator().getKind() == SqlKind.EQUALS) {
+ int lPos = pos(call.getOperands().get(0));
+ int rPos = pos(call.getOperands().get(1));
+ if (lPos != -1 && rPos != -1) {
+ JoinConditionBasedPredicateInference.this.equivalent(lPos, rPos);
+ JoinConditionBasedPredicateInference.this.equalityPredicates
+ .add(call.toString());
+ }
+ }
+ return null;
+ }
+ }
+
+ /**
+ * Given an expression returns all the possible substitutions.
+ *
+ * <p>For example, for an expression 'a + b + c' and the following
+ * equivalences: <pre>
+ * a : {a, b}
+ * b : {a, b}
+ * c : {c, e}
+ * </pre>
+ *
+ * <p>The following Mappings will be returned:
+ * <pre>
+ * {a->a, b->a, c->c}
+ * {a->a, b->a, c->e}
+ * {a->a, b->b, c->c}
+ * {a->a, b->b, c->e}
+ * {a->b, b->a, c->c}
+ * {a->b, b->a, c->e}
+ * {a->b, b->b, c->c}
+ * {a->b, b->b, c->e}
+ * </pre>
+ *
+ * <p>which imply the following inferences:
+ * <pre>
+ * a + a + c
+ * a + a + e
+ * a + b + c
+ * a + b + e
+ * b + a + c
+ * b + a + e
+ * b + b + c
+ * b + b + e
+ * </pre>
+ */
+ class ExprsItr implements Iterator<Mapping> {
+ final int[] columns;
+ final BitSet[] columnSets;
+ final int[] iterationIdx;
+ Mapping nextMapping;
+ boolean firstCall;
+
+ ExprsItr(BitSet fields) {
+ nextMapping = null;
+ columns = new int[fields.cardinality()];
+ columnSets = new BitSet[fields.cardinality()];
+ iterationIdx = new int[fields.cardinality()];
+ for (int j = 0, i = fields.nextSetBit(0); i >= 0; i = fields
+ .nextSetBit(i + 1), j++) {
+ columns[j] = i;
+ columnSets[j] = equivalence.get(i);
+ iterationIdx[j] = 0;
+ }
+ firstCall = true;
+ }
+
+ public boolean hasNext() {
+ if (firstCall) {
+ initializeMapping();
+ firstCall = false;
+ } else {
+ computeNextMapping(iterationIdx.length - 1);
+ }
+ return nextMapping != null;
+ }
+
+ public Mapping next() {
+ return nextMapping;
+ }
+
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+
+ private void computeNextMapping(int level) {
+ int t = columnSets[level].nextSetBit(iterationIdx[level]);
+ if (t < 0) {
+ if (level == 0) {
+ nextMapping = null;
+ } else {
+ iterationIdx[level] = 0;
+ computeNextMapping(level - 1);
+ }
+ } else {
+ nextMapping.set(columns[level], t);
+ iterationIdx[level] = t + 1;
+ }
+ }
+
+ private void initializeMapping() {
+ nextMapping = Mappings.create(MappingType.PARTIAL_FUNCTION,
+ nSysFields + nFieldsLeft + nFieldsRight,
+ nSysFields + nFieldsLeft + nFieldsRight);
+ for (int i = 0; i < columnSets.length; i++) {
+ BitSet c = columnSets[i];
+ int t = c.nextSetBit(iterationIdx[i]);
+ if (t < 0) {
+ nextMapping = null;
+ return;
+ }
+ nextMapping.set(columns[i], t);
+ iterationIdx[i] = t + 1;
+ }
+ }
+ }
+
+ private int pos(RexNode expr) {
+ if (expr instanceof RexInputRef) {
+ return ((RexInputRef) expr).getIndex();
+ }
+ return -1;
+ }
+
+ private boolean isAlwaysTrue(RexNode predicate) {
+ if (predicate instanceof RexCall) {
+ RexCall c = (RexCall) predicate;
+ if (c.getOperator().getKind() == SqlKind.EQUALS) {
+ int lPos = pos(c.getOperands().get(0));
+ int rPos = pos(c.getOperands().get(1));
+ return lPos != -1 && lPos == rPos;
+ }
+ }
+ return predicate.isAlwaysTrue();
+ }
+ }
+}
+
+// End RelMdPredicates.java
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/c33e602f/core/src/main/java/org/eigenbase/rel/metadata/RelMetadataQuery.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/rel/metadata/RelMetadataQuery.java b/core/src/main/java/org/eigenbase/rel/metadata/RelMetadataQuery.java
index 5f6f3a4..e2ac524 100644
--- a/core/src/main/java/org/eigenbase/rel/metadata/RelMetadataQuery.java
+++ b/core/src/main/java/org/eigenbase/rel/metadata/RelMetadataQuery.java
@@ -329,6 +329,20 @@ public abstract class RelMetadataQuery {
/**
* Returns the
+ * {@link org.eigenbase.rel.metadata.BuiltInMetadata.Predicates#getPredicates()}
+ * statistic.
+ *
+ * @param rel the relational expression
+ * @return Predicates that can be pulled above this RelNode
+ */
+ public static RelOptPredicateList getPulledUpPredicates(RelNode rel) {
+ final BuiltInMetadata.Predicates metadata =
+ rel.metadata(BuiltInMetadata.Predicates.class);
+ return metadata.getPredicates();
+ }
+
+ /**
+ * Returns the
* {@link BuiltInMetadata.ExplainVisibility#isVisibleInExplain(SqlExplainLevel)}
* statistic.
*
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/c33e602f/core/src/main/java/org/eigenbase/rel/rules/TransitivePredicatesOnJoinRule.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/rel/rules/TransitivePredicatesOnJoinRule.java b/core/src/main/java/org/eigenbase/rel/rules/TransitivePredicatesOnJoinRule.java
new file mode 100644
index 0000000..bcecb48
--- /dev/null
+++ b/core/src/main/java/org/eigenbase/rel/rules/TransitivePredicatesOnJoinRule.java
@@ -0,0 +1,86 @@
+/*
+// Licensed to the Apache Software Foundation (ASF) under one or more
+// contributor license agreements. See the NOTICE file distributed with
+// this work for additional information regarding copyright ownership.
+// The ASF licenses this file to you under the Apache License, Version 2.0
+// (the "License"); you may not use this file except in compliance with
+// the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+*/
+package org.eigenbase.rel.rules;
+
+import org.eigenbase.rel.JoinRelBase;
+import org.eigenbase.rel.RelFactories;
+import org.eigenbase.rel.RelNode;
+import org.eigenbase.rel.metadata.RelMetadataQuery;
+import org.eigenbase.relopt.RelOptPredicateList;
+import org.eigenbase.relopt.RelOptRule;
+import org.eigenbase.relopt.RelOptRuleCall;
+import org.eigenbase.rex.RexBuilder;
+import org.eigenbase.rex.RexUtil;
+
+/**
+ * A Rule to apply inferred predicates from
+ * {@link org.eigenbase.rel.metadata.RelMdPredicates}.
+ *
+ * <p>Predicates returned in {@link org.eigenbase.relopt.RelOptPredicateList}
+ * are applied appropriately.
+ */
+public class TransitivePredicatesOnJoinRule extends RelOptRule {
+ private final RelFactories.FilterFactory filterFactory;
+
+ /** The singleton. */
+ public static final TransitivePredicatesOnJoinRule INSTANCE =
+ new TransitivePredicatesOnJoinRule(JoinRelBase.class,
+ RelFactories.DEFAULT_FILTER_FACTORY);
+
+ public TransitivePredicatesOnJoinRule(Class<? extends JoinRelBase> clazz,
+ RelFactories.FilterFactory filterFactory) {
+ super(operand(clazz, any()));
+ this.filterFactory = filterFactory;
+ }
+
+ @Override
+ public void onMatch(RelOptRuleCall call) {
+ JoinRelBase join = call.rel(0);
+ RelOptPredicateList preds = RelMetadataQuery.getPulledUpPredicates(join);
+
+ if (preds.leftInferredPredicates.isEmpty()
+ && preds.rightInferredPredicates.isEmpty()) {
+ return;
+ }
+
+ RexBuilder rB = join.getCluster().getRexBuilder();
+ RelNode lChild = join.getLeft();
+ RelNode rChild = join.getRight();
+
+ if (preds.leftInferredPredicates.size() > 0) {
+ RelNode curr = lChild;
+ lChild = filterFactory.createFilter(lChild,
+ RexUtil.composeConjunction(rB, preds.leftInferredPredicates, false));
+ call.getPlanner().onCopy(curr, lChild);
+ }
+
+ if (preds.rightInferredPredicates.size() > 0) {
+ RelNode curr = rChild;
+ rChild = filterFactory.createFilter(rChild,
+ RexUtil.composeConjunction(rB, preds.rightInferredPredicates, false));
+ call.getPlanner().onCopy(curr, rChild);
+ }
+
+ RelNode newRel = join.copy(join.getTraitSet(), join.getCondition(),
+ lChild, rChild, join.getJoinType(), join.isSemiJoinDone());
+ call.getPlanner().onCopy(join, newRel);
+
+ call.transformTo(newRel);
+ }
+}
+
+// End TransitivePredicatesOnJoinRule.java
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/c33e602f/core/src/main/java/org/eigenbase/relopt/RelOptPredicateList.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/relopt/RelOptPredicateList.java b/core/src/main/java/org/eigenbase/relopt/RelOptPredicateList.java
new file mode 100644
index 0000000..60e459f
--- /dev/null
+++ b/core/src/main/java/org/eigenbase/relopt/RelOptPredicateList.java
@@ -0,0 +1,74 @@
+/*
+// Licensed to the Apache Software Foundation (ASF) under one or more
+// contributor license agreements. See the NOTICE file distributed with
+// this work for additional information regarding copyright ownership.
+// The ASF licenses this file to you under the Apache License, Version 2.0
+// (the "License"); you may not use this file except in compliance with
+// the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+*/
+package org.eigenbase.relopt;
+
+import org.eigenbase.rex.RexNode;
+
+import com.google.common.collect.ImmutableList;
+
+/**
+ * Predicates that are known to hold in the output of a particular relational
+ * expression.
+ */
+public class RelOptPredicateList {
+ private static final ImmutableList<RexNode> EMPTY_LIST = ImmutableList.of();
+ public static final RelOptPredicateList EMPTY =
+ new RelOptPredicateList(EMPTY_LIST, EMPTY_LIST, EMPTY_LIST);
+
+ public final ImmutableList<RexNode> pulledUpPredicates;
+ public final ImmutableList<RexNode> leftInferredPredicates;
+ public final ImmutableList<RexNode> rightInferredPredicates;
+
+ private RelOptPredicateList(Iterable<RexNode> pulledUpPredicates,
+ Iterable<RexNode> leftInferredPredicates,
+ Iterable<RexNode> rightInferredPredicates) {
+ this.pulledUpPredicates = ImmutableList.copyOf(pulledUpPredicates);
+ this.leftInferredPredicates = ImmutableList.copyOf(leftInferredPredicates);
+ this.rightInferredPredicates =
+ ImmutableList.copyOf(rightInferredPredicates);
+ }
+
+ public static RelOptPredicateList of(Iterable<RexNode> pulledUpPredicates) {
+ ImmutableList<RexNode> pulledUpPredicatesList =
+ ImmutableList.copyOf(pulledUpPredicates);
+ if (pulledUpPredicatesList.isEmpty()) {
+ return EMPTY;
+ }
+ return new RelOptPredicateList(pulledUpPredicatesList, EMPTY_LIST,
+ EMPTY_LIST);
+ }
+
+ public static RelOptPredicateList of(Iterable<RexNode> pulledUpPredicates,
+ Iterable<RexNode> leftInferredPredicates,
+ Iterable<RexNode> rightInferredPredicates) {
+ final ImmutableList<RexNode> pulledUpPredicatesList =
+ ImmutableList.copyOf(pulledUpPredicates);
+ final ImmutableList<RexNode> leftInferredPredicateList =
+ ImmutableList.copyOf(leftInferredPredicates);
+ final ImmutableList<RexNode> rightInferredPredicatesList =
+ ImmutableList.copyOf(rightInferredPredicates);
+ if (pulledUpPredicatesList.isEmpty()
+ && leftInferredPredicateList.isEmpty()
+ && rightInferredPredicatesList.isEmpty()) {
+ return EMPTY;
+ }
+ return new RelOptPredicateList(pulledUpPredicatesList,
+ leftInferredPredicateList, rightInferredPredicatesList);
+ }
+}
+
+// End RelOptPulledUpPredicates.java
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/c33e602f/core/src/main/java/org/eigenbase/relopt/RelOptUtil.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/relopt/RelOptUtil.java b/core/src/main/java/org/eigenbase/relopt/RelOptUtil.java
index 59d67e2..9f00333 100644
--- a/core/src/main/java/org/eigenbase/relopt/RelOptUtil.java
+++ b/core/src/main/java/org/eigenbase/relopt/RelOptUtil.java
@@ -1764,7 +1764,8 @@ public abstract class RelOptUtil {
/**
* Returns a condition decomposed by AND.
*
- * <p>For example, {@code conjunctions(TRUE)} returns the empty list.</p>
+ * <p>For example, {@code conjunctions(TRUE)} returns the empty list;
+ * {@code conjunctions(FALSE)} returns list {@code {FALSE}}.</p>
*/
public static List<RexNode> conjunctions(RexNode rexPredicate) {
final List<RexNode> list = new ArrayList<RexNode>();
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/c33e602f/core/src/test/java/net/hydromatic/optiq/util/BitSetsTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/net/hydromatic/optiq/util/BitSetsTest.java b/core/src/test/java/net/hydromatic/optiq/util/BitSetsTest.java
index ae11b69..8bc4d75 100644
--- a/core/src/test/java/net/hydromatic/optiq/util/BitSetsTest.java
+++ b/core/src/test/java/net/hydromatic/optiq/util/BitSetsTest.java
@@ -18,11 +18,14 @@ package net.hydromatic.optiq.util;
import org.eigenbase.util.ImmutableIntList;
+import com.google.common.collect.Maps;
+
import org.junit.Test;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Collections;
+import java.util.SortedMap;
import static org.hamcrest.CoreMatchers.equalTo;
import static org.junit.Assert.assertEquals;
@@ -186,6 +189,36 @@ public class BitSetsTest {
equalTo(-1));
assertThat(BitSets.previousClearBit(BitSets.of(1, 3, 4), 1), equalTo(0));
}
+
+ /**
+ * Tests the method {@link BitSets#closure(java.util.SortedMap)}
+ */
+ @Test public void testClosure() {
+ final SortedMap<Integer, BitSet> empty = Maps.newTreeMap();
+ assertThat(BitSets.closure(empty), equalTo(empty));
+
+ // Currently you need an entry for each position, otherwise you get an NPE.
+ // We should fix that.
+ final SortedMap<Integer, BitSet> map = Maps.newTreeMap();
+ map.put(0, BitSets.of(3));
+ map.put(1, BitSets.of());
+ map.put(2, BitSets.of(7));
+ map.put(3, BitSets.of(4, 12));
+ map.put(4, BitSets.of());
+ map.put(5, BitSets.of());
+ map.put(6, BitSets.of());
+ map.put(7, BitSets.of());
+ map.put(8, BitSets.of());
+ map.put(9, BitSets.of());
+ map.put(10, BitSets.of());
+ map.put(11, BitSets.of());
+ map.put(12, BitSets.of());
+ String original = map.toString();
+ assertThat(BitSets.closure(map).toString(),
+ equalTo(
+ "{0={3, 4, 12}, 1={}, 2={7}, 3={3, 4, 12}, 4={4, 12}, 5={}, 6={}, 7={7}, 8={}, 9={}, 10={}, 11={}, 12={4, 12}}"));
+ assertThat("argument modified", map.toString(), equalTo(original));
+ }
}
// End BitSetsTest.java
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/c33e602f/core/src/test/java/org/eigenbase/test/RelOptRulesTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/eigenbase/test/RelOptRulesTest.java b/core/src/test/java/org/eigenbase/test/RelOptRulesTest.java
index fa982fc..91347a0 100644
--- a/core/src/test/java/org/eigenbase/test/RelOptRulesTest.java
+++ b/core/src/test/java/org/eigenbase/test/RelOptRulesTest.java
@@ -16,9 +16,48 @@
*/
package org.eigenbase.test;
+import java.util.List;
+
+import org.eigenbase.rel.RelNode;
import org.eigenbase.rel.TableModificationRel;
-import org.eigenbase.rel.rules.*;
-import org.eigenbase.relopt.hep.*;
+import org.eigenbase.rel.metadata.CachingRelMetadataProvider;
+import org.eigenbase.rel.metadata.ChainedRelMetadataProvider;
+import org.eigenbase.rel.metadata.DefaultRelMetadataProvider;
+import org.eigenbase.rel.metadata.RelMetadataProvider;
+import org.eigenbase.rel.rules.AddRedundantSemiJoinRule;
+import org.eigenbase.rel.rules.CoerceInputsRule;
+import org.eigenbase.rel.rules.ConvertMultiJoinRule;
+import org.eigenbase.rel.rules.ExtractJoinFilterRule;
+import org.eigenbase.rel.rules.FilterToCalcRule;
+import org.eigenbase.rel.rules.MergeCalcRule;
+import org.eigenbase.rel.rules.MergeProjectRule;
+import org.eigenbase.rel.rules.ProjectToCalcRule;
+import org.eigenbase.rel.rules.PullConstantsThroughAggregatesRule;
+import org.eigenbase.rel.rules.PushAggregateThroughUnionRule;
+import org.eigenbase.rel.rules.PushFilterPastJoinRule;
+import org.eigenbase.rel.rules.PushFilterPastProjectRule;
+import org.eigenbase.rel.rules.PushFilterPastSetOpRule;
+import org.eigenbase.rel.rules.PushJoinThroughUnionRule;
+import org.eigenbase.rel.rules.PushProjectPastFilterRule;
+import org.eigenbase.rel.rules.PushProjectPastJoinRule;
+import org.eigenbase.rel.rules.PushProjectPastSetOpRule;
+import org.eigenbase.rel.rules.PushSemiJoinPastFilterRule;
+import org.eigenbase.rel.rules.PushSemiJoinPastJoinRule;
+import org.eigenbase.rel.rules.PushSemiJoinPastProjectRule;
+import org.eigenbase.rel.rules.ReduceAggregatesRule;
+import org.eigenbase.rel.rules.ReduceExpressionsRule;
+import org.eigenbase.rel.rules.ReduceValuesRule;
+import org.eigenbase.rel.rules.RemoveEmptyRules;
+import org.eigenbase.rel.rules.RemoveSemiJoinRule;
+import org.eigenbase.rel.rules.RemoveTrivialProjectRule;
+import org.eigenbase.rel.rules.TableAccessRule;
+import org.eigenbase.rel.rules.TransitivePredicatesOnJoinRule;
+import org.eigenbase.rel.rules.UnionToDistinctRule;
+import org.eigenbase.relopt.RelOptUtil;
+import org.eigenbase.relopt.hep.HepMatchOrder;
+import org.eigenbase.relopt.hep.HepPlanner;
+import org.eigenbase.relopt.hep.HepProgram;
+import org.eigenbase.relopt.hep.HepProgramBuilder;
import org.eigenbase.reltype.RelDataType;
import org.eigenbase.reltype.RelDataTypeFactory;
import org.eigenbase.sql.type.SqlTypeName;
@@ -26,10 +65,13 @@ import org.eigenbase.sql.type.SqlTypeName;
import net.hydromatic.optiq.prepare.Prepare;
import com.google.common.base.Function;
+import com.google.common.collect.Lists;
import org.junit.Ignore;
import org.junit.Test;
+import static org.junit.Assert.assertTrue;
+
/**
* Unit test for rules in {@code org.eigenbase.rel} and subpackages.
*
@@ -729,6 +771,123 @@ public class RelOptRulesTest extends RelOptTestBase {
throws Exception {
basePullConstantTroughAggregate();
}
+
+ public void transitiveInference() throws Exception {
+ final DiffRepository diffRepos = getDiffRepos();
+ String sql = diffRepos.expand(null, "${sql}");
+
+ HepProgram program = new HepProgramBuilder().addRuleCollection(
+ Lists.newArrayList(PushFilterPastJoinRule.FILTER_ON_JOIN,
+ PushFilterPastJoinRule.JOIN, PushFilterPastProjectRule.INSTANCE,
+ PushFilterPastSetOpRule.INSTANCE)).build();
+ HepPlanner planner = new HepPlanner(program);
+
+ RelNode relInitial = tester.convertSqlToRel(sql);
+
+ assertTrue(relInitial != null);
+
+ List<RelMetadataProvider> list = Lists.newArrayList();
+ DefaultRelMetadataProvider defaultProvider =
+ new DefaultRelMetadataProvider();
+ list.add(defaultProvider);
+ planner.registerMetadataProviders(list);
+ RelMetadataProvider plannerChain = ChainedRelMetadataProvider.of(list);
+ relInitial.getCluster().setMetadataProvider(
+ new CachingRelMetadataProvider(plannerChain, planner));
+
+ planner.setRoot(relInitial);
+ RelNode relAfter = planner.findBestExp();
+
+ String planBefore = NL + RelOptUtil.toString(relAfter);
+ diffRepos.assertEquals("planBefore", "${planBefore}", planBefore);
+
+ HepProgram program2 = new HepProgramBuilder()
+ .addMatchOrder(HepMatchOrder.BOTTOM_UP)
+ .addRuleCollection(
+ Lists.newArrayList(PushFilterPastJoinRule.FILTER_ON_JOIN,
+ PushFilterPastJoinRule.JOIN,
+ PushFilterPastProjectRule.INSTANCE,
+ PushFilterPastSetOpRule.INSTANCE,
+ TransitivePredicatesOnJoinRule.INSTANCE)).build();
+ HepPlanner planner2 = new HepPlanner(program2);
+ planner.registerMetadataProviders(list);
+ planner2.setRoot(relAfter);
+ relAfter = planner2.findBestExp();
+
+ String planAfter = NL + RelOptUtil.toString(relAfter);
+ diffRepos.assertEquals("planAfter", "${planAfter}", planAfter);
+ }
+
+ @Test public void testTransitiveInferenceJoin() throws Exception {
+ transitiveInference();
+ }
+
+ @Test public void testTransitiveInferenceProject() throws Exception {
+ transitiveInference();
+ }
+
+ @Test public void testTransitiveInferenceAggregate() throws Exception {
+ transitiveInference();
+ }
+
+ @Test public void testTransitiveInferenceUnion() throws Exception {
+ transitiveInference();
+ }
+
+ @Test public void testTransitiveInferenceJoin3way() throws Exception {
+ transitiveInference();
+ }
+
+ @Test public void testTransitiveInferenceJoin3wayAgg() throws Exception {
+ transitiveInference();
+ }
+
+ @Test public void testTransitiveInferenceLeftOuterJoin() throws Exception {
+ transitiveInference();
+ }
+
+ @Test public void testTransitiveInferenceRightOuterJoin() throws Exception {
+ transitiveInference();
+ }
+
+ @Test public void testTransitiveInferenceFullOuterJoin() throws Exception {
+ transitiveInference();
+ }
+
+ @Test public void testTransitiveInferencePreventProjectPullup()
+ throws Exception {
+ transitiveInference();
+ }
+
+ @Test public void testTransitiveInferencePullupThruAlias() throws Exception {
+ transitiveInference();
+ }
+
+ @Test public void testTransitiveInferenceConjunctInPullUp() throws Exception {
+ transitiveInference();
+ }
+
+ @Test public void testTransitiveInferenceNoPullUpExprs() throws Exception {
+ transitiveInference();
+ }
+
+ @Test public void testTransitiveInferenceUnion3way() throws Exception {
+ transitiveInference();
+ }
+
+ @Ignore("not working")
+ @Test public void testTransitiveInferenceUnion3wayOr() throws Exception {
+ transitiveInference();
+ }
+
+ @Test public void testTransitiveInferenceConstantEquiPredicate()
+ throws Exception {
+ transitiveInference();
+ }
+
+ @Test public void testTransitiveInferenceComplexPredicate() throws Exception {
+ transitiveInference();
+ }
}
// End RelOptRulesTest.java
http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/c33e602f/core/src/test/resources/org/eigenbase/test/RelOptRulesTest.xml
----------------------------------------------------------------------
diff --git a/core/src/test/resources/org/eigenbase/test/RelOptRulesTest.xml b/core/src/test/resources/org/eigenbase/test/RelOptRulesTest.xml
index f783941..e33ca4a 100644
--- a/core/src/test/resources/org/eigenbase/test/RelOptRulesTest.xml
+++ b/core/src/test/resources/org/eigenbase/test/RelOptRulesTest.xml
@@ -1494,4 +1494,513 @@ UnionRel(all=[true])
]]>
</Resource>
</TestCase>
+ <TestCase name="testTransitiveInferenceJoin">
+ <Resource name="sql">
+ <![CDATA[select 1 from sales.emp d inner join sales.emp e on d.deptno = e.deptno where e.deptno > 7]]>
+ </Resource>
+ <Resource name="planBefore">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($7, $16)], joinType=[inner])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ <Resource name="planAfter">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($7, $16)], joinType=[inner])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ </TestCase>
+ <TestCase name="testTransitiveInferenceProject">
+ <Resource name="sql">
+ <![CDATA[select 1 from (select * from sales.emp where deptno > 7) d inner join sales.emp e on d.deptno = e.deptno ]]>
+ </Resource>
+ <Resource name="planBefore">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($7, $16)], joinType=[inner])
+ ProjectRel(EMPNO=[$0], ENAME=[$1], JOB=[$2], MGR=[$3], HIREDATE=[$4], SAL=[$5], COMM=[$6], DEPTNO=[$7], SLACKER=[$8])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ <Resource name="planAfter">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($7, $16)], joinType=[inner])
+ ProjectRel(EMPNO=[$0], ENAME=[$1], JOB=[$2], MGR=[$3], HIREDATE=[$4], SAL=[$5], COMM=[$6], DEPTNO=[$7], SLACKER=[$8])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ </TestCase>
+ <TestCase name="testTransitiveInferenceAggregate">
+ <Resource name="sql">
+ <![CDATA[select 1 from (select deptno, count(*) from sales.emp where deptno > 7 group by deptno) d inner join sales.emp e on d.deptno = e.deptno ]]>
+ </Resource>
+ <Resource name="planBefore">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($0, $9)], joinType=[inner])
+ AggregateRel(group=[{0}], EXPR$1=[COUNT()])
+ ProjectRel(DEPTNO=[$7])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ <Resource name="planAfter">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($0, $9)], joinType=[inner])
+ AggregateRel(group=[{0}], EXPR$1=[COUNT()])
+ ProjectRel(DEPTNO=[$7])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ </TestCase>
+ <TestCase name="testTransitiveInferenceUnion">
+ <Resource name="sql">
+ <![CDATA[select 1 from (select deptno from sales.emp where deptno > 7 union all select deptno from sales.emp where deptno > 10) d inner join sales.emp e on d.deptno = e.deptno ]]>
+ </Resource>
+ <Resource name="planBefore">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($0, $8)], joinType=[inner])
+ UnionRel(all=[true])
+ ProjectRel(DEPTNO=[$7])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ ProjectRel(DEPTNO=[$7])
+ FilterRel(condition=[>($7, 10)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ <Resource name="planAfter">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($0, $8)], joinType=[inner])
+ UnionRel(all=[true])
+ ProjectRel(DEPTNO=[$7])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ ProjectRel(DEPTNO=[$7])
+ FilterRel(condition=[>($7, 10)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ FilterRel(condition=[OR(>($7, 7), >($7, 10))])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ </TestCase>
+ <TestCase name="testTransitiveInferenceJoin3way">
+ <Resource name="sql">
+ <![CDATA[select 1 from sales.emp d inner join sales.emp e on d.deptno = e.deptno inner join sales.emp f on e.deptno = f.deptno where d.deptno > 7]]>
+ </Resource>
+ <Resource name="planBefore">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($16, $25)], joinType=[inner])
+ JoinRel(condition=[=($7, $16)], joinType=[inner])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ <Resource name="planAfter">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($16, $25)], joinType=[inner])
+ JoinRel(condition=[=($7, $16)], joinType=[inner])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ </TestCase>
+ <TestCase name="testTransitiveInferenceJoin3wayAgg">
+ <Resource name="sql">
+ <![CDATA[select 1 from (select deptno, count(*) from sales.emp where deptno > 7 group by deptno) d inner join sales.emp e on d.deptno = e.deptno inner join sales.emp f on e.deptno = f.deptno ]]>
+ </Resource>
+ <Resource name="planBefore">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($9, $18)], joinType=[inner])
+ JoinRel(condition=[=($0, $9)], joinType=[inner])
+ AggregateRel(group=[{0}], EXPR$1=[COUNT()])
+ ProjectRel(DEPTNO=[$7])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ <Resource name="planAfter">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($9, $18)], joinType=[inner])
+ JoinRel(condition=[=($0, $9)], joinType=[inner])
+ AggregateRel(group=[{0}], EXPR$1=[COUNT()])
+ ProjectRel(DEPTNO=[$7])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ </TestCase>
+ <TestCase name="testTransitiveInferenceLeftOuterJoin">
+ <Resource name="sql">
+ <![CDATA[select 1 from sales.emp d left outer join sales.emp e on d.deptno = e.deptno where d.deptno > 7 and e.deptno > 9]]>
+ </Resource>
+ <Resource name="planBefore">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ FilterRel(condition=[>($16, 9)])
+ JoinRel(condition=[=($7, $16)], joinType=[left])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ <Resource name="planAfter">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ FilterRel(condition=[>($16, 9)])
+ JoinRel(condition=[=($7, $16)], joinType=[left])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ </TestCase>
+ <TestCase name="testTransitiveInferenceRightOuterJoin">
+ <Resource name="sql">
+ <![CDATA[select 1 from sales.emp d right outer join sales.emp e on d.deptno = e.deptno where d.deptno > 7 and e.deptno > 9]]>
+ </Resource>
+ <Resource name="planBefore">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ FilterRel(condition=[>($7, 7)])
+ JoinRel(condition=[=($7, $16)], joinType=[right])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ FilterRel(condition=[>($7, 9)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ <Resource name="planAfter">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ FilterRel(condition=[>($7, 7)])
+ JoinRel(condition=[=($7, $16)], joinType=[right])
+ FilterRel(condition=[>($7, 9)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ FilterRel(condition=[>($7, 9)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ </TestCase>
+ <TestCase name="testTransitiveInferenceFullOuterJoin">
+ <Resource name="sql">
+ <![CDATA[select 1 from sales.emp d full outer join sales.emp e on d.deptno = e.deptno where d.deptno > 7 and e.deptno > 9]]>
+ </Resource>
+ <Resource name="planBefore">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ FilterRel(condition=[AND(>($7, 7), >($16, 9))])
+ JoinRel(condition=[=($7, $16)], joinType=[full])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ <Resource name="planAfter">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ FilterRel(condition=[AND(>($7, 7), >($16, 9))])
+ JoinRel(condition=[=($7, $16)], joinType=[full])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ </TestCase>
+ <TestCase name="testTransitiveInferencePreventProjectPullup">
+ <Resource name="sql">
+ <![CDATA[select 1 from (select comm as deptno from sales.emp where deptno > 7) d inner join sales.emp e on d.deptno = e.deptno ]]>
+ </Resource>
+ <Resource name="planBefore">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($0, $8)], joinType=[inner])
+ ProjectRel(DEPTNO=[$6])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ <Resource name="planAfter">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($0, $8)], joinType=[inner])
+ ProjectRel(DEPTNO=[$6])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ </TestCase>
+ <TestCase name="testTransitiveInferencePullupThruAlias">
+ <Resource name="sql">
+ <![CDATA[select 1 from (select comm as deptno from sales.emp where comm > 7) d inner join sales.emp e on d.deptno = e.deptno ]]>
+ </Resource>
+ <Resource name="planBefore">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($0, $8)], joinType=[inner])
+ ProjectRel(DEPTNO=[$6])
+ FilterRel(condition=[>($6, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ <Resource name="planAfter">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($0, $8)], joinType=[inner])
+ ProjectRel(DEPTNO=[$6])
+ FilterRel(condition=[>($6, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ </TestCase>
+ <TestCase name="testTransitiveInferenceConjunctInPullUp">
+ <Resource name="sql">
+ <![CDATA[select 1 from sales.emp d inner join sales.emp e on d.deptno = e.deptno where d.deptno in (7, 9) or d.deptno > 10]]>
+ </Resource>
+ <Resource name="planBefore">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($7, $16)], joinType=[inner])
+ FilterRel(condition=[OR(=($7, 7), =($7, 9), >($7, 10))])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ <Resource name="planAfter">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($7, $16)], joinType=[inner])
+ FilterRel(condition=[OR(=($7, 7), =($7, 9), >($7, 10))])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ FilterRel(condition=[OR(=($7, 7), =($7, 9), >($7, 10))])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ </TestCase>
+ <TestCase name="testTransitiveInferenceNoPullUpExprs">
+ <Resource name="sql">
+ <![CDATA[select 1 from sales.emp d inner join sales.emp e on d.deptno = e.deptno where d.deptno in (7, 9) or d.comm > 10]]>
+ </Resource>
+ <Resource name="planBefore">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($7, $16)], joinType=[inner])
+ FilterRel(condition=[OR(=($7, 7), =($7, 9), >($6, 10))])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ <Resource name="planAfter">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($7, $16)], joinType=[inner])
+ FilterRel(condition=[OR(=($7, 7), =($7, 9), >($6, 10))])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ </TestCase>
+ <TestCase name="testTransitiveInferenceUnion3way">
+ <Resource name="sql">
+ <![CDATA[select 1 from (select deptno from sales.emp where deptno > 7 union all select deptno from sales.emp where deptno > 10 union all select deptno from sales.emp where deptno > 1) d inner join sales.emp e on d.deptno = e.deptno ]]>
+ </Resource>
+ <Resource name="planBefore">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($0, $8)], joinType=[inner])
+ UnionRel(all=[true])
+ UnionRel(all=[true])
+ ProjectRel(DEPTNO=[$7])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ ProjectRel(DEPTNO=[$7])
+ FilterRel(condition=[>($7, 10)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ ProjectRel(DEPTNO=[$7])
+ FilterRel(condition=[>($7, 1)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ <Resource name="planAfter">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($0, $8)], joinType=[inner])
+ UnionRel(all=[true])
+ UnionRel(all=[true])
+ ProjectRel(DEPTNO=[$7])
+ FilterRel(condition=[>($7, 7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ ProjectRel(DEPTNO=[$7])
+ FilterRel(condition=[>($7, 10)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ ProjectRel(DEPTNO=[$7])
+ FilterRel(condition=[>($7, 1)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ FilterRel(condition=[OR(>($7, 7), >($7, 10), >($7, 1))])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ </TestCase>
+ <TestCase name="testTransitiveInferenceUnion3wayOr">
+ <Resource name="sql">
+ <![CDATA[
+select 1 from (
+ select empno, deptno from sales.emp where deptno > 7 or empno < 10
+ union all
+ select empno, deptno from sales.emp where deptno > 10 or empno < deptno
+ union all
+ select empno, deptno from sales.emp where deptno > 1) d
+inner join sales.emp e on d.deptno = e.deptno ]]>
+ </Resource>
+ <Resource name="planBefore">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($1, $9)], joinType=[inner])
+ UnionRel(all=[true])
+ UnionRel(all=[true])
+ ProjectRel(EMPNO=[$0], DEPTNO=[$7])
+ FilterRel(condition=[OR(>($7, 7), <($0, 10))])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ ProjectRel(EMPNO=[$0], DEPTNO=[$7])
+ FilterRel(condition=[OR(>($7, 10), <($0, $7))])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ ProjectRel(EMPNO=[$0], DEPTNO=[$7])
+ FilterRel(condition=[>($7, 1)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ <Resource name="planAfter">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($1, $9)], joinType=[inner])
+ UnionRel(all=[true])
+ UnionRel(all=[true])
+ ProjectRel(EMPNO=[$0], DEPTNO=[$7])
+ FilterRel(condition=[OR(>($7, 7), <($0, 10))])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ ProjectRel(EMPNO=[$0], DEPTNO=[$7])
+ FilterRel(condition=[OR(>($7, 10), <($0, $7))])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ ProjectRel(EMPNO=[$0], DEPTNO=[$7])
+ FilterRel(condition=[>($7, 1)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ </TestCase>
+ <TestCase name="testTransitiveInferenceConstantEquiPredicate">
+ <Resource name="sql">
+ <![CDATA[select 1 from sales.emp d inner join sales.emp e on d.deptno = e.deptno where 1 = 1]]>
+ </Resource>
+ <Resource name="planBefore">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($7, $16)], joinType=[inner])
+ FilterRel(condition=[=(1, 1)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ <Resource name="planAfter">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($7, $16)], joinType=[inner])
+ FilterRel(condition=[=(1, 1)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ </TestCase>
+ <TestCase name="testTransitiveInferenceConstantPredicate">
+ <Resource name="sql">
+ <![CDATA[select 1 from sales.emp d inner join sales.emp e on d.deptno = e.deptno where 2 > 1]]>
+ </Resource>
+ <Resource name="planBefore">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($7, $16)], joinType=[inner])
+ FilterRel(condition=[>(2, 1)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ <Resource name="planAfter">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($7, $16)], joinType=[inner])
+ FilterRel(condition=[>(2, 1)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ </TestCase>
+ <TestCase name="testTransitiveInferenceComplexPredicate">
+ <Resource name="sql">
+ <![CDATA[select 1 from sales.emp d inner join sales.emp e on d.deptno = e.deptno where d.deptno > 7 and e.sal = e.deptno and d.comm = d.deptno and d.comm + d.deptno > d.comm/2]]>
+ </Resource>
+ <Resource name="planBefore">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($7, $16)], joinType=[inner])
+ FilterRel(condition=[AND(>($7, 7), =($6, $7), >(+($6, $7), /($6, 2)))])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ FilterRel(condition=[=($5, $7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ <Resource name="planAfter">
+ <![CDATA[
+ProjectRel(EXPR$0=[1])
+ JoinRel(condition=[=($7, $16)], joinType=[inner])
+ FilterRel(condition=[AND(>($7, 7), =($6, $7), >(+($6, $7), /($6, 2)))])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+ FilterRel(condition=[>($7, 7)])
+ FilterRel(condition=[=($5, $7)])
+ TableAccessRel(table=[[CATALOG, SALES, EMP]])
+]]>
+ </Resource>
+ </TestCase>
</Root>