@@ -36,8 +36,8 @@ use datafusion_expr::utils::{
3636 collect_subquery_cols, conjunction, find_join_exprs, split_conjunction,
3737} ;
3838use datafusion_expr:: {
39- BinaryExpr , Cast , EmptyRelation , Expr , ExprSchemable , FetchType , LogicalPlan ,
40- LogicalPlanBuilder , Operator , SkipType , expr, lit,
39+ Aggregate , BinaryExpr , Cast , EmptyRelation , Expr , ExprSchemable , FetchType ,
40+ LogicalPlan , LogicalPlanBuilder , Operator , SkipType , expr, lit,
4141} ;
4242
4343/// This struct rewrite the sub query plan by pull up the correlated
@@ -91,6 +91,13 @@ pub struct PullUpCorrelatedExpr {
9191 /// The list is cleared when the pull up passes a node that can put a NULL
9292 /// back into such a column: an outer join, a union or a grouping set.
9393 pub correlated_filters : Vec < Expr > ,
94+ /// Columns read, above the subquery's `Aggregate`, by a node the rewrite
95+ /// has not reached yet when it visits that `Aggregate` (the rewrite runs
96+ /// bottom-up, so a `Projection` or `HAVING` above it is only visited
97+ /// afterwards). Populated once, from the original subquery plan, by
98+ /// [`Self::with_column_refs_above_aggregate`], since [`Self::f_up`] has no
99+ /// way to compute it on its own.
100+ column_refs_above_aggregate : BTreeSet < Column > ,
94101}
95102
96103impl Default for PullUpCorrelatedExpr {
@@ -113,6 +120,7 @@ impl PullUpCorrelatedExpr {
113120 pull_up_having_expr : None ,
114121 pulled_up_scalar_agg : false ,
115122 correlated_filters : Vec :: new ( ) ,
123+ column_refs_above_aggregate : BTreeSet :: new ( ) ,
116124 }
117125 }
118126
@@ -142,6 +150,36 @@ impl PullUpCorrelatedExpr {
142150 self . can_pull_up = false ;
143151 Ok ( Transformed :: new ( plan, false , TreeNodeRecursion :: Jump ) )
144152 }
153+
154+ /// Record the columns read above the subquery's `Aggregate`, computed
155+ /// from `subquery_plan` (the plan as it is before this rewrite runs).
156+ ///
157+ /// A grouping set that omits a correlated column only needs to reject the
158+ /// pull up when something reads the column the pull up would fill in, so
159+ /// [`Self::f_up`] needs this computed ahead of time. See
160+ /// [`columns_read_above_aggregate`].
161+ pub fn with_column_refs_above_aggregate (
162+ mut self ,
163+ subquery_plan : & LogicalPlan ,
164+ ) -> Self {
165+ self . column_refs_above_aggregate = columns_read_above_aggregate ( subquery_plan) ;
166+ self
167+ }
168+ }
169+
170+ /// The outcome of trying to fold the pull up's columns into a grouping set
171+ /// `Aggregate`. See [`PullUpCorrelatedExpr::grouping_sets_pull_up_outcome`].
172+ #[ derive( Debug , PartialEq , Eq ) ]
173+ enum GroupingSetsPullUp {
174+ /// Every set already groups by the columns; the aggregate's `group_expr`
175+ /// stays as it is.
176+ NoColumnsToAdd ,
177+ /// Some set leaves a required column out, but extending every set with it
178+ /// changes nothing the rest of the query can observe.
179+ SafeToExtend ,
180+ /// Some set leaves a required column out, and extending every set with it
181+ /// would change what the query returns.
182+ Unsafe ,
145183}
146184
147185/// Used to indicate the unmatched rows from the inner(subquery) table after the left out Join
@@ -363,42 +401,54 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
363401 & mut local_correlated_cols,
364402 ) ;
365403
366- // A grouping set cannot take the columns the pull up adds.
367- // `LogicalPlanBuilder::aggregate` cross joins a plain group
368- // expression with the sets that are already there, so `ROLLUP(i.k)`,
369- // which is `GROUPING SETS ((i.k), ())`, becomes
370- // `GROUPING SETS ((i.k), (i.k, i.k))`. The empty set is gone, and
371- // with it the grand total row the subquery returns for every outer
372- // row, including the rows whose correlated filter matches nothing.
373- // The join that replaces the filter cannot bring those rows back,
374- // so the subquery stays correlated unless every set already groups
375- // by each column the pull up would add .
404+ // A grouping set that omits a column the pull up adds either
405+ // keeps its sets as they are (every set already groups by the
406+ // column), or gains the column in every set, `ROLLUP(i.k)`
407+ // ( `GROUPING SETS ((i.k), ())`) becoming
408+ // `GROUPING SETS ((i.k), (i.k, i.k))`. The latter loses the
409+ // empty set, and with it the grand total row the subquery
410+ // returns for every outer row, including the rows whose
411+ // correlated filter matches nothing, so it is only safe when
412+ // no set is empty and nothing reads the column the fill
413+ // changes from `NULL` to the correlated value .
376414 let mut missing_exprs = if aggregate
377415 . group_expr
378416 . iter ( )
379417 . any ( |expr| matches ! ( expr, Expr :: GroupingSet ( _) ) )
380418 {
381- if self . grouping_sets_cover_pull_up_cols (
382- & aggregate. group_expr ,
383- & local_correlated_cols,
384- ) {
385- // Every set already groups by them, so the sets stay as
386- // they are. Adding the columns again would repeat them
387- // inside every set.
388- aggregate. group_expr . to_vec ( )
389- } else {
390- self . can_pull_up = false ;
391- // The rewrite still runs, the same way the
392- // `can_pull_over_aggregation` case above does. The callers
393- // read `can_pull_up` only after the whole rewrite has
394- // finished, and the nodes above this one still expect the
395- // pulled up columns in its output, so leaving them out here
396- // would fail the rewrite with a schema error instead. They
397- // drop this plan and keep the correlated subquery.
398- self . collect_missing_exprs (
399- & aggregate. group_expr ,
400- & local_correlated_cols,
401- ) ?
419+ match self
420+ . grouping_sets_pull_up_outcome ( aggregate, & local_correlated_cols)
421+ {
422+ GroupingSetsPullUp :: NoColumnsToAdd => {
423+ // Every set already groups by them, so the sets stay as
424+ // they are. Adding the columns again would repeat them
425+ // inside every set.
426+ aggregate. group_expr . to_vec ( )
427+ }
428+ GroupingSetsPullUp :: SafeToExtend => {
429+ // No set is empty and nothing reads the columns the
430+ // fill changes from `NULL` to the correlated value,
431+ // so extending every set is invisible to the rest of
432+ // the query.
433+ self . collect_missing_exprs (
434+ & aggregate. group_expr ,
435+ & local_correlated_cols,
436+ ) ?
437+ }
438+ GroupingSetsPullUp :: Unsafe => {
439+ self . can_pull_up = false ;
440+ // The rewrite still runs, the same way the
441+ // `can_pull_over_aggregation` case above does. The callers
442+ // read `can_pull_up` only after the whole rewrite has
443+ // finished, and the nodes above this one still expect the
444+ // pulled up columns in its output, so leaving them out here
445+ // would fail the rewrite with a schema error instead. They
446+ // drop this plan and keep the correlated subquery.
447+ self . collect_missing_exprs (
448+ & aggregate. group_expr ,
449+ & local_correlated_cols,
450+ ) ?
451+ }
402452 }
403453 } else {
404454 // add missing columns to Aggregation's group expressions
@@ -492,26 +542,41 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
492542}
493543
494544impl PullUpCorrelatedExpr {
495- /// Whether the pull up can add its columns to `group_expr` without changing
496- /// what the aggregate returns .
545+ /// Whether the pull up can add its columns to a grouping set `Aggregate`,
546+ /// and whether it needs to .
497547 ///
498- /// `true` when `group_expr` holds no grouping set, and when every set of every
499- /// grouping set it holds already groups by each column
500- /// [`Self::collect_missing_exprs`] would add. In the second case the pull up
501- /// adds nothing and the aggregate keeps the sets it has.
548+ /// [`GroupingSetsPullUp::NoColumnsToAdd`] when every set of every grouping
549+ /// set already groups by each column [`Self::collect_missing_exprs`]
550+ /// would add: the pull up adds nothing and the aggregate keeps the sets
551+ /// it has.
502552 ///
503- /// `ROLLUP` and `CUBE` always contain the empty set, which yields a row for
504- /// outer rows the correlated filter matches nothing for, so they are only safe
505- /// when there is nothing to add.
553+ /// Otherwise some set leaves a required column out, which fills that
554+ /// column with `NULL` in the set's rows. Adding the column to every set
555+ /// (`LogicalPlanBuilder::aggregate` cross joins a plain group expression
556+ /// with the sets that are already there) gives it a value instead. This
557+ /// is only invisible to the rest of the query when:
558+ /// - no set is empty. `ROLLUP(i.k)`, `GROUPING SETS ((i.k), ())`, always
559+ /// holds one, and turns into `GROUPING SETS ((i.k), (i.k, i.k))`,
560+ /// losing the empty set and the grand total row it yields for every
561+ /// outer row, including the rows the correlated filter matches
562+ /// nothing for. The join that replaces the filter cannot bring that
563+ /// row back.
564+ /// - the aggregate does not compute `GROUPING`/`GROUPING_ID`, which
565+ /// reads whether a row's set groups by a column.
566+ /// - nothing above the aggregate reads the column, which
567+ /// `column_refs_above_aggregate` was populated with ahead of time (this
568+ /// rewrite runs bottom-up, so a `HAVING` or `Projection` above the
569+ /// aggregate is only visited after it).
506570 ///
507- /// A non-empty set that leaves a column out fills it with NULL. Adding the
508- /// column would give it a value instead, which a `HAVING` or a projection
509- /// above the aggregate can read, so such a set is rejected as well .
510- fn grouping_sets_cover_pull_up_cols (
571+ /// When one of these fails, [`GroupingSetsPullUp::Unsafe`] is returned:
572+ /// the columns are still added, so the schema the nodes above expect
573+ /// stays correct, but the caller must give up on decorrelating .
574+ fn grouping_sets_pull_up_outcome (
511575 & self ,
512- group_expr : & [ Expr ] ,
576+ aggregate : & Aggregate ,
513577 correlated_subquery_cols : & BTreeSet < Column > ,
514- ) -> bool {
578+ ) -> GroupingSetsPullUp {
579+ let group_expr = & aggregate. group_expr ;
515580 let grouping_sets = group_expr
516581 . iter ( )
517582 . filter_map ( |expr| match expr {
@@ -520,7 +585,7 @@ impl PullUpCorrelatedExpr {
520585 } )
521586 . collect :: < Vec < _ > > ( ) ;
522587 if grouping_sets. is_empty ( ) {
523- return true ;
588+ return GroupingSetsPullUp :: NoColumnsToAdd ;
524589 }
525590
526591 // The same columns `collect_missing_exprs` appends: the correlated columns
@@ -536,18 +601,37 @@ impl PullUpCorrelatedExpr {
536601 . any ( |expr| matches ! ( expr, Expr :: Column ( c) if c == * col) )
537602 } ) ;
538603 if required_cols. is_empty ( ) {
539- return true ;
604+ return GroupingSetsPullUp :: NoColumnsToAdd ;
540605 }
541606
542- grouping_sets. iter ( ) . all ( |grouping_set| match grouping_set {
543- GroupingSet :: Rollup ( _) | GroupingSet :: Cube ( _) => false ,
544- GroupingSet :: GroupingSets ( sets) => sets. iter ( ) . all ( |set| {
545- required_cols. iter ( ) . all ( |col| {
546- set. iter ( )
547- . any ( |expr| matches ! ( expr, Expr :: Column ( c) if c == * col) )
548- } )
549- } ) ,
550- } )
607+ let already_covered =
608+ grouping_sets. iter ( ) . all ( |grouping_set| match grouping_set {
609+ GroupingSet :: Rollup ( _) | GroupingSet :: Cube ( _) => false ,
610+ GroupingSet :: GroupingSets ( sets) => sets. iter ( ) . all ( |set| {
611+ required_cols. iter ( ) . all ( |col| {
612+ set. iter ( )
613+ . any ( |expr| matches ! ( expr, Expr :: Column ( c) if c == * col) )
614+ } )
615+ } ) ,
616+ } ) ;
617+ if already_covered {
618+ return GroupingSetsPullUp :: NoColumnsToAdd ;
619+ }
620+
621+ let has_empty_set = grouping_sets. iter ( ) . any ( |grouping_set| match grouping_set {
622+ GroupingSet :: Rollup ( _) | GroupingSet :: Cube ( _) => true ,
623+ GroupingSet :: GroupingSets ( sets) => sets. iter ( ) . any ( |set| set. is_empty ( ) ) ,
624+ } ) ;
625+ let reads_grouping_fn = aggregate. aggr_expr . iter ( ) . any ( is_grouping_call) ;
626+ let read_above = required_cols
627+ . iter ( )
628+ . any ( |col| self . column_refs_above_aggregate . contains ( * col) ) ;
629+
630+ if has_empty_set || reads_grouping_fn || read_above {
631+ GroupingSetsPullUp :: Unsafe
632+ } else {
633+ GroupingSetsPullUp :: SafeToExtend
634+ }
551635 }
552636
553637 fn collect_missing_exprs (
@@ -661,6 +745,45 @@ fn can_pullup_over_aggregation(expr: &Expr) -> bool {
661745 }
662746}
663747
748+ /// Whether `expr` computes `GROUPING`/`GROUPING_ID`, which reads whether a
749+ /// row's grouping set groups by a particular column.
750+ fn is_grouping_call ( expr : & Expr ) -> bool {
751+ matches ! ( expr, Expr :: AggregateFunction ( agg) if agg. func. name( ) . eq_ignore_ascii_case( "grouping" ) )
752+ }
753+
754+ /// Columns read by a node strictly above the first `Aggregate` found in
755+ /// `plan`, which is the subquery's original, not yet rewritten, plan.
756+ ///
757+ /// [`PullUpCorrelatedExpr::f_up`] runs bottom-up, so by the time it visits an
758+ /// `Aggregate` it cannot yet tell whether a `HAVING` or `Projection` above it
759+ /// reads one of the columns a grouping set pull up would add. This walks the
760+ /// plan top-down instead, before the rewrite starts, and stops at the first
761+ /// `Aggregate` along each branch, collecting the columns every node above it
762+ /// reads in its own expressions. A nested `Subquery` is a different
763+ /// correlation scope and is skipped, the same way
764+ /// [`PullUpCorrelatedExpr::f_down`] skips it.
765+ fn columns_read_above_aggregate ( plan : & LogicalPlan ) -> BTreeSet < Column > {
766+ fn walk ( plan : & LogicalPlan , above : & mut BTreeSet < Column > ) -> bool {
767+ if matches ! ( plan, LogicalPlan :: Subquery ( _) ) {
768+ return false ;
769+ }
770+ if matches ! ( plan, LogicalPlan :: Aggregate ( _) ) {
771+ return true ;
772+ }
773+ let found_below = plan. inputs ( ) . into_iter ( ) . any ( |child| walk ( child, above) ) ;
774+ if found_below {
775+ for expr in plan. expressions ( ) {
776+ above. extend ( expr. column_refs ( ) . into_iter ( ) . cloned ( ) ) ;
777+ }
778+ }
779+ found_below
780+ }
781+
782+ let mut above = BTreeSet :: new ( ) ;
783+ walk ( plan, & mut above) ;
784+ above
785+ }
786+
664787fn collect_local_correlated_cols (
665788 plan : & LogicalPlan ,
666789 all_cols_map : & HashMap < LogicalPlan , BTreeSet < Column > > ,
0 commit comments