@@ -21,10 +21,10 @@ use crate::physical_optimizer::test_utils::{
2121 aggregate_exec, bounded_window_exec, check_integrity, coalesce_batches_exec,
2222 coalesce_partitions_exec, create_test_schema, create_test_schema2,
2323 create_test_schema3, filter_exec, global_limit_exec, hash_join_exec, limit_exec,
24- local_limit_exec, memory_exec, parquet_exec, repartition_exec, sort_exec, sort_expr ,
25- sort_expr_options , sort_merge_join_exec , sort_preserving_merge_exec ,
26- sort_preserving_merge_exec_with_fetch , spr_repartition_exec , stream_exec_ordered ,
27- union_exec, RequirementsTestExec ,
24+ local_limit_exec, memory_exec, parquet_exec, repartition_exec, sort_exec,
25+ sort_exec_with_fetch , sort_expr , sort_expr_options , sort_merge_join_exec ,
26+ sort_preserving_merge_exec , sort_preserving_merge_exec_with_fetch ,
27+ spr_repartition_exec , stream_exec_ordered , union_exec, RequirementsTestExec ,
2828} ;
2929
3030use arrow:: compute:: SortOptions ;
@@ -3346,3 +3346,89 @@ async fn test_window_partial_constant_and_set_monotonicity() -> Result<()> {
33463346
33473347 Ok ( ( ) )
33483348}
3349+
3350+ #[ test]
3351+ fn test_removes_unused_orthogonal_sort ( ) -> Result < ( ) > {
3352+ let schema = create_test_schema3 ( ) ?;
3353+ let input_sort_exprs = vec ! [ sort_expr( "b" , & schema) , sort_expr( "c" , & schema) ] ;
3354+ let unbounded_input = stream_exec_ordered ( & schema, input_sort_exprs. clone ( ) ) ;
3355+
3356+ let orthogonal_sort = sort_exec ( vec ! [ sort_expr( "a" , & schema) ] , unbounded_input) ;
3357+ let output_sort = sort_exec ( input_sort_exprs, orthogonal_sort) ; // same sort as data source
3358+
3359+ // Test scenario/input has an orthogonal sort:
3360+ let expected_input = [
3361+ "SortExec: expr=[b@1 ASC, c@2 ASC], preserve_partitioning=[false]" ,
3362+ " SortExec: expr=[a@0 ASC], preserve_partitioning=[false]" ,
3363+ " StreamingTableExec: partition_sizes=1, projection=[a, b, c, d, e], infinite_source=true, output_ordering=[b@1 ASC, c@2 ASC]"
3364+ ] ;
3365+ assert_eq ! ( get_plan_string( & output_sort) , expected_input, ) ;
3366+
3367+ // Test: should remove orthogonal sort, and the uppermost (unneeded) sort:
3368+ let expected_optimized = [
3369+ "StreamingTableExec: partition_sizes=1, projection=[a, b, c, d, e], infinite_source=true, output_ordering=[b@1 ASC, c@2 ASC]"
3370+ ] ;
3371+ assert_optimized ! ( expected_input, expected_optimized, output_sort, true ) ;
3372+
3373+ Ok ( ( ) )
3374+ }
3375+
3376+ #[ test]
3377+ fn test_keeps_used_orthogonal_sort ( ) -> Result < ( ) > {
3378+ let schema = create_test_schema3 ( ) ?;
3379+ let input_sort_exprs = vec ! [ sort_expr( "b" , & schema) , sort_expr( "c" , & schema) ] ;
3380+ let unbounded_input = stream_exec_ordered ( & schema, input_sort_exprs. clone ( ) ) ;
3381+
3382+ let orthogonal_sort =
3383+ sort_exec_with_fetch ( vec ! [ sort_expr( "a" , & schema) ] , Some ( 3 ) , unbounded_input) ; // has fetch, so this orthogonal sort changes the output
3384+ let output_sort = sort_exec ( input_sort_exprs, orthogonal_sort) ;
3385+
3386+ // Test scenario/input has an orthogonal sort:
3387+ let expected_input = [
3388+ "SortExec: expr=[b@1 ASC, c@2 ASC], preserve_partitioning=[false]" ,
3389+ " SortExec: TopK(fetch=3), expr=[a@0 ASC], preserve_partitioning=[false]" ,
3390+ " StreamingTableExec: partition_sizes=1, projection=[a, b, c, d, e], infinite_source=true, output_ordering=[b@1 ASC, c@2 ASC]"
3391+ ] ;
3392+ assert_eq ! ( get_plan_string( & output_sort) , expected_input, ) ;
3393+
3394+ // Test: should keep the orthogonal sort, since it modifies the output:
3395+ let expected_optimized = expected_input;
3396+ assert_optimized ! ( expected_input, expected_optimized, output_sort, true ) ;
3397+
3398+ Ok ( ( ) )
3399+ }
3400+
3401+ #[ test]
3402+ fn test_handles_multiple_orthogonal_sorts ( ) -> Result < ( ) > {
3403+ let schema = create_test_schema3 ( ) ?;
3404+ let input_sort_exprs = vec ! [ sort_expr( "b" , & schema) , sort_expr( "c" , & schema) ] ;
3405+ let unbounded_input = stream_exec_ordered ( & schema, input_sort_exprs. clone ( ) ) ;
3406+
3407+ let orthogonal_sort_0 = sort_exec ( vec ! [ sort_expr( "c" , & schema) ] , unbounded_input) ; // has no fetch, so can be removed
3408+ let orthogonal_sort_1 =
3409+ sort_exec_with_fetch ( vec ! [ sort_expr( "a" , & schema) ] , Some ( 3 ) , orthogonal_sort_0) ; // has fetch, so this orthogonal sort changes the output
3410+ let orthogonal_sort_2 = sort_exec ( vec ! [ sort_expr( "c" , & schema) ] , orthogonal_sort_1) ; // has no fetch, so can be removed
3411+ let orthogonal_sort_3 = sort_exec ( vec ! [ sort_expr( "a" , & schema) ] , orthogonal_sort_2) ; // has no fetch, so can be removed
3412+ let output_sort = sort_exec ( input_sort_exprs, orthogonal_sort_3) ; // final sort
3413+
3414+ // Test scenario/input has an orthogonal sort:
3415+ let expected_input = [
3416+ "SortExec: expr=[b@1 ASC, c@2 ASC], preserve_partitioning=[false]" ,
3417+ " SortExec: expr=[a@0 ASC], preserve_partitioning=[false]" ,
3418+ " SortExec: expr=[c@2 ASC], preserve_partitioning=[false]" ,
3419+ " SortExec: TopK(fetch=3), expr=[a@0 ASC], preserve_partitioning=[false]" ,
3420+ " SortExec: expr=[c@2 ASC], preserve_partitioning=[false]" ,
3421+ " StreamingTableExec: partition_sizes=1, projection=[a, b, c, d, e], infinite_source=true, output_ordering=[b@1 ASC, c@2 ASC]" ,
3422+ ] ;
3423+ assert_eq ! ( get_plan_string( & output_sort) , expected_input, ) ;
3424+
3425+ // Test: should keep only the needed orthogonal sort, and remove the unneeded ones:
3426+ let expected_optimized = [
3427+ "SortExec: expr=[b@1 ASC, c@2 ASC], preserve_partitioning=[false]" ,
3428+ " SortExec: TopK(fetch=3), expr=[a@0 ASC], preserve_partitioning=[false]" ,
3429+ " StreamingTableExec: partition_sizes=1, projection=[a, b, c, d, e], infinite_source=true, output_ordering=[b@1 ASC, c@2 ASC]" ,
3430+ ] ;
3431+ assert_optimized ! ( expected_input, expected_optimized, output_sort, true ) ;
3432+
3433+ Ok ( ( ) )
3434+ }
0 commit comments