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 <[email protected]> Authored: Mon Dec 25 23:29:16 2017 +0800 Committer: Julian Hyde <[email protected]> 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
