Skip to content

Commit fb42cf5

Browse files
fix: keep a correlated filter below an aggregate with a grouping set (apache#25529)
## Which issue does this PR close? - Closes apache#25519. ## Rationale for this change A correlated subquery whose filter sits below an aggregate with a grouping set returns wrong results, with no error and no warning. `PullUpCorrelatedExpr` moves the correlated filter above the aggregate and adds the correlated column to the aggregate's group expressions. `LogicalPlanBuilder::aggregate` cross joins a plain group expression with the sets a grouping set already holds, so `ROLLUP(i.k)`, which is `GROUPING SETS ((i.k), ())`, becomes `GROUPING SETS ((i.k), (i.k, i.k))`. The empty set is gone, and with it the grand total row the subquery returns for every outer row, including the rows whose filter matches nothing. The join that replaces the filter cannot bring those rows back. On `main` at `b4a8c824b4`, with `datafusion-cli`: ```sql CREATE TABLE o(k INT) AS VALUES (1), (2), (NULL), (4), (5); CREATE TABLE i(k INT) AS VALUES (1), (NULL), (5), (2); SELECT o.k, EXISTS (SELECT 1 FROM i WHERE i.k = o.k GROUP BY ROLLUP(i.k)) AS e FROM o ORDER BY o.k; SELECT o.k, o.k IN (SELECT i.k FROM i WHERE i.k = o.k GROUP BY ROLLUP(i.k)) AS m FROM o ORDER BY o.k; ``` | `o.k` | `EXISTS` on `main` | `IN` on `main` | correct, per the issue | | --- | --- | --- | --- | | 1 | true | true | true / true | | 2 | true | true | true / true | | 4 | **false** | **false** | true / NULL | | 5 | true | true | true / true | | NULL | **false** | **false** | true / NULL | The physical plan for the `EXISTS` query shows the loss directly. `ROLLUP(k)` has two sets, and both of them now group by `k`: ```text AggregateExec: group_by: (k), (k), mode: Partial ``` ## What changes are included in this PR? `datafusion/optimizer/src/decorrelate.rs`, in the `Aggregate` arm of `PullUpCorrelatedExpr::f_up`: - When the group expressions hold a grouping set, the pull up no longer adds its columns to them. If any set would be missing one, `can_pull_up` is set to `false` and the subquery stays correlated, which is what the issue asks for instead of a wrong result. - `ROLLUP` and `CUBE` always contain the empty set, so they are only safe when the pull up has nothing to add. An explicit `GROUPING SETS` is checked set by set. - When every set already groups by each column the pull up needs, the aggregate keeps its sets untouched and the subquery still decorrelates. Before this PR that case appended the column anyway and produced `GROUPING SETS ((c, c), (c, b, c))`; it now stays `GROUPING SETS ((c), (c, b))`. - The columns checked are the ones `collect_missing_exprs` would append: the correlated columns and the columns of a pulled up `HAVING`, minus the ones the group expressions already list on their own. The rewrite still runs to completion in the unsupported case, the same way the existing `can_pull_over_aggregation` case does. The three callers (`decorrelate_predicate_subquery`, `scalar_subquery_to_join`, `decorrelate_lateral_join`) read `can_pull_up` only after the whole rewrite has finished, and the nodes above the aggregate still expect the pulled up columns in its output, so returning early there fails the rewrite with a schema error rather than declining the transform. ## What is the testing strategy for this PR? Five unit tests, in the two rules that reach this code path: - `decorrelate_predicate_subquery.rs`: `ROLLUP` under `EXISTS`, `CUBE` under `IN`, a `GROUPING SETS` whose second set groups by another column, and the covering `GROUPING SETS` that must still decorrelate. - `scalar_subquery_to_join.rs`: `ROLLUP` under a correlated scalar subquery. Twelve queries in `datafusion/sqllogictest/test_files/subquery.slt` cover the end-to-end behaviour: `ROLLUP`, `CUBE`, an explicit set list holding `()`, a set list whose sets group by different columns, a grouping set that does not mention the correlated column at all, and the `IN`, `NOT EXISTS` and correlated scalar forms; plus the four that must keep working, a covering `GROUPING SETS` with one and with two sets, a plain `GROUP BY`, and an uncorrelated `ROLLUP` subquery. Ablation, with only `decorrelate.rs` reverted to `main` and every test kept (the tests live in other files, so the revert does not delete them): all five unit tests fail, and seven of the eight `statement error` cases in `subquery.slt` fail with "query is expected to fail, but actually succeed". The eighth, the correlated scalar subquery, already errors on `main`. On the branch: `cargo test -p datafusion-optimizer` passes, 901 + 26 + 5 tests; the full `sqllogictest` suite passes, 521 files; `cargo clippy -p datafusion-optimizer --all-targets -- -D warnings` and `cargo fmt --all -- --check` are clean. ## Are there any user-facing changes? Yes, and it is worth a look before merging. The queries above stop returning wrong rows, but they do not start returning right ones: leaving the subquery correlated means the physical planner rejects it with ```text This feature is not implemented: Physical plan does not support logical expression Exists(...) ``` That is the behaviour apache#25519 asks for, and it matches how the rule already declines a `Union`, `Sort` or `Extension` that holds an outer reference, and a `Limit` that holds one outside an `EXISTS`. Supporting these plans properly needs the aggregate to keep its sets through decorrelation, which is a larger change than this one. Queries whose grouping set already groups by the correlated column in every set are unaffected, other than no longer repeating that column inside each set.
1 parent 839cec3 commit fb42cf5

4 files changed

Lines changed: 384 additions & 8 deletions

File tree

‎datafusion/optimizer/src/decorrelate.rs‎

Lines changed: 104 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -28,7 +28,7 @@ use datafusion_common::tree_node::{
2828
use datafusion_common::{
2929
Column, DFSchemaRef, HashMap, Result, ScalarValue, assert_or_internal_err, plan_err,
3030
};
31-
use datafusion_expr::expr::Alias;
31+
use datafusion_expr::expr::{Alias, GroupingSet};
3232
use datafusion_expr::simplify::SimplifyContext;
3333
use datafusion_expr::utils::{
3434
collect_subquery_cols, conjunction, find_join_exprs, split_conjunction,
@@ -299,11 +299,51 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
299299
&self.correlated_subquery_cols_map,
300300
&mut local_correlated_cols,
301301
);
302-
// add missing columns to Aggregation's group expressions
303-
let mut missing_exprs = self.collect_missing_exprs(
304-
&aggregate.group_expr,
305-
&local_correlated_cols,
306-
)?;
302+
303+
// A grouping set cannot take the columns the pull up adds.
304+
// `LogicalPlanBuilder::aggregate` cross joins a plain group
305+
// expression with the sets that are already there, so `ROLLUP(i.k)`,
306+
// which is `GROUPING SETS ((i.k), ())`, becomes
307+
// `GROUPING SETS ((i.k), (i.k, i.k))`. The empty set is gone, and
308+
// with it the grand total row the subquery returns for every outer
309+
// row, including the rows whose correlated filter matches nothing.
310+
// The join that replaces the filter cannot bring those rows back,
311+
// so the subquery stays correlated unless every set already groups
312+
// by each column the pull up would add.
313+
let mut missing_exprs = if aggregate
314+
.group_expr
315+
.iter()
316+
.any(|expr| matches!(expr, Expr::GroupingSet(_)))
317+
{
318+
if self.grouping_sets_cover_pull_up_cols(
319+
&aggregate.group_expr,
320+
&local_correlated_cols,
321+
) {
322+
// Every set already groups by them, so the sets stay as
323+
// they are. Adding the columns again would repeat them
324+
// inside every set.
325+
aggregate.group_expr.to_vec()
326+
} else {
327+
self.can_pull_up = false;
328+
// The rewrite still runs, the same way the
329+
// `can_pull_over_aggregation` case above does. The callers
330+
// read `can_pull_up` only after the whole rewrite has
331+
// finished, and the nodes above this one still expect the
332+
// pulled up columns in its output, so leaving them out here
333+
// would fail the rewrite with a schema error instead. They
334+
// drop this plan and keep the correlated subquery.
335+
self.collect_missing_exprs(
336+
&aggregate.group_expr,
337+
&local_correlated_cols,
338+
)?
339+
}
340+
} else {
341+
// add missing columns to Aggregation's group expressions
342+
self.collect_missing_exprs(
343+
&aggregate.group_expr,
344+
&local_correlated_cols,
345+
)?
346+
};
307347

308348
// if the original group expressions are empty, need to handle the Count bug
309349
let mut expr_result_map_for_count_bug = HashMap::new();
@@ -404,6 +444,64 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
404444
}
405445

406446
impl PullUpCorrelatedExpr {
447+
/// Whether the pull up can add its columns to `group_expr` without changing
448+
/// what the aggregate returns.
449+
///
450+
/// `true` when `group_expr` holds no grouping set, and when every set of every
451+
/// grouping set it holds already groups by each column
452+
/// [`Self::collect_missing_exprs`] would add. In the second case the pull up
453+
/// adds nothing and the aggregate keeps the sets it has.
454+
///
455+
/// `ROLLUP` and `CUBE` always contain the empty set, which yields a row for
456+
/// outer rows the correlated filter matches nothing for, so they are only safe
457+
/// when there is nothing to add.
458+
///
459+
/// A non-empty set that leaves a column out fills it with NULL. Adding the
460+
/// column would give it a value instead, which a `HAVING` or a projection
461+
/// above the aggregate can read, so such a set is rejected as well.
462+
fn grouping_sets_cover_pull_up_cols(
463+
&self,
464+
group_expr: &[Expr],
465+
correlated_subquery_cols: &BTreeSet<Column>,
466+
) -> bool {
467+
let grouping_sets = group_expr
468+
.iter()
469+
.filter_map(|expr| match expr {
470+
Expr::GroupingSet(grouping_set) => Some(grouping_set),
471+
_ => None,
472+
})
473+
.collect::<Vec<_>>();
474+
if grouping_sets.is_empty() {
475+
return true;
476+
}
477+
478+
// The same columns `collect_missing_exprs` appends: the correlated columns
479+
// and the columns of a pulled up HAVING, minus the ones `group_expr`
480+
// already lists on their own, which it leaves alone.
481+
let mut required_cols = correlated_subquery_cols.iter().collect::<BTreeSet<_>>();
482+
if let Some(pull_up_having) = &self.pull_up_having_expr {
483+
required_cols.extend(pull_up_having.column_refs());
484+
}
485+
required_cols.retain(|col| {
486+
!group_expr
487+
.iter()
488+
.any(|expr| matches!(expr, Expr::Column(c) if c == *col))
489+
});
490+
if required_cols.is_empty() {
491+
return true;
492+
}
493+
494+
grouping_sets.iter().all(|grouping_set| match grouping_set {
495+
GroupingSet::Rollup(_) | GroupingSet::Cube(_) => false,
496+
GroupingSet::GroupingSets(sets) => sets.iter().all(|set| {
497+
required_cols.iter().all(|col| {
498+
set.iter()
499+
.any(|expr| matches!(expr, Expr::Column(c) if c == *col))
500+
})
501+
}),
502+
})
503+
}
504+
407505
fn collect_missing_exprs(
408506
&self,
409507
exprs: &[Expr],

‎datafusion/optimizer/src/decorrelate_predicate_subquery.rs‎

Lines changed: 135 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -772,7 +772,9 @@ mod tests {
772772
use crate::assert_optimized_plan_eq_display_indent_snapshot;
773773
use arrow::datatypes::{DataType, Field, Schema};
774774
use datafusion_expr::builder::table_source;
775-
use datafusion_expr::{and, binary_expr, col, out_ref_col, table_scan};
775+
use datafusion_expr::{
776+
and, binary_expr, col, cube, grouping_set, out_ref_col, rollup, table_scan,
777+
};
776778

777779
macro_rules! assert_optimized_plan_equal {
778780
(
@@ -822,6 +824,138 @@ mod tests {
822824
optimizer.optimize(plan, &crate::OptimizerContext::new(), |_, _| {})
823825
}
824826

827+
/// A grouping set subquery for the tests below: `SELECT c FROM <name> WHERE
828+
/// c = test.c GROUP BY <group_expr>`.
829+
fn correlated_grouping_set_subquery(
830+
name: &str,
831+
group_expr: Expr,
832+
) -> Result<Arc<LogicalPlan>> {
833+
Ok(Arc::new(
834+
LogicalPlanBuilder::from(test_table_scan_with_name(name)?)
835+
.filter(
836+
col(format!("{name}.c")).eq(out_ref_col(DataType::UInt32, "test.c")),
837+
)?
838+
.aggregate(vec![group_expr], Vec::<Expr>::new())?
839+
.project(vec![col(format!("{name}.c"))])?
840+
.build()?,
841+
))
842+
}
843+
844+
/// `ROLLUP(c)` is `GROUPING SETS ((c), ())`. Adding the correlated column to
845+
/// every set drops the empty one, so the subquery is left correlated.
846+
/// <https://github.com/apache/datafusion/issues/25519>
847+
#[test]
848+
fn exists_subquery_with_rollup_is_not_decorrelated() -> Result<()> {
849+
let subquery = correlated_grouping_set_subquery("sq", rollup(vec![col("sq.c")]))?;
850+
let plan = LogicalPlanBuilder::from(test_table_scan()?)
851+
.filter(exists(subquery))?
852+
.project(vec![col("test.b")])?
853+
.build()?;
854+
855+
assert_optimized_plan_equal!(
856+
plan,
857+
@r"
858+
Projection: test.b [b:UInt32]
859+
Filter: EXISTS (<subquery>) [a:UInt32, b:UInt32, c:UInt32]
860+
Subquery: [c:UInt32;N]
861+
Projection: sq.c [c:UInt32;N]
862+
Aggregate: groupBy=[[ROLLUP (sq.c)]], aggr=[[]] [c:UInt32;N, __grouping_id:UInt8]
863+
Filter: sq.c = outer_ref(test.c) [a:UInt32, b:UInt32, c:UInt32]
864+
TableScan: sq [a:UInt32, b:UInt32, c:UInt32]
865+
TableScan: test [a:UInt32, b:UInt32, c:UInt32]
866+
"
867+
)
868+
}
869+
870+
/// `CUBE(c)` holds the empty set for the same reason. The correlation is on
871+
/// `a` rather than on the `IN` key, so it stays a filter of its own instead
872+
/// of being folded into the `IN` predicate.
873+
/// <https://github.com/apache/datafusion/issues/25519>
874+
#[test]
875+
fn in_subquery_with_cube_is_not_decorrelated() -> Result<()> {
876+
let subquery = Arc::new(
877+
LogicalPlanBuilder::from(test_table_scan_with_name("sq")?)
878+
.filter(col("sq.a").eq(out_ref_col(DataType::UInt32, "test.a")))?
879+
.aggregate(vec![cube(vec![col("sq.c")])], Vec::<Expr>::new())?
880+
.project(vec![col("sq.c")])?
881+
.build()?,
882+
);
883+
let plan = LogicalPlanBuilder::from(test_table_scan()?)
884+
.filter(in_subquery(col("test.c"), subquery))?
885+
.project(vec![col("test.b")])?
886+
.build()?;
887+
888+
assert_optimized_plan_equal!(
889+
plan,
890+
@r"
891+
Projection: test.b [b:UInt32]
892+
Filter: test.c IN (<subquery>) [a:UInt32, b:UInt32, c:UInt32]
893+
Subquery: [c:UInt32;N]
894+
Projection: sq.c [c:UInt32;N]
895+
Aggregate: groupBy=[[CUBE (sq.c)]], aggr=[[]] [c:UInt32;N, __grouping_id:UInt8]
896+
Filter: sq.a = outer_ref(test.a) [a:UInt32, b:UInt32, c:UInt32]
897+
TableScan: sq [a:UInt32, b:UInt32, c:UInt32]
898+
TableScan: test [a:UInt32, b:UInt32, c:UInt32]
899+
"
900+
)
901+
}
902+
903+
/// A set that groups by another column does not carry the correlated one.
904+
/// <https://github.com/apache/datafusion/issues/25519>
905+
#[test]
906+
fn exists_subquery_with_partial_grouping_set_is_not_decorrelated() -> Result<()> {
907+
let subquery = correlated_grouping_set_subquery(
908+
"sq",
909+
grouping_set(vec![vec![col("sq.c")], vec![col("sq.b")]]),
910+
)?;
911+
let plan = LogicalPlanBuilder::from(test_table_scan()?)
912+
.filter(exists(subquery))?
913+
.project(vec![col("test.b")])?
914+
.build()?;
915+
916+
assert_optimized_plan_equal!(
917+
plan,
918+
@r"
919+
Projection: test.b [b:UInt32]
920+
Filter: EXISTS (<subquery>) [a:UInt32, b:UInt32, c:UInt32]
921+
Subquery: [c:UInt32;N]
922+
Projection: sq.c [c:UInt32;N]
923+
Aggregate: groupBy=[[GROUPING SETS ((sq.c), (sq.b))]], aggr=[[]] [c:UInt32;N, b:UInt32;N, __grouping_id:UInt8]
924+
Filter: sq.c = outer_ref(test.c) [a:UInt32, b:UInt32, c:UInt32]
925+
TableScan: sq [a:UInt32, b:UInt32, c:UInt32]
926+
TableScan: test [a:UInt32, b:UInt32, c:UInt32]
927+
"
928+
)
929+
}
930+
931+
/// Every set already groups by the correlated column, so the pull up adds
932+
/// nothing and the subquery decorrelates as it did before.
933+
/// <https://github.com/apache/datafusion/issues/25519>
934+
#[test]
935+
fn exists_subquery_with_covering_grouping_set_is_decorrelated() -> Result<()> {
936+
let subquery = correlated_grouping_set_subquery(
937+
"sq",
938+
grouping_set(vec![vec![col("sq.c")], vec![col("sq.c"), col("sq.b")]]),
939+
)?;
940+
let plan = LogicalPlanBuilder::from(test_table_scan()?)
941+
.filter(exists(subquery))?
942+
.project(vec![col("test.b")])?
943+
.build()?;
944+
945+
assert_optimized_plan_equal!(
946+
plan,
947+
@r"
948+
Projection: test.b [b:UInt32]
949+
LeftSemi Join: Filter: __correlated_sq_1.c = test.c [a:UInt32, b:UInt32, c:UInt32]
950+
TableScan: test [a:UInt32, b:UInt32, c:UInt32]
951+
SubqueryAlias: __correlated_sq_1 [c:UInt32;N]
952+
Projection: sq.c [c:UInt32;N]
953+
Aggregate: groupBy=[[GROUPING SETS ((sq.c), (sq.c, sq.b))]], aggr=[[]] [c:UInt32;N, b:UInt32;N, __grouping_id:UInt8]
954+
TableScan: sq [a:UInt32, b:UInt32, c:UInt32]
955+
"
956+
)
957+
}
958+
825959
/// Test for several IN subquery expressions
826960
#[test]
827961
fn in_subquery_multiple() -> Result<()> {

‎datafusion/optimizer/src/scalar_subquery_to_join.rs‎

Lines changed: 41 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -445,7 +445,7 @@ mod tests {
445445
use datafusion_expr::test::function_stub::sum;
446446

447447
use crate::assert_optimized_plan_eq_display_indent_snapshot;
448-
use datafusion_expr::{Between, col, expr, out_ref_col, scalar_subquery};
448+
use datafusion_expr::{Between, col, expr, out_ref_col, rollup, scalar_subquery};
449449
use datafusion_functions_aggregate::min_max::{max, min};
450450

451451
macro_rules! assert_optimized_plan_equal {
@@ -462,6 +462,46 @@ mod tests {
462462
}};
463463
}
464464

465+
/// A correlated scalar subquery whose aggregate uses `ROLLUP` keeps its
466+
/// correlation: the empty set yields a row for outer rows the filter matches
467+
/// nothing for, and the join that would replace the filter cannot produce it.
468+
/// <https://github.com/apache/datafusion/issues/25519>
469+
#[test]
470+
fn scalar_subquery_with_rollup_is_not_decorrelated() -> Result<()> {
471+
let sq = Arc::new(
472+
LogicalPlanBuilder::from(scan_tpch_table("orders"))
473+
.filter(
474+
col("orders.o_custkey")
475+
.eq(out_ref_col(DataType::Int64, "customer.c_custkey")),
476+
)?
477+
.aggregate(
478+
vec![rollup(vec![col("orders.o_custkey")])],
479+
vec![max(col("orders.o_custkey"))],
480+
)?
481+
.project(vec![max(col("orders.o_custkey"))])?
482+
.build()?,
483+
);
484+
485+
let plan = LogicalPlanBuilder::from(scan_tpch_table("customer"))
486+
.filter(col("customer.c_custkey").eq(scalar_subquery(sq)))?
487+
.project(vec![col("customer.c_custkey")])?
488+
.build()?;
489+
490+
assert_optimized_plan_equal!(
491+
plan,
492+
@r"
493+
Projection: customer.c_custkey [c_custkey:Int64]
494+
Filter: customer.c_custkey = (<subquery>) [c_custkey:Int64, c_name:Utf8]
495+
Subquery: [max(orders.o_custkey):Int64;N]
496+
Projection: max(orders.o_custkey) [max(orders.o_custkey):Int64;N]
497+
Aggregate: groupBy=[[ROLLUP (orders.o_custkey)]], aggr=[[max(orders.o_custkey)]] [o_custkey:Int64;N, __grouping_id:UInt8, max(orders.o_custkey):Int64;N]
498+
Filter: orders.o_custkey = outer_ref(customer.c_custkey) [o_orderkey:Int64, o_custkey:Int64, o_orderstatus:Utf8, o_totalprice:Float64;N]
499+
TableScan: orders [o_orderkey:Int64, o_custkey:Int64, o_orderstatus:Utf8, o_totalprice:Float64;N]
500+
TableScan: customer [c_custkey:Int64, c_name:Utf8]
501+
"
502+
)
503+
}
504+
465505
/// Test multiple correlated subqueries
466506
#[test]
467507
fn multiple_subqueries() -> Result<()> {

0 commit comments

Comments
 (0)