[
https://issues.apache.org/jira/browse/CALCITE-7936?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Zhen Chen updated CALCITE-7936:
-------------------------------
Description:
The top-down decorrelator can introduce a redundant join when decorrelating
nested INNER LATERAL queries. If the left input of a nested Correlate does not
reference any enclosing correlation variables, it does not need to carry the
outer correlation domain when that domain is already carried by the right input.
For example, with top-down decorrelation enabled:
{{WITH dept (deptno, dname) AS (
VALUES (10, 'ACCOUNTING'), (20, 'RESEARCH')
),
emp (empno, deptno, ename) AS (
VALUES (7369, 20, 'SMITH'),
(7782, 10, 'CLARK'),
(7499, 30, 'ALLEN')
)
SELECT *
FROM dept,
(VALUES 'A', 'M') AS v (v)
CROSS JOIN LATERAL (
SELECT *
FROM emp
WHERE emp.deptno = dept.deptno
AND POSITION(v.v IN emp.ename) > 0
) AS emp;}}
The input {{v}} is independent of {{{}dept{}}}, while the LATERAL subquery
references both {{dept.deptno}} and {{{}v.v{}}}.
Before this optimization, the decorrelated plan contains five joins. The left
input of the nested join is unnecessarily expanded by a cross join between
{{v}} and the outer department domain:
{{LogicalProject(EXPR$0=[$0], EXPR$1=[$1], V=[$2], EXPR$000=[$4], EXPR$10=[$5],
EXPR$2=[$6])
LogicalJoin(condition=[IS NOT DISTINCT FROM($0, $3)], joinType=[inner])
LogicalValues(tuples=[[\{ 10, 'ACCOUNTING' }, \{ 20, 'RESEARCH ' }]])
LogicalJoin(condition=[AND(IS NOT DISTINCT FROM($1, $5), IS NOT DISTINCT
FROM($0, $6))], joinType=[inner])
LogicalJoin(condition=[true], joinType=[inner])
LogicalValues(tuples=[[\{ 'A' }, \{ 'M' }]])
LogicalProject(EXPR$0=[$0])
LogicalValues(tuples=[[\{ 10, 'ACCOUNTING' }, \{ 20, 'RESEARCH ' }]])
LogicalJoin(condition=[AND(=($1, $3), >(POSITION($4, $2), 0))],
joinType=[inner])
LogicalValues(tuples=[[\{ 7369, 20, 'SMITH' }, \{ 7782, 10, 'CLARK' },
\{ 7499, 30, 'ALLEN' }]])
LogicalProject(EXPR$0=[$1], V=[$0])
LogicalJoin(condition=[true], joinType=[inner])
LogicalValues(tuples=[[\{ 'A' }, \{ 'M' }]])
LogicalProject(EXPR$0=[$0])
LogicalValues(tuples=[[\{ 10, 'ACCOUNTING' }, \{ 20, 'RESEARCH '
}]])}}
After this optimization, the plan contains four joins. The left input remains
the original {{{}VALUES{}}}, and the right input carries the outer correlation
domain:
{{LogicalProject(EXPR$0=[$0], EXPR$1=[$1], V=[$2], EXPR$00=[$3], EXPR$10=[$4],
EXPR$2=[$5])
LogicalJoin(condition=[IS NOT DISTINCT FROM($0, $6)], joinType=[inner])
LogicalValues(tuples=[[\{ 10, 'ACCOUNTING' }, \{ 20, 'RESEARCH ' }]])
LogicalJoin(condition=[IS NOT DISTINCT FROM($0, $5)], joinType=[inner])
LogicalValues(tuples=[[\{ 'A' }, \{ 'M' }]])
LogicalJoin(condition=[AND(=($1, $3), >(POSITION($4, $2), 0))],
joinType=[inner])
LogicalValues(tuples=[[\{ 7369, 20, 'SMITH' }, \{ 7782, 10, 'CLARK' },
\{ 7499, 30, 'ALLEN' }]])
LogicalProject(EXPR$0=[$1], V=[$0])
LogicalJoin(condition=[true], joinType=[inner])
LogicalValues(tuples=[[\{ 'A' }, \{ 'M' }]])
LogicalProject(EXPR$0=[$0])
LogicalValues(tuples=[[\{ 10, 'ACCOUNTING' }, \{ 20, 'RESEARCH '
}]])}}
Both plans were generated from the same SQL using the same planning steps, with
only the implementation of {{TopDownGeneralDecorrelator}} changed.
The optimization removes the redundant domain join from the left branch and
adjusts the join conditions and output mappings accordingly. The combined
domain needed to decorrelate the right input remains present. This produces a
simpler plan for subsequent optimization.
The scope is limited to nested INNER Correlates whose left input does not
reference enclosing correlation variables. The rewrite must preserve duplicate
rows, NULL correlation keys, and output column mappings.
The regression test {{testTopDownGeneralDecorrelateForNestedLateralJoin}}
checks the new plan through its expected {{planAfter}} snapshot. Execution
tests in {{lateral.iq}} cover duplicate rows and NULL correlation keys.
This improvement was identified during the investigation of CALCITE-7928 and
initially implemented in [PR
#5408|https://github.com/apache/calcite/pull/5408]. It is independent of the
Volcano planning-time explosion discussed in [PR
#5410|https://github.com/apache/calcite/pull/5410], which involves
join-reordering rules and {{PROJECT_MERGE}} generating many duplicate Projects.
Simplifying the decorrelated plan does not resolve that underlying planner
issue.
was:
The top-down decorrelator can generate unnecessarily complex plans for nested
LATERAL queries. When a nested INNER Correlate has a left input that does not
reference any enclosing correlation variables, the current implementation still
joins that input with the outer correlation domain. This introduces a redundant
cross join and additional correlation columns into the generated plan.
For example, consider the following query with top-down decorrelation enabled:
{code:java}
WITH dept (deptno, dname) AS (
VALUES (10, 'ACCOUNTING'), (20, 'RESEARCH')
),
emp (empno, deptno, ename) AS (
VALUES (7369, 20, 'SMITH'),
(7782, 10, 'CLARK'),
(7499, 30, 'ALLEN')
)
SELECT *
FROM dept,
(VALUES 'A', 'M') AS v (v)
CROSS JOIN LATERAL (
SELECT *
FROM emp
WHERE emp.deptno = dept.deptno
AND POSITION(v.v IN emp.ename) > 0
) AS emp;
{code}
Here, the left input of the nested LATERAL join (`v`) is independent of `dept`,
while its right input references both `dept` and `v`. The enclosing correlation
variables can be carried by the right input, allowing the resulting join to use
an independently decorrelated left input without attaching the outer domain to
it.
The proposed improvement is to avoid this redundant domain propagation for
nested INNER Correlates. The combined domain required to decorrelate the right
input must remain available, and the rewrite must preserve duplicate rows, NULL
correlation keys, and output column mappings. Other join types and left inputs
that reference enclosing correlation variables require their existing treatment.
Generating a smaller equivalent plan reduces unnecessary joins and columns
passed to subsequent optimization, and can reduce the work required to explore
alternative plans. Regression coverage should verify both the simplified plan
structure and result correctness.
This opportunity was identified while investigating
CALCITE-7928([https://issues.apache.org/jira/browse/CALCITE-7928]). As
explained in [PR #5410|#5410]([https://github.com/apache/calcite/pull/5410]),
the original excessive planning time involves join-reordering rules and
`PROJECT_MERGE` generating many duplicate Projects. That PR disables
`PROJECT_MERGE` for the affected test as a workaround; the underlying planner
issue remains separate.
This ticket tracks the decorrelator improvement independently of that planner
issue. [PR #5408|#5408]([https://github.com/apache/calcite/pull/5408]) contains
an initial implementation.
> Top-down decorrelator should avoid redundant domain joins for nested LATERAL
> queries
> ------------------------------------------------------------------------------------
>
> Key: CALCITE-7936
> URL: https://issues.apache.org/jira/browse/CALCITE-7936
> Project: Calcite
> Issue Type: Improvement
> Components: core
> Reporter: Zhen Chen
> Priority: Major
>
> The top-down decorrelator can introduce a redundant join when decorrelating
> nested INNER LATERAL queries. If the left input of a nested Correlate does
> not reference any enclosing correlation variables, it does not need to carry
> the outer correlation domain when that domain is already carried by the right
> input.
> For example, with top-down decorrelation enabled:
> {{WITH dept (deptno, dname) AS (
> VALUES (10, 'ACCOUNTING'), (20, 'RESEARCH')
> ),
> emp (empno, deptno, ename) AS (
> VALUES (7369, 20, 'SMITH'),
> (7782, 10, 'CLARK'),
> (7499, 30, 'ALLEN')
> )
> SELECT *
> FROM dept,
> (VALUES 'A', 'M') AS v (v)
> CROSS JOIN LATERAL (
> SELECT *
> FROM emp
> WHERE emp.deptno = dept.deptno
> AND POSITION(v.v IN emp.ename) > 0
> ) AS emp;}}
>
> The input {{v}} is independent of {{{}dept{}}}, while the LATERAL subquery
> references both {{dept.deptno}} and {{{}v.v{}}}.
> Before this optimization, the decorrelated plan contains five joins. The left
> input of the nested join is unnecessarily expanded by a cross join between
> {{v}} and the outer department domain:
>
> {{LogicalProject(EXPR$0=[$0], EXPR$1=[$1], V=[$2], EXPR$000=[$4],
> EXPR$10=[$5], EXPR$2=[$6])
> LogicalJoin(condition=[IS NOT DISTINCT FROM($0, $3)], joinType=[inner])
> LogicalValues(tuples=[[\{ 10, 'ACCOUNTING' }, \{ 20, 'RESEARCH ' }]])
> LogicalJoin(condition=[AND(IS NOT DISTINCT FROM($1, $5), IS NOT DISTINCT
> FROM($0, $6))], joinType=[inner])
> LogicalJoin(condition=[true], joinType=[inner])
> LogicalValues(tuples=[[\{ 'A' }, \{ 'M' }]])
> LogicalProject(EXPR$0=[$0])
> LogicalValues(tuples=[[\{ 10, 'ACCOUNTING' }, \{ 20, 'RESEARCH '
> }]])
> LogicalJoin(condition=[AND(=($1, $3), >(POSITION($4, $2), 0))],
> joinType=[inner])
> LogicalValues(tuples=[[\{ 7369, 20, 'SMITH' }, \{ 7782, 10, 'CLARK'
> }, \{ 7499, 30, 'ALLEN' }]])
> LogicalProject(EXPR$0=[$1], V=[$0])
> LogicalJoin(condition=[true], joinType=[inner])
> LogicalValues(tuples=[[\{ 'A' }, \{ 'M' }]])
> LogicalProject(EXPR$0=[$0])
> LogicalValues(tuples=[[\{ 10, 'ACCOUNTING' }, \{ 20, 'RESEARCH
> ' }]])}}
>
> After this optimization, the plan contains four joins. The left input remains
> the original {{{}VALUES{}}}, and the right input carries the outer
> correlation domain:
>
> {{LogicalProject(EXPR$0=[$0], EXPR$1=[$1], V=[$2], EXPR$00=[$3],
> EXPR$10=[$4], EXPR$2=[$5])
> LogicalJoin(condition=[IS NOT DISTINCT FROM($0, $6)], joinType=[inner])
> LogicalValues(tuples=[[\{ 10, 'ACCOUNTING' }, \{ 20, 'RESEARCH ' }]])
> LogicalJoin(condition=[IS NOT DISTINCT FROM($0, $5)], joinType=[inner])
> LogicalValues(tuples=[[\{ 'A' }, \{ 'M' }]])
> LogicalJoin(condition=[AND(=($1, $3), >(POSITION($4, $2), 0))],
> joinType=[inner])
> LogicalValues(tuples=[[\{ 7369, 20, 'SMITH' }, \{ 7782, 10, 'CLARK'
> }, \{ 7499, 30, 'ALLEN' }]])
> LogicalProject(EXPR$0=[$1], V=[$0])
> LogicalJoin(condition=[true], joinType=[inner])
> LogicalValues(tuples=[[\{ 'A' }, \{ 'M' }]])
> LogicalProject(EXPR$0=[$0])
> LogicalValues(tuples=[[\{ 10, 'ACCOUNTING' }, \{ 20, 'RESEARCH
> ' }]])}}
>
> Both plans were generated from the same SQL using the same planning steps,
> with only the implementation of {{TopDownGeneralDecorrelator}} changed.
> The optimization removes the redundant domain join from the left branch and
> adjusts the join conditions and output mappings accordingly. The combined
> domain needed to decorrelate the right input remains present. This produces a
> simpler plan for subsequent optimization.
> The scope is limited to nested INNER Correlates whose left input does not
> reference enclosing correlation variables. The rewrite must preserve
> duplicate rows, NULL correlation keys, and output column mappings.
> The regression test {{testTopDownGeneralDecorrelateForNestedLateralJoin}}
> checks the new plan through its expected {{planAfter}} snapshot. Execution
> tests in {{lateral.iq}} cover duplicate rows and NULL correlation keys.
> This improvement was identified during the investigation of CALCITE-7928 and
> initially implemented in [PR
> #5408|https://github.com/apache/calcite/pull/5408]. It is independent of the
> Volcano planning-time explosion discussed in [PR
> #5410|https://github.com/apache/calcite/pull/5410], which involves
> join-reordering rules and {{PROJECT_MERGE}} generating many duplicate
> Projects. Simplifying the decorrelated plan does not resolve that underlying
> planner issue.
--
This message was sent by Atlassian Jira
(v10.3.26#10030026)
