Skip to content

Commit a16d10d

Browse files
fix: error instead of wrong rows for a LATERAL with a HAVING over an ungrouped aggregate (apache#26874)
## Which issue does this PR close? - Part of apache#21198. It does not add `HAVING` support. Following apache#5492 (comment), it makes the shapes that return wrong rows error instead. ## Rationale for this change - A `LATERAL` subquery over an aggregate without `GROUP BY`, with a `HAVING`, returns wrong rows today instead of an error: ```sql CREATE TABLE a(k INT) AS VALUES (1), (2), (3); CREATE TABLE b(k INT, v INT) AS VALUES (1, 10), (1, 20), (2, 30); SELECT a.k, s.c FROM a, LATERAL (SELECT count(*) AS c FROM b WHERE b.k = a.k HAVING count(*) > 1) s; -- main: (1, 2), (2, NULL), (3, NULL) -- DuckDB: (1, 2) ``` - The existing check only refuses a `HAVING` that `PullUpCorrelatedExpr` pulls up, which happens when it is true on an empty group. Two cases get past it: - a `HAVING` that is false on an empty group stays above the aggregate. The rewrite turns the inner join into an outer join, so an outer row whose row the `HAVING` removes comes back with NULLs - a `HAVING` that reads an outer column is moved into the join condition, and the count bug handling turns its unmatched rows into a count of 0. This is wrong for a left lateral join too (`(2, 0)` where the answer is `(2, NULL)`) ## What changes are included in this PR? - `DecorrelateLateralJoin` looks for a `HAVING` over an ungrouped aggregate in the original subquery, and leaves the join correlated (so it errors) when the join is inner, or when the `HAVING` reads an outer column. - A filter below the aggregate is not a `HAVING` and is not affected, and neither is a left lateral join with a `HAVING` that reads only the subquery. ## What is the testing strategy for this PR? - New `lateral_join.slt` cases: - inner join with `HAVING count(*) > 1` and with `HAVING max(t2.id) > 15`: now an error - inner and left join with `HAVING count(*) > t1.id`: now an error - left join with `HAVING count(*) > 1`, and an inner join with `GROUP BY ... HAVING`: still decorrelated, with the same rows as before - Without the change, the four error cases return wrong rows instead of failing. - I compared 20 lateral aggregate shapes against DuckDB on main and on this branch. The 8 that return wrong rows on main now error, the 8 that return correct rows still return the same rows, and the 4 that already errored still do. - Optimizer unit tests and the full sqllogictest suite pass. ## Are there any user-facing changes? - Queries that returned wrong rows now fail with `OuterReferenceColumn`. Every query that returned correct rows still does. 🤖 Generated with [Claude Code](https://claude.com/claude-code)
1 parent 2310b39 commit a16d10d

2 files changed

Lines changed: 136 additions & 1 deletion

File tree

‎datafusion/optimizer/src/decorrelate_lateral_join.rs‎

Lines changed: 50 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,7 @@ use datafusion_common::tree_node::{
1919
use datafusion_common::{Column, DFSchema, Result, ScalarValue, TableReference};
2020
use datafusion_expr::logical_plan::{JoinType, Subquery};
2121
use datafusion_expr::utils::conjunction;
22-
use datafusion_expr::{LogicalPlan, LogicalPlanBuilder, SubqueryAlias};
22+
use datafusion_expr::{Filter, LogicalPlan, LogicalPlanBuilder, SubqueryAlias};
2323

2424
/// Optimizer rule for rewriting lateral joins to joins
2525
#[derive(Default, Debug)]
@@ -97,6 +97,22 @@ fn rewrite_internal(join: Join) -> Result<Transformed<LogicalPlan>> {
9797
return Ok(Transformed::no(LogicalPlan::Join(join)));
9898
}
9999

100+
// A HAVING over an ungrouped aggregate can remove the aggregate's only
101+
// row. The rewrite below handles neither case correctly, so leave the join
102+
// correlated and let the query error instead of returning wrong rows.
103+
// <https://github.com/apache/datafusion/issues/21198>
104+
// - An inner lateral join becomes an outer join that keeps every outer row,
105+
// so an outer row whose row the HAVING removes comes back with NULLs.
106+
// - A HAVING that reads an outer column is moved into the join condition,
107+
// where the count bug handling turns its unmatched rows into a count of 0,
108+
// for a left lateral join too.
109+
if pull_up.pulled_up_scalar_agg
110+
&& let Some(having) = having_over_ungrouped_aggregate(subquery_plan)
111+
&& (original_join_type == JoinType::Inner || having.predicate.contains_outer())
112+
{
113+
return Ok(Transformed::no(LogicalPlan::Join(join)));
114+
}
115+
100116
// TODO: support HAVING in lateral subqueries.
101117
// <https://github.com/apache/datafusion/issues/21198>
102118
if pull_up.pull_up_having_expr.is_some() {
@@ -315,6 +331,39 @@ fn rewrite_internal(join: Join) -> Result<Transformed<LogicalPlan>> {
315331
Ok(Transformed::new(new_plan, true, TreeNodeRecursion::Jump))
316332
}
317333

334+
/// The `HAVING` of a subquery whose result is an ungrouped aggregate: a
335+
/// `Filter` between the subquery's output and that aggregate, with only
336+
/// projections and aliases around them. A filter below the aggregate only
337+
/// changes the aggregate's input, so it is not returned.
338+
fn having_over_ungrouped_aggregate(plan: &LogicalPlan) -> Option<&Filter> {
339+
match plan {
340+
LogicalPlan::Projection(projection) => {
341+
having_over_ungrouped_aggregate(&projection.input)
342+
}
343+
LogicalPlan::SubqueryAlias(alias) => {
344+
having_over_ungrouped_aggregate(&alias.input)
345+
}
346+
LogicalPlan::Filter(filter) => {
347+
feeds_ungrouped_aggregate(&filter.input).then_some(filter)
348+
}
349+
_ => None,
350+
}
351+
}
352+
353+
/// Whether `plan` is an ungrouped aggregate, seen through projections,
354+
/// aliases and filters.
355+
fn feeds_ungrouped_aggregate(plan: &LogicalPlan) -> bool {
356+
match plan {
357+
LogicalPlan::Aggregate(aggregate) => aggregate.group_expr.is_empty(),
358+
LogicalPlan::Projection(projection) => {
359+
feeds_ungrouped_aggregate(&projection.input)
360+
}
361+
LogicalPlan::SubqueryAlias(alias) => feeds_ungrouped_aggregate(&alias.input),
362+
LogicalPlan::Filter(filter) => feeds_ungrouped_aggregate(&filter.input),
363+
_ => false,
364+
}
365+
}
366+
318367
/// Extract the Subquery and optional alias from a lateral join's right side.
319368
fn extract_lateral_subquery(
320369
plan: &LogicalPlan,

‎datafusion/sqllogictest/test_files/lateral_join.slt‎

Lines changed: 86 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -726,6 +726,92 @@ FROM t1, LATERAL (
726726
) AS sub
727727
ORDER BY t1.id;
728728

729+
# HAVING count(*) > 1 is false on an empty group, so it is not pulled up and
730+
# stays above the aggregate. The inner lateral join must drop t1.id=2 (cnt=1)
731+
# and t1.id=3 (cnt=0), so until that is supported the query errors instead
732+
# of returning them with a NULL cnt.
733+
# Expected result once supported: only t1.id=1 (cnt=2).
734+
statement error OuterReferenceColumn
735+
SELECT t1.id, sub.cnt
736+
FROM t1, LATERAL (
737+
SELECT count(*) AS cnt FROM t2 WHERE t2.t1_id = t1.id HAVING count(*) > 1
738+
) AS sub
739+
ORDER BY t1.id;
740+
741+
# The same with a HAVING on another aggregate than the one returned.
742+
statement error OuterReferenceColumn
743+
SELECT t1.id, sub.cnt
744+
FROM t1, LATERAL (
745+
SELECT count(*) AS cnt FROM t2 WHERE t2.t1_id = t1.id HAVING max(t2.id) > 15
746+
) AS sub
747+
ORDER BY t1.id;
748+
749+
# A left lateral join keeps the outer rows the HAVING removes, with NULLs, so
750+
# it is still decorrelated when the HAVING does not read an outer column.
751+
query II
752+
SELECT t1.id, sub.cnt
753+
FROM t1 LEFT JOIN LATERAL (
754+
SELECT count(*) AS cnt FROM t2 WHERE t2.t1_id = t1.id HAVING count(*) > 1
755+
) AS sub ON true
756+
ORDER BY t1.id;
757+
----
758+
1 2
759+
2 NULL
760+
3 NULL
761+
762+
# A HAVING that reads an outer column is moved into the join condition, where
763+
# rows it rejects became a count of 0, for an inner and a left lateral join.
764+
# Expected result once supported: only t1.id=1 (cnt=2) for the inner join, and
765+
# (1, 2), (2, NULL), (3, NULL) for the left join.
766+
statement error OuterReferenceColumn
767+
SELECT t1.id, sub.cnt
768+
FROM t1, LATERAL (
769+
SELECT count(*) AS cnt FROM t2 WHERE t2.t1_id = t1.id HAVING count(*) > t1.id
770+
) AS sub
771+
ORDER BY t1.id;
772+
773+
statement error OuterReferenceColumn
774+
SELECT t1.id, sub.cnt
775+
FROM t1 LEFT JOIN LATERAL (
776+
SELECT count(*) AS cnt FROM t2 WHERE t2.t1_id = t1.id HAVING count(*) > t1.id
777+
) AS sub ON true
778+
ORDER BY t1.id;
779+
780+
# Without a correlated WHERE the aggregate keeps its single row for every
781+
# outer row, so a HAVING that reads an outer column is a plain join filter.
782+
query II
783+
SELECT t1.id, sub.cnt
784+
FROM t1, LATERAL (
785+
SELECT count(*) AS cnt FROM t2 HAVING count(*) > t1.id
786+
) AS sub
787+
ORDER BY t1.id;
788+
----
789+
1 3
790+
2 3
791+
792+
query II
793+
SELECT t1.id, sub.cnt
794+
FROM t1 LEFT JOIN LATERAL (
795+
SELECT count(*) AS cnt FROM t2 HAVING count(*) > t1.id
796+
) AS sub ON true
797+
ORDER BY t1.id;
798+
----
799+
1 3
800+
2 3
801+
3 NULL
802+
803+
# With GROUP BY, a group the HAVING removes has no row at all, so an inner
804+
# lateral join is still decorrelated.
805+
query III
806+
SELECT t1.id, sub.t1_id, sub.cnt
807+
FROM t1, LATERAL (
808+
SELECT t2.t1_id, count(*) AS cnt FROM t2 WHERE t2.t1_id = t1.id
809+
GROUP BY t2.t1_id HAVING count(*) > 1
810+
) AS sub
811+
ORDER BY t1.id;
812+
----
813+
1 1 2
814+
729815
# --- Correlated filter on the nullable side of an outer join ---
730816
# https://github.com/apache/datafusion/issues/25507
731817
# Pulling `t2.t1_id = t1.id` above the LEFT JOIN would drop the t3 rows that

0 commit comments

Comments
 (0)