calcite-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jh...@apache.org
Subject calcite git commit: [CALCITE-2111] In HepPlanner, allow applying rules to RelNodes in depth-first order (LeoWangLZ)
Date Wed, 03 Jan 2018 18:43:06 GMT
Repository: calcite
Updated Branches:
  refs/heads/master b88bd70a9 -> 1945c9a92


[CALCITE-2111] In HepPlanner, allow applying rules to RelNodes in depth-first order (LeoWangLZ)

Add new HepMatchOrder value DEPTH_FIRST, and make it the default for
HepPlanner. It is more efficient than ARBITRARY because it avoids
applying the same rule repeatedly to the whole tree each time there is
a match.


Project: http://git-wip-us.apache.org/repos/asf/calcite/repo
Commit: http://git-wip-us.apache.org/repos/asf/calcite/commit/1945c9a9
Tree: http://git-wip-us.apache.org/repos/asf/calcite/tree/1945c9a9
Diff: http://git-wip-us.apache.org/repos/asf/calcite/diff/1945c9a9

Branch: refs/heads/master
Commit: 1945c9a9283121f7a690ec024632dcd09dff8351
Parents: b88bd70
Author: LeoWangLZ <wanglongzhong2006@163.com>
Authored: Mon Dec 25 23:29:16 2017 +0800
Committer: Julian Hyde <jhyde@apache.org>
Committed: Tue Jan 2 20:23:01 2018 -0800

----------------------------------------------------------------------
 .../apache/calcite/plan/hep/HepMatchOrder.java  |  15 +-
 .../org/apache/calcite/plan/hep/HepPlanner.java | 103 ++++++++----
 .../org/apache/calcite/plan/hep/HepProgram.java |   2 +-
 .../org/apache/calcite/test/HepPlannerTest.java | 164 +++++++++++++++++++
 4 files changed, 253 insertions(+), 31 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/calcite/blob/1945c9a9/core/src/main/java/org/apache/calcite/plan/hep/HepMatchOrder.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/plan/hep/HepMatchOrder.java b/core/src/main/java/org/apache/calcite/plan/hep/HepMatchOrder.java
index 2b5f1ae..a590f75 100644
--- a/core/src/main/java/org/apache/calcite/plan/hep/HepMatchOrder.java
+++ b/core/src/main/java/org/apache/calcite/plan/hep/HepMatchOrder.java
@@ -22,7 +22,7 @@ package org.apache.calcite.plan.hep;
  */
 public enum HepMatchOrder {
   /**
-   * Match in arbitrary order. This is the default because it is the most
+   * Match in arbitrary order. This is the default because it is
    * efficient, and most rules don't care about order.
    */
   ARBITRARY,
@@ -37,7 +37,18 @@ public enum HepMatchOrder {
    * Match from root down. A match attempt at an ancestor always precedes all
    * match attempts at its descendants.
    */
-  TOP_DOWN
+  TOP_DOWN,
+
+  /**
+   * Match in depth-first order.
+   *
+   * <p>It avoids applying a rule to the previous
+   * {@link org.apache.calcite.rel.RelNode} repeatedly after new vertex is
+   * generated in one rule application. It can therefore be more efficient than
+   * {@link #ARBITRARY} in cases such as
+   * {@link org.apache.calcite.rel.core.Union} with large fan-out.
+   */
+  DEPTH_FIRST
 }
 
 // End HepMatchOrder.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/1945c9a9/core/src/main/java/org/apache/calcite/plan/hep/HepPlanner.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/plan/hep/HepPlanner.java b/core/src/main/java/org/apache/calcite/plan/hep/HepPlanner.java
index 410ef27..657460a 100644
--- a/core/src/main/java/org/apache/calcite/plan/hep/HepPlanner.java
+++ b/core/src/main/java/org/apache/calcite/plan/hep/HepPlanner.java
@@ -360,6 +360,33 @@ public class HepPlanner extends AbstractRelOptPlanner {
     LOGGER.trace("Leaving group");
   }
 
+  private int depthFirstApply(Iterator<HepRelVertex> iter,
+      Collection<RelOptRule> rules,
+      boolean forceConversions, int nMatches) {
+    while (iter.hasNext()) {
+      HepRelVertex vertex = iter.next();
+      for (RelOptRule rule : rules) {
+        HepRelVertex newVertex =
+            applyRule(rule, vertex, forceConversions);
+        if (newVertex != null) {
+          ++nMatches;
+          if (nMatches >= currentProgram.matchLimit) {
+            return nMatches;
+          }
+
+          // To the extent possible, pick up where we left
+          // off; have to create a new iterator because old
+          // one was invalidated by transformation.
+          Iterator<HepRelVertex> depthIter = getGraphIterator(newVertex);
+          nMatches = depthFirstApply(depthIter, rules, forceConversions,
+              nMatches);
+          break;
+        }
+      }
+    }
+    return nMatches;
+  }
+
   private void applyRules(
       Collection<RelOptRule> rules,
       boolean forceConversions) {
@@ -372,7 +399,8 @@ public class HepPlanner extends AbstractRelOptPlanner {
     LOGGER.trace("Applying rule set {}", rules);
 
     boolean fullRestartAfterTransformation =
-        currentProgram.matchOrder != HepMatchOrder.ARBITRARY;
+        currentProgram.matchOrder != HepMatchOrder.ARBITRARY
+        && currentProgram.matchOrder != HepMatchOrder.DEPTH_FIRST;
 
     int nMatches = 0;
 
@@ -397,7 +425,13 @@ public class HepPlanner extends AbstractRelOptPlanner {
               // off; have to create a new iterator because old
               // one was invalidated by transformation.
               iter = getGraphIterator(newVertex);
-
+              if (currentProgram.matchOrder == HepMatchOrder.DEPTH_FIRST) {
+                nMatches =
+                    depthFirstApply(iter, rules, forceConversions, nMatches);
+                if (nMatches >= currentProgram.matchLimit) {
+                  return;
+                }
+              }
               // Remember to go around again since we're
               // skipping some stuff.
               fixpoint = false;
@@ -420,39 +454,52 @@ public class HepPlanner extends AbstractRelOptPlanner {
     // better optimizer performance.
     collectGarbage();
 
-    if (currentProgram.matchOrder == HepMatchOrder.ARBITRARY) {
+    switch (currentProgram.matchOrder) {
+    case ARBITRARY:
+    case DEPTH_FIRST:
       return DepthFirstIterator.of(graph, start).iterator();
-    }
-
-    assert start == root;
 
-    // see above
+    case TOP_DOWN:
+      assert start == root;
+      // see above
 /*
         collectGarbage();
 */
+      return TopologicalOrderIterator.of(graph).iterator();
 
-    Iterable<HepRelVertex> iter =
-        TopologicalOrderIterator.of(graph);
+    case BOTTOM_UP:
+    default:
+      assert start == root;
 
-    if (currentProgram.matchOrder == HepMatchOrder.TOP_DOWN) {
-      return iter.iterator();
-    }
+      // see above
+/*
+        collectGarbage();
+*/
 
-    // TODO jvs 4-Apr-2006:  enhance TopologicalOrderIterator
-    // to support reverse walk.
-    assert currentProgram.matchOrder == HepMatchOrder.BOTTOM_UP;
-    final List<HepRelVertex> list = new ArrayList<>();
-    for (HepRelVertex vertex : iter) {
-      list.add(vertex);
+      // TODO jvs 4-Apr-2006:  enhance TopologicalOrderIterator
+      // to support reverse walk.
+      final List<HepRelVertex> list = new ArrayList<>();
+      for (HepRelVertex vertex : TopologicalOrderIterator.of(graph)) {
+        list.add(vertex);
+      }
+      Collections.reverse(list);
+      return list.iterator();
     }
-    Collections.reverse(list);
-    return list.iterator();
+  }
+
+  /** Returns whether the vertex is valid. */
+  private boolean belongsToDag(HepRelVertex vertex) {
+    String digest = vertex.getCurrentRel().getDigest();
+    return mapDigestToVertex.get(digest) != null;
   }
 
   private HepRelVertex applyRule(
       RelOptRule rule,
       HepRelVertex vertex,
       boolean forceConversions) {
+    if (!belongsToDag(vertex)) {
+      return null;
+    }
     RelTrait parentTrait = null;
     List<RelNode> parents = null;
     if (rule instanceof ConverterRule) {
@@ -840,14 +887,14 @@ public class HepPlanner extends AbstractRelOptPlanner {
       mapDigestToVertex.remove(oldDigest);
     }
     String newDigest = rel.recomputeDigest();
-    if (mapDigestToVertex.get(newDigest) == null) {
-      mapDigestToVertex.put(newDigest, vertex);
-    } else {
-      // REVIEW jvs 5-Apr-2006:  Could this lead us to
-      // miss common subexpressions?  When called from
-      // addRelToGraph, we'll check after this method returns,
-      // but what about the other callers?
-    }
+    // When a transformation happened in one rule apply, support
+    // vertex2 replace vertex1, but the current relNode of
+    // vertex1 and vertex2 is same,
+    // then the digest is also same. but we can't remove vertex2,
+    // otherwise the digest will be removed wrongly in the mapDigestToVertex
+    //  when collectGC
+    // so it must update the digest that map to vertex
+    mapDigestToVertex.put(newDigest, vertex);
     if (rel != vertex.getCurrentRel()) {
       vertex.replaceRel(rel);
     }

http://git-wip-us.apache.org/repos/asf/calcite/blob/1945c9a9/core/src/main/java/org/apache/calcite/plan/hep/HepProgram.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/plan/hep/HepProgram.java b/core/src/main/java/org/apache/calcite/plan/hep/HepProgram.java
index c7f44df..d068a93 100644
--- a/core/src/main/java/org/apache/calcite/plan/hep/HepProgram.java
+++ b/core/src/main/java/org/apache/calcite/plan/hep/HepProgram.java
@@ -66,7 +66,7 @@ public class HepProgram {
 
   void initialize(boolean clearCache) {
     matchLimit = MATCH_UNTIL_FIXPOINT;
-    matchOrder = HepMatchOrder.ARBITRARY;
+    matchOrder = HepMatchOrder.DEPTH_FIRST;
     group = null;
 
     for (HepInstruction instruction : instructions) {

http://git-wip-us.apache.org/repos/asf/calcite/blob/1945c9a9/core/src/test/java/org/apache/calcite/test/HepPlannerTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/test/HepPlannerTest.java b/core/src/test/java/org/apache/calcite/test/HepPlannerTest.java
index c88fe24..e3e144b 100644
--- a/core/src/test/java/org/apache/calcite/test/HepPlannerTest.java
+++ b/core/src/test/java/org/apache/calcite/test/HepPlannerTest.java
@@ -16,6 +16,7 @@
  */
 package org.apache.calcite.test;
 
+import org.apache.calcite.plan.RelOptListener;
 import org.apache.calcite.plan.hep.HepMatchOrder;
 import org.apache.calcite.plan.hep.HepPlanner;
 import org.apache.calcite.plan.hep.HepProgram;
@@ -28,10 +29,14 @@ import org.apache.calcite.rel.rules.CoerceInputsRule;
 import org.apache.calcite.rel.rules.FilterToCalcRule;
 import org.apache.calcite.rel.rules.ProjectRemoveRule;
 import org.apache.calcite.rel.rules.ProjectToCalcRule;
+import org.apache.calcite.rel.rules.ReduceExpressionsRule;
 import org.apache.calcite.rel.rules.UnionToDistinctRule;
 
 import org.junit.Test;
 
+import static org.hamcrest.CoreMatchers.is;
+import static org.junit.Assert.assertThat;
+
 /**
  * HepPlannerTest is a unit test for {@link HepPlanner}. See
  * {@link RelOptRulesTest} for an explanation of how to add tests; the tests in
@@ -46,6 +51,109 @@ public class HepPlannerTest extends RelOptTestBase {
       "(select name from dept union select ename from emp)"
       + " union (select ename from bonus)";
 
+  private static final String COMPLEX_UNION_TREE = "select * from (\n"
+      + "  select ENAME, 50011895 as cat_id, '1' as cat_name, 1 as require_free_postage,
0 as require_15return, 0 as require_48hour,1 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50011895 union all\n"
+      + "  select ENAME, 50013023 as cat_id, '2' as cat_name, 0 as require_free_postage,
0 as require_15return, 0 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50013023 union all\n"
+      + "  select ENAME, 50013032 as cat_id, '3' as cat_name, 0 as require_free_postage,
0 as require_15return, 0 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50013032 union all\n"
+      + "  select ENAME, 50013024 as cat_id, '4' as cat_name, 0 as require_free_postage,
0 as require_15return, 0 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50013024 union all\n"
+      + "  select ENAME, 50004204 as cat_id, '5' as cat_name, 0 as require_free_postage,
0 as require_15return, 0 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50004204 union all\n"
+      + "  select ENAME, 50013043 as cat_id, '6' as cat_name, 0 as require_free_postage,
0 as require_15return, 0 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50013043 union all\n"
+      + "  select ENAME, 290903 as cat_id, '7' as cat_name, 1 as require_free_postage, 0
as require_15return, 0 as require_48hour,1 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 290903 union all\n"
+      + "  select ENAME, 50008261 as cat_id, '8' as cat_name, 1 as require_free_postage,
0 as require_15return, 0 as require_48hour,1 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50008261 union all\n"
+      + "  select ENAME, 124478013 as cat_id, '9' as cat_name, 0 as require_free_postage,
0 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 124478013 union all\n"
+      + "  select ENAME, 124472005 as cat_id, '10' as cat_name, 0 as require_free_postage,
0 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 124472005 union all\n"
+      + "  select ENAME, 50013475 as cat_id, '11' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50013475 union all\n"
+      + "  select ENAME, 50018263 as cat_id, '12' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50018263 union all\n"
+      + "  select ENAME, 50013498 as cat_id, '13' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50013498 union all\n"
+      + "  select ENAME, 350511 as cat_id, '14' as cat_name, 0 as require_free_postage, 1
as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 350511 union all\n"
+      + "  select ENAME, 50019790 as cat_id, '15' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50019790 union all\n"
+      + "  select ENAME, 50015382 as cat_id, '16' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50015382 union all\n"
+      + "  select ENAME, 350503 as cat_id, '17' as cat_name, 0 as require_free_postage, 1
as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 350503 union all\n"
+      + "  select ENAME, 350401 as cat_id, '18' as cat_name, 0 as require_free_postage, 1
as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 350401 union all\n"
+      + "  select ENAME, 50015560 as cat_id, '19' as cat_name, 0 as require_free_postage,
0 as require_15return, 0 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50015560 union all\n"
+      + "  select ENAME, 122658003 as cat_id, '20' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 122658003 union all\n"
+      + "  select ENAME, 122716008 as cat_id, '21' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 122716008 union all\n"
+      + "  select ENAME, 50018406 as cat_id, '22' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50018406 union all\n"
+      + "  select ENAME, 50018407 as cat_id, '23' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50018407 union all\n"
+      + "  select ENAME, 50024678 as cat_id, '24' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50024678 union all\n"
+      + "  select ENAME, 50022290 as cat_id, '25' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50022290 union all\n"
+      + "  select ENAME, 50020072 as cat_id, '26' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50020072 union all\n"
+      + "  select ENAME, 50024679 as cat_id, '27' as cat_name, 1 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50024679 union all\n"
+      + "  select ENAME, 50013326 as cat_id, '28' as cat_name, 1 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50013326 union all\n"
+      + "  select ENAME, 50020032 as cat_id, '19' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50020032 union all\n"
+      + "  select ENAME, 50022273 as cat_id, '30' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50022273 union all\n"
+      + "  select ENAME, 50013511 as cat_id, '31' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50013511 union all\n"
+      + "  select ENAME, 122694006 as cat_id, '32' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 122694006 union all\n"
+      + "  select ENAME, 50019940 as cat_id, '33' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50019940 union all\n"
+      + "  select ENAME, 50022288 as cat_id, '34' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50022288 union all\n"
+      + "  select ENAME, 50020069 as cat_id, '35' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50020069 union all\n"
+      + "  select ENAME, 50021800 as cat_id, '36' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50021800 union all\n"
+      + "  select ENAME, 50024684 as cat_id, '37' as cat_name, 1 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50024684 union all\n"
+      + "  select ENAME, 50024676 as cat_id, '38' as cat_name, 1 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50024676 union all\n"
+      + "  select ENAME, 50020070 as cat_id, '39' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50020070 union all\n"
+      + "  select ENAME, 50020058 as cat_id, '40' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50020058 union all\n"
+      + "  select ENAME, 50019938 as cat_id, '41' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50019938 union all\n"
+      + "  select ENAME, 122686009 as cat_id, '42' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 122686009 union all\n"
+      + "  select ENAME, 50022286 as cat_id, '43' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50022286 union all\n"
+      + "  select ENAME, 122692007 as cat_id, '44' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 122692007 union all\n"
+      + "  select ENAME, 50020059 as cat_id, '45' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50020059 union all\n"
+      + "  select ENAME, 50006050 as cat_id, '45' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50006050 union all\n"
+      + "  select ENAME, 122718006 as cat_id, '47' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 122718006 union all\n"
+      + "  select ENAME, 50022652 as cat_id, '48' as cat_name, 1 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50022652 union all\n"
+      + "  select ENAME, 50024685 as cat_id, '49' as cat_name, 1 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50024685 union all\n"
+      + "  select ENAME, 50020104 as cat_id, '50' as cat_name, 1 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50020104 union all\n"
+      + "  select ENAME, 50013500 as cat_id, '51' as cat_name, 1 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50013500 union all\n"
+      + "  select ENAME, 50003558 as cat_id, '52' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50003558 union all\n"
+      + "  select ENAME, 50020061 as cat_id, '53' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50020061 union all\n"
+      + "  select ENAME, 122656012 as cat_id, '54' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 122656012 union all\n"
+      + "  select ENAME, 50024812 as cat_id, '55' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50024812 union all\n"
+      + "  select ENAME, 50022287 as cat_id, '56' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50022287 union all\n"
+      + "  select ENAME, 50020107 as cat_id, '57' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50020107 union all\n"
+      + "  select ENAME, 50019842 as cat_id, '58' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50019842 union all\n"
+      + "  select ENAME, 50020106 as cat_id, '59' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50020106 union all\n"
+      + "  select ENAME, 50020071 as cat_id, '60' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50020071 union all\n"
+      + "  select ENAME, 50019939 as cat_id, '61' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50019939 union all\n"
+      + "  select ENAME, 50020034 as cat_id, '62' as cat_name, 1 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50020034 union all\n"
+      + "  select ENAME, 50020025 as cat_id, '63' as cat_name, 1 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50020025 union all\n"
+      + "  select ENAME, 50022293 as cat_id, '64' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50022293 union all\n"
+      + "  select ENAME, 50022279 as cat_id, '65' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50022279 union all\n"
+      + "  select ENAME, 50013818 as cat_id, '66' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50013818 union all\n"
+      + "  select ENAME, 50020060 as cat_id, '67' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50020060 union all\n"
+      + "  select ENAME, 50020062 as cat_id, '68' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50020062 union all\n"
+      + "  select ENAME, 50022276 as cat_id, '69' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50022276 union all\n"
+      + "  select ENAME, 50022280 as cat_id, '70' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50022280 union all\n"
+      + "  select ENAME, 50020619 as cat_id, '71' as cat_name, 1 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50020619 union all\n"
+      + "  select ENAME, 50013347 as cat_id, '72' as cat_name, 1 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50013347 union all\n"
+      + "  select ENAME, 50008698 as cat_id, '73' as cat_name, 1 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50008698 union all\n"
+      + "  select ENAME, 50013334 as cat_id, '74' as cat_name, 1 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50013334 union all\n"
+      + "  select ENAME, 50024810 as cat_id, '75' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50024810 union all\n"
+      + "  select ENAME, 50019936 as cat_id, '76' as cat_name, 1 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50019936 union all\n"
+      + "  select ENAME, 50024813 as cat_id, '77' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50024813 union all\n"
+      + "  select ENAME, 50020959 as cat_id, '78' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50020959 union all\n"
+      + "  select ENAME, 124474002 as cat_id, '79' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 124474002 union all\n"
+      + "  select ENAME, 50019853 as cat_id, '80' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50019853 union all\n"
+      + "  select ENAME, 50019837 as cat_id, '81' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50019837 union all\n"
+      + "  select ENAME, 50022289 as cat_id, '82' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50022289 union all\n"
+      + "  select ENAME, 50022278 as cat_id, '83' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50022278 union all\n"
+      + "  select ENAME, 50024690 as cat_id, '84' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50024690 union all\n"
+      + "  select ENAME, 50592002 as cat_id, '85' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50592002 union all\n"
+      + "  select ENAME, 50013342 as cat_id, '86' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50013342 union all\n"
+      + "  select ENAME, 50022296 as cat_id, '87' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50022296 union all\n"
+      + "  select ENAME, 123456001 as cat_id, '88' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 123456001 union all\n"
+      + "  select ENAME, 50022298 as cat_id, '89' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50022298 union all\n"
+      + "  select ENAME, 50022274 as cat_id, '90' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50022274 union all\n"
+      + "  select ENAME, 50006046 as cat_id, '91' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50006046 union all\n"
+      + "  select ENAME, 50020676 as cat_id, '92' as cat_name, 1 as require_free_postage,
0 as require_15return, 0 as require_48hour,1 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50020676 union all\n"
+      + "  select ENAME, 50020678 as cat_id, '93' as cat_name, 1 as require_free_postage,
0 as require_15return, 0 as require_48hour,1 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50020678 union all\n"
+      + "  select ENAME, 121398012 as cat_id, '94' as cat_name, 1 as require_free_postage,
0 as require_15return, 0 as require_48hour,1 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 121398012 union all\n"
+      + "  select ENAME, 50020720 as cat_id, '95' as cat_name, 1 as require_free_postage,
0 as require_15return, 0 as require_48hour,1 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50020720 union all\n"
+      + "  select ENAME, 50001714 as cat_id, '96' as cat_name, 0 as require_free_postage,
1 as require_15return, 1 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50001714 union all\n"
+      + "  select ENAME, 50008905 as cat_id, '97' as cat_name, 1 as require_free_postage,
0 as require_15return, 1 as require_48hour,1 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50008905 union all\n"
+      + "  select ENAME, 50008904 as cat_id, '98' as cat_name, 1 as require_free_postage,
0 as require_15return, 1 as require_48hour,1 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50008904 union all\n"
+      + "  select ENAME, 50022358 as cat_id, '99' as cat_name, 0 as require_free_postage,
0 as require_15return, 0 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50022358 union all\n"
+      + "  select ENAME, 50022371 as cat_id, '100' as cat_name, 0 as require_free_postage,
0 as require_15return, 0 as require_48hour,0 as require_insurance from emp where EMPNO = 20171216
and MGR = 0 and ENAME = 'Y' and SAL = 50022371\n"
+      + ") a";
+
   //~ Methods ----------------------------------------------------------------
 
   protected DiffRepository getDiffRepos() {
@@ -191,6 +299,62 @@ public class HepPlannerTest extends RelOptTestBase {
         tester.convertSqlToRel("select upper(name) from dept where deptno=20").rel);
     planner.findBestExp();
   }
+
+  @Test public void testRuleApplyCount() {
+    final long applyTimes1 = checkRuleApplyCount(HepMatchOrder.ARBITRARY);
+    assertThat(applyTimes1, is(5451L));
+
+    final long applyTimes2 = checkRuleApplyCount(HepMatchOrder.DEPTH_FIRST);
+    assertThat(applyTimes2, is(403L));
+
+    // DEPTH_FIRST has 10x fewer matches than ARBITRARY
+    assertThat(applyTimes1 > applyTimes2 * 10, is(true));
+  }
+
+  private long checkRuleApplyCount(HepMatchOrder matchOrder) {
+    final HepProgramBuilder programBuilder = HepProgram.builder();
+    programBuilder.addMatchOrder(matchOrder);
+    programBuilder.addRuleInstance(ReduceExpressionsRule.FILTER_INSTANCE);
+    programBuilder.addRuleInstance(ReduceExpressionsRule.PROJECT_INSTANCE);
+
+    final HepTestListener listener = new HepTestListener(0);
+    HepPlanner planner = new HepPlanner(programBuilder.build());
+    planner.addListener(listener);
+    planner.setRoot(tester.convertSqlToRel(COMPLEX_UNION_TREE).rel);
+    planner.findBestExp();
+    return listener.getApplyTimes();
+  }
+
+  /** Listener for HepPlannerTest; counts how many times rules fire. */
+  private class HepTestListener implements RelOptListener {
+    private long applyTimes;
+
+    HepTestListener(long applyTimes) {
+      this.applyTimes = applyTimes;
+    }
+
+    long getApplyTimes() {
+      return applyTimes;
+    }
+
+    @Override public void relEquivalenceFound(RelEquivalenceEvent event) {
+    }
+
+    @Override public void ruleAttempted(RuleAttemptedEvent event) {
+      if (event.isBefore()) {
+        ++applyTimes;
+      }
+    }
+
+    @Override public void ruleProductionSucceeded(RuleProductionEvent event) {
+    }
+
+    @Override public void relDiscarded(RelDiscardedEvent event) {
+    }
+
+    @Override public void relChosen(RelChosenEvent event) {
+    }
+  }
 }
 
 // End HepPlannerTest.java


Mime
View raw message