Skip to content

Commit 290ad15

Browse files
fix: decorrelate grouping sets that leave out the correlated column when safe (apache#25781)
## Which issue does this PR close? - Closes apache#25708. ## Rationale for this change apache#25529 fixed a wrong-results bug where a correlated filter under a grouping-set `Aggregate` was pulled up into the aggregate's grouping sets, but the guard it added is more conservative than it needs to be: it rejects the pull up whenever *any* grouping set omits the correlated column, even in cases like ```sql SELECT o.k FROM o WHERE EXISTS ( SELECT 1 FROM i WHERE i.k = o.k GROUP BY GROUPING SETS ((i.k), (i.j)) ) ``` where nothing above the aggregate ever reads `i.k`, so filling it in changes nothing the query can observe. These queries now fail to plan (`This feature is not implemented: ... does not support logical expression Exists`) instead of decorrelating. ## What changes are included in this PR? - `datafusion/optimizer/src/decorrelate.rs`: `grouping_sets_cover_pull_up_cols` becomes `grouping_sets_pull_up_outcome`, returning a three-way `GroupingSetsPullUp` (`NoColumnsToAdd` / `SafeToExtend` / `Unsafe`) instead of a bool. A set that omits a required column is now only `Unsafe` when: - some grouping set is empty (`ROLLUP`/`CUBE` always hold one), or - the aggregate itself computes `GROUPING`/`GROUPING_ID`, or - a node above the aggregate reads the column, per a new `column_refs_above_aggregate` set. - Since `PullUpCorrelatedExpr::f_up` runs bottom-up, it hasn't visited whatever sits above the `Aggregate` (a `HAVING`, a `Projection`) by the time it needs to decide. `column_refs_above_aggregate` is instead computed once, top-down, over the original (not yet rewritten) subquery plan by a new `columns_read_above_aggregate` helper, and threaded in via a new `with_column_refs_above_aggregate` builder call at all three call sites (`scalar_subquery_to_join.rs`, `decorrelate_predicate_subquery.rs`, `decorrelate_lateral_join.rs`). - `datafusion/sqllogictest/test_files/subquery.slt`: the `EXISTS` case above now decorrelates and asserts correct results; added a case showing a `GROUPING(k)` read still keeps the subquery correlated (correctly), alongside the existing `HAVING`/empty-set cases that stay correlated. ## What is the testing strategy for this PR? Extended `datafusion/sqllogictest/test_files/subquery.slt`'s existing `apache#25519` regression block: - The previously-rejected `EXISTS ... GROUPING SETS ((i.k), (i.j))` case is now a `query IB` asserting the correct results. - Added a case with `GROUPING(k)` read out of the aggregate, asserting it still correctly stays correlated. - The `HAVING i.k IS NULL` and every empty-set (`ROLLUP`/`CUBE`/explicit `()`) case are unchanged and still assert they stay correlated. Ran the full `datafusion-optimizer` unit + integration suite (905 + 26 tests) and the full sqllogictest suite (523 files), all green. ## Are there any user-facing changes? More `EXISTS`/`IN`/lateral-join subqueries with a correlated filter under a grouping-set aggregate now decorrelate into a join instead of failing to plan. No public API changes. --------- Co-authored-by: namanjain24-sudo <[email protected]>
1 parent 484183d commit 290ad15

2 files changed

Lines changed: 209 additions & 67 deletions

File tree

‎datafusion/optimizer/src/decorrelate.rs‎

Lines changed: 150 additions & 60 deletions
Original file line numberDiff line numberDiff line change
@@ -36,8 +36,8 @@ use datafusion_expr::utils::{
3636
collect_subquery_cols, conjunction, find_join_exprs, split_conjunction,
3737
};
3838
use datafusion_expr::{
39-
BinaryExpr, Cast, Distinct, EmptyRelation, Expr, ExprSchemable, Extension, FetchType,
40-
LogicalPlan, LogicalPlanBuilder, MaterializedCte, Operator, SkipType,
39+
Aggregate, BinaryExpr, Cast, Distinct, EmptyRelation, Expr, ExprSchemable, Extension,
40+
FetchType, LogicalPlan, LogicalPlanBuilder, MaterializedCte, Operator, SkipType,
4141
UserDefinedLogicalNodeCore, expr, lit,
4242
};
4343

@@ -92,6 +92,14 @@ pub struct PullUpCorrelatedExpr {
9292
/// The list is cleared when the pull up passes a node that can put a NULL
9393
/// back into such a column: an outer join, a union or a grouping set.
9494
pub correlated_filters: Vec<Expr>,
95+
/// Columns each node on the path from the subquery's root to the node
96+
/// [`Self::f_down`]/[`Self::f_up`] is currently visiting reads in its own
97+
/// expressions: one entry per node on that path, pushed in `f_down` and
98+
/// popped in `f_up`. When `f_up` visits an `Aggregate`, this holds every
99+
/// node strictly above it - its own entry is popped first - so a
100+
/// grouping set that omits a correlated column can tell whether
101+
/// something above it reads the column the pull up would fill in.
102+
column_refs_above: Vec<BTreeSet<Column>>,
95103
}
96104

97105
impl Default for PullUpCorrelatedExpr {
@@ -114,6 +122,7 @@ impl PullUpCorrelatedExpr {
114122
pull_up_having_expr: None,
115123
pulled_up_scalar_agg: false,
116124
correlated_filters: Vec::new(),
125+
column_refs_above: Vec::new(),
117126
}
118127
}
119128

@@ -138,6 +147,21 @@ impl PullUpCorrelatedExpr {
138147
}
139148
}
140149

150+
/// The outcome of trying to fold the pull up's columns into a grouping set
151+
/// `Aggregate`. See [`PullUpCorrelatedExpr::grouping_sets_pull_up_outcome`].
152+
#[derive(Debug, PartialEq, Eq)]
153+
enum GroupingSetsPullUp {
154+
/// Every set already groups by the columns; the aggregate's `group_expr`
155+
/// stays as it is.
156+
NoColumnsToAdd,
157+
/// Some set leaves a required column out, but extending every set with it
158+
/// changes nothing the rest of the query can observe.
159+
SafeToExtend,
160+
/// Some set leaves a required column out, and extending every set with it
161+
/// would change what the query returns.
162+
Unsafe,
163+
}
164+
141165
/// Used to indicate the unmatched rows from the inner(subquery) table after the left out Join
142166
/// This is used to handle [the Count bug]
143167
///
@@ -153,6 +177,15 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
153177
type Node = LogicalPlan;
154178

155179
fn f_down(&mut self, plan: LogicalPlan) -> Result<Transformed<LogicalPlan>> {
180+
// Tracks the columns this node's own expressions read, so a
181+
// descendant `Aggregate` can later tell what reads above it. Popped
182+
// by the matching `f_up` call for this same node.
183+
let mut column_refs = BTreeSet::new();
184+
for expr in plan.expressions() {
185+
column_refs.extend(expr.column_refs().into_iter().cloned());
186+
}
187+
self.column_refs_above.push(column_refs);
188+
156189
// This match is exhaustive on purpose. A correlated filter moves above
157190
// a node only when the node is known to keep the result the same. Add
158191
// each new `LogicalPlan` variant to one of the groups below.
@@ -262,7 +295,12 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
262295
match (limit.get_skip_type()?, fetch) {
263296
(SkipType::Literal(0), FetchType::Literal(_)) => {
264297
// The rewriter does not call `f_down` on the returned
265-
// node, so do it here
298+
// node, so do it here. This call pushes its own
299+
// entry onto `column_refs_above`; pop the one this
300+
// call pushed for the `Limit` itself first; only one
301+
// `f_up` call reaches this tree position once `Limit`
302+
// is gone, so only one entry must remain pushed.
303+
self.column_refs_above.pop();
266304
let mut t = self.f_down((*limit.input).clone())?;
267305
t.transformed = true;
268306
Ok(t)
@@ -332,6 +370,10 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
332370
}
333371

334372
fn f_up(&mut self, plan: LogicalPlan) -> Result<Transformed<LogicalPlan>> {
373+
// Pop this node's own entry, pushed by the matching `f_down` call, so
374+
// `column_refs_above` holds only the nodes strictly above `plan`.
375+
self.column_refs_above.pop();
376+
335377
// A node that null-extends or regroups rows can put a NULL back into
336378
// a column that a correlated filter below it rejected, so the filters
337379
// recorded so far no longer bound what the subquery returns.
@@ -470,42 +512,54 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
470512
&mut local_correlated_cols,
471513
);
472514

473-
// A grouping set cannot take the columns the pull up adds.
474-
// `LogicalPlanBuilder::aggregate` cross joins a plain group
475-
// expression with the sets that are already there, so `ROLLUP(i.k)`,
476-
// which is `GROUPING SETS ((i.k), ())`, becomes
477-
// `GROUPING SETS ((i.k), (i.k, i.k))`. The empty set is gone, and
478-
// with it the grand total row the subquery returns for every outer
479-
// row, including the rows whose correlated filter matches nothing.
480-
// The join that replaces the filter cannot bring those rows back,
481-
// so the subquery stays correlated unless every set already groups
482-
// by each column the pull up would add.
515+
// A grouping set that omits a column the pull up adds either
516+
// keeps its sets as they are (every set already groups by the
517+
// column), or gains the column in every set, `ROLLUP(i.k)`
518+
// (`GROUPING SETS ((i.k), ())`) becoming
519+
// `GROUPING SETS ((i.k), (i.k, i.k))`. The latter loses the
520+
// empty set, and with it the grand total row the subquery
521+
// returns for every outer row, including the rows whose
522+
// correlated filter matches nothing, so it is only safe when
523+
// no set is empty and nothing reads the column the fill
524+
// changes from `NULL` to the correlated value.
483525
let mut missing_exprs = if aggregate
484526
.group_expr
485527
.iter()
486528
.any(|expr| matches!(expr, Expr::GroupingSet(_)))
487529
{
488-
if self.grouping_sets_cover_pull_up_cols(
489-
&aggregate.group_expr,
490-
&local_correlated_cols,
491-
) {
492-
// Every set already groups by them, so the sets stay as
493-
// they are. Adding the columns again would repeat them
494-
// inside every set.
495-
aggregate.group_expr.to_vec()
496-
} else {
497-
self.can_pull_up = false;
498-
// The rewrite still runs, the same way the
499-
// `can_pull_over_aggregation` case above does. The callers
500-
// read `can_pull_up` only after the whole rewrite has
501-
// finished, and the nodes above this one still expect the
502-
// pulled up columns in its output, so leaving them out here
503-
// would fail the rewrite with a schema error instead. They
504-
// drop this plan and keep the correlated subquery.
505-
self.collect_missing_exprs(
506-
&aggregate.group_expr,
507-
&local_correlated_cols,
508-
)?
530+
match self
531+
.grouping_sets_pull_up_outcome(aggregate, &local_correlated_cols)
532+
{
533+
GroupingSetsPullUp::NoColumnsToAdd => {
534+
// Every set already groups by them, so the sets stay as
535+
// they are. Adding the columns again would repeat them
536+
// inside every set.
537+
aggregate.group_expr.to_vec()
538+
}
539+
GroupingSetsPullUp::SafeToExtend => {
540+
// No set is empty and nothing reads the columns the
541+
// fill changes from `NULL` to the correlated value,
542+
// so extending every set is invisible to the rest of
543+
// the query.
544+
self.collect_missing_exprs(
545+
&aggregate.group_expr,
546+
&local_correlated_cols,
547+
)?
548+
}
549+
GroupingSetsPullUp::Unsafe => {
550+
self.can_pull_up = false;
551+
// The rewrite still runs, the same way the
552+
// `can_pull_over_aggregation` case above does. The callers
553+
// read `can_pull_up` only after the whole rewrite has
554+
// finished, and the nodes above this one still expect the
555+
// pulled up columns in its output, so leaving them out here
556+
// would fail the rewrite with a schema error instead. They
557+
// drop this plan and keep the correlated subquery.
558+
self.collect_missing_exprs(
559+
&aggregate.group_expr,
560+
&local_correlated_cols,
561+
)?
562+
}
509563
}
510564
} else {
511565
// add missing columns to Aggregation's group expressions
@@ -651,26 +705,40 @@ impl PullUpCorrelatedExpr {
651705
Ok(Transformed::yes(plan.recompute_schema()?))
652706
}
653707

654-
/// Whether the pull up can add its columns to `group_expr` without changing
655-
/// what the aggregate returns.
708+
/// Whether the pull up can add its columns to a grouping set `Aggregate`,
709+
/// and whether it needs to.
656710
///
657-
/// `true` when `group_expr` holds no grouping set, and when every set of every
658-
/// grouping set it holds already groups by each column
659-
/// [`Self::collect_missing_exprs`] would add. In the second case the pull up
660-
/// adds nothing and the aggregate keeps the sets it has.
711+
/// [`GroupingSetsPullUp::NoColumnsToAdd`] when every set of every grouping
712+
/// set already groups by each column [`Self::collect_missing_exprs`]
713+
/// would add: the pull up adds nothing and the aggregate keeps the sets
714+
/// it has.
661715
///
662-
/// `ROLLUP` and `CUBE` always contain the empty set, which yields a row for
663-
/// outer rows the correlated filter matches nothing for, so they are only safe
664-
/// when there is nothing to add.
716+
/// Otherwise some set leaves a required column out, which fills that
717+
/// column with `NULL` in the set's rows. Adding the column to every set
718+
/// (`LogicalPlanBuilder::aggregate` cross joins a plain group expression
719+
/// with the sets that are already there) gives it a value instead. This
720+
/// is only invisible to the rest of the query when:
721+
/// - no set is empty. `ROLLUP(i.k)`, `GROUPING SETS ((i.k), ())`, always
722+
/// holds one, and turns into `GROUPING SETS ((i.k), (i.k, i.k))`,
723+
/// losing the empty set and the grand total row it yields for every
724+
/// outer row, including the rows the correlated filter matches
725+
/// nothing for. The join that replaces the filter cannot bring that
726+
/// row back.
727+
/// - the aggregate does not compute `GROUPING`/`GROUPING_ID`, which
728+
/// reads whether a row's set groups by a column.
729+
/// - nothing above the aggregate reads the column, which
730+
/// `column_refs_above` tracks as `f_down`/`f_up` push and pop a node's
731+
/// own columns while they walk down to and back up from it.
665732
///
666-
/// A non-empty set that leaves a column out fills it with NULL. Adding the
667-
/// column would give it a value instead, which a `HAVING` or a projection
668-
/// above the aggregate can read, so such a set is rejected as well.
669-
fn grouping_sets_cover_pull_up_cols(
733+
/// When one of these fails, [`GroupingSetsPullUp::Unsafe`] is returned:
734+
/// the columns are still added, so the schema the nodes above expect
735+
/// stays correct, but the caller must give up on decorrelating.
736+
fn grouping_sets_pull_up_outcome(
670737
&self,
671-
group_expr: &[Expr],
738+
aggregate: &Aggregate,
672739
correlated_subquery_cols: &BTreeSet<Column>,
673-
) -> bool {
740+
) -> GroupingSetsPullUp {
741+
let group_expr = &aggregate.group_expr;
674742
let grouping_sets = group_expr
675743
.iter()
676744
.filter_map(|expr| match expr {
@@ -679,7 +747,7 @@ impl PullUpCorrelatedExpr {
679747
})
680748
.collect::<Vec<_>>();
681749
if grouping_sets.is_empty() {
682-
return true;
750+
return GroupingSetsPullUp::NoColumnsToAdd;
683751
}
684752

685753
// The same columns `collect_missing_exprs` appends: the correlated columns
@@ -695,18 +763,40 @@ impl PullUpCorrelatedExpr {
695763
.any(|expr| matches!(expr, Expr::Column(c) if c == *col))
696764
});
697765
if required_cols.is_empty() {
698-
return true;
766+
return GroupingSetsPullUp::NoColumnsToAdd;
699767
}
700768

701-
grouping_sets.iter().all(|grouping_set| match grouping_set {
702-
GroupingSet::Rollup(_) | GroupingSet::Cube(_) => false,
703-
GroupingSet::GroupingSets(sets) => sets.iter().all(|set| {
704-
required_cols.iter().all(|col| {
705-
set.iter()
706-
.any(|expr| matches!(expr, Expr::Column(c) if c == *col))
707-
})
708-
}),
709-
})
769+
let already_covered =
770+
grouping_sets.iter().all(|grouping_set| match grouping_set {
771+
GroupingSet::Rollup(_) | GroupingSet::Cube(_) => false,
772+
GroupingSet::GroupingSets(sets) => sets.iter().all(|set| {
773+
required_cols.iter().all(|col| {
774+
set.iter()
775+
.any(|expr| matches!(expr, Expr::Column(c) if c == *col))
776+
})
777+
}),
778+
});
779+
if already_covered {
780+
return GroupingSetsPullUp::NoColumnsToAdd;
781+
}
782+
783+
let has_empty_set = grouping_sets.iter().any(|grouping_set| match grouping_set {
784+
GroupingSet::Rollup(_) | GroupingSet::Cube(_) => true,
785+
GroupingSet::GroupingSets(sets) => sets.iter().any(|set| set.is_empty()),
786+
});
787+
// `GROUPING`/`GROUPING_ID` are resolved to bit tests on `__grouping_id`
788+
// above the aggregate by `ResolveGroupingFunction` before this rule
789+
// runs, so `aggregate.aggr_expr` never holds a `GROUPING` call by the
790+
// time this is reached; adding a column shifts those bits instead.
791+
let unsafe_read = self.column_refs_above.iter().flatten().any(|col| {
792+
col.name == Aggregate::INTERNAL_GROUPING_ID || required_cols.contains(col)
793+
});
794+
795+
if has_empty_set || unsafe_read {
796+
GroupingSetsPullUp::Unsafe
797+
} else {
798+
GroupingSetsPullUp::SafeToExtend
799+
}
710800
}
711801

712802
fn collect_missing_exprs(

0 commit comments

Comments
 (0)