@@ -26,7 +26,7 @@ use crate::physical_optimizer::test_utils::{
2626 sort_merge_join_exec, sort_preserving_merge_exec, union_exec,
2727} ;
2828
29- use arrow:: array:: { RecordBatch , UInt8Array , UInt64Array } ;
29+ use arrow:: array:: { Int64Array , RecordBatch , UInt8Array , UInt64Array } ;
3030use arrow:: compute:: SortOptions ;
3131use arrow_schema:: { DataType , Field , Schema , SchemaRef } ;
3232use datafusion:: config:: ConfigOptions ;
@@ -47,6 +47,7 @@ use datafusion_common::tree_node::{
4747} ;
4848use datafusion_datasource:: file_groups:: FileGroup ;
4949use datafusion_datasource:: file_scan_config:: FileScanConfigBuilder ;
50+ use datafusion_datasource:: memory:: MemorySourceConfig ;
5051use datafusion_expr:: { JoinType , Operator } ;
5152use datafusion_functions_aggregate:: count:: count_udaf;
5253use datafusion_physical_expr:: aggregate:: AggregateExprBuilder ;
@@ -76,11 +77,12 @@ use datafusion_physical_plan::joins::utils::JoinOn;
7677use datafusion_physical_plan:: limit:: { GlobalLimitExec , LocalLimitExec } ;
7778use datafusion_physical_plan:: projection:: { ProjectionExec , ProjectionExpr } ;
7879use datafusion_physical_plan:: repartition:: RepartitionExec ;
80+ use datafusion_physical_plan:: sorts:: sort:: SortExec ;
7981use datafusion_physical_plan:: sorts:: sort_preserving_merge:: SortPreservingMergeExec ;
8082use datafusion_physical_plan:: union:: { InterleaveExec , UnionExec } ;
8183use datafusion_physical_plan:: {
8284 ChildrenPropertiesMode , DisplayAs , DisplayFormatType , ExecutionPlanProperties ,
83- PlanProperties , ReplaceChildrenOptions , displayable,
85+ PlanProperties , ReplaceChildrenOptions , collect , displayable,
8486} ;
8587use insta:: Settings ;
8688
@@ -4844,11 +4846,12 @@ fn test_replace_order_preserving_variants_with_fetch() -> Result<()> {
48444846 // Apply the function
48454847 let result = replace_order_preserving_variants ( dist_context) ?;
48464848
4847- // Verify the plan was transformed to CoalescePartitionsExec
4849+ // A fetched ordered merge must still select the TopK rows.
4850+ let result = check_integrity ( result) ?;
48484851 result
48494852 . plan
4850- . downcast_ref :: < CoalescePartitionsExec > ( )
4851- . expect ( "Expected CoalescePartitionsExec " ) ;
4853+ . downcast_ref :: < SortExec > ( )
4854+ . expect ( "Expected a TopK SortExec " ) ;
48524855
48534856 // Verify fetch was preserved
48544857 assert_eq ! (
@@ -4860,6 +4863,318 @@ fn test_replace_order_preserving_variants_with_fetch() -> Result<()> {
48604863 Ok ( ( ) )
48614864}
48624865
4866+ #[ test]
4867+ fn preserve_fetch_when_reoptimizing_ordered_merge ( ) -> Result < ( ) > {
4868+ let schema = schema ( ) ;
4869+ let sort_key: LexOrdering =
4870+ [ PhysicalSortExpr :: new_default ( col ( "c" , & schema) ?) ] . into ( ) ;
4871+ let input = parquet_exec_multiple_sorted ( vec ! [ sort_key. clone( ) ] ) ;
4872+ let plan: Arc < dyn ExecutionPlan > =
4873+ Arc :: new ( SortPreservingMergeExec :: new ( sort_key, input) . with_fetch ( Some ( 5 ) ) ) ;
4874+
4875+ let optimized =
4876+ EnsureRequirements :: new ( ) . optimize ( plan, & test_suite_default_config_options ( ) ) ?;
4877+ let plan = displayable ( optimized. as_ref ( ) ) . indent ( true ) . to_string ( ) ;
4878+
4879+ assert ! (
4880+ plan. contains( "SortPreservingMergeExec: [c@2 ASC], fetch=5" ) ,
4881+ "expected the optimizer to preserve fetch:\n {plan}"
4882+ ) ;
4883+
4884+ Ok ( ( ) )
4885+ }
4886+
4887+ #[ test]
4888+ fn preserve_fetch_when_reoptimizing_coalesce_partitions ( ) -> Result < ( ) > {
4889+ let input = parquet_exec_multiple ( ) ;
4890+ let plan: Arc < dyn ExecutionPlan > =
4891+ Arc :: new ( CoalescePartitionsExec :: new ( input) . with_fetch ( Some ( 5 ) ) ) ;
4892+
4893+ let optimized =
4894+ EnsureRequirements :: new ( ) . optimize ( plan, & test_suite_default_config_options ( ) ) ?;
4895+
4896+ assert_eq ! ( optimized. fetch( ) , Some ( 5 ) ) ;
4897+ optimized
4898+ . downcast_ref :: < CoalescePartitionsExec > ( )
4899+ . expect ( "expected CoalescePartitionsExec" ) ;
4900+
4901+ Ok ( ( ) )
4902+ }
4903+
4904+ #[ tokio:: test]
4905+ async fn move_fetch_to_replacement_sort ( ) -> Result < ( ) > {
4906+ for ( options, partitions, expected) in [
4907+ (
4908+ SortOptions :: default ( ) ,
4909+ [
4910+ vec ! [ None , Some ( 1 ) , Some ( 1 ) , Some ( 6 ) ] ,
4911+ vec ! [ None , Some ( 1 ) , Some ( 2 ) , Some ( 7 ) ] ,
4912+ ] ,
4913+ vec ! [ None , None , Some ( 1 ) , Some ( 1 ) , Some ( 1 ) ] ,
4914+ ) ,
4915+ (
4916+ SortOptions {
4917+ descending : true ,
4918+ nulls_first : false ,
4919+ } ,
4920+ [ vec ! [ Some ( 7 ) , Some ( 1 ) , None ] , vec ! [ Some ( 6 ) , Some ( 1 ) , None ] ] ,
4921+ vec ! [ Some ( 7 ) , Some ( 6 ) , Some ( 1 ) , Some ( 1 ) , None ] ,
4922+ ) ,
4923+ ] {
4924+ let ( input, sort_key) = sorted_memory_input ( partitions, options) ?;
4925+ let merge: Arc < dyn ExecutionPlan > = Arc :: new (
4926+ SortPreservingMergeExec :: new ( sort_key. clone ( ) , input) . with_fetch ( Some ( 5 ) ) ,
4927+ ) ;
4928+ assert_eq ! ( fetch_test_values( Arc :: clone( & merge) ) . await ?, expected) ;
4929+ let plan = sort_required_exec_with_req ( merge, sort_key) ;
4930+ let optimized = ensure_distribution_helper ( plan, 10 , false ) ?;
4931+ let replacement = Arc :: clone ( optimized. children ( ) [ 0 ] ) ;
4932+ let sort = replacement
4933+ . downcast_ref :: < SortExec > ( )
4934+ . expect ( "expected a replacement sort" ) ;
4935+ assert_eq ! ( sort. fetch( ) , Some ( 5 ) ) ;
4936+ assert_eq ! ( fetch_test_values( replacement) . await ?, expected) ;
4937+ }
4938+ Ok ( ( ) )
4939+ }
4940+
4941+ #[ tokio:: test]
4942+ async fn preserve_fetch_in_nested_distribution_operators ( ) -> Result < ( ) > {
4943+ for outer_fetch in [ 0 , 3 , 10 ] {
4944+ let ( input, sort_key) = sorted_memory_input (
4945+ [ 0 , 1 ] . map ( |start| ( start..10 ) . step_by ( 2 ) . map ( Some ) . collect ( ) ) ,
4946+ SortOptions :: default ( ) ,
4947+ ) ?;
4948+ let merge: Arc < dyn ExecutionPlan > =
4949+ Arc :: new ( SortPreservingMergeExec :: new ( sort_key, input) . with_fetch ( Some ( 5 ) ) ) ;
4950+ let plan: Arc < dyn ExecutionPlan > =
4951+ Arc :: new ( CoalescePartitionsExec :: new ( merge) . with_fetch ( Some ( outer_fetch) ) ) ;
4952+ let expected = ( 0 ..outer_fetch. min ( 5 ) )
4953+ . map ( |value| Some ( value as i64 ) )
4954+ . collect :: < Vec < _ > > ( ) ;
4955+ assert_reoptimized_fetch_values ( plan, & expected) . await ?;
4956+ }
4957+ Ok ( ( ) )
4958+ }
4959+
4960+ #[ tokio:: test]
4961+ async fn preserve_topk_when_parent_changes_ordering ( ) -> Result < ( ) > {
4962+ let ( input, sort_key) = sorted_memory_input (
4963+ [ 0 , 1 ] . map ( |start| ( start..10 ) . step_by ( 2 ) . map ( Some ) . collect ( ) ) ,
4964+ SortOptions :: default ( ) ,
4965+ ) ?;
4966+ let descending = [ PhysicalSortExpr :: new (
4967+ col ( "c" , & input. schema ( ) ) ?,
4968+ SortOptions {
4969+ descending : true ,
4970+ nulls_first : false ,
4971+ } ,
4972+ ) ]
4973+ . into ( ) ;
4974+ let merge: Arc < dyn ExecutionPlan > =
4975+ Arc :: new ( SortPreservingMergeExec :: new ( sort_key, input) . with_fetch ( Some ( 5 ) ) ) ;
4976+ let plan: Arc < dyn ExecutionPlan > = Arc :: new ( SortExec :: new ( descending, merge) ) ;
4977+ assert_reoptimized_fetch_values ( plan, & [ Some ( 4 ) , Some ( 3 ) , Some ( 2 ) , Some ( 1 ) , Some ( 0 ) ] )
4978+ . await
4979+ }
4980+
4981+ #[ tokio:: test]
4982+ async fn preserve_fetch_when_parallelizing_sort_above_filter ( ) -> Result < ( ) > {
4983+ let ( input, sort_key) = sorted_memory_input (
4984+ [
4985+ vec ! [ Some ( -4 ) , Some ( -2 ) , Some ( 2 ) , Some ( 4 ) , Some ( 6 ) ] ,
4986+ vec ! [ Some ( -3 ) , Some ( -1 ) , Some ( 3 ) , Some ( 5 ) , Some ( 7 ) ] ,
4987+ ] ,
4988+ SortOptions :: default ( ) ,
4989+ ) ?;
4990+ let predicate = Arc :: new ( BinaryExpr :: new (
4991+ col ( "c" , & input. schema ( ) ) ?,
4992+ Operator :: Gt ,
4993+ lit ( 0_i64 ) ,
4994+ ) ) ;
4995+ let coalesce: Arc < dyn ExecutionPlan > =
4996+ Arc :: new ( CoalescePartitionsExec :: new ( input) . with_fetch ( Some ( 5 ) ) ) ;
4997+ let filter: Arc < dyn ExecutionPlan > =
4998+ Arc :: new ( FilterExec :: try_new ( predicate, coalesce) ?) ;
4999+ let mut plan: Arc < dyn ExecutionPlan > = Arc :: new ( SortExec :: new ( sort_key, filter) ) ;
5000+ let mut config = test_suite_default_config_options ( ) ;
5001+ config. optimizer . enable_round_robin_repartition = false ;
5002+ config. optimizer . repartition_sorts = true ;
5003+ for iteration in 0 ..3 {
5004+ if iteration > 0 {
5005+ plan = EnsureRequirements :: new ( ) . optimize ( plan, & config) ?;
5006+ }
5007+ // Either input batch can arrive first. Both contain three positive
5008+ // rows, so keeping the limit below the filter always returns three.
5009+ assert_eq ! (
5010+ fetch_test_values( Arc :: clone( & plan) ) . await ?. len( ) ,
5011+ 3 ,
5012+ "iteration {iteration}:\n {}" ,
5013+ displayable( plan. as_ref( ) ) . indent( true )
5014+ ) ;
5015+ }
5016+ Ok ( ( ) )
5017+ }
5018+
5019+ fn sorted_memory_input (
5020+ partitions : [ Vec < Option < i64 > > ; 2 ] ,
5021+ options : SortOptions ,
5022+ ) -> Result < ( Arc < dyn ExecutionPlan > , LexOrdering ) > {
5023+ let schema = Arc :: new ( Schema :: new ( vec ! [ Field :: new( "c" , DataType :: Int64 , true ) ] ) ) ;
5024+ let order: LexOrdering = [ PhysicalSortExpr :: new ( col ( "c" , & schema) ?, options) ] . into ( ) ;
5025+ let partitions = partitions
5026+ . into_iter ( )
5027+ . map ( |values| {
5028+ RecordBatch :: try_new (
5029+ Arc :: clone ( & schema) ,
5030+ vec ! [ Arc :: new( Int64Array :: from( values) ) ] ,
5031+ )
5032+ . map ( |batch| vec ! [ batch] )
5033+ } )
5034+ . collect :: < std:: result:: Result < Vec < _ > , _ > > ( ) ?;
5035+ let source = MemorySourceConfig :: try_new ( & partitions, schema, None ) ?
5036+ . try_with_sort_information ( vec ! [ order. clone( ) ] ) ?;
5037+ Ok ( ( DataSourceExec :: from_data_source ( source) , order) )
5038+ }
5039+
5040+ async fn fetch_test_values ( plan : Arc < dyn ExecutionPlan > ) -> Result < Vec < Option < i64 > > > {
5041+ let batches = collect ( plan, SessionContext :: new ( ) . task_ctx ( ) ) . await ?;
5042+ Ok ( batches
5043+ . iter ( )
5044+ . flat_map ( |batch| {
5045+ batch
5046+ . column ( 0 )
5047+ . as_any ( )
5048+ . downcast_ref :: < Int64Array > ( )
5049+ . unwrap ( )
5050+ . iter ( )
5051+ } )
5052+ . collect ( ) )
5053+ }
5054+
5055+ async fn assert_reoptimized_fetch_values (
5056+ plan : Arc < dyn ExecutionPlan > ,
5057+ expected : & [ Option < i64 > ] ,
5058+ ) -> Result < ( ) > {
5059+ for repartition_sorts in [ false , true ] {
5060+ let mut optimized = Arc :: clone ( & plan) ;
5061+ let mut config = test_suite_default_config_options ( ) ;
5062+ config. optimizer . enable_round_robin_repartition = false ;
5063+ config. optimizer . repartition_sorts = repartition_sorts;
5064+ for iteration in 0 ..3 {
5065+ if iteration > 0 {
5066+ let distribution =
5067+ DistributionContext :: new_default ( Arc :: clone ( & optimized) )
5068+ . transform_up ( |context| ensure_distribution ( context, & config) ) ?
5069+ . data ;
5070+ check_integrity ( distribution) ?;
5071+ optimized = EnsureRequirements :: new ( ) . optimize ( optimized, & config) ?;
5072+ }
5073+ assert_eq ! (
5074+ fetch_test_values( Arc :: clone( & optimized) ) . await ?,
5075+ expected,
5076+ "iteration {iteration}, repartition_sorts={repartition_sorts}:\n {}" ,
5077+ displayable( optimized. as_ref( ) ) . indent( true )
5078+ ) ;
5079+ }
5080+ }
5081+ Ok ( ( ) )
5082+ }
5083+
5084+ #[ tokio:: test]
5085+ async fn preserve_fetch_below_filter_when_reoptimizing ( ) -> Result < ( ) > {
5086+ check_fetch_below_filter (
5087+ Operator :: Gt ,
5088+ [ vec ! [ -2 , 0 , 2 , 4 ] , vec ! [ -1 , 1 , 3 , 5 ] ] ,
5089+ & [ 1 , 2 ] ,
5090+ )
5091+ . await
5092+ }
5093+
5094+ #[ tokio:: test]
5095+ async fn preserve_fetch_below_filter_with_constant_ordering ( ) -> Result < ( ) > {
5096+ check_fetch_below_filter (
5097+ Operator :: Eq ,
5098+ [ vec ! [ -2 , 0 , 0 , 0 ] , vec ! [ -1 , 0 , 0 , 0 ] ] ,
5099+ & [ 0 , 0 , 0 ] ,
5100+ )
5101+ . await
5102+ }
5103+
5104+ async fn check_fetch_below_filter (
5105+ op : Operator ,
5106+ partitions : [ Vec < i64 > ; 2 ] ,
5107+ expected : & [ i64 ] ,
5108+ ) -> Result < ( ) > {
5109+ let schema = Arc :: new ( Schema :: new ( vec ! [ Field :: new( "c" , DataType :: Int64 , false ) ] ) ) ;
5110+ let sort_key: LexOrdering =
5111+ [ PhysicalSortExpr :: new_default ( col ( "c" , & schema) ?) ] . into ( ) ;
5112+ let partitions = partitions
5113+ . into_iter ( )
5114+ . map ( |values| {
5115+ RecordBatch :: try_new (
5116+ Arc :: clone ( & schema) ,
5117+ vec ! [ Arc :: new( Int64Array :: from( values) ) ] ,
5118+ )
5119+ . map ( |batch| vec ! [ batch] )
5120+ } )
5121+ . collect :: < std:: result:: Result < Vec < _ > , _ > > ( ) ?;
5122+ let source = MemorySourceConfig :: try_new ( & partitions, Arc :: clone ( & schema) , None ) ?
5123+ . try_with_sort_information ( vec ! [ sort_key. clone( ) ] ) ?;
5124+ let merge: Arc < dyn ExecutionPlan > = Arc :: new (
5125+ SortPreservingMergeExec :: new (
5126+ sort_key. clone ( ) ,
5127+ DataSourceExec :: from_data_source ( source) ,
5128+ )
5129+ . with_fetch ( Some ( 5 ) ) ,
5130+ ) ;
5131+ let predicate = Arc :: new ( BinaryExpr :: new ( col ( "c" , & schema) ?, op, lit ( 0_i64 ) ) ) ;
5132+ let filter: Arc < dyn ExecutionPlan > = Arc :: new ( FilterExec :: try_new ( predicate, merge) ?) ;
5133+ let mut plan = sort_required_exec_with_req ( filter, sort_key) ;
5134+ let mut config = test_suite_default_config_options ( ) ;
5135+ config. optimizer . enable_round_robin_repartition = false ;
5136+ let task_context = SessionContext :: new ( ) . task_ctx ( ) ;
5137+
5138+ // The test operator only declares ordering requirements. Execute its child
5139+ // to compare query results before optimization and after repeated passes.
5140+ for iteration in 0 ..3 {
5141+ if iteration > 0 {
5142+ let distribution = DistributionContext :: new_default ( Arc :: clone ( & plan) )
5143+ . transform_up ( |context| ensure_distribution ( context, & config) ) ?
5144+ . data ;
5145+ check_integrity ( distribution) ?;
5146+ plan = EnsureRequirements :: new ( ) . optimize ( plan, & config) ?;
5147+ }
5148+ let input = Arc :: clone ( plan. children ( ) [ 0 ] ) ;
5149+ let batches = collect ( input, Arc :: clone ( & task_context) ) . await ?;
5150+ let values = batches
5151+ . iter ( )
5152+ . flat_map ( |batch| {
5153+ batch
5154+ . column ( 0 )
5155+ . as_any ( )
5156+ . downcast_ref :: < Int64Array > ( )
5157+ . unwrap ( )
5158+ . values ( )
5159+ . iter ( )
5160+ . copied ( )
5161+ } )
5162+ . collect :: < Vec < _ > > ( ) ;
5163+ assert_eq ! (
5164+ values,
5165+ expected,
5166+ "iteration {iteration}:\n {}" ,
5167+ displayable( plan. as_ref( ) ) . indent( true )
5168+ ) ;
5169+ assert ! (
5170+ plan. children( ) [ 0 ] . is:: <FilterExec >( ) ,
5171+ "fetch must stay below the filter:\n {}" ,
5172+ displayable( plan. as_ref( ) ) . indent( true )
5173+ ) ;
5174+ }
5175+ Ok ( ( ) )
5176+ }
5177+
48635178/// When a parent requires SinglePartition and maintains input order, order-preserving
48645179/// variants (e.g. SortPreservingMergeExec) should be kept so that ordering can
48655180/// propagate to ancestors. Replacing them with CoalescePartitionsExec would destroy
0 commit comments