@@ -49,7 +49,10 @@ use datafusion_physical_plan::repartition::RepartitionExec;
4949use datafusion_physical_plan:: sorts:: sort:: SortExec ;
5050use datafusion_physical_plan:: sorts:: sort_preserving_merge:: SortPreservingMergeExec ;
5151use datafusion_physical_plan:: tree_node:: PlanContext ;
52- use datafusion_physical_plan:: { ExecutionPlan , ExecutionPlanProperties } ;
52+ use datafusion_physical_plan:: {
53+ ChildSatisfactionOptions , ChildrenPropertiesMode , ExecutionPlan ,
54+ ExecutionPlanProperties , ReplaceChildrenOptions ,
55+ } ;
5356
5457/// "Data class" used by sort pushdown (now driven from `EnsureRequirements`)
5558/// to push down [`SortExec`] in the plan. In some cases the total
@@ -548,49 +551,18 @@ fn pushdown_requirement_to_children(
548551 } else {
549552 Ok ( None )
550553 }
551- } else if plan. fetch ( ) . is_some ( )
552- && plan. supports_limit_pushdown ( )
553- && plan
554- . maintains_input_order ( )
555- . into_iter ( )
556- . all ( |maintain| maintain)
557- {
558- // Push down through operator with fetch when:
559- // - requirement is aligned with output ordering
560- // - it preserves ordering during execution
561- //
562- // A `ProjectionExec` reports a `fetch()` forwarded from its input and
563- // can renumber/reorder columns, so the requirement (expressed in the
564- // projection's output schema) must be remapped into the child schema
565- // before being pushed down — forwarding it unchanged would let a key
566- // such as `score@1` (valid in the output schema) refer to a different
567- // column in the child schema, producing a `SortExec` whose key points
568- // at the wrong column ("does not satisfy order requirements ...
569- // Child-0 order: []"). If a required column maps to a computed
570- // (non-`Column`) projection expression it cannot be expressed below the
571- // projection, so the sort is kept above it.
572- let child_required =
573- if let Some ( projection) = plan. downcast_ref :: < ProjectionExec > ( ) {
574- match remap_requirement_through_projection ( projection, & parent_required) {
575- Some ( remapped) => remapped,
576- None => return Ok ( None ) ,
577- }
578- } else {
579- parent_required. clone ( )
580- } ;
581-
582- // Pushing a sort below an unordered fetch changes which rows it keeps.
583- let Some ( ordering) = plan. properties ( ) . output_ordering ( ) else {
554+ } else if plan. is :: < SortPreservingMergeExec > ( ) && plan. fetch ( ) . is_some ( ) {
555+ // Refining a fetched merge must preserve the ordering that selected its rows.
556+ let Some ( ordering) = plan. output_ordering ( ) else {
584557 return Ok ( None ) ;
585558 } ;
586- if plan. properties ( ) . eq_properties . requirements_compatible (
587- parent_required. first ( ) . clone ( ) ,
588- ordering. clone ( ) . into ( ) ,
589- ) {
590- Ok ( Some ( vec ! [ Some ( child_required) ] ) )
591- } else {
592- Ok ( None )
593- }
559+ Ok ( plan
560+ . equivalence_properties ( )
561+ . requirements_compatible (
562+ parent_required. first ( ) . clone ( ) ,
563+ ordering. clone ( ) . into ( ) ,
564+ )
565+ . then ( || vec ! [ Some ( parent_required) ] ) )
594566 } else if is_union ( plan) {
595567 // `UnionExec` does not have real sort requirements for its input, we
596568 // just propagate the sort requirements down:
@@ -635,14 +607,11 @@ fn pushdown_requirement_to_children(
635607 } else if let Some ( projection_exec) = plan. downcast_ref :: < ProjectionExec > ( ) {
636608 handle_projection_pushdown ( projection_exec, & parent_required)
637609 } else if maintains_input_order. is_empty ( )
638- || !maintains_input_order. iter ( ) . any ( |o | * o )
610+ || !maintains_input_order. iter ( ) . any ( |maintains | * maintains )
639611 || plan. is :: < RepartitionExec > ( )
640612 || plan. is :: < FilterExec > ( )
641613 || pushdown_would_violate_requirements ( & parent_required, plan. as_ref ( ) )
642614 {
643- // If the current plan is a leaf node or can not maintain any of the input ordering, can not pushed down requirements.
644- // For RepartitionExec, we always choose to not push down the sort requirements even the RepartitionExec(input_partition=1) could maintain input ordering.
645- // Pushing down is not beneficial
646615 Ok ( None )
647616 } else if is_sort_preserving_merge ( plan) {
648617 let new_ordering = LexOrdering :: from ( parent_required. first ( ) . clone ( ) ) ;
@@ -1000,14 +969,22 @@ fn handle_custom_pushdown(
1000969) -> Result < Option < Vec < Option < OrderingRequirements > > > > {
1001970 let plan_children = plan. children ( ) ;
1002971
1003- // If the plan has no children, return early:
1004- if plan_children. is_empty ( ) {
972+ // A fetched custom node already selects rows; reordering its input can
973+ // change that selection. Native limit and merge cases are handled earlier.
974+ if plan_children. is_empty ( ) || plan. fetch ( ) . is_some ( ) {
1005975 return Ok ( None ) ;
1006976 }
1007977
1008978 // Collect all unique column indices used in the parent-required sorting
1009979 // expression:
1010980 let requirement = parent_required. into_single ( ) ;
981+ // Evaluating a computed key earlier can fail on rows this node would discard.
982+ if requirement
983+ . iter ( )
984+ . any ( |sort| sort. expr . downcast_ref :: < Column > ( ) . is_none ( ) )
985+ {
986+ return Ok ( None ) ;
987+ }
1011988 let all_indices: HashSet < usize > = requirement
1012989 . iter ( )
1013990 . flat_map ( |order| {
@@ -1051,6 +1028,7 @@ fn handle_custom_pushdown(
10511028 // Transform the parent-required expression for the child schema by
10521029 // adjusting columns:
10531030 let updated_parent_req = requirement
1031+ . clone ( )
10541032 . into_iter ( )
10551033 . map ( |req| {
10561034 let child_schema = plan_children[ maintained_child_idx] . schema ( ) ;
@@ -1073,7 +1051,7 @@ fn handle_custom_pushdown(
10731051 . collect :: < Result < Vec < _ > > > ( ) ?;
10741052
10751053 // Prepare the result, populating with the updated requirements for children that maintain order
1076- let result = maintains_input_order
1054+ let result: Vec < _ > = maintains_input_order
10771055 . iter ( )
10781056 . map ( |& maintains_order| {
10791057 if maintains_order {
@@ -1085,12 +1063,101 @@ fn handle_custom_pushdown(
10851063 } )
10861064 . collect ( ) ;
10871065
1066+ // Test the proposed child orderings without moving the real sorts yet.
1067+ let mut probe_children = Vec :: with_capacity ( plan_children. len ( ) ) ;
1068+ for ( child, required) in plan_children. iter ( ) . zip ( & result) {
1069+ let child = if let Some ( required) = required {
1070+ // Other order-maintaining inputs may have narrower schemas.
1071+ if required. first ( ) . iter ( ) . any ( |sort| {
1072+ collect_columns ( & sort. expr )
1073+ . iter ( )
1074+ . any ( |column| column. index ( ) >= child. schema ( ) . fields ( ) . len ( ) )
1075+ } ) {
1076+ return Ok ( None ) ;
1077+ }
1078+ // A bounded operator can stop an unbounded input; a new blocking
1079+ // sort below it cannot. An already ordered input needs no new sort.
1080+ if child. boundedness ( ) . is_unbounded ( )
1081+ && !child
1082+ . equivalence_properties ( )
1083+ . ordering_satisfy_requirement ( required. first ( ) . clone ( ) ) ?
1084+ {
1085+ return Ok ( None ) ;
1086+ }
1087+ Arc :: new (
1088+ SortExec :: new ( required. first ( ) . clone ( ) . into ( ) , Arc :: clone ( child) )
1089+ . with_preserve_partitioning ( true ) ,
1090+ ) as Arc < dyn ExecutionPlan >
1091+ } else {
1092+ Arc :: clone ( child)
1093+ } ;
1094+ probe_children. push ( child) ;
1095+ }
1096+ let children = probe_children
1097+ . iter ( )
1098+ . map ( |child| child. as_ref ( ) )
1099+ . collect :: < Vec < _ > > ( ) ;
1100+ if !sort_pushdown_inputs_satisfied ( plan. as_ref ( ) , & children) ? {
1101+ return Ok ( None ) ;
1102+ }
1103+ let probe = Arc :: clone ( plan) . replace_children (
1104+ probe_children,
1105+ ReplaceChildrenOptions :: new ( ChildrenPropertiesMode :: Recompute ) ,
1106+ ) ?;
1107+ let children = probe
1108+ . children ( )
1109+ . into_iter ( )
1110+ . map ( |child| child. as_ref ( ) )
1111+ . collect :: < Vec < _ > > ( ) ;
1112+ if !sort_pushdown_inputs_satisfied ( probe. as_ref ( ) , & children) ?
1113+ || !probe
1114+ . equivalence_properties ( )
1115+ . ordering_satisfy_requirement ( requirement) ?
1116+ {
1117+ return Ok ( None ) ;
1118+ }
10881119 Ok ( Some ( result) )
10891120 } else {
10901121 Ok ( None )
10911122 }
10921123}
10931124
1125+ /// A sort probe must satisfy the node's input requirements as well as its output order.
1126+ fn sort_pushdown_inputs_satisfied (
1127+ plan : & dyn ExecutionPlan ,
1128+ children : & [ & dyn ExecutionPlan ] ,
1129+ ) -> Result < bool > {
1130+ let ordering = plan. required_input_ordering ( ) ;
1131+ let distribution = plan. input_distribution_requirements ( ) ;
1132+ if ordering. len ( ) != children. len ( )
1133+ || distribution. per_child_distributions ( ) . len ( ) != children. len ( )
1134+ {
1135+ return Ok ( false ) ;
1136+ }
1137+ for ( index, ( child, required) ) in children. iter ( ) . zip ( ordering) . enumerate ( ) {
1138+ if let Some ( required) = required
1139+ && !child
1140+ . equivalence_properties ( )
1141+ . ordering_satisfy_requirement ( required. first ( ) . clone ( ) ) ?
1142+ {
1143+ return Ok ( false ) ;
1144+ }
1145+ if !distribution
1146+ . child_satisfaction (
1147+ index,
1148+ * child,
1149+ ChildSatisfactionOptions :: new ( ) . with_allow_subset ( true ) ,
1150+ ) ?
1151+ . is_satisfied ( )
1152+ {
1153+ return Ok ( false ) ;
1154+ }
1155+ }
1156+ Ok ( distribution
1157+ . unsatisfied_co_partitioned_children ( plan. name ( ) , children) ?
1158+ . is_empty ( ) )
1159+ }
1160+
10941161// For hash join we only maintain the input order for the right child
10951162// for join type: Inner, Right, RightSemi, RightAnti, RightMark
10961163fn handle_hash_join (
@@ -1247,10 +1314,16 @@ mod tests {
12471314 use arrow:: compute:: SortOptions ;
12481315 use arrow:: datatypes:: { DataType , Field , Schema } ;
12491316 use datafusion_expr:: Operator ;
1317+ use datafusion_expr:: physical_planning_context:: {
1318+ ScalarSubqueryResults , SubqueryIndex ,
1319+ } ;
12501320 use datafusion_physical_expr:: PhysicalExpr ;
12511321 use datafusion_physical_expr:: expressions:: { BinaryExpr , col} ;
12521322 use datafusion_physical_plan:: empty:: EmptyExec ;
12531323 use datafusion_physical_plan:: limit:: GlobalLimitExec ;
1324+ use datafusion_physical_plan:: scalar_subquery:: {
1325+ ScalarSubqueryExec , ScalarSubqueryLink ,
1326+ } ;
12541327
12551328 const DESC : SortOptions = SortOptions {
12561329 descending : true ,
@@ -1366,6 +1439,29 @@ mod tests {
13661439 LexRequirement :: new ( reqs) . unwrap ( )
13671440 }
13681441
1442+ #[ test]
1443+ fn scalar_subquery_sort_applies_only_to_the_main_input ( ) -> Result < ( ) > {
1444+ let schema = child_schema ( ) ;
1445+ let input: Arc < dyn ExecutionPlan > = Arc :: new ( EmptyExec :: new ( Arc :: clone ( & schema) ) ) ;
1446+ let requirement = OrderingRequirements :: new ( lex ( [
1447+ req ( "c" , & schema, DESC ) ,
1448+ req ( "a" , & schema, ASC ) ,
1449+ ] ) ) ;
1450+ let plan: Arc < dyn ExecutionPlan > = Arc :: new ( ScalarSubqueryExec :: new (
1451+ Arc :: clone ( & input) ,
1452+ vec ! [ ScalarSubqueryLink {
1453+ plan: Arc :: clone( & input) ,
1454+ index: SubqueryIndex :: new( 0 ) ,
1455+ } ] ,
1456+ ScalarSubqueryResults :: new ( 1 ) ,
1457+ ) ) ;
1458+ assert_eq ! (
1459+ pushdown_requirement_to_children( & plan, requirement. clone( ) , None ) ?,
1460+ Some ( vec![ Some ( requirement) , None ] )
1461+ ) ;
1462+ Ok ( ( ) )
1463+ }
1464+
13691465 #[ test]
13701466 fn remap_single_hard_requirement_through_reordering_projection ( ) {
13711467 let projection = reordering_projection ( ) ;
0 commit comments