@@ -27,7 +27,8 @@ use datafusion_common::tree_node::{
2727 Transformed , TransformedResult , TreeNode , TreeNodeRecursion , TreeNodeRewriter ,
2828} ;
2929use datafusion_common:: {
30- Column , DFSchemaRef , HashMap , Result , ScalarValue , assert_or_internal_err, plan_err,
30+ Column , DFSchemaRef , HashMap , Result , ScalarValue , TableReference ,
31+ assert_or_internal_err, plan_err,
3132} ;
3233use datafusion_expr:: expr:: { Alias , GroupingSet } ;
3334use datafusion_expr:: logical_plan:: { Join , JoinType } ;
@@ -38,8 +39,9 @@ use datafusion_expr::utils::{
3839use datafusion_expr:: {
3940 BinaryExpr , Cast , Distinct , EmptyRelation , Expr , ExprSchemable , Extension , FetchType ,
4041 LogicalPlan , LogicalPlanBuilder , MaterializedCte , Operator , SkipType ,
41- UserDefinedLogicalNodeCore , expr, lit,
42+ UserDefinedLogicalNodeCore , Window , expr, lit,
4243} ;
44+ use itertools:: Itertools ;
4345
4446/// This struct rewrite the sub query plan by pull up the correlated
4547/// expressions(contains outer reference columns) from the inner subquery's
@@ -51,6 +53,11 @@ pub struct PullUpCorrelatedExpr {
5153 pub join_filters : Vec < Expr > ,
5254 /// mapping from the plan to its holding correlated columns
5355 pub correlated_subquery_cols_map : HashMap < LogicalPlan , BTreeSet < Column > > ,
56+ /// The columns of the correlated conjuncts that `remove_duplicated_filter`
57+ /// drops because the `IN` predicate repeats them. The join still applies
58+ /// those conjuncts, so a Window between them and the join has to partition
59+ /// by these columns too.
60+ in_predicate_cols_map : HashMap < LogicalPlan , BTreeSet < Column > > ,
5461 pub in_predicate_opt : Option < Expr > ,
5562 /// Is this an Exists(Not Exists) SubQuery. Defaults to **FALSE**
5663 pub exists_sub_query : bool ,
@@ -59,6 +66,10 @@ pub struct PullUpCorrelatedExpr {
5966 /// Indicates if we encounter any correlated expression that can not be pulled up
6067 /// above a aggregation without changing the meaning of the query.
6168 can_pull_over_aggregation : bool ,
69+ /// Whether every correlated conjunct seen so far satisfies
70+ /// [`is_column_equality`], so that a Window above them can partition by
71+ /// their columns.
72+ can_extend_partition_by : bool ,
6273 /// Do we need to handle [the count bug] during the pull up process.
6374 ///
6475 /// The "count bug" was described in [Optimization of Nested SQL
@@ -105,10 +116,12 @@ impl PullUpCorrelatedExpr {
105116 Self {
106117 join_filters : vec ! [ ] ,
107118 correlated_subquery_cols_map : HashMap :: new ( ) ,
119+ in_predicate_cols_map : HashMap :: new ( ) ,
108120 in_predicate_opt : None ,
109121 exists_sub_query : false ,
110122 can_pull_up : true ,
111123 can_pull_over_aggregation : true ,
124+ can_extend_partition_by : true ,
112125 need_handle_count_bug : false ,
113126 collected_count_expr_map : HashMap :: new ( ) ,
114127 pull_up_having_expr : None ,
@@ -347,19 +360,28 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
347360 . iter ( )
348361 . filter ( |e| e. contains_outer ( ) )
349362 . all ( |& e| can_pullup_over_aggregation ( e) ) ;
363+ self . can_extend_partition_by = self . can_extend_partition_by
364+ && subquery_filter_exprs
365+ . iter ( )
366+ . filter ( |e| e. contains_outer ( ) )
367+ . all ( |& e| is_column_equality ( e) ) ;
350368 for expr in & subquery_filter_exprs {
351369 if expr. contains_outer ( ) && !self . correlated_filters . contains ( expr) {
352370 self . correlated_filters . push ( ( * expr) . clone ( ) ) ;
353371 }
354372 }
355373 let ( mut join_filters, subquery_filters) =
356374 find_join_exprs ( subquery_filter_exprs) ?;
375+ let mut in_predicate_cols = BTreeSet :: new ( ) ;
357376 if let Some ( in_predicate) = & self . in_predicate_opt {
377+ in_predicate_cols =
378+ collect_subquery_cols ( & join_filters, subquery_schema) ?;
358379 // in_predicate may be already included in the join filters, remove it from the join filters first.
359380 join_filters = remove_duplicated_filter ( join_filters, in_predicate) ?;
360381 }
361382 let correlated_subquery_cols =
362383 collect_subquery_cols ( & join_filters, subquery_schema) ?;
384+ in_predicate_cols. retain ( |col| !correlated_subquery_cols. contains ( col) ) ;
363385 for expr in join_filters {
364386 if !self . join_filters . contains ( & expr) {
365387 self . join_filters . push ( expr)
@@ -384,19 +406,14 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
384406 None
385407 } ;
386408
387- match ( & pull_up_expr_opt, & self . pull_up_having_expr ) {
409+ let new_plan = match ( & pull_up_expr_opt, & self . pull_up_having_expr ) {
388410 ( Some ( _) , Some ( _) ) => {
389411 // Error path
390- plan_err ! ( "Unsupported Subquery plan" )
412+ return plan_err ! ( "Unsupported Subquery plan" ) ;
391413 }
392414 ( Some ( _) , None ) => {
393415 self . pull_up_having_expr = pull_up_expr_opt;
394- let new_plan =
395- LogicalPlanBuilder :: from ( ( * plan_filter. input ) . clone ( ) )
396- . build ( ) ?;
397- self . correlated_subquery_cols_map
398- . insert ( new_plan. clone ( ) , correlated_subquery_cols) ;
399- Ok ( Transformed :: yes ( new_plan) )
416+ LogicalPlanBuilder :: from ( ( * plan_filter. input ) . clone ( ) ) . build ( ) ?
400417 }
401418 ( None , _) => {
402419 // if the subquery still has filter expressions, restore them.
@@ -405,12 +422,16 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
405422 if let Some ( expr) = conjunction ( subquery_filters) {
406423 plan = plan. filter ( expr) ?
407424 }
408- let new_plan = plan. build ( ) ?;
409- self . correlated_subquery_cols_map
410- . insert ( new_plan. clone ( ) , correlated_subquery_cols) ;
411- Ok ( Transformed :: yes ( new_plan) )
425+ plan. build ( ) ?
412426 }
427+ } ;
428+ self . correlated_subquery_cols_map
429+ . insert ( new_plan. clone ( ) , correlated_subquery_cols) ;
430+ if !in_predicate_cols. is_empty ( ) {
431+ self . in_predicate_cols_map
432+ . insert ( new_plan. clone ( ) , in_predicate_cols) ;
413433 }
434+ Ok ( Transformed :: yes ( new_plan) )
414435 }
415436 LogicalPlan :: Projection ( projection)
416437 if self . in_predicate_opt . is_some ( ) || !self . join_filters . is_empty ( ) =>
@@ -548,17 +569,16 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
548569 Ok ( Transformed :: yes ( new_plan) )
549570 }
550571 LogicalPlan :: SubqueryAlias ( alias) => {
551- let mut local_correlated_cols = BTreeSet :: new ( ) ;
552- collect_local_correlated_cols (
572+ let new_correlated_cols = aliased_local_correlated_cols (
553573 & plan,
554574 & self . correlated_subquery_cols_map ,
555- & mut local_correlated_cols,
575+ & alias. alias ,
576+ ) ;
577+ let new_in_predicate_cols = aliased_local_correlated_cols (
578+ & plan,
579+ & self . in_predicate_cols_map ,
580+ & alias. alias ,
556581 ) ;
557- let mut new_correlated_cols = BTreeSet :: new ( ) ;
558- for col in local_correlated_cols. iter ( ) {
559- new_correlated_cols
560- . insert ( Column :: new ( Some ( alias. alias . clone ( ) ) , col. name . clone ( ) ) ) ;
561- }
562582
563583 let new_plan = if alias. input . schema ( ) . fields ( ) . len ( )
564584 != alias. schema . fields ( ) . len ( )
@@ -572,6 +592,10 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
572592
573593 self . correlated_subquery_cols_map
574594 . insert ( new_plan. clone ( ) , new_correlated_cols) ;
595+ if !new_in_predicate_cols. is_empty ( ) {
596+ self . in_predicate_cols_map
597+ . insert ( new_plan. clone ( ) , new_in_predicate_cols) ;
598+ }
575599 if let Some ( input_map) = self . collected_count_expr_map . get ( & * alias. input )
576600 {
577601 self . collected_count_expr_map
@@ -600,19 +624,36 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
600624 & self . correlated_subquery_cols_map ,
601625 & mut local_correlated_cols,
602626 ) ;
627+ collect_local_correlated_cols (
628+ & plan,
629+ & self . in_predicate_cols_map ,
630+ & mut local_correlated_cols,
631+ ) ;
603632 // A filter that reads only `PARTITION BY` columns keeps or drops
604633 // whole partitions, so each window function sees the same rows
605- // above it or below it. A filter on any other column changes the
606- // rows of a partition.
607- if !local_correlated_cols. is_empty ( )
608- && !window
634+ // above it or below it.
635+ if local_correlated_cols. is_empty ( )
636+ || window
609637 . window_expr
610638 . iter ( )
611639 . all ( |expr| partitions_by_all ( expr, & local_correlated_cols) )
640+ {
641+ return self . pass_through_pulled_up_cols ( plan) ;
642+ }
643+ // A filter like `inner.y = outer.k` keeps the rows of one `y`
644+ // value for each outer row. Partitioning by `y` as well gives
645+ // each window function the same rows once the filter is above
646+ // it. This is what the pull up does for an Aggregate too.
647+ if !self . can_extend_partition_by
648+ || self . collected_count_expr_map . contains_key ( & * window. input )
612649 {
613650 self . can_pull_up = false ;
651+ return self . pass_through_pulled_up_cols ( plan) ;
614652 }
615- self . pass_through_pulled_up_cols ( plan)
653+ Ok ( Transformed :: yes ( partition_window_by (
654+ window,
655+ & local_correlated_cols,
656+ ) ?) )
616657 }
617658 // `f_down` checked that the pulled up filters do not read an
618659 // unnested column.
@@ -817,6 +858,56 @@ fn correlated_filter_columns(plan: &LogicalPlan) -> Vec<Column> {
817858 cols
818859}
819860
861+ /// Adds `cols` to the `PARTITION BY` of every window function of `window`.
862+ /// That changes the names of the window function columns, so a Projection on
863+ /// top gives them their old names back.
864+ fn partition_window_by ( window : & Window , cols : & BTreeSet < Column > ) -> Result < LogicalPlan > {
865+ let new_window_expr = window
866+ . window_expr
867+ . iter ( )
868+ . map ( |expr| add_partition_by ( expr, cols) )
869+ . collect :: < Vec < _ > > ( ) ;
870+ let mut proj_exprs = window
871+ . input
872+ . schema ( )
873+ . columns ( )
874+ . into_iter ( )
875+ . map ( Expr :: Column )
876+ . collect :: < Vec < _ > > ( ) ;
877+ for ( old, new) in window. window_expr . iter ( ) . zip ( & new_window_expr) {
878+ let new_col = Expr :: Column ( Column :: from_name ( new. schema_name ( ) . to_string ( ) ) ) ;
879+ proj_exprs. push ( new_col. alias ( old. schema_name ( ) . to_string ( ) ) ) ;
880+ }
881+ // Window functions that differed only in the added columns are now equal.
882+ let new_window_expr = new_window_expr. into_iter ( ) . unique ( ) . collect ( ) ;
883+ LogicalPlanBuilder :: from ( LogicalPlan :: Window ( Window :: try_new (
884+ new_window_expr,
885+ Arc :: clone ( & window. input ) ,
886+ ) ?) )
887+ . project ( proj_exprs) ?
888+ . build ( )
889+ }
890+
891+ fn add_partition_by ( expr : & Expr , cols : & BTreeSet < Column > ) -> Expr {
892+ match expr {
893+ Expr :: Alias ( alias) => Expr :: Alias ( Alias {
894+ expr : Box :: new ( add_partition_by ( & alias. expr , cols) ) ,
895+ ..alias. clone ( )
896+ } ) ,
897+ Expr :: WindowFunction ( window_fun) => {
898+ let mut window_fun = window_fun. clone ( ) ;
899+ for col in cols {
900+ let col = Expr :: Column ( col. clone ( ) ) ;
901+ if !window_fun. params . partition_by . contains ( & col) {
902+ window_fun. params . partition_by . push ( col) ;
903+ }
904+ }
905+ Expr :: WindowFunction ( window_fun)
906+ }
907+ _ => expr. clone ( ) ,
908+ }
909+ }
910+
820911/// Whether the window function `expr` lists each of `cols` as a plain
821912/// `PARTITION BY` column.
822913fn partitions_by_all ( expr : & Expr , cols : & BTreeSet < Column > ) -> bool {
@@ -862,6 +953,39 @@ fn can_pullup_over_aggregation(expr: &Expr) -> bool {
862953 }
863954}
864955
956+ /// Whether `expr` is `col = <expr>` or `<expr> = col`, where `<expr>` reads no
957+ /// subquery column. Unlike [`can_pullup_over_aggregation`], this rejects
958+ /// `CAST(col AS ..) = <expr>`: a lossy cast lets several `col` values match one
959+ /// outer row, and partitioning by `col` would split those rows.
960+ fn is_column_equality ( expr : & Expr ) -> bool {
961+ let Expr :: BinaryExpr ( BinaryExpr {
962+ left,
963+ op : Operator :: Eq ,
964+ right,
965+ } ) = expr
966+ else {
967+ return false ;
968+ } ;
969+ match ( & * * left, & * * right) {
970+ ( Expr :: Column ( _) , other) | ( other, Expr :: Column ( _) ) => !other. any_column_refs ( ) ,
971+ _ => false ,
972+ }
973+ }
974+
975+ /// [`collect_local_correlated_cols`], with each column qualified by `alias`.
976+ fn aliased_local_correlated_cols (
977+ plan : & LogicalPlan ,
978+ all_cols_map : & HashMap < LogicalPlan , BTreeSet < Column > > ,
979+ alias : & TableReference ,
980+ ) -> BTreeSet < Column > {
981+ let mut local_cols = BTreeSet :: new ( ) ;
982+ collect_local_correlated_cols ( plan, all_cols_map, & mut local_cols) ;
983+ local_cols
984+ . into_iter ( )
985+ . map ( |col| Column :: new ( Some ( alias. clone ( ) ) , col. name ) )
986+ . collect ( )
987+ }
988+
865989fn collect_local_correlated_cols (
866990 plan : & LogicalPlan ,
867991 all_cols_map : & HashMap < LogicalPlan , BTreeSet < Column > > ,
0 commit comments