[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 <[email protected]> Authored: Fri Aug 25 15:42:32 2017 +0800 Committer: Julian Hyde <[email protected]> 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"
