Skip to content

Commit 2bb383e

Browse files
compheadjayzhan211
andauthored
fix: keep a subquery correlated when an aggregate sits above a pulled up scalar aggregate (apache#26544)
## Which issue does this PR close? - Part of apache#26508. ## Rationale for this change An aggregate without `GROUP BY` returns one row even when its input is empty. When such an aggregate is in a correlated subquery and another aggregate sits above it, DataFusion returns wrong results for outer rows that match no inner rows: ```sql SELECT x.a, (SELECT count(*) FROM (SELECT max(y.b) FROM (VALUES (1, 10)) AS y(a, b) WHERE y.a = x.a)) AS v1, (SELECT max(n) FROM (SELECT count(*) AS n FROM (VALUES (1, 10)) AS y(a, b) WHERE y.a = x.a)) AS v2 FROM (VALUES (1), (2)) AS x(a) ``` For `a = 2` this returns `v1 = 0, v2 = NULL` instead of `v1 = 1, v2 = 0`, which DuckDB, SQLite and PostgreSQL return. The same shape gives wrong results under `IN` and `LEFT JOIN LATERAL` too. When the correlated filter is pulled up, the inner scalar aggregate becomes a grouped aggregate, which returns no row for the outer rows it does not match. The aggregate above then runs over an empty input. The count bug handling only fixes the aggregate the join reads, which here is the outer one, so the inner row is never restored. The existing `TODO` next to `pulled_up_scalar_agg` described this case. ## What changes are included in this PR? `PullUpCorrelatedExpr` stops the pull up when it reaches an `Aggregate` after a scalar aggregate has already been pulled up. The subquery stays correlated, the same way a window over an aggregate with count bug handling does today. The rewrite stops at that `Aggregate`, so the nodes above it are not rebuilt over the pulled up plan. Before, the rebuild could fail with a schema error. Such a query now fails with `Physical plan does not support logical expression ScalarSubquery` instead of returning wrong rows. A projection over the scalar aggregate (`SELECT n + 1 FROM (SELECT count(*) AS n ...)`) and an aggregate over a grouped aggregate are still pulled up. ## What is the testing strategy for this PR? New `sqllogictest` cases at the end of `subquery.slt` cover the two queries from the issue, the `IN`, `LATERAL` and `EXISTS` forms, a projection, a filter, a `GROUP BY`-only aggregate and a grouped aggregate between the aggregates, a `max` over `max` query that is now blocked, and the two shapes that must still be pulled up. All `sqllogictest` files, the `datafusion-optimizer` unit tests and the `core_integration` `sql::` tests (which include the TPC-DS planning tests) pass locally. ## Are there any user-facing changes? Queries with this shape now return a "not implemented" error instead of wrong results. Some queries of this shape returned correct rows before and now fail too, for example `max` over `max`. Telling them apart needs the outer aggregate evaluated on the inner one's empty-input row. No API changes. --------- Co-authored-by: Jay Zhan <[email protected]>
1 parent 53e1210 commit 2bb383e

2 files changed

Lines changed: 84 additions & 2 deletions

File tree

‎datafusion/optimizer/src/decorrelate.rs‎

Lines changed: 11 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -83,6 +83,9 @@ pub struct PullUpCorrelatedExpr {
8383
pub pull_up_having_expr: Option<Expr>,
8484
/// whether we have converted a scalar aggregation into a group aggregation. When unnesting
8585
/// lateral joins, we need to produce a left outer join in such cases.
86+
///
87+
/// An `Aggregate` above stops the pull up when this is set. `f_up` visits
88+
/// the aggregate that sets it before any node above.
8689
pub pulled_up_scalar_agg: bool,
8790
/// Every correlated conjunct that a `Filter` of the subquery applies,
8891
/// before `remove_duplicated_filter` drops the ones that the `IN`
@@ -556,6 +559,14 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
556559
LogicalPlan::Aggregate(aggregate)
557560
if self.in_predicate_opt.is_some() || !self.join_filters.is_empty() =>
558561
{
562+
// A pulled up scalar aggregate below gives no row for unmatched
563+
// outer rows, so this aggregate would see an empty input. Stop
564+
// the rewrite here, since rebuilding the nodes above can fail
565+
// with a schema error. See https://github.com/apache/datafusion/issues/26508
566+
if self.pulled_up_scalar_agg {
567+
self.can_pull_up = false;
568+
return Ok(Transformed::new(plan, false, TreeNodeRecursion::Stop));
569+
}
559570
// If the aggregation is from a distinct it will not change the result for
560571
// exists/in subqueries so we can still pull up all predicates.
561572
let is_distinct = aggregate.aggr_expr.is_empty();
@@ -647,8 +658,6 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
647658
}
648659
}
649660
if aggregate.group_expr.is_empty() {
650-
// TODO: how do we handle the case where we have pulled multiple aggregations? For example,
651-
// a group agg with a scalar agg as child.
652661
self.pulled_up_scalar_agg = true;
653662
}
654663
let new_plan = LogicalPlanBuilder::from((*aggregate.input).clone())

‎datafusion/sqllogictest/test_files/subquery.slt‎

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4003,3 +4003,76 @@ DROP TABLE unnest_outer;
40034003

40044004
statement ok
40054005
DROP TABLE unnest_inner;
4006+
4007+
# An aggregate over a correlated scalar aggregate stays correlated.
4008+
# https://github.com/apache/datafusion/issues/26508
4009+
statement ok
4010+
CREATE TABLE nested_agg_outer(k INT) AS VALUES (1), (2);
4011+
4012+
statement ok
4013+
CREATE TABLE nested_agg_inner(id INT, v INT) AS VALUES (1, 10);
4014+
4015+
# Errors rather than returning wrong rows. Expected `(1, 1), (2, 1)`.
4016+
query error Physical plan does not support logical expression ScalarSubquery
4017+
SELECT o.k, (SELECT count(*) FROM (SELECT max(i.v) FROM nested_agg_inner AS i WHERE i.id = o.k)) FROM nested_agg_outer AS o ORDER BY o.k;
4018+
4019+
# Errors rather than returning wrong rows. Expected `(1, 1), (2, 0)`.
4020+
query error Physical plan does not support logical expression ScalarSubquery
4021+
SELECT o.k, (SELECT max(n) FROM (SELECT count(*) AS n FROM nested_agg_inner AS i WHERE i.id = o.k)) FROM nested_agg_outer AS o ORDER BY o.k;
4022+
4023+
# IN. Errors rather than returning wrong rows. Expected `2`.
4024+
query error Physical plan does not support logical expression InSubquery
4025+
SELECT o.k FROM nested_agg_outer AS o WHERE 0 IN (SELECT max(n) FROM (SELECT count(*) AS n FROM nested_agg_inner AS i WHERE i.id = o.k)) ORDER BY o.k;
4026+
4027+
# LATERAL. Errors rather than returning wrong rows. Expected `(1, 1), (2, 0)`.
4028+
query error Physical plan does not support logical expression OuterReferenceColumn
4029+
SELECT o.k, s.m FROM nested_agg_outer AS o LEFT JOIN LATERAL (SELECT max(n) AS m FROM (SELECT count(*) AS n FROM nested_agg_inner AS i WHERE i.id = o.k)) AS s ON true ORDER BY o.k;
4030+
4031+
# EXISTS. Errors rather than returning wrong rows. Expected `1, 2`.
4032+
query error Physical plan does not support logical expression Exists
4033+
SELECT o.k FROM nested_agg_outer AS o WHERE EXISTS (SELECT max(n) FROM (SELECT count(*) AS n FROM nested_agg_inner AS i WHERE i.id = o.k)) ORDER BY o.k;
4034+
4035+
# A projection between the aggregates. Errors rather than returning wrong rows. Expected `(1, 2), (2, 1)`.
4036+
query error Physical plan does not support logical expression ScalarSubquery
4037+
SELECT o.k, (SELECT max(n2) FROM (SELECT n + 1 AS n2 FROM (SELECT count(*) AS n FROM nested_agg_inner AS i WHERE i.id = o.k))) FROM nested_agg_outer AS o ORDER BY o.k;
4038+
4039+
# A filter between the aggregates. Errors rather than returning wrong rows.
4040+
# Expected `(1, 1), (2, 1)`.
4041+
query error Physical plan does not support logical expression ScalarSubquery
4042+
SELECT o.k, (SELECT count(*) FROM (SELECT count(*) AS n FROM nested_agg_inner AS i WHERE i.id = o.k) WHERE n >= 0) FROM nested_agg_outer AS o ORDER BY o.k;
4043+
4044+
# A GROUP BY-only aggregate over the scalar aggregate.
4045+
# Errors rather than returning wrong rows. Expected `(1, 1), (2, 1)`.
4046+
query error Physical plan does not support logical expression ScalarSubquery
4047+
SELECT o.k, (SELECT count(*) FROM (SELECT n FROM (SELECT count(*) AS n FROM nested_agg_inner AS i WHERE i.id = o.k) GROUP BY n)) FROM nested_agg_outer AS o ORDER BY o.k;
4048+
4049+
# A grouped aggregate over the scalar aggregate.
4050+
# Errors rather than returning wrong rows. Expected `(1, 1), (2, 1)`.
4051+
query error Physical plan does not support logical expression ScalarSubquery
4052+
SELECT o.k, (SELECT max(c) FROM (SELECT n, count(*) AS c FROM (SELECT count(*) AS n FROM nested_agg_inner AS i WHERE i.id = o.k) GROUP BY n)) FROM nested_agg_outer AS o ORDER BY o.k;
4053+
4054+
# Returned the right rows before, but is blocked too, since telling it apart
4055+
# needs the outer aggregate evaluated on the inner one's empty input row.
4056+
# Expected `(1, 10), (2, NULL)`.
4057+
query error Physical plan does not support logical expression ScalarSubquery
4058+
SELECT o.k, (SELECT max(m) FROM (SELECT max(i.v) AS m FROM nested_agg_inner AS i WHERE i.id = o.k)) FROM nested_agg_outer AS o ORDER BY o.k;
4059+
4060+
# A projection over the scalar aggregate is still pulled up.
4061+
query II
4062+
SELECT o.k, (SELECT n + 1 FROM (SELECT count(*) AS n FROM nested_agg_inner AS i WHERE i.id = o.k)) FROM nested_agg_outer AS o ORDER BY o.k;
4063+
----
4064+
1 2
4065+
2 1
4066+
4067+
# An aggregate over a grouped aggregate is still pulled up.
4068+
query II
4069+
SELECT o.k, (SELECT max(c) FROM (SELECT i.id, count(*) AS c FROM nested_agg_inner AS i WHERE i.id = o.k GROUP BY i.id)) FROM nested_agg_outer AS o ORDER BY o.k;
4070+
----
4071+
1 1
4072+
2 NULL
4073+
4074+
statement ok
4075+
DROP TABLE nested_agg_outer;
4076+
4077+
statement ok
4078+
DROP TABLE nested_agg_inner;

0 commit comments

Comments
 (0)