Arnaud Jegou created CALCITE-7869:
-------------------------------------
Summary: 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
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
(v8.20.10#820010)
