@@ -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 , Distinct , EmptyRelation , Expr , ExprSchemable , FetchType ,
40- LogicalPlan , LogicalPlanBuilder , Operator , SkipType , expr, lit,
39+ Aggregate , BinaryExpr , Cast , Distinct , EmptyRelation , Expr , ExprSchemable ,
40+ FetchType , 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
@@ -135,6 +143,43 @@ impl PullUpCorrelatedExpr {
135143 self . exists_sub_query = exists_sub_query;
136144 self
137145 }
146+
147+ /// Mark the plan as one whose correlated expressions cannot be pulled up
148+ /// and stop descending into it
149+ fn unsupported ( & mut self , plan : LogicalPlan ) -> Result < Transformed < LogicalPlan > > {
150+ self . can_pull_up = false ;
151+ Ok ( Transformed :: new ( plan, false , TreeNodeRecursion :: Jump ) )
152+ }
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 ,
138183}
139184
140185/// Used to indicate the unmatched rows from the inner(subquery) table after the left out Join
@@ -437,42 +482,54 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
437482 & mut local_correlated_cols,
438483 ) ;
439484
440- // A grouping set cannot take the columns the pull up adds.
441- // `LogicalPlanBuilder::aggregate` cross joins a plain group
442- // expression with the sets that are already there, so `ROLLUP(i.k)`,
443- // which is `GROUPING SETS ((i.k), ())`, becomes
444- // `GROUPING SETS ((i.k), (i.k, i.k))`. The empty set is gone, and
445- // with it the grand total row the subquery returns for every outer
446- // row, including the rows whose correlated filter matches nothing.
447- // The join that replaces the filter cannot bring those rows back,
448- // so the subquery stays correlated unless every set already groups
449- // by each column the pull up would add .
485+ // A grouping set that omits a column the pull up adds either
486+ // keeps its sets as they are (every set already groups by the
487+ // column), or gains the column in every set, `ROLLUP(i.k)`
488+ // ( `GROUPING SETS ((i.k), ())`) becoming
489+ // `GROUPING SETS ((i.k), (i.k, i.k))`. The latter loses the
490+ // empty set, and with it the grand total row the subquery
491+ // returns for every outer row, including the rows whose
492+ // correlated filter matches nothing, so it is only safe when
493+ // no set is empty and nothing reads the column the fill
494+ // changes from `NULL` to the correlated value .
450495 let mut missing_exprs = if aggregate
451496 . group_expr
452497 . iter ( )
453498 . any ( |expr| matches ! ( expr, Expr :: GroupingSet ( _) ) )
454499 {
455- if self . grouping_sets_cover_pull_up_cols (
456- & aggregate. group_expr ,
457- & local_correlated_cols,
458- ) {
459- // Every set already groups by them, so the sets stay as
460- // they are. Adding the columns again would repeat them
461- // inside every set.
462- aggregate. group_expr . to_vec ( )
463- } else {
464- self . can_pull_up = false ;
465- // The rewrite still runs, the same way the
466- // `can_pull_over_aggregation` case above does. The callers
467- // read `can_pull_up` only after the whole rewrite has
468- // finished, and the nodes above this one still expect the
469- // pulled up columns in its output, so leaving them out here
470- // would fail the rewrite with a schema error instead. They
471- // drop this plan and keep the correlated subquery.
472- self . collect_missing_exprs (
473- & aggregate. group_expr ,
474- & local_correlated_cols,
475- ) ?
500+ match self
501+ . grouping_sets_pull_up_outcome ( aggregate, & local_correlated_cols)
502+ {
503+ GroupingSetsPullUp :: NoColumnsToAdd => {
504+ // Every set already groups by them, so the sets stay as
505+ // they are. Adding the columns again would repeat them
506+ // inside every set.
507+ aggregate. group_expr . to_vec ( )
508+ }
509+ GroupingSetsPullUp :: SafeToExtend => {
510+ // No set is empty and nothing reads the columns the
511+ // fill changes from `NULL` to the correlated value,
512+ // so extending every set is invisible to the rest of
513+ // the query.
514+ self . collect_missing_exprs (
515+ & aggregate. group_expr ,
516+ & local_correlated_cols,
517+ ) ?
518+ }
519+ GroupingSetsPullUp :: Unsafe => {
520+ self . can_pull_up = false ;
521+ // The rewrite still runs, the same way the
522+ // `can_pull_over_aggregation` case above does. The callers
523+ // read `can_pull_up` only after the whole rewrite has
524+ // finished, and the nodes above this one still expect the
525+ // pulled up columns in its output, so leaving them out here
526+ // would fail the rewrite with a schema error instead. They
527+ // drop this plan and keep the correlated subquery.
528+ self . collect_missing_exprs (
529+ & aggregate. group_expr ,
530+ & local_correlated_cols,
531+ ) ?
532+ }
476533 }
477534 } else {
478535 // add missing columns to Aggregation's group expressions
@@ -618,26 +675,41 @@ impl PullUpCorrelatedExpr {
618675 Ok ( Transformed :: yes ( plan. recompute_schema ( ) ?) )
619676 }
620677
621- /// Whether the pull up can add its columns to `group_expr` without changing
622- /// what the aggregate returns .
678+ /// Whether the pull up can add its columns to a grouping set `Aggregate`,
679+ /// and whether it needs to .
623680 ///
624- /// `true` when `group_expr` holds no grouping set, and when every set of every
625- /// grouping set it holds already groups by each column
626- /// [`Self::collect_missing_exprs`] would add. In the second case the pull up
627- /// adds nothing and the aggregate keeps the sets it has.
681+ /// [`GroupingSetsPullUp::NoColumnsToAdd`] when every set of every grouping
682+ /// set already groups by each column [`Self::collect_missing_exprs`]
683+ /// would add: the pull up adds nothing and the aggregate keeps the sets
684+ /// it has.
628685 ///
629- /// `ROLLUP` and `CUBE` always contain the empty set, which yields a row for
630- /// outer rows the correlated filter matches nothing for, so they are only safe
631- /// when there is nothing to add.
686+ /// Otherwise some set leaves a required column out, which fills that
687+ /// column with `NULL` in the set's rows. Adding the column to every set
688+ /// (`LogicalPlanBuilder::aggregate` cross joins a plain group expression
689+ /// with the sets that are already there) gives it a value instead. This
690+ /// is only invisible to the rest of the query when:
691+ /// - no set is empty. `ROLLUP(i.k)`, `GROUPING SETS ((i.k), ())`, always
692+ /// holds one, and turns into `GROUPING SETS ((i.k), (i.k, i.k))`,
693+ /// losing the empty set and the grand total row it yields for every
694+ /// outer row, including the rows the correlated filter matches
695+ /// nothing for. The join that replaces the filter cannot bring that
696+ /// row back.
697+ /// - the aggregate does not compute `GROUPING`/`GROUPING_ID`, which
698+ /// reads whether a row's set groups by a column.
699+ /// - nothing above the aggregate reads the column, which
700+ /// `column_refs_above_aggregate` was populated with ahead of time (this
701+ /// rewrite runs bottom-up, so a `HAVING` or `Projection` above the
702+ /// aggregate is only visited after it).
632703 ///
633- /// A non-empty set that leaves a column out fills it with NULL. Adding the
634- /// column would give it a value instead, which a `HAVING` or a projection
635- /// above the aggregate can read, so such a set is rejected as well .
636- fn grouping_sets_cover_pull_up_cols (
704+ /// When one of these fails, [`GroupingSetsPullUp::Unsafe`] is returned:
705+ /// the columns are still added, so the schema the nodes above expect
706+ /// stays correct, but the caller must give up on decorrelating .
707+ fn grouping_sets_pull_up_outcome (
637708 & self ,
638- group_expr : & [ Expr ] ,
709+ aggregate : & Aggregate ,
639710 correlated_subquery_cols : & BTreeSet < Column > ,
640- ) -> bool {
711+ ) -> GroupingSetsPullUp {
712+ let group_expr = & aggregate. group_expr ;
641713 let grouping_sets = group_expr
642714 . iter ( )
643715 . filter_map ( |expr| match expr {
@@ -646,7 +718,7 @@ impl PullUpCorrelatedExpr {
646718 } )
647719 . collect :: < Vec < _ > > ( ) ;
648720 if grouping_sets. is_empty ( ) {
649- return true ;
721+ return GroupingSetsPullUp :: NoColumnsToAdd ;
650722 }
651723
652724 // The same columns `collect_missing_exprs` appends: the correlated columns
@@ -662,18 +734,37 @@ impl PullUpCorrelatedExpr {
662734 . any ( |expr| matches ! ( expr, Expr :: Column ( c) if c == * col) )
663735 } ) ;
664736 if required_cols. is_empty ( ) {
665- return true ;
737+ return GroupingSetsPullUp :: NoColumnsToAdd ;
666738 }
667739
668- grouping_sets. iter ( ) . all ( |grouping_set| match grouping_set {
669- GroupingSet :: Rollup ( _) | GroupingSet :: Cube ( _) => false ,
670- GroupingSet :: GroupingSets ( sets) => sets. iter ( ) . all ( |set| {
671- required_cols. iter ( ) . all ( |col| {
672- set. iter ( )
673- . any ( |expr| matches ! ( expr, Expr :: Column ( c) if c == * col) )
674- } )
675- } ) ,
676- } )
740+ let already_covered =
741+ grouping_sets. iter ( ) . all ( |grouping_set| match grouping_set {
742+ GroupingSet :: Rollup ( _) | GroupingSet :: Cube ( _) => false ,
743+ GroupingSet :: GroupingSets ( sets) => sets. iter ( ) . all ( |set| {
744+ required_cols. iter ( ) . all ( |col| {
745+ set. iter ( )
746+ . any ( |expr| matches ! ( expr, Expr :: Column ( c) if c == * col) )
747+ } )
748+ } ) ,
749+ } ) ;
750+ if already_covered {
751+ return GroupingSetsPullUp :: NoColumnsToAdd ;
752+ }
753+
754+ let has_empty_set = grouping_sets. iter ( ) . any ( |grouping_set| match grouping_set {
755+ GroupingSet :: Rollup ( _) | GroupingSet :: Cube ( _) => true ,
756+ GroupingSet :: GroupingSets ( sets) => sets. iter ( ) . any ( |set| set. is_empty ( ) ) ,
757+ } ) ;
758+ let reads_grouping_fn = aggregate. aggr_expr . iter ( ) . any ( is_grouping_call) ;
759+ let read_above = required_cols
760+ . iter ( )
761+ . any ( |col| self . column_refs_above_aggregate . contains ( * col) ) ;
762+
763+ if has_empty_set || reads_grouping_fn || read_above {
764+ GroupingSetsPullUp :: Unsafe
765+ } else {
766+ GroupingSetsPullUp :: SafeToExtend
767+ }
677768 }
678769
679770 fn collect_missing_exprs (
@@ -828,6 +919,45 @@ fn can_pullup_over_aggregation(expr: &Expr) -> bool {
828919 }
829920}
830921
922+ /// Whether `expr` computes `GROUPING`/`GROUPING_ID`, which reads whether a
923+ /// row's grouping set groups by a particular column.
924+ fn is_grouping_call ( expr : & Expr ) -> bool {
925+ matches ! ( expr, Expr :: AggregateFunction ( agg) if agg. func. name( ) . eq_ignore_ascii_case( "grouping" ) )
926+ }
927+
928+ /// Columns read by a node strictly above the first `Aggregate` found in
929+ /// `plan`, which is the subquery's original, not yet rewritten, plan.
930+ ///
931+ /// [`PullUpCorrelatedExpr::f_up`] runs bottom-up, so by the time it visits an
932+ /// `Aggregate` it cannot yet tell whether a `HAVING` or `Projection` above it
933+ /// reads one of the columns a grouping set pull up would add. This walks the
934+ /// plan top-down instead, before the rewrite starts, and stops at the first
935+ /// `Aggregate` along each branch, collecting the columns every node above it
936+ /// reads in its own expressions. A nested `Subquery` is a different
937+ /// correlation scope and is skipped, the same way
938+ /// [`PullUpCorrelatedExpr::f_down`] skips it.
939+ fn columns_read_above_aggregate ( plan : & LogicalPlan ) -> BTreeSet < Column > {
940+ fn walk ( plan : & LogicalPlan , above : & mut BTreeSet < Column > ) -> bool {
941+ if matches ! ( plan, LogicalPlan :: Subquery ( _) ) {
942+ return false ;
943+ }
944+ if matches ! ( plan, LogicalPlan :: Aggregate ( _) ) {
945+ return true ;
946+ }
947+ let found_below = plan. inputs ( ) . into_iter ( ) . any ( |child| walk ( child, above) ) ;
948+ if found_below {
949+ for expr in plan. expressions ( ) {
950+ above. extend ( expr. column_refs ( ) . into_iter ( ) . cloned ( ) ) ;
951+ }
952+ }
953+ found_below
954+ }
955+
956+ let mut above = BTreeSet :: new ( ) ;
957+ walk ( plan, & mut above) ;
958+ above
959+ }
960+
831961fn collect_local_correlated_cols (
832962 plan : & LogicalPlan ,
833963 all_cols_map : & HashMap < LogicalPlan , BTreeSet < Column > > ,
0 commit comments