@@ -23,11 +23,14 @@ use std::sync::Arc;
2323use crate :: push_down_filter:: lr_is_preserved;
2424use crate :: simplify_expressions:: ExprSimplifier ;
2525
26+ use datafusion_common:: nested_struct:: is_injective_cast;
2627use datafusion_common:: tree_node:: {
2728 Transformed , TransformedResult , TreeNode , TreeNodeRecursion , TreeNodeRewriter ,
2829} ;
30+ use datafusion_common:: utils:: has_float_leaf;
2931use datafusion_common:: {
30- Column , DFSchemaRef , HashMap , Result , ScalarValue , assert_or_internal_err, plan_err,
32+ Column , DFSchema , DFSchemaRef , HashMap , Result , ScalarValue , assert_or_internal_err,
33+ plan_err,
3134} ;
3235use datafusion_expr:: expr:: { Alias , GroupingSet } ;
3336use datafusion_expr:: logical_plan:: { Join , JoinType } ;
@@ -38,7 +41,7 @@ use datafusion_expr::utils::{
3841use datafusion_expr:: {
3942 Aggregate , BinaryExpr , Cast , Distinct , EmptyRelation , Expr , ExprSchemable , Extension ,
4043 FetchType , LogicalPlan , LogicalPlanBuilder , MaterializedCte , Operator , SkipType ,
41- UserDefinedLogicalNodeCore , expr, lit,
44+ UserDefinedLogicalNodeCore , Window , expr, lit,
4245} ;
4346
4447/// This struct rewrite the sub query plan by pull up the correlated
@@ -59,6 +62,10 @@ pub struct PullUpCorrelatedExpr {
5962 /// Indicates if we encounter any correlated expression that can not be pulled up
6063 /// above a aggregation without changing the meaning of the query.
6164 can_pull_over_aggregation : bool ,
65+ /// Whether every correlated conjunct seen so far passes
66+ /// [`is_partitionable_equality`], so a Window above them can partition by their
67+ /// columns.
68+ can_extend_partition_by : bool ,
6269 /// Do we need to handle [the count bug] during the pull up process.
6370 ///
6471 /// The "count bug" was described in [Optimization of Nested SQL
@@ -117,6 +124,7 @@ impl PullUpCorrelatedExpr {
117124 exists_sub_query : false ,
118125 can_pull_up : true ,
119126 can_pull_over_aggregation : true ,
127+ can_extend_partition_by : true ,
120128 need_handle_count_bug : false ,
121129 collected_count_expr_map : HashMap :: new ( ) ,
122130 pull_up_having_expr : None ,
@@ -321,7 +329,9 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
321329 // outer row. A non-equality filter can return duplicates, see
322330 // https://github.com/apache/datafusion/issues/25808.
323331 // - A Window keeps or drops whole partitions when the filter reads
324- // only its `PARTITION BY` columns. `f_up` checks this.
332+ // only its `PARTITION BY` columns. For other filters, `f_up` adds
333+ // the columns of a column equality to `PARTITION BY` and keeps
334+ // the subquery correlated in the remaining cases.
325335 // - An Unnest maps each input row to its own output rows, so a
326336 // filter on a column it passes through keeps the same rows.
327337 // The arm above checks that the filter does not read an unnested
@@ -384,11 +394,11 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
384394 match & plan {
385395 LogicalPlan :: Filter ( plan_filter) => {
386396 let subquery_filter_exprs = split_conjunction ( & plan_filter. predicate ) ;
387- self . can_pull_over_aggregation = self . can_pull_over_aggregation
388- && subquery_filter_exprs
389- . iter ( )
390- . filter ( |e| e . contains_outer ( ) )
391- . all ( | & e| can_pullup_over_aggregation ( e ) ) ;
397+ for & expr in subquery_filter_exprs . iter ( ) . filter ( |e| e . contains_outer ( ) ) {
398+ self . can_pull_over_aggregation &= can_pullup_over_aggregation ( expr ) ;
399+ self . can_extend_partition_by &=
400+ is_partitionable_equality ( expr , plan_filter . input . schema ( ) ) ;
401+ }
392402 for expr in & subquery_filter_exprs {
393403 if expr. contains_outer ( ) && !self . correlated_filters . contains ( expr) {
394404 self . correlated_filters . push ( ( * expr) . clone ( ) ) ;
@@ -664,6 +674,16 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
664674 . iter ( )
665675 . all ( |expr| partitions_by_all ( expr, & local_correlated_cols) )
666676 {
677+ // `inner.y = outer.k` keeps the rows of one `y` value for
678+ // each outer row, so partitioning by `y` as well gives each
679+ // window function the same rows. A window over an
680+ // aggregate with count bug handling stops the pull up in
681+ // `pass_through_pulled_up_cols`.
682+ if self . can_extend_partition_by {
683+ let extended =
684+ partition_window_by ( window, & local_correlated_cols) ?;
685+ return self . pass_through_pulled_up_cols ( extended) ;
686+ }
667687 self . can_pull_up = false ;
668688 }
669689 self . pass_through_pulled_up_cols ( plan)
@@ -907,6 +927,46 @@ fn correlated_filter_columns(plan: &LogicalPlan) -> Vec<Column> {
907927 cols
908928}
909929
930+ /// Adds `cols` to the `PARTITION BY` of every window function of `window`. Each
931+ /// window expression keeps its old output name, so nothing above sees a change.
932+ fn partition_window_by ( window : & Window , cols : & BTreeSet < Column > ) -> Result < LogicalPlan > {
933+ let window_expr = window
934+ . window_expr
935+ . iter ( )
936+ . map ( |expr| {
937+ add_partition_by ( expr, cols) . alias_if_changed ( expr. schema_name ( ) . to_string ( ) )
938+ } )
939+ . collect :: < Result < Vec < _ > > > ( ) ?;
940+ Window :: try_new ( window_expr, Arc :: clone ( & window. input ) ) . map ( LogicalPlan :: Window )
941+ }
942+
943+ fn add_partition_by ( expr : & Expr , cols : & BTreeSet < Column > ) -> Expr {
944+ match expr {
945+ Expr :: Alias ( alias) => Expr :: Alias ( Alias {
946+ expr : Box :: new ( add_partition_by ( & alias. expr , cols) ) ,
947+ ..alias. clone ( )
948+ } ) ,
949+ Expr :: WindowFunction ( window_fun) => {
950+ let mut window_fun = window_fun. clone ( ) ;
951+ for col in cols {
952+ let partitioned = window_fun
953+ . params
954+ . partition_by
955+ . iter ( )
956+ . any ( |expr| matches ! ( expr, Expr :: Column ( c) if c == col) ) ;
957+ if !partitioned {
958+ window_fun
959+ . params
960+ . partition_by
961+ . push ( Expr :: Column ( col. clone ( ) ) ) ;
962+ }
963+ }
964+ Expr :: WindowFunction ( window_fun)
965+ }
966+ _ => expr. clone ( ) ,
967+ }
968+ }
969+
910970/// Whether the window function `expr` lists each of `cols` as a plain
911971/// `PARTITION BY` column.
912972fn partitions_by_all ( expr : & Expr , cols : & BTreeSet < Column > ) -> bool {
@@ -926,30 +986,54 @@ fn partitions_by_all(expr: &Expr, cols: &BTreeSet<Column>) -> bool {
926986}
927987
928988fn can_pullup_over_aggregation ( expr : & Expr ) -> bool {
929- if let Expr :: BinaryExpr ( BinaryExpr {
989+ split_column_equality ( expr) . is_some ( )
990+ }
991+
992+ /// Whether partitioning by the columns of `expr` keeps the rows `expr` matches
993+ /// for one outer row in one partition. That holds for `col = <expr>` or
994+ /// `<expr> = col`, where:
995+ /// - `<expr>` reads no subquery column and is not volatile.
996+ /// - `col` has no float leaf, because `-0.0 = 0.0` holds but a partition
997+ /// keeps the two apart.
998+ /// - `col` is cast only by a cast that keeps distinct values distinct. A lossy
999+ /// cast lets several `col` values match one outer row, see #26014.
1000+ fn is_partitionable_equality ( expr : & Expr , schema : & DFSchema ) -> bool {
1001+ let Some ( ( col_side, other) ) = split_column_equality ( expr) else {
1002+ return false ;
1003+ } ;
1004+ let ( col, cast_to) = match col_side {
1005+ Expr :: Cast ( Cast { expr, field } ) => ( & * * expr, Some ( field. data_type ( ) ) ) ,
1006+ _ => ( col_side, None ) ,
1007+ } ;
1008+ let Ok ( col_type) = col. get_type ( schema) else {
1009+ return false ;
1010+ } ;
1011+ !other. is_volatile ( )
1012+ && !has_float_leaf ( & col_type)
1013+ && cast_to. is_none_or ( |to| is_injective_cast ( & col_type, to) )
1014+ }
1015+
1016+ /// Splits `col = <expr>` or `<expr> = col` into the subquery column side, a
1017+ /// column or a cast of one, and the other side, which reads no subquery column.
1018+ fn split_column_equality ( expr : & Expr ) -> Option < ( & Expr , & Expr ) > {
1019+ let Expr :: BinaryExpr ( BinaryExpr {
9301020 left,
9311021 op : Operator :: Eq ,
9321022 right,
9331023 } ) = expr
934- {
935- match ( & * * left, & * * right) {
936- ( Expr :: Column ( _) , right) => !right. any_column_refs ( ) ,
937- ( left, Expr :: Column ( _) ) => !left. any_column_refs ( ) ,
938- ( Expr :: Cast ( Cast { expr, .. } ) , right)
939- if matches ! ( & * * expr, Expr :: Column ( _) ) =>
940- {
941- !right. any_column_refs ( )
942- }
943- ( left, Expr :: Cast ( Cast { expr, .. } ) )
944- if matches ! ( & * * expr, Expr :: Column ( _) ) =>
945- {
946- !left. any_column_refs ( )
947- }
948- ( _, _) => false ,
949- }
950- } else {
951- false
952- }
1024+ else {
1025+ return None ;
1026+ } ;
1027+ [ ( & * * left, & * * right) , ( & * * right, & * * left) ]
1028+ . into_iter ( )
1029+ . find ( |( col_side, other) | {
1030+ let is_col = match col_side {
1031+ Expr :: Column ( _) => true ,
1032+ Expr :: Cast ( Cast { expr, .. } ) => matches ! ( & * * expr, Expr :: Column ( _) ) ,
1033+ _ => false ,
1034+ } ;
1035+ is_col && !other. any_column_refs ( )
1036+ } )
9531037}
9541038
9551039fn collect_local_correlated_cols (
0 commit comments