You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@calcite.apache.org by "Jin Xing (Jira)" <ji...@apache.org> on 2020/01/13 05:09:00 UTC
[jira] [Comment Edited] (CALCITE-3505) Infinite matching of
FilterProjectTransposeRule causes stackoverflow
[ https://issues.apache.org/jira/browse/CALCITE-3505?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16979910#comment-16979910 ]
Jin Xing edited comment on CALCITE-3505 at 1/13/20 5:08 AM:
------------------------------------------------------------
[~hyuan] I commented in CALCITE-3124 and gave my understanding about the root cause.
The root cause of this issue is different from CALCITE-3124 but similar with CALCITE-2223.
Yes, [~zabetak] . It's caused by cycle between RelSubsets.
The infinite loop happens by below steps.
Step-1:
The Sql and original plan is as below
{code:java}
select * from b1, b2
where b1.i = 10 and b2.i = 10
and b1.i = b2.i
LogicalProject(i=[$0], j=[$1], k=[$2], i0=[$3], j0=[$4], k0=[$5])
LogicalFilter(condition=[AND(=($0, 10), =($3, 10), =($0, $3))])
LogicalJoin(condition=[true], joinType=[inner])
LogicalTableScan(table=[[s, b1]])
LogicalTableScan(table=[[s, b2]])
{code}
Step-2:
Thanks to FilterJoinRule, ProjectRemoveRule & JoinCommuteRule, the original plan can be transformed to be equivalents and collect as RelSubset-M:
{code:java}
RelSubset-M:
LogicalProject(i=[$0], j=[$1], k=[$2], i0=[$3], j0=[$4], k0=[$5]) --> OriginalPlan
LogicalFilter(condition=[AND(=($0, 10), =($3, 10), =($0, $3))])
LogicalJoin(condition=[true], joinType=[inner])
LogicalTableScan(table=[[s, b1]])
LogicalTableScan(table=[[s, b2]])
LogicalFilter(condition=[AND(=($0,10),=($3, 10),=($0,$3))]) --> OriginalPlan-equiv0
LogicalJoin(condition=[true], joinType=[inner])
LogicalTableScan(table=[[s, b1]])
LogicalTableScan(table=[[s, b2]])
LogicalFilter(condition=[=($0, $3))]) --> OriginalPlan-equiv1
LogicalJoin(condition=[true], joinType=[inner])
LogicalFilter(condition=[=($0, 10)])
LogicalTableScan(table=[[s, b1]])
LogicalFilter(condition=[=($0, 10)])
LogicalTableScan(table=[[s, b2]])
LogicalProject(i=[$3],j=[$4],k=[$5],i0=[$0],j0=[$1],k0=[$2]) --> OriginalPlan-equiv2
RelSubset-N
{code}
Step-3:
During the transformation in Step-2, we will get a RelSubset-N as below:
{code:java}
RelSubset-N:
LogicalFilter(condition=[=($3, $0))]) --> Plan0
LogicalJoin(condition=[true], joinType=[inner])
LogicalFilter(condition=[=($0, 10)])
LogicalTableScan(table=[[s, b2]])
LogicalFilter(condition=[=($0, 10)])
LogicalTableScan(table=[[s, b1]])
LogicalProject(i=[$3], j=[$4], k=[$5], i0=[$0], j0=[$1], k0=[$2]) --> Plan1
RelSubset-M
{code}
From here, we will notice that RelSubset-M and RelSubset-N references each other and form a cycle.
# LogicalProject in OriginalPlan-equiv2 and LogicalFilter(condition=[=($3, $0)] in Plan0 is transformed by ProjectFilterTransposeRule and generate a new Filter in RelSubset-M
# The LogicalProject in Plan1 and the new generated Filter in RelSubset-M will be matched by ProjectFilterTransposeRule again and generate another new Filter.
# Above two steps will alternate infinitely
was (Author: jinxing6042@126.com):
[~hyuan] I commented in CALCITE-3124 and gave my understanding about the root cause.
The root cause of this issue is different from CALCITE-3124 but similar with CALCITE-2223.
Yes, [~zabetak] . It's caused by cycle between RelSubsets.
The infinite loop happens by below steps.
Step-1:
The Sql and original plan is as below
{code:java}
select * from b1, b2
where b1.i = 10 and b2.i = 10
and b1.i = b2.i
LogicalProject(i=[$0], j=[$1], k=[$2], i0=[$3], j0=[$4], k0=[$5])
LogicalFilter(condition=[AND(=($0, 10), =($3, 10), =($0, $3))])
LogicalJoin(condition=[true], joinType=[inner])
LogicalTableScan(table=[[s, b1]])
LogicalTableScan(table=[[s, b2]])
{code}
Step-2:
Thanks to FilterJoinRule, ProjectRemoveRule & JoinCommuteRule, the original plan can be transformed to be equivalents and collect as RelSubset-M:
{code:java}
RelSubset-M:
LogicalProject(i=[$0], j=[$1], k=[$2], i0=[$3], j0=[$4], k0=[$5]) ------------------------------> OriginalPlan
LogicalFilter(condition=[AND(=($0, 10), =($3, 10), =($0, $3))])
LogicalJoin(condition=[true], joinType=[inner])
LogicalTableScan(table=[[s, b1]])
LogicalTableScan(table=[[s, b2]])
LogicalFilter(condition=[AND(=($0, 10), =($3, 10), =($0, $3))]) ------------------------------> OriginalPlan-equiv0
LogicalJoin(condition=[true], joinType=[inner])
LogicalTableScan(table=[[s, b1]])
LogicalTableScan(table=[[s, b2]])
LogicalFilter(condition=[=($0, $3))]) ------------------------------> OriginalPlan-equiv1
LogicalJoin(condition=[true], joinType=[inner])
LogicalFilter(condition=[=($0, 10)])
LogicalTableScan(table=[[s, b1]])
LogicalFilter(condition=[=($0, 10)])
LogicalTableScan(table=[[s, b2]])
LogicalProject(i=[$3], j=[$4], k=[$5], i0=[$0], j0=[$1], k0=[$2]) ------------------------------> OriginalPlan-equiv2
RelSubset-N
{code}
Step-3:
During the transformation in Step-2, we will get a RelSubset-N as below:
{code:java}
RelSubset-N:
LogicalFilter(condition=[=($3, $0))]) ------------------------------> Plan0
LogicalJoin(condition=[true], joinType=[inner])
LogicalFilter(condition=[=($0, 10)])
LogicalTableScan(table=[[s, b2]])
LogicalFilter(condition=[=($0, 10)])
LogicalTableScan(table=[[s, b1]])
LogicalProject(i=[$3], j=[$4], k=[$5], i0=[$0], j0=[$1], k0=[$2]) ------------------------------> Plan1
RelSubset-M
{code}
From here, we will notice that RelSubset-M and RelSubset-N references each other and form a cycle.
# LogicalProject in OriginalPlan-equiv2 and LogicalFilter(condition=[=($3, $0)] in Plan0 is transformed by ProjectFilterTransposeRule and generate a new Filter in RelSubset-M
# The LogicalProject in Plan1 and the new generated Filter in RelSubset-M will be matched by ProjectFilterTransposeRule again and generate another new Filter.
# Above two steps will alternate infinitely
> Infinite matching of FilterProjectTransposeRule causes stackoverflow
> --------------------------------------------------------------------
>
> Key: CALCITE-3505
> URL: https://issues.apache.org/jira/browse/CALCITE-3505
> Project: Calcite
> Issue Type: Bug
> Components: core
> Reporter: Jin Xing
> Priority: Major
> Attachments: graphviz.svg
>
>
> Run ScannableTableTest#testProjectableFilterableTableJoin with minor change to reproduce
> {code:java}
> @Test public void testProjectableFilterableTableJoin() throws Exception {
> final StringBuilder buf = new StringBuilder();
> final String explain = "PLAN="
> + "EnumerableHashJoin(condition=[=($0, $3)], joinType=[inner])\n"
> + " EnumerableInterpreter\n"
> + " BindableTableScan(table=[[s, b1]], filters=[[=($0, 10)]])\n"
> + " EnumerableInterpreter\n"
> + " BindableTableScan(table=[[s, b2]], filters=[[=($0, 10)]])";
> CalciteAssert.that()
> .with(
> newSchema("s",
> Pair.of("b1", new BeatlesProjectableFilterableTable(buf, true)),
> Pair.of("b2", new BeatlesProjectableFilterableTable(buf, true))))
> .query("select * from \"s\".\"b1\", \"s\".\"b2\" "
> + "where \"s\".\"b1\".\"i\" = 10 and \"s\".\"b2\".\"i\" = 10 "
> + "and \"s\".\"b1\".\"i\" = \"s\".\"b2\".\"i\"")
> .withHook(Hook.PLANNER, (Consumer<RelOptPlanner>) planner -> {
> planner.removeRule(EnumerableRules.ENUMERABLE_MERGE_JOIN_RULE);
> })
> .explainContains(explain);
> }
> {code}
> This test has nothing to do with ENUMERABLE_MERGE_JOIN_RULE, but if we disable it with planner hook, stackoverflow happens;
> I debugged and found that FilterProjectTransposeRule is matched infinitely but not sure the root cause.
>
>
--
This message was sent by Atlassian Jira
(v8.3.4#803005)