calcite-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jh...@apache.org
Subject git commit: [OPTIQ-435] LoptOptimizeJoinRule incorrectly re-orders outer joins
Date Sat, 18 Oct 2014 23:42:05 GMT
Repository: incubator-optiq
Updated Branches:
  refs/heads/master b4918cc45 -> 99c7ff96b


[OPTIQ-435] LoptOptimizeJoinRule incorrectly re-orders outer joins

Re-structure some code to use immutable lists rather than int arrays.

Parameterize Programs.heuristicJoinOrder to use a heuristic join only if there are at least a given number of joins.

Add "dependents" and "locations" tables to "hr" schema.


Project: http://git-wip-us.apache.org/repos/asf/incubator-optiq/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-optiq/commit/99c7ff96
Tree: http://git-wip-us.apache.org/repos/asf/incubator-optiq/tree/99c7ff96
Diff: http://git-wip-us.apache.org/repos/asf/incubator-optiq/diff/99c7ff96

Branch: refs/heads/master
Commit: 99c7ff96b35bca2066202779ce4a5af502dec6e1
Parents: b4918cc
Author: Julian Hyde <jhyde@apache.org>
Authored: Thu Oct 9 15:15:41 2014 -0700
Committer: Julian Hyde <julianhyde@gmail.com>
Committed: Sat Oct 18 15:42:31 2014 -0700

----------------------------------------------------------------------
 .../net/hydromatic/optiq/tools/Programs.java    |   4 +-
 .../rel/rules/ConvertMultiJoinRule.java         | 224 ++++++++-----------
 .../org/eigenbase/rel/rules/MultiJoinRel.java   |  39 ++--
 .../rel/rules/NestedLoopsJoinRule.java          |  44 ++--
 .../org/eigenbase/util/ImmutableIntList.java    |   5 +
 .../net/hydromatic/optiq/test/JdbcTest.java     |  40 +++-
 .../net/hydromatic/optiq/tools/PlannerTest.java |  91 +++++++-
 .../org/eigenbase/test/RelOptRulesTest.java     |  27 ++-
 .../org/eigenbase/test/RelOptRulesTest.xml      |  99 +++++++-
 .../hydromatic/optiq/impl/tpcds/TpcdsTest.java  |  11 +-
 10 files changed, 385 insertions(+), 199 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/99c7ff96/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 2b7fe78..a0fd46b 100644
--- a/core/src/main/java/net/hydromatic/optiq/tools/Programs.java
+++ b/core/src/main/java/net/hydromatic/optiq/tools/Programs.java
@@ -174,13 +174,13 @@ public class Programs {
    * {@link org.eigenbase.rel.rules.LoptOptimizeJoinRule})
    * if there are 6 or more joins (7 or more relations). */
   public static Program heuristicJoinOrder(final Collection<RelOptRule> rules,
-      final boolean bushy) {
+      final boolean bushy, final int minJoinCount) {
     return new Program() {
       public RelNode run(RelOptPlanner planner, RelNode rel,
           RelTraitSet requiredOutputTraits) {
         final int joinCount = RelOptUtil.countJoins(rel);
         final Program program;
-        if (joinCount < (bushy ? 2 : 6)) {
+        if (joinCount < minJoinCount) {
           program = ofRules(rules);
         } else {
           // Create a program that gathers together joins as a MultiJoinRel.

http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/99c7ff96/core/src/main/java/org/eigenbase/rel/rules/ConvertMultiJoinRule.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/rel/rules/ConvertMultiJoinRule.java b/core/src/main/java/org/eigenbase/rel/rules/ConvertMultiJoinRule.java
index f4f13b4..29ccad1 100644
--- a/core/src/main/java/org/eigenbase/rel/rules/ConvertMultiJoinRule.java
+++ b/core/src/main/java/org/eigenbase/rel/rules/ConvertMultiJoinRule.java
@@ -22,8 +22,13 @@ import org.eigenbase.rel.*;
 import org.eigenbase.relopt.*;
 import org.eigenbase.reltype.*;
 import org.eigenbase.rex.*;
+import org.eigenbase.util.ImmutableIntList;
 import org.eigenbase.util.Pair;
 
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.Lists;
+import com.google.common.collect.Maps;
+
 /**
  * Rule to flatten a tree of {@link JoinRel}s into a single {@link MultiJoinRel}
  * with N inputs. An input is not flattened if the input is a null generating
@@ -45,22 +50,33 @@ import org.eigenbase.util.Pair;
  * <p>Here are examples of the {@link MultiJoinRel}s constructed after this rule
  * has been applied on following join trees.
  *
- * <pre>
- * A JOIN B &rarr; MJ(A, B)
- * A JOIN B JOIN C &rarr; MJ(A, B, C)
- * A LEFTOUTER B &rarr; MJ(A, B), left outer join on input#1
- * A RIGHTOUTER B &rarr; MJ(A, B), right outer join on input#0
- * A FULLOUTER B &rarr; MJ[full](A, B)
- * A LEFTOUTER (B JOIN C) &rarr; MJ(A, MJ(B, C))), left outer join on input#1 in
- * the outermost MultiJoinRel
- * (A JOIN B) LEFTOUTER C &rarr; MJ(A, B, C), left outer join on input#2
- * A LEFTOUTER (B FULLOUTER C) &rarr; MJ(A, MJ[full](B, C)), left outer join on
- *      input#1 in the outermost MultiJoinRel
- * (A LEFTOUTER B) FULLOUTER (C RIGHTOUTER D) &rarr;
+ * <ul>
+ * <li>A JOIN B &rarr; MJ(A, B)
+ *
+ * <li>A JOIN B JOIN C &rarr; MJ(A, B, C)
+ *
+ * <li>A LEFT JOIN B &rarr; MJ(A, B), left outer join on input#1
+ *
+ * <li>A RIGHT JOIN B &rarr; MJ(A, B), right outer join on input#0
+ *
+ * <li>A FULL JOIN B &rarr; MJ[full](A, B)
+ *
+ * <li>A LEFT JOIN (B JOIN C) &rarr; MJ(A, MJ(B, C))), left outer join on
+ * input#1 in the outermost MultiJoinRel
+ *
+ * <li>(A JOIN B) LEFT JOIN C &rarr; MJ(A, B, C), left outer join on input#2
+ *
+ * <li>(A LEFT JOIN B) JOIN C &rarr; MJ(MJ(A, B), C), left outer join on input#1
+ * of the inner MultiJoinRel        TODO
+ *
+ * <li>A LEFT JOIN (B FULL JOIN C) &rarr; MJ(A, MJ[full](B, C)), left outer join
+ * on input#1 in the outermost MultiJoinRel
+ *
+ * <li>(A LEFT JOIN B) FULL JOIN (C RIGHT JOIN D) &rarr;
  *      MJ[full](MJ(A, B), MJ(C, D)), left outer join on input #1 in the first
  *      inner MultiJoinRel and right outer join on input#0 in the second inner
  *      MultiJoinRel
- * </pre>
+ * </ul>
  *
  * <p>The constructor is parameterized to allow any sub-class of
  * {@link JoinRelBase}, not just {@link JoinRel}.</p>
@@ -85,15 +101,14 @@ public class ConvertMultiJoinRule extends RelOptRule {
 
   public void onMatch(RelOptRuleCall call) {
     final JoinRelBase origJoin = call.rel(0);
-
     final RelNode left = call.rel(1);
     final RelNode right = call.rel(2);
 
     // combine the children MultiJoinRel inputs into an array of inputs
     // for the new MultiJoinRel
-    List<BitSet> projFieldsList = new ArrayList<BitSet>();
-    List<int[]> joinFieldRefCountsList = new ArrayList<int[]>();
-    List<RelNode> newInputs =
+    final List<BitSet> projFieldsList = Lists.newArrayList();
+    final List<int[]> joinFieldRefCountsList = Lists.newArrayList();
+    final List<RelNode> newInputs =
         combineInputs(
             origJoin,
             left,
@@ -104,8 +119,7 @@ public class ConvertMultiJoinRule extends RelOptRule {
     // combine the outer join information from the left and right
     // inputs, and include the outer join information from the current
     // join, if it's a left/right outer join
-    final List<Pair<JoinRelType, RexNode>> joinSpecs =
-        new ArrayList<Pair<JoinRelType, RexNode>>();
+    final List<Pair<JoinRelType, RexNode>> joinSpecs = Lists.newArrayList();
     combineOuterJoins(
         origJoin,
         newInputs,
@@ -113,39 +127,35 @@ public class ConvertMultiJoinRule extends RelOptRule {
         right,
         joinSpecs);
 
-    List<RexNode> newOuterJoinConds = Pair.right(joinSpecs);
-    List<JoinRelType> joinTypes = Pair.left(joinSpecs);
-
     // pull up the join filters from the children MultiJoinRels and
     // combine them with the join filter associated with this JoinRel to
     // form the join filter for the new MultiJoinRel
-    RexNode newJoinFilter = combineJoinFilters(origJoin, left, right);
+    List<RexNode> newJoinFilters = combineJoinFilters(origJoin, left, right);
 
     // add on the join field reference counts for the join condition
     // associated with this JoinRel
-    Map<Integer, int[]> newJoinFieldRefCountsMap =
-        new HashMap<Integer, int[]>();
-    addOnJoinFieldRefCounts(newInputs,
-        origJoin.getRowType().getFieldCount(),
-        origJoin.getCondition(),
-        joinFieldRefCountsList,
-        newJoinFieldRefCountsMap);
-
-    RexNode newPostJoinFilter =
+    final ImmutableMap<Integer, ImmutableIntList> newJoinFieldRefCountsMap =
+        addOnJoinFieldRefCounts(newInputs,
+            origJoin.getRowType().getFieldCount(),
+            origJoin.getCondition(),
+            joinFieldRefCountsList);
+
+    List<RexNode> newPostJoinFilters =
         combinePostJoinFilters(origJoin, left, right);
 
+    final RexBuilder rexBuilder = origJoin.getCluster().getRexBuilder();
     RelNode multiJoin =
         new MultiJoinRel(
             origJoin.getCluster(),
             newInputs,
-            newJoinFilter,
+            RexUtil.composeConjunction(rexBuilder, newJoinFilters, false),
             origJoin.getRowType(),
             origJoin.getJoinType() == JoinRelType.FULL,
-            newOuterJoinConds,
-            joinTypes,
+            Pair.right(joinSpecs),
+            Pair.left(joinSpecs),
             projFieldsList,
             newJoinFieldRefCountsMap,
-            newPostJoinFilter);
+            RexUtil.composeConjunction(rexBuilder, newPostJoinFilters, true));
 
     call.transformTo(multiJoin);
   }
@@ -168,57 +178,33 @@ public class ConvertMultiJoinRule extends RelOptRule {
       RelNode right,
       List<BitSet> projFieldsList,
       List<int[]> joinFieldRefCountsList) {
+    final List<RelNode> newInputs = Lists.newArrayList();
+
     // leave the null generating sides of an outer join intact; don't
     // pull up those children inputs into the array we're constructing
-    int nInputs;
-    int nInputsOnLeft;
-    final MultiJoinRel leftMultiJoin;
-    JoinRelType joinType = join.getJoinType();
-    boolean combineLeft = canCombine(left, joinType.generatesNullsOnLeft());
-    if (combineLeft) {
-      leftMultiJoin = (MultiJoinRel) left;
-      nInputs = left.getInputs().size();
-      nInputsOnLeft = nInputs;
-    } else {
-      leftMultiJoin = null;
-      nInputs = 1;
-      nInputsOnLeft = 1;
-    }
-    final MultiJoinRel rightMultiJoin;
-    boolean combineRight =
-        canCombine(right, joinType.generatesNullsOnRight());
-    if (combineRight) {
-      rightMultiJoin = (MultiJoinRel) right;
-      nInputs += right.getInputs().size();
-    } else {
-      rightMultiJoin = null;
-      nInputs += 1;
-    }
-
-    List<RelNode> newInputs = new ArrayList<RelNode>();
-    int i = 0;
-    if (combineLeft) {
-      for (; i < left.getInputs().size(); i++) {
+    if (canCombine(left, join.getJoinType().generatesNullsOnLeft())) {
+      final MultiJoinRel leftMultiJoin = (MultiJoinRel) left;
+      for (int i = 0; i < left.getInputs().size(); i++) {
         newInputs.add(leftMultiJoin.getInput(i));
         projFieldsList.add(leftMultiJoin.getProjFields().get(i));
         joinFieldRefCountsList.add(
-            leftMultiJoin.getJoinFieldRefCountsMap().get(i));
+            leftMultiJoin.getJoinFieldRefCountsMap().get(i).toIntArray());
       }
     } else {
       newInputs.add(left);
-      i = 1;
       projFieldsList.add(null);
       joinFieldRefCountsList.add(
           new int[left.getRowType().getFieldCount()]);
     }
-    if (combineRight) {
-      for (; i < nInputs; i++) {
-        newInputs.add(rightMultiJoin.getInput(i - nInputsOnLeft));
+
+    if (canCombine(right, join.getJoinType().generatesNullsOnRight())) {
+      final MultiJoinRel rightMultiJoin = (MultiJoinRel) right;
+      for (int i = 0; i < right.getInputs().size(); i++) {
+        newInputs.add(rightMultiJoin.getInput(i));
         projFieldsList.add(
-            rightMultiJoin.getProjFields().get(i - nInputsOnLeft));
+            rightMultiJoin.getProjFields().get(i));
         joinFieldRefCountsList.add(
-            rightMultiJoin.getJoinFieldRefCountsMap().get(
-                i - nInputsOnLeft));
+            rightMultiJoin.getJoinFieldRefCountsMap().get(i).toIntArray());
       }
     } else {
       newInputs.add(right);
@@ -365,51 +351,38 @@ public class ConvertMultiJoinRule extends RelOptRule {
    * @param right   right child of the join
    * @return combined join filters AND-ed together
    */
-  private RexNode combineJoinFilters(
+  private List<RexNode> combineJoinFilters(
       JoinRelBase joinRel,
       RelNode left,
       RelNode right) {
-    RexBuilder rexBuilder = joinRel.getCluster().getRexBuilder();
     JoinRelType joinType = joinRel.getJoinType();
 
-    // first need to adjust the RexInputs of the right child, since
-    // those need to shift over to the right
-    RexNode rightFilter = null;
-    if (canCombine(right, joinType.generatesNullsOnRight())) {
-      MultiJoinRel multiJoin = (MultiJoinRel) right;
-      rightFilter =
-          shiftRightFilter(
-              joinRel,
-              left,
-              multiJoin,
-              multiJoin.getJoinFilter());
-    }
-
     // AND the join condition if this isn't a left or right outer join;
     // in those cases, the outer join condition is already tracked
     // separately
-    RexNode newFilter = null;
+    final List<RexNode> filters = Lists.newArrayList();
     if ((joinType != JoinRelType.LEFT) && (joinType != JoinRelType.RIGHT)) {
-      newFilter = joinRel.getCondition();
+      filters.add(joinRel.getCondition());
     }
     if (canCombine(left, joinType.generatesNullsOnLeft())) {
-      RexNode leftFilter = ((MultiJoinRel) left).getJoinFilter();
-      newFilter =
-          RelOptUtil.andJoinFilters(
-              rexBuilder,
-              newFilter,
-              leftFilter);
+      filters.add(((MultiJoinRel) left).getJoinFilter());
+    }
+    // Need to adjust the RexInputs of the right child, since
+    // those need to shift over to the right
+    if (canCombine(right, joinType.generatesNullsOnRight())) {
+      MultiJoinRel multiJoin = (MultiJoinRel) right;
+      filters.add(
+          shiftRightFilter(joinRel, left, multiJoin,
+              multiJoin.getJoinFilter()));
     }
-    newFilter =
-        RelOptUtil.andJoinFilters(
-            rexBuilder,
-            newFilter,
-            rightFilter);
 
-    return newFilter;
+    return filters;
   }
 
   /**
+   * Returns whether an input can be merged into a given relational expression
+   * without changing semantics.
+   *
    * @param input          input into a join
    * @param nullGenerating true if the input is null generating
    * @return true if the input can be combined into a parent MultiJoinRel
@@ -417,6 +390,7 @@ public class ConvertMultiJoinRule extends RelOptRule {
   private boolean canCombine(RelNode input, boolean nullGenerating) {
     return input instanceof MultiJoinRel
         && !((MultiJoinRel) input).isFullOuterJoin()
+        && !((MultiJoinRel) input).containsOuter()
         && !nullGenerating;
   }
 
@@ -464,23 +438,24 @@ public class ConvertMultiJoinRule extends RelOptRule {
    * @param nTotalFields             total number of fields in the MultiJoinRel
    * @param joinCondition            the new join condition
    * @param origJoinFieldRefCounts   existing join condition reference counts
-   * @param newJoinFieldRefCountsMap map containing the new join condition
+   *
+   * @return Map containing the new join condition
    */
-  private void addOnJoinFieldRefCounts(
+  private ImmutableMap<Integer, ImmutableIntList> addOnJoinFieldRefCounts(
       List<RelNode> multiJoinInputs,
       int nTotalFields,
       RexNode joinCondition,
-      List<int[]> origJoinFieldRefCounts,
-      Map<Integer, int[]> newJoinFieldRefCountsMap) {
+      List<int[]> origJoinFieldRefCounts) {
     // count the input references in the join condition
     int[] joinCondRefCounts = new int[nTotalFields];
     joinCondition.accept(new InputReferenceCounter(joinCondRefCounts));
 
     // first, make a copy of the ref counters
+    final Map<Integer, int[]> refCountsMap = Maps.newHashMap();
     int nInputs = multiJoinInputs.size();
     int currInput = 0;
     for (int[] origRefCounts : origJoinFieldRefCounts) {
-      newJoinFieldRefCountsMap.put(
+      refCountsMap.put(
           currInput,
           origRefCounts.clone());
       currInput++;
@@ -502,9 +477,16 @@ public class ConvertMultiJoinRule extends RelOptRule {
         nFields =
             multiJoinInputs.get(currInput).getRowType().getFieldCount();
       }
-      int[] refCounts = newJoinFieldRefCountsMap.get(currInput);
+      int[] refCounts = refCountsMap.get(currInput);
       refCounts[i - startField] += joinCondRefCounts[i];
     }
+
+    final ImmutableMap.Builder<Integer, ImmutableIntList> builder =
+        ImmutableMap.builder();
+    for (Map.Entry<Integer, int[]> entry : refCountsMap.entrySet()) {
+      builder.put(entry.getKey(), ImmutableIntList.of(entry.getValue()));
+    }
+    return builder.build();
   }
 
   /**
@@ -516,33 +498,23 @@ public class ConvertMultiJoinRule extends RelOptRule {
    * @param right   right child of the JoinRel
    * @return combined post-join filters AND'd together
    */
-  private RexNode combinePostJoinFilters(
+  private List<RexNode> combinePostJoinFilters(
       JoinRelBase joinRel,
       RelNode left,
       RelNode right) {
-    RexNode rightPostJoinFilter = null;
+    final List<RexNode> filters = Lists.newArrayList();
     if (right instanceof MultiJoinRel) {
-      rightPostJoinFilter =
-          shiftRightFilter(
-              joinRel,
-              left,
-              (MultiJoinRel) right,
-              ((MultiJoinRel) right).getPostJoinFilter());
+      final MultiJoinRel multiRight = (MultiJoinRel) right;
+      filters.add(
+          shiftRightFilter(joinRel, left, multiRight,
+              multiRight.getPostJoinFilter()));
     }
 
-    RexNode leftPostJoinFilter = null;
     if (left instanceof MultiJoinRel) {
-      leftPostJoinFilter = ((MultiJoinRel) left).getPostJoinFilter();
+      filters.add(((MultiJoinRel) left).getPostJoinFilter());
     }
 
-    if ((leftPostJoinFilter == null) && (rightPostJoinFilter == null)) {
-      return null;
-    } else {
-      return RelOptUtil.andJoinFilters(
-          joinRel.getCluster().getRexBuilder(),
-          leftPostJoinFilter,
-          rightPostJoinFilter);
-    }
+    return filters;
   }
 
   //~ Inner Classes ----------------------------------------------------------

http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/99c7ff96/core/src/main/java/org/eigenbase/rel/rules/MultiJoinRel.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/rel/rules/MultiJoinRel.java b/core/src/main/java/org/eigenbase/rel/rules/MultiJoinRel.java
index 5e83e97..2f252cd 100644
--- a/core/src/main/java/org/eigenbase/rel/rules/MultiJoinRel.java
+++ b/core/src/main/java/org/eigenbase/rel/rules/MultiJoinRel.java
@@ -22,6 +22,7 @@ import org.eigenbase.rel.*;
 import org.eigenbase.relopt.*;
 import org.eigenbase.reltype.*;
 import org.eigenbase.rex.*;
+import org.eigenbase.util.ImmutableIntList;
 import org.eigenbase.util.ImmutableNullableList;
 
 import net.hydromatic.linq4j.Ord;
@@ -37,15 +38,15 @@ import com.google.common.collect.Lists;
 public final class MultiJoinRel extends AbstractRelNode {
   //~ Instance fields --------------------------------------------------------
 
-  private List<RelNode> inputs;
-  private RexNode joinFilter;
-  private RelDataType rowType;
-  private boolean isFullOuterJoin;
-  private List<RexNode> outerJoinConditions;
-  private ImmutableList<JoinRelType> joinTypes;
-  private List<BitSet> projFields;
-  private ImmutableMap<Integer, int[]> joinFieldRefCountsMap;
-  private RexNode postJoinFilter;
+  private final List<RelNode> inputs;
+  private final RexNode joinFilter;
+  private final RelDataType rowType;
+  private final boolean isFullOuterJoin;
+  private final List<RexNode> outerJoinConditions;
+  private final ImmutableList<JoinRelType> joinTypes;
+  private final List<BitSet> projFields;
+  public final ImmutableMap<Integer, ImmutableIntList> joinFieldRefCountsMap;
+  private final RexNode postJoinFilter;
 
   //~ Constructors -----------------------------------------------------------
 
@@ -73,7 +74,6 @@ public final class MultiJoinRel extends AbstractRelNode {
    *                              is referenced in join conditions, indexed by
    *                              the input #
    * @param postJoinFilter        filter to be applied after the joins are
-   *                              executed
    */
   public MultiJoinRel(
       RelOptCluster cluster,
@@ -84,7 +84,7 @@ public final class MultiJoinRel extends AbstractRelNode {
       List<RexNode> outerJoinConditions,
       List<JoinRelType> joinTypes,
       List<BitSet> projFields,
-      Map<Integer, int[]> joinFieldRefCountsMap,
+      ImmutableMap<Integer, ImmutableIntList> joinFieldRefCountsMap,
       RexNode postJoinFilter) {
     super(cluster, cluster.traitSetOf(Convention.NONE));
     this.inputs = Lists.newArrayList(inputs);
@@ -96,7 +96,7 @@ public final class MultiJoinRel extends AbstractRelNode {
     assert outerJoinConditions.size() == inputs.size();
     this.joinTypes = ImmutableList.copyOf(joinTypes);
     this.projFields = ImmutableNullableList.copyOf(projFields);
-    this.joinFieldRefCountsMap = ImmutableMap.copyOf(joinFieldRefCountsMap);
+    this.joinFieldRefCountsMap = joinFieldRefCountsMap;
     this.postJoinFilter = postJoinFilter;
   }
 
@@ -117,7 +117,7 @@ public final class MultiJoinRel extends AbstractRelNode {
         outerJoinConditions,
         joinTypes,
         projFields,
-        cloneJoinFieldRefCountsMap(),
+        joinFieldRefCountsMap,
         postJoinFilter);
   }
 
@@ -127,7 +127,7 @@ public final class MultiJoinRel extends AbstractRelNode {
   private Map<Integer, int[]> cloneJoinFieldRefCountsMap() {
     Map<Integer, int[]> clonedMap = new HashMap<Integer, int[]>();
     for (int i = 0; i < inputs.size(); i++) {
-      clonedMap.put(i, joinFieldRefCountsMap.get(i).clone());
+      clonedMap.put(i, joinFieldRefCountsMap.get(i).toIntArray());
     }
     return clonedMap;
   }
@@ -215,7 +215,7 @@ public final class MultiJoinRel extends AbstractRelNode {
    * @return the map of reference counts for each input, representing the
    * fields accessed in join conditions
    */
-  public Map<Integer, int[]> getJoinFieldRefCountsMap() {
+  public ImmutableMap<Integer, ImmutableIntList> getJoinFieldRefCountsMap() {
     return joinFieldRefCountsMap;
   }
 
@@ -233,6 +233,15 @@ public final class MultiJoinRel extends AbstractRelNode {
   public RexNode getPostJoinFilter() {
     return postJoinFilter;
   }
+
+  boolean containsOuter() {
+    for (JoinRelType joinType : joinTypes) {
+      if (joinType != JoinRelType.INNER) {
+        return true;
+      }
+    }
+    return false;
+  }
 }
 
 // End MultiJoinRel.java

http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/99c7ff96/core/src/main/java/org/eigenbase/rel/rules/NestedLoopsJoinRule.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/rel/rules/NestedLoopsJoinRule.java b/core/src/main/java/org/eigenbase/rel/rules/NestedLoopsJoinRule.java
index f0fed59..de40ede 100644
--- a/core/src/main/java/org/eigenbase/rel/rules/NestedLoopsJoinRule.java
+++ b/core/src/main/java/org/eigenbase/rel/rules/NestedLoopsJoinRule.java
@@ -86,39 +86,29 @@ public class NestedLoopsJoinRule extends RelOptRule {
     final RelNode left = join.getLeft();
     final JoinInfo joinInfo = join.analyzeCondition();
     final List<Correlation> correlationList = Lists.newArrayList();
-    if (joinInfo.leftKeys.size() > 0) {
-      final RelOptCluster cluster = join.getCluster();
-      final RexBuilder rexBuilder = cluster.getRexBuilder();
-      RexNode condition = null;
-      for (IntPair p : joinInfo.pairs()) {
-        final String dynInIdStr = cluster.getQuery().createCorrel();
-        final int dynInId = RelOptQuery.getCorrelOrdinal(dynInIdStr);
+    final RelOptCluster cluster = join.getCluster();
+    final RexBuilder rexBuilder = cluster.getRexBuilder();
+    final List<RexNode> conditions = Lists.newArrayList();
+    for (IntPair p : joinInfo.pairs()) {
+      final String dynInIdStr = cluster.getQuery().createCorrel();
+      final int dynInId = RelOptQuery.getCorrelOrdinal(dynInIdStr);
 
-        // Create correlation to say 'each row, set variable #id
-        // to the value of column #leftKey'.
-        correlationList.add(new Correlation(dynInId, p.source));
-        condition =
-            RelOptUtil.andJoinFilters(
-                rexBuilder,
-                condition,
-                rexBuilder.makeCall(
-                    SqlStdOperatorTable.EQUALS,
-                    rexBuilder.makeInputRef(right, p.target),
-                    rexBuilder.makeCorrel(
-                        left.getRowType().getFieldList().get(p.source)
-                            .getType(),
-                        dynInIdStr)));
-      }
-      right =
-          RelOptUtil.createFilter(
-              right,
-              condition);
+      // Create correlation to say 'each row, set variable #id
+      // to the value of column #leftKey'.
+      correlationList.add(new Correlation(dynInId, p.source));
+      conditions.add(
+          rexBuilder.makeCall(SqlStdOperatorTable.EQUALS,
+              rexBuilder.makeInputRef(right, p.target),
+              rexBuilder.makeCorrel(
+                  left.getRowType().getFieldList().get(p.source).getType(),
+                  dynInIdStr)));
     }
+    final RelNode filteredRight = RelOptUtil.createFilter(right, conditions);
     RelNode newRel =
         new CorrelatorRel(
             join.getCluster(),
             left,
-            right,
+            filteredRight,
             joinInfo.getRemaining(join.getCluster().getRexBuilder()),
             correlationList,
             join.getJoinType());

http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/99c7ff96/core/src/main/java/org/eigenbase/util/ImmutableIntList.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/eigenbase/util/ImmutableIntList.java b/core/src/main/java/org/eigenbase/util/ImmutableIntList.java
index 0aefb05..1e1c2e3 100644
--- a/core/src/main/java/org/eigenbase/util/ImmutableIntList.java
+++ b/core/src/main/java/org/eigenbase/util/ImmutableIntList.java
@@ -142,6 +142,11 @@ public class ImmutableIntList extends FlatLists.AbstractFlatList<Integer> {
     return a;
   }
 
+  /** Returns an array of {@code int}s with the same contents as this list. */
+  public int[] toIntArray() {
+    return ints.clone();
+  }
+
   public Integer get(int index) {
     return ints[index];
   }

http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/99c7ff96/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 3869aec..2d19fdc 100644
--- a/core/src/test/java/net/hydromatic/optiq/test/JdbcTest.java
+++ b/core/src/test/java/net/hydromatic/optiq/test/JdbcTest.java
@@ -354,8 +354,10 @@ public class JdbcTest {
             + "id=hr; names=[hr]; type=SCHEMA\n"
             + "id=metadata; names=[metadata]; type=SCHEMA\n"
             + "id=s; names=[s]; type=SCHEMA\n"
+            + "id=hr.dependents; names=[hr, dependents]; type=TABLE\n"
             + "id=hr.depts; names=[hr, depts]; type=TABLE\n"
-            + "id=hr.emps; names=[hr, emps]; type=TABLE\n"));
+            + "id=hr.emps; names=[hr, emps]; type=TABLE\n"
+            + "id=hr.locations; names=[hr, locations]; type=TABLE\n"));
   }
 
   private String adviseSql(String sql) throws ClassNotFoundException,
@@ -5989,6 +5991,14 @@ public class JdbcTest {
       new Department(30, "Marketing", Collections.<Employee>emptyList()),
       new Department(40, "HR", Collections.singletonList(emps[1])),
     };
+    public final Dependent[] dependents = {
+      new Dependent(10, "Michael"),
+      new Dependent(10, "Jane"),
+    };
+    public final Dependent[] locations = {
+      new Dependent(10, "San Francisco"),
+      new Dependent(20, "San Diego"),
+    };
 
     public QueryableTable foo(int count) {
       return generateStrings(count);
@@ -6050,6 +6060,34 @@ public class JdbcTest {
     }
   }
 
+  public static class Location {
+    public final int locid;
+    public final String name;
+
+    public Location(int locid, String name) {
+      this.locid = locid;
+      this.name = name;
+    }
+
+    @Override public String toString() {
+      return "Location [locid: " + locid + ", name: " + name + "]";
+    }
+  }
+
+  public static class Dependent {
+    public final int empid;
+    public final String name;
+
+    public Dependent(int empid, String name) {
+      this.empid = empid;
+      this.name = name;
+    }
+
+    @Override public String toString() {
+      return "Dependent [empid: " + empid + ", name: " + name + "]";
+    }
+  }
+
   public static class FoodmartSchema {
     public final SalesFact[] sales_fact_1997 = {
       new SalesFact(100, 10),

http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/99c7ff96/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 f1ddbfe..8502f2b 100644
--- a/core/src/test/java/net/hydromatic/optiq/tools/PlannerTest.java
+++ b/core/src/test/java/net/hydromatic/optiq/tools/PlannerTest.java
@@ -71,12 +71,12 @@ public class PlannerTest {
         "select * from \"emps\" where \"name\" like '%e%'",
 
         "SELECT *\n"
-        + "FROM `emps`\n"
-        + "WHERE `name` LIKE '%e%'",
+            + "FROM `emps`\n"
+            + "WHERE `name` LIKE '%e%'",
 
         "ProjectRel(empid=[$0], deptno=[$1], name=[$2], salary=[$3], commission=[$4])\n"
-        + "  FilterRel(condition=[LIKE($2, '%e%')])\n"
-        + "    EnumerableTableAccessRel(table=[[hr, emps]])\n");
+            + "  FilterRel(condition=[LIKE($2, '%e%')])\n"
+            + "    EnumerableTableAccessRel(table=[[hr, emps]])\n");
   }
 
   /** Unit test that parses, validates and converts the query using
@@ -351,7 +351,7 @@ public class PlannerTest {
     Planner planner = getPlanner(null);
     SqlNode parse = planner.parse(
         "select * from (select * from \"emps\") as t\n"
-        + "where \"name\" like '%e%'");
+            + "where \"name\" like '%e%'");
     final SqlDialect hiveDialect =
         new SqlDialect(SqlDialect.DatabaseProduct.HIVE, "Hive", null);
     assertThat(Util.toLinux(parse.toSqlString(hiveDialect).getSql()),
@@ -440,8 +440,8 @@ public class PlannerTest {
           .append(i).append(".\"deptno\" = d")
           .append(i - 1).append(".\"deptno\"");
     }
-    Planner planner =
-        getPlanner(null, Programs.heuristicJoinOrder(Programs.RULE_SET, false));
+    Planner planner = getPlanner(null,
+        Programs.heuristicJoinOrder(Programs.RULE_SET, false, 6));
     SqlNode parse = planner.parse(buf.toString());
 
     SqlNode validate = planner.validate(parse);
@@ -453,6 +453,81 @@ public class PlannerTest {
         "EnumerableJoinRel(condition=[=($0, $3)], joinType=[inner])"));
   }
 
+  /** Test case for
+   * <a href="https://issues.apache.org/jira/browse/OPTIQ-435">OPTIQ-435</a>,
+   * "LoptOptimizeJoinRule incorrectly re-orders outer joins".
+   *
+   * <p>Checks the {@link org.eigenbase.rel.rules.LoptOptimizeJoinRule} on a
+   * query with a left outer join.
+   *
+   * <p>Specifically, tests that a relation (dependents) in an inner join
+   * cannot be pushed into an outer join (emps left join depts).
+   */
+  @Test public void testHeuristicLeftJoin() throws Exception {
+    checkHeuristic(
+        "select * from \"emps\" as e\n"
+        + "left join \"depts\" as d using (\"deptno\")\n"
+        + "join \"dependents\" as p on e.\"empid\" = p.\"empid\"",
+        "EnumerableProjectRel(empid=[$0], deptno=[$1], name=[$2], salary=[$3], commission=[$4], deptno0=[$5], name0=[$6], employees=[$7], empid0=[$8], name1=[$9])\n"
+        + "  EnumerableProjectRel(empid=[$2], deptno=[$3], name=[$4], salary=[$5], commission=[$6], deptno0=[$7], name0=[$8], employees=[$9], empid0=[$0], name1=[$1])\n"
+        + "    EnumerableJoinRel(condition=[=($0, $2)], joinType=[inner])\n"
+        + "      EnumerableTableAccessRel(table=[[hr, dependents]])\n"
+        + "      EnumerableProjectRel(empid=[$0], deptno=[$1], name=[$2], salary=[$3], commission=[$4], deptno0=[$5], name0=[$6], employees=[$7])\n"
+        + "        EnumerableJoinRel(condition=[=($1, $5)], joinType=[left])\n"
+        + "          EnumerableTableAccessRel(table=[[hr, emps]])\n"
+        + "          EnumerableTableAccessRel(table=[[hr, depts]])");
+  }
+
+  /** It would probably be OK to transform
+   * {@code (emps right join depts) join dependents}
+   * to
+   * {@code (emps  join dependents) right join depts}
+   * but we do not currently allow it.
+   */
+  @Test public void testHeuristicPushInnerJoin() throws Exception {
+    checkHeuristic(
+        "select * from \"emps\" as e\n"
+        + "right join \"depts\" as d using (\"deptno\")\n"
+        + "join \"dependents\" as p on e.\"empid\" = p.\"empid\"",
+        "EnumerableProjectRel(empid=[$0], deptno=[$1], name=[$2], salary=[$3], commission=[$4], deptno0=[$5], name0=[$6], employees=[$7], empid0=[$8], name1=[$9])\n"
+        + "  EnumerableProjectRel(empid=[$2], deptno=[$3], name=[$4], salary=[$5], commission=[$6], deptno0=[$7], name0=[$8], employees=[$9], empid0=[$0], name1=[$1])\n"
+        + "    EnumerableJoinRel(condition=[=($0, $2)], joinType=[inner])\n"
+        + "      EnumerableTableAccessRel(table=[[hr, dependents]])\n"
+        + "      EnumerableProjectRel(empid=[$0], deptno=[$1], name=[$2], salary=[$3], commission=[$4], deptno0=[$5], name0=[$6], employees=[$7])\n"
+        + "        EnumerableJoinRel(condition=[=($1, $5)], joinType=[right])\n"
+        + "          EnumerableTableAccessRel(table=[[hr, emps]])\n"
+        + "          EnumerableTableAccessRel(table=[[hr, depts]])");
+  }
+
+  /** Tests that a relation (dependents) that is on the null-generating side of
+   * an outer join cannot be pushed into an inner join (emps join depts). */
+  @Test public void testHeuristicRightJoin() throws Exception {
+    checkHeuristic(
+        "select * from \"emps\" as e\n"
+        + "join \"depts\" as d using (\"deptno\")\n"
+        + "right join \"dependents\" as p on e.\"empid\" = p.\"empid\"",
+        "EnumerableProjectRel(empid=[$0], deptno=[$1], name=[$2], salary=[$3], commission=[$4], deptno0=[$5], name0=[$6], employees=[$7], empid0=[$8], name1=[$9])\n"
+        + "  EnumerableProjectRel(empid=[$2], deptno=[$3], name=[$4], salary=[$5], commission=[$6], deptno0=[$7], name0=[$8], employees=[$9], empid0=[$0], name1=[$1])\n"
+        + "    EnumerableJoinRel(condition=[=($0, $2)], joinType=[left])\n"
+        + "      EnumerableTableAccessRel(table=[[hr, dependents]])\n"
+        + "      EnumerableProjectRel(empid=[$0], deptno=[$1], name=[$2], salary=[$3], commission=[$4], deptno0=[$5], name0=[$6], employees=[$7])\n"
+        + "        EnumerableJoinRel(condition=[=($1, $5)], joinType=[inner])\n"
+        + "          EnumerableTableAccessRel(table=[[hr, emps]])\n"
+        + "          EnumerableTableAccessRel(table=[[hr, depts]])");
+  }
+
+  private void checkHeuristic(String sql, String expected) throws Exception {
+    Planner planner = getPlanner(null,
+        Programs.heuristicJoinOrder(Programs.RULE_SET, false, 0));
+    SqlNode parse = planner.parse(sql);
+    SqlNode validate = planner.validate(parse);
+    RelNode convert = planner.convert(validate);
+    RelTraitSet traitSet = planner.getEmptyTraitSet()
+        .replace(EnumerableConvention.INSTANCE);
+    RelNode transform = planner.transform(0, traitSet, convert);
+    assertThat(toString(transform), containsString(expected));
+  }
+
   /** Plans a 3-table join query on the FoodMart schema. The ideal plan is not
    * bushy, but nevertheless exercises the bushy-join heuristic optimizer. */
   @Test public void testAlmostBushy() throws Exception {
@@ -568,7 +643,7 @@ public class PlannerTest {
             OptiqAssert.addSchema(rootSchema,
                 OptiqAssert.SchemaSpec.CLONE_FOODMART))
         .traitDefs((List<RelTraitDef>) null)
-        .programs(Programs.heuristicJoinOrder(Programs.RULE_SET, true))
+        .programs(Programs.heuristicJoinOrder(Programs.RULE_SET, true, 2))
         .build();
     Planner planner = Frameworks.getPlanner(config);
     SqlNode parse = planner.parse(sql);

http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/99c7ff96/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 8668907..93659b7 100644
--- a/core/src/test/java/org/eigenbase/test/RelOptRulesTest.java
+++ b/core/src/test/java/org/eigenbase/test/RelOptRulesTest.java
@@ -554,7 +554,7 @@ public class RelOptRulesTest extends RelOptTestBase {
         + "and d.name = 'foo'");
   }
 
-  @Test public void testConvertMultiJoinRuleOuterJoins() throws Exception {
+  private void checkPlanning(String query) throws Exception {
     final Tester tester1 = tester.withCatalogReaderFactory(
         new Function<RelDataTypeFactory, Prepare.CatalogReader>() {
           public Prepare.CatalogReader apply(RelDataTypeFactory typeFactory) {
@@ -587,8 +587,11 @@ public class RelOptRulesTest extends RelOptTestBase {
         .addRuleInstance(ConvertMultiJoinRule.INSTANCE)
         .build();
     checkPlanning(tester1, null,
-        new HepPlanner(program),
-        "select * from "
+        new HepPlanner(program), query);
+  }
+
+  @Test public void testConvertMultiJoinRuleOuterJoins() throws Exception {
+    checkPlanning("select * from "
         + "    (select * from "
         + "        (select * from "
         + "            (select * from A right outer join B on a = b) "
@@ -607,6 +610,24 @@ public class RelOptRulesTest extends RelOptTestBase {
         + "    on a = i and h = j");
   }
 
+  @Test public void testConvertMultiJoinRuleOuterJoins2() throws Exception {
+    // in (A right join B) join C, pushing C is not allowed;
+    // therefore there should be 2 MultiJoinRel
+    checkPlanning("select * from A right join B on a = b join C on b = c");
+  }
+
+  @Test public void testConvertMultiJoinRuleOuterJoins3() throws Exception {
+    // in (A join B) left join C, pushing C is allowed;
+    // therefore there should be 1 MultiJoinRel
+    checkPlanning("select * from A join B on a = b left join C on b = c");
+  }
+
+  @Test public void testConvertMultiJoinRuleOuterJoins4() throws Exception {
+    // in (A join B) right join C, pushing C is not allowed;
+    // therefore there should be 2 MultiJoinRel
+    checkPlanning("select * from A join B on a = b right join C on b = c");
+  }
+
   @Test public void testPushSemiJoinPastProject() throws Exception {
     HepProgram program = new HepProgramBuilder()
         .addRuleInstance(PushFilterPastJoinRule.FILTER_ON_JOIN)

http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/99c7ff96/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 372f7ea..015c361 100644
--- a/core/src/test/resources/org/eigenbase/test/RelOptRulesTest.xml
+++ b/core/src/test/resources/org/eigenbase/test/RelOptRulesTest.xml
@@ -1355,18 +1355,22 @@ ProjectRel(A=[$0], B=[$1], C=[$2], D=[$3], E=[$4], F=[$5], G=[$6], H=[$7], I=[$8
         </Resource>
         <Resource name="planAfter">
             <![CDATA[
-MultiJoinRel(joinFilter=[AND(AND(=($0, $8), =($7, $9)), =($8, $9))], isFullOuterJoin=[false], joinTypes=[[RIGHT, RIGHT, INNER, LEFT, INNER, INNER]], outerJoinConditions=[[AND(=($0, $4), =($1, $5), =($2, $6), =($3, $7)), AND(=($4, $6), =($5, $7)), NULL, =($6, $7), NULL, NULL]], projFields=[[ALL, ALL, ALL, ALL, ALL, ALL]])
-  MultiJoinRel(joinFilter=[true], isFullOuterJoin=[false], joinTypes=[[RIGHT, INNER, LEFT]], outerJoinConditions=[[=($0, $1), NULL, AND(=($0, $2), =($1, $3))]], projFields=[[ALL, ALL, ALL]])
-    TableAccessRel(table=[[CATALOG, SALES, A]])
-    TableAccessRel(table=[[CATALOG, SALES, B]])
-    MultiJoinRel(joinFilter=[=($0, $1)], isFullOuterJoin=[true], joinTypes=[[INNER, INNER]], outerJoinConditions=[[NULL, NULL]], projFields=[[ALL, ALL]])
-      TableAccessRel(table=[[CATALOG, SALES, C]])
-      TableAccessRel(table=[[CATALOG, SALES, D]])
-  MultiJoinRel(joinFilter=[=($0, $1)], isFullOuterJoin=[true], joinTypes=[[INNER, INNER]], outerJoinConditions=[[NULL, NULL]], projFields=[[ALL, ALL]])
-    TableAccessRel(table=[[CATALOG, SALES, E]])
-    TableAccessRel(table=[[CATALOG, SALES, F]])
-  TableAccessRel(table=[[CATALOG, SALES, G]])
-  TableAccessRel(table=[[CATALOG, SALES, H]])
+MultiJoinRel(joinFilter=[AND(=($0, $8), =($7, $9), =($8, $9))], isFullOuterJoin=[false], joinTypes=[[INNER, INNER, INNER]], outerJoinConditions=[[NULL, NULL, NULL]], projFields=[[ALL, ALL, ALL]])
+  MultiJoinRel(joinFilter=[true], isFullOuterJoin=[false], joinTypes=[[RIGHT, INNER]], outerJoinConditions=[[AND(=($0, $4), =($1, $5), =($2, $6), =($3, $7)), NULL]], projFields=[[ALL, ALL]])
+    MultiJoinRel(joinFilter=[true], isFullOuterJoin=[false], joinTypes=[[INNER, LEFT]], outerJoinConditions=[[NULL, AND(=($0, $2), =($1, $3))]], projFields=[[ALL, ALL]])
+      MultiJoinRel(joinFilter=[true], isFullOuterJoin=[false], joinTypes=[[RIGHT, INNER]], outerJoinConditions=[[=($0, $1), NULL]], projFields=[[ALL, ALL]])
+        TableAccessRel(table=[[CATALOG, SALES, A]])
+        TableAccessRel(table=[[CATALOG, SALES, B]])
+      MultiJoinRel(joinFilter=[=($0, $1)], isFullOuterJoin=[true], joinTypes=[[INNER, INNER]], outerJoinConditions=[[NULL, NULL]], projFields=[[ALL, ALL]])
+        TableAccessRel(table=[[CATALOG, SALES, C]])
+        TableAccessRel(table=[[CATALOG, SALES, D]])
+    MultiJoinRel(joinFilter=[true], isFullOuterJoin=[false], joinTypes=[[RIGHT, INNER]], outerJoinConditions=[[AND(=($0, $2), =($1, $3)), NULL]], projFields=[[ALL, ALL]])
+      MultiJoinRel(joinFilter=[=($0, $1)], isFullOuterJoin=[true], joinTypes=[[INNER, INNER]], outerJoinConditions=[[NULL, NULL]], projFields=[[ALL, ALL]])
+        TableAccessRel(table=[[CATALOG, SALES, E]])
+        TableAccessRel(table=[[CATALOG, SALES, F]])
+      MultiJoinRel(joinFilter=[true], isFullOuterJoin=[false], joinTypes=[[INNER, LEFT]], outerJoinConditions=[[NULL, =($0, $1)]], projFields=[[ALL, ALL]])
+        TableAccessRel(table=[[CATALOG, SALES, G]])
+        TableAccessRel(table=[[CATALOG, SALES, H]])
   TableAccessRel(table=[[CATALOG, SALES, I]])
   TableAccessRel(table=[[CATALOG, SALES, J]])
 ]]>
@@ -2278,4 +2282,75 @@ AggregateRel(group=[{1}], EXPR$1=[COUNT($0)])
 ]]>
         </Resource>
     </TestCase>
+    <TestCase name="testConvertMultiJoinRuleOuterJoins2">
+        <Resource name="sql">
+            <![CDATA[select * from A right join B on a = b join C on b = c]]>
+        </Resource>
+        <Resource name="planBefore">
+            <![CDATA[
+ProjectRel(A=[$0], B=[$1], C=[$2])
+  JoinRel(condition=[=($1, $2)], joinType=[inner])
+    JoinRel(condition=[=($0, $1)], joinType=[right])
+      TableAccessRel(table=[[CATALOG, SALES, A]])
+      TableAccessRel(table=[[CATALOG, SALES, B]])
+    TableAccessRel(table=[[CATALOG, SALES, C]])
+]]>
+        </Resource>
+        <Resource name="planAfter">
+            <![CDATA[
+MultiJoinRel(joinFilter=[=($1, $2)], isFullOuterJoin=[false], joinTypes=[[INNER, INNER]], outerJoinConditions=[[NULL, NULL]], projFields=[[ALL, ALL]])
+  MultiJoinRel(joinFilter=[true], isFullOuterJoin=[false], joinTypes=[[RIGHT, INNER]], outerJoinConditions=[[=($0, $1), NULL]], projFields=[[ALL, ALL]])
+    TableAccessRel(table=[[CATALOG, SALES, A]])
+    TableAccessRel(table=[[CATALOG, SALES, B]])
+  TableAccessRel(table=[[CATALOG, SALES, C]])
+]]>
+        </Resource>
+    </TestCase>
+    <TestCase name="testConvertMultiJoinRuleOuterJoins3">
+        <Resource name="sql">
+            <![CDATA[select * from A join B on a = b left join C on b = c]]>
+        </Resource>
+        <Resource name="planBefore">
+            <![CDATA[
+ProjectRel(A=[$0], B=[$1], C=[$2])
+  JoinRel(condition=[=($1, $2)], joinType=[left])
+    JoinRel(condition=[=($0, $1)], joinType=[inner])
+      TableAccessRel(table=[[CATALOG, SALES, A]])
+      TableAccessRel(table=[[CATALOG, SALES, B]])
+    TableAccessRel(table=[[CATALOG, SALES, C]])
+]]>
+        </Resource>
+        <Resource name="planAfter">
+            <![CDATA[
+MultiJoinRel(joinFilter=[=($0, $1)], isFullOuterJoin=[false], joinTypes=[[INNER, INNER, LEFT]], outerJoinConditions=[[NULL, NULL, =($1, $2)]], projFields=[[ALL, ALL, ALL]])
+  TableAccessRel(table=[[CATALOG, SALES, A]])
+  TableAccessRel(table=[[CATALOG, SALES, B]])
+  TableAccessRel(table=[[CATALOG, SALES, C]])
+]]>
+        </Resource>
+    </TestCase>
+    <TestCase name="testConvertMultiJoinRuleOuterJoins4">
+        <Resource name="sql">
+            <![CDATA[select * from A join B on a = b right join C on b = c]]>
+        </Resource>
+        <Resource name="planBefore">
+            <![CDATA[
+ProjectRel(A=[$0], B=[$1], C=[$2])
+  JoinRel(condition=[=($1, $2)], joinType=[right])
+    JoinRel(condition=[=($0, $1)], joinType=[inner])
+      TableAccessRel(table=[[CATALOG, SALES, A]])
+      TableAccessRel(table=[[CATALOG, SALES, B]])
+    TableAccessRel(table=[[CATALOG, SALES, C]])
+]]>
+        </Resource>
+        <Resource name="planAfter">
+            <![CDATA[
+MultiJoinRel(joinFilter=[true], isFullOuterJoin=[false], joinTypes=[[RIGHT, INNER]], outerJoinConditions=[[=($1, $2), NULL]], projFields=[[ALL, ALL]])
+  MultiJoinRel(joinFilter=[=($0, $1)], isFullOuterJoin=[false], joinTypes=[[INNER, INNER]], outerJoinConditions=[[NULL, NULL]], projFields=[[ALL, ALL]])
+    TableAccessRel(table=[[CATALOG, SALES, A]])
+    TableAccessRel(table=[[CATALOG, SALES, B]])
+  TableAccessRel(table=[[CATALOG, SALES, C]])
+]]>
+        </Resource>
+    </TestCase>
 </Root>

http://git-wip-us.apache.org/repos/asf/incubator-optiq/blob/99c7ff96/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 f1458ac..7bbadea 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
@@ -44,14 +44,15 @@ import net.hydromatic.tpcds.query.Query;
 public class TpcdsTest {
   private static
   Function<Pair<List<Prepare.Materialization>, Holder<Program>>, Void>
-  handler(final boolean bushy) {
+  handler(final boolean bushy, final int minJoinCount) {
     return new Function<Pair<List<Prepare.Materialization>, Holder<Program>>,
         Void>() {
       public Void apply(
           Pair<List<Prepare.Materialization>, Holder<Program>> pair) {
         pair.right.set(
             Programs.sequence(
-                Programs.heuristicJoinOrder(Programs.RULE_SET, bushy),
+                Programs.heuristicJoinOrder(Programs.RULE_SET, bushy,
+                    minJoinCount),
                 Programs.CALC_PROGRAM));
         return null;
       }
@@ -115,7 +116,7 @@ public class TpcdsTest {
   @Test public void testQuery17Plan() {
     //noinspection unchecked
     checkQuery(17)
-        .withHook(Hook.PROGRAM, handler(true))
+        .withHook(Hook.PROGRAM, handler(true, 2))
         .explainMatches("including all attributes ",
             OptiqAssert.checkMaskedResultContains(""
                 + "EnumerableCalcRel(expr#0..11=[{inputs}], expr#12=[/($t5, $t4)], expr#13=[/($t8, $t7)], expr#14=[/($t11, $t10)], proj#0..5=[{exprs}], STORE_SALES_QUANTITYCOV=[$t12], AS_STORE_RETURNS_QUANTITYCOUNT=[$t6], AS_STORE_RETURNS_QUANTITYAVE=[$t7], AS_STORE_RETURNS_QUANTITYSTDEV=[$t8], STORE_RETURNS_QUANTITYCOV=[$t13], CATALOG_SALES_QUANTITYCOUNT=[$t9], CATALOG_SALES_QUANTITYAVE=[$t10], CATALOG_SALES_QUANTITYSTDEV=[$t14], CATALOG_SALES_QUANTITYCOV=[$t14]): rowcount = 5.434029018852197E26, cumulative cost = {1.618185849567114E30 rows, 1.2672155671963324E30 cpu, 0.0 io}\n"
@@ -155,13 +156,13 @@ public class TpcdsTest {
   @Ignore("work in progress")
   @Test public void testQuery72Plan() {
     checkQuery(72)
-        .withHook(Hook.PROGRAM, handler(true))
+        .withHook(Hook.PROGRAM, handler(true, 2))
         .planContains("xx");
   }
 
   @Test public void testQuery95() {
     checkQuery(95)
-        .withHook(Hook.PROGRAM, handler(false))
+        .withHook(Hook.PROGRAM, handler(false, 6))
         .runs();
   }
 


Mime
View raw message