[
https://issues.apache.org/jira/browse/CALCITE-7869?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=18140636#comment-18140636
]
huangsheng commented on CALCITE-7869:
-------------------------------------
Arnaud, thanks for the two-scan example. Following up on CALCITE-7924, I'd like
to try the approach you outlined here. For {{empno + deptno}}, both operands
must refer to the same scan occurrence, even when both branches scan EMP. A
work limit can stop enumeration, but it cannot make a mixed-branch expression
valid.
*Proposed change.* At a Union, ask each input for the lineage of the whole
expression, remap table occurrences as today, and collect the answers. If one
input is unknown, the result should stay unknown rather than report partial
lineage. Project and Calc would substitute their input expressions before
delegating once; Aggregate would do the same for supported grouping keys only.
At a Join, resolve the referenced fields from each side together, then combine
left and right alternatives. RelMdAllPredicates would ask for the whole filter
or join condition, preserving each conjunction as one predicate. This requires
neither a new public API nor a budget.
I'd start with the two EMP scans and the filter example in this issue. Then I'd
check the inner-join variant of CALCITE-5365: with three branches per side and
seven equality keys, we should construct nine complete predicates directly, one
per branch pair.
*Open question: windows.* The Feldera reproducer in CALCITE-7924 has
{{ROW_NUMBER()}} above a 90-branch UNION ALL. A given row's partition and
ordering keys come from one branch, but its rank can depend on rows from other
branches. Ranking each branch separately is not equivalent to ranking the union.
I haven't verified what lineage a {{RexOver}} in Project or Calc should return
here, or whether preserving branch correlation alone resolves the compilation
issue. I'd first run the original query with only the branch-aware change,
without a budget or a window-specific guard. A separate question is whether the
window result should return unknown while passthrough columns retain their
lineage, as they do for a relational Window in CALCITE-7843.
[~mbudiu], would you expect the metadata to distinguish the origins of the
window keys from the lineage of the rank itself in this case?
Arnaud thanks
> 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)
