[
https://issues.apache.org/jira/browse/CALCITE-7869?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=18141580#comment-18141580
]
Mihai Budiu commented on CALCITE-7869:
--------------------------------------
I do not have much experience with lineage in Calcite, so I cannot comment on
the desired result.
> RelMdExpressionLineage should not combine fields from different Union inputs
> ----------------------------------------------------------------------------
>
> Key: CALCITE-7869
> URL: https://issues.apache.org/jira/browse/CALCITE-7869
> Project: Calcite
> Issue Type: Bug
> Components: core
> Affects Versions: 1.42.0
> Reporter: Arnaud Jegou
> Priority: Major
>
> When an expression reads several fields that come from the same Union,
> RelMdExpressionLineage resolves each field's origins from every Union input
> independently, then builds every combination. Most of those combinations
> cannot occur: a row comes from one input of the Union, so all the fields it
> reads come from that input.
> The following test in RelMetadataTest fails on main:
> {code:java}
> @Test void testExpressionLineageUnionKeepsInputFieldsTogether() {
> // empno is column 0 and deptno is column 7 in catalog.sales.emp
> final RelNode rel = sql("select empno + deptno from (\n"
> + " select empno, deptno from emp\n"
> + " union all\n"
> + " select empno, deptno from emp)").toRel();
> final RelMetadataQuery mq = rel.getCluster().getMetadataQuery();
> final RexNode ref = RexInputRef.of(0, rel.getRowType().getFieldList());
> final Set<RexNode> r = mq.getExpressionLineage(rel, ref);
> // A row comes from one input of the union, so empno and deptno always
> // come from the same input: two possible origins, not four.
> assertThat(r.toString(), r, hasSize(2));
> for (RexNode result : r) {
> final RexCall call = (RexCall) result;
> final RexTableInputRef empno =
> (RexTableInputRef) call.getOperands().get(0);
> final RexTableInputRef deptno =
> (RexTableInputRef) call.getOperands().get(1);
> assertThat(result.toString(), empno.getIdentifier(),
> is(deptno.getIdentifier()));
> }
> }
> {code}
> {noformat}
> java.lang.AssertionError: [+([CATALOG, SALES, EMP].#1.$0, [CATALOG, SALES,
> EMP].#0.$7), +([CATALOG, SALES, EMP].#1.$0, [CATALOG, SALES, EMP].#1.$7),
> +([CATALOG, SALES, EMP].#0.$0, [CATALOG, SALES, EMP].#0.$7), +([CATALOG,
> SALES, EMP].#0.$0, [CATALOG, SALES, EMP].#1.$7)]
> Expected: a collection with size <2>
> but: collection size was <4>
> {noformat}
> The first and last expressions pair empno from one input with deptno from the
> other.
> RelMdAllPredicates builds filter predicates the same way, so it reports
> predicates that the plan does not contain:
> {code:java}
> @Test void testAllPredicatesFilterAboveUnion() {
> // empno is column 0 and deptno is column 7 in catalog.sales.emp
> final RelNode rel = sql("select * from (\n"
> + " select empno, deptno from emp\n"
> + " union all\n"
> + " select empno, deptno from emp)\n"
> + "where empno = deptno").toRel();
> final RelMetadataQuery mq = rel.getCluster().getMetadataQuery();
> final RelOptPredicateList predicates = mq.getAllPredicates(rel);
> assertThat(predicates.pulledUpPredicates,
> sortsAs("[=([CATALOG, SALES, EMP].#0.$0, [CATALOG, SALES, EMP].#0.$7), "
> + "=([CATALOG, SALES, EMP].#1.$0, [CATALOG, SALES, EMP].#1.$7)]"));
> }
> {code}
> {noformat}
> Expected: "[=([CATALOG, SALES, EMP].#0.$0, [CATALOG, SALES, EMP].#0.$7),
> =([CATALOG, SALES, EMP].#1.$0, [CATALOG, SALES, EMP].#1.$7)]"
> but: was "[=([CATALOG, SALES, EMP].#0.$0, [CATALOG, SALES, EMP].#0.$7),
> =([CATALOG, SALES, EMP].#0.$0, [CATALOG, SALES, EMP].#1.$7), =([CATALOG,
> SALES, EMP].#1.$0, [CATALOG, SALES, EMP].#0.$7), =([CATALOG, SALES,
> EMP].#1.$0, [CATALOG, SALES, EMP].#1.$7)]"
> {noformat}
> The second and third predicates compare empno of one input with deptno of the
> other. They describe a join condition between the two inputs that does not
> exist in the query.
> The same happens wherever an expression combines two or more fields from the
> same Union, at any depth: in the Union handler, as above, or in a Project,
> Aggregate, Join or Calc above the Union. Each of these handlers resolves the
> fields separately and then calls createAllPossibleExpressions. An expression
> reading k fields from a Union of N inputs therefore gets N^k lineage
> expressions, of which only N can occur.
> This is related to CALCITE-5365, where getAllPredicates runs out of memory on
> a join of two three-input unions on seven keys. With an inner join,
> getAllPredicates builds 3^14 combinations for that join condition, of which
> only 3 x 3 = 9 can occur. On main, the same shape with two keys returns 81
> predicates instead of 9. A bound on the number of combinations, which would
> address CALCITE-5365, would not fix this issue. Below the bound, the invalid
> combinations would still be returned. And because they inflate the count,
> lineage could reach the bound and be dropped even when only a few valid
> combinations exist.
> A possible fix is to resolve the whole expression at once, instead of each
> field separately, so that the fields of one input stay together:
> * Union: compute the lineage of the whole expression on each input, then
> gather the results.
> * Project, Calc and Aggregate: replace the fields in the expression with the
> input expressions they stand for, then ask the input for the lineage of the
> result.
> * Join: combining the two sides is correct, since any left row can pair with
> any right row, but the fields of each side must be resolved together, for
> example as a ROW of the fields read from that side.
> RelMdAllPredicates combines the lineage of each field in the same way in its
> Filter, Calc and Join handlers, so they need the same change: ask for the
> lineage of the whole condition.
> Plans without a Union do not change, because each field then has a single
> lineage expression.
--
This message was sent by Atlassian Jira
(v10.3.26#10030026)
