[10/15] calcite git commit: [CALCITE-1960] RelMdPredicates.getPredicates is slow if there are many equivalent columns (Rheet Wong)

[jh...@apache.org]

[CALCITE-1960] RelMdPredicates.getPredicates is slow if there are many equivalent columns (Rheet Wong)

The algorithm to generate candidate mappings was generating very many
duplicates. They were filtered out eventually, but caused an
exponential running time.

Close apache/calcite#530


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

Branch: refs/heads/master
Commit: f1a002ea8386fc89abcebc185b1f0e7a7bd30246
Parents: dc2b86a
Author: LeoWangLZ <wa...@163.com>
Authored: Fri Aug 25 15:42:32 2017 +0800
Committer: Julian Hyde <jh...@apache.org>
Committed: Mon Oct 2 11:13:44 2017 -0700

----------------------------------------------------------------------
 .../calcite/rel/metadata/RelMdPredicates.java   |  4 ++-
 .../apache/calcite/test/RelMetadataTest.java    | 27 ++++++++++++++++++++
 2 files changed, 30 insertions(+), 1 deletion(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/calcite/blob/f1a002ea/core/src/main/java/org/apache/calcite/rel/metadata/RelMdPredicates.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdPredicates.java b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdPredicates.java
index feeabd4..1b7dbc3 100644
--- a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdPredicates.java
+++ b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdPredicates.java
@@ -827,7 +827,9 @@ public class RelMdPredicates
           if (level == 0) {
             nextMapping = null;
           } else {
-            iterationIdx[level] = 0;
+            int tmp = columnSets[level].nextSetBit(0);
+            nextMapping.set(columns[level], tmp);
+            iterationIdx[level] = tmp + 1;
             computeNextMapping(level - 1);
           }
         } else {

http://git-wip-us.apache.org/repos/asf/calcite/blob/f1a002ea/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java b/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java
index 115da8e..f2bed82 100644
--- a/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java
+++ b/core/src/test/java/org/apache/calcite/test/RelMetadataTest.java
@@ -1438,6 +1438,33 @@ public class RelMetadataTest extends SqlToRelTestBase {
     assertThat(pulledUpPredicates, sortsAs("[=($0, 1)]"));
   }
 
+  /** Test case for
+   * <a href="https://issues.apache.org/jira/browse/CALCITE-1960">[CALCITE-1960]
+   * RelMdPredicates.getPredicates is slow if there are many equivalent
+   * columns</a>. Since this is a performance problem, the test result does not
+   * change, but takes over 15 minutes before the fix and 6 seconds after. */
+  @Test(timeout = 20_000) public void testPullUpPredicatesForExprsItr() {
+    final String sql = "select a.EMPNO, a.ENAME\n"
+        + "from (select * from sales.emp ) a\n"
+        + "join (select * from sales.emp  ) b\n"
+        + "on a.empno = b.deptno\n"
+        + "  and a.comm = b.comm\n"
+        + "  and a.mgr=b.mgr\n"
+        + "  and (a.empno < 10 or a.comm < 3 or a.deptno < 10\n"
+        + "    or a.job ='abc' or a.ename='abc' or a.sal='30' or a.mgr >3\n"
+        + "    or a.slacker is not null  or a.HIREDATE is not null\n"
+        + "    or b.empno < 9 or b.comm < 3 or b.deptno < 10 or b.job ='abc'\n"
+        + "    or b.ename='abc' or b.sal='30' or b.mgr >3 or b.slacker )\n"
+        + "join emp c\n"
+        + "on b.mgr =a.mgr and a.empno =b.deptno and a.comm=b.comm\n"
+        + "  and a.deptno=b.deptno and a.job=b.job and a.ename=b.ename\n"
+        + "  and a.mgr=b.deptno and a.slacker=b.slacker";
+    final RelNode rel = convertSql(sql);
+    final RelMetadataQuery mq = RelMetadataQuery.instance();
+    RelOptPredicateList inputSet = mq.getPulledUpPredicates(rel.getInput(0));
+    assertThat(inputSet.pulledUpPredicates.size(), is(131089));
+  }
+
   @Test public void testPullUpPredicatesOnConstant() {
     final String sql = "select deptno, mgr, x, 'y' as y, z from (\n"
         + "  select deptno, mgr, cast(null as integer) as x, cast('1' as int) as z\n"