@@ -949,40 +949,56 @@ pub fn lexsort_to_indices(
949949 ) ) ;
950950 } ;
951951
952- let mut value_indices = ( 0 ..row_count) . collect :: < Vec < usize > > ( ) ;
953- let mut len = value_indices. len ( ) ;
952+ let len = limit. unwrap_or ( row_count) . min ( row_count) ;
954953
955- if let Some ( limit ) = limit {
956- len = limit . min ( len ) ;
954+ if len == 0 {
955+ return Ok ( UInt32Array :: from ( Vec :: < u32 > :: new ( ) ) ) ;
957956 }
958957
959- // Instantiate specialized versions of comparisons for small numbers
960- // of columns as it helps the compiler generate better code.
961- match columns. len ( ) {
962- 2 => {
963- sort_fixed_column :: < 2 > ( columns, & mut value_indices, len) ?;
964- }
965- 3 => {
966- sort_fixed_column :: < 3 > ( columns, & mut value_indices, len) ?;
967- }
968- 4 => {
969- sort_fixed_column :: < 4 > ( columns, & mut value_indices, len) ?;
970- }
971- 5 => {
972- sort_fixed_column :: < 5 > ( columns, & mut value_indices, len) ?;
973- }
958+ // The heap path avoids allocating and partially sorting all row indices
959+ // when the requested limit is a small fraction of the input. For larger
960+ // limits, the existing partial-sort path is preferred because heap
961+ // maintenance costs grow with the requested limit.
962+ let value_indices = match limit {
963+ Some ( limit) if limit <= row_count / 10 => match columns. len ( ) {
964+ 2 => lexsort_topk_fixed :: < 2 > ( columns, row_count, len) ?,
965+ 3 => lexsort_topk_fixed :: < 3 > ( columns, row_count, len) ?,
966+ 4 => lexsort_topk_fixed :: < 4 > ( columns, row_count, len) ?,
967+ 5 => lexsort_topk_fixed :: < 5 > ( columns, row_count, len) ?,
968+ _ => {
969+ let lexicographical_comparator = LexicographicalComparator :: try_new ( columns) ?;
970+ lexsort_topk ( row_count, len, |a, b| {
971+ lexicographical_comparator. compare ( a, b)
972+ } )
973+ }
974+ } ,
974975 _ => {
975- let lexicographical_comparator = LexicographicalComparator :: try_new ( columns) ?;
976- // uint32 can be sorted unstably
977- sort_unstable_by ( & mut value_indices, len, |a, b| {
978- lexicographical_comparator. compare ( * a, * b)
979- } ) ;
976+ let mut value_indices = ( 0 ..row_count) . collect :: < Vec < usize > > ( ) ;
977+
978+ // Instantiate specialized versions of comparisons for small numbers
979+ // of columns as it helps the compiler generate better code.
980+ match columns. len ( ) {
981+ 2 => sort_fixed_column :: < 2 > ( columns, & mut value_indices, len) ?,
982+ 3 => sort_fixed_column :: < 3 > ( columns, & mut value_indices, len) ?,
983+ 4 => sort_fixed_column :: < 4 > ( columns, & mut value_indices, len) ?,
984+ 5 => sort_fixed_column :: < 5 > ( columns, & mut value_indices, len) ?,
985+ _ => {
986+ let lexicographical_comparator = LexicographicalComparator :: try_new ( columns) ?;
987+ sort_unstable_by ( & mut value_indices, len, |a, b| {
988+ lexicographical_comparator. compare ( * a, * b)
989+ } ) ;
990+ }
991+ }
992+
993+ value_indices. truncate ( len) ;
994+ value_indices
980995 }
981- }
996+ } ;
997+
982998 Ok ( UInt32Array :: from (
983- value_indices[ ..len ]
984- . iter ( )
985- . map ( |i| * i as u32 )
999+ value_indices
1000+ . into_iter ( )
1001+ . map ( |i| i as u32 )
9861002 . collect :: < Vec < _ > > ( ) ,
9871003 ) )
9881004}
@@ -1000,6 +1016,90 @@ fn sort_fixed_column<const N: usize>(
10001016 Ok ( ( ) )
10011017}
10021018
1019+ // Uses the fixed-column comparator for the bounded heap path.
1020+ fn lexsort_topk_fixed < const N : usize > (
1021+ columns : & [ SortColumn ] ,
1022+ row_count : usize ,
1023+ limit : usize ,
1024+ ) -> Result < Vec < usize > , ArrowError > {
1025+ let lexicographical_comparator = FixedLexicographicalComparator :: < N > :: try_new ( columns) ?;
1026+ Ok ( lexsort_topk ( row_count, limit, |a, b| {
1027+ lexicographical_comparator. compare ( a, b)
1028+ } ) )
1029+ }
1030+
1031+ // Keeps the smallest `limit` indices in a bounded max-heap.
1032+ // The root is the largest retained index according to `compare`.
1033+ fn lexsort_topk (
1034+ row_count : usize ,
1035+ limit : usize ,
1036+ mut compare : impl FnMut ( usize , usize ) -> Ordering ,
1037+ ) -> Vec < usize > {
1038+ let mut heap = Vec :: with_capacity ( limit) ;
1039+
1040+ for idx in 0 ..row_count {
1041+ if heap. len ( ) < limit {
1042+ heap. push ( idx) ;
1043+ let pos = heap. len ( ) - 1 ;
1044+ sift_up_worst_heap ( & mut heap, pos, & mut compare) ;
1045+ } else if compare ( idx, heap[ 0 ] ) == Ordering :: Less {
1046+ heap[ 0 ] = idx;
1047+ sift_down_worst_heap ( & mut heap, 0 , & mut compare) ;
1048+ }
1049+ }
1050+
1051+ heap. sort_unstable_by ( |a, b| compare ( * a, * b) ) ;
1052+ heap
1053+ }
1054+
1055+ // Moves a newly inserted index toward the root while it is larger than its parent.
1056+ fn sift_up_worst_heap (
1057+ heap : & mut [ usize ] ,
1058+ mut pos : usize ,
1059+ compare : & mut impl FnMut ( usize , usize ) -> Ordering ,
1060+ ) {
1061+ while pos > 0 {
1062+ let parent = ( pos - 1 ) / 2 ;
1063+
1064+ if compare ( heap[ parent] , heap[ pos] ) != Ordering :: Less {
1065+ break ;
1066+ }
1067+
1068+ heap. swap ( parent, pos) ;
1069+ pos = parent;
1070+ }
1071+ }
1072+
1073+ // Moves the root down until both children are no larger than it.
1074+ // The larger child is selected at each step so the worst retained row remains
1075+ // at heap[0].
1076+ fn sift_down_worst_heap (
1077+ heap : & mut [ usize ] ,
1078+ mut pos : usize ,
1079+ compare : & mut impl FnMut ( usize , usize ) -> Ordering ,
1080+ ) {
1081+ loop {
1082+ let left = pos * 2 + 1 ;
1083+ if left >= heap. len ( ) {
1084+ break ;
1085+ }
1086+
1087+ let right = left + 1 ;
1088+ let mut worst = left;
1089+
1090+ if right < heap. len ( ) && compare ( heap[ left] , heap[ right] ) == Ordering :: Less {
1091+ worst = right;
1092+ }
1093+
1094+ if compare ( heap[ pos] , heap[ worst] ) != Ordering :: Less {
1095+ break ;
1096+ }
1097+
1098+ heap. swap ( pos, worst) ;
1099+ pos = worst;
1100+ }
1101+ }
1102+
10031103/// It's unstable_sort, may not preserve the order of equal elements
10041104pub fn partial_sort < T , F > ( v : & mut [ T ] , limit : usize , mut is_less : F )
10051105where
@@ -4483,6 +4583,30 @@ mod tests {
44834583 run_test ! ( LargeListArray ) ;
44844584 }
44854585
4586+ #[ test]
4587+ fn test_lex_sort_limit_paths ( ) {
4588+ let input = vec ! [
4589+ SortColumn {
4590+ values: Arc :: new( Int32Array :: from_iter_values( ( 0 ..100 ) . rev( ) ) ) as ArrayRef ,
4591+ options: None ,
4592+ } ,
4593+ SortColumn {
4594+ values: Arc :: new( Int32Array :: from_iter_values( 0 ..100 ) ) as ArrayRef ,
4595+ options: None ,
4596+ } ,
4597+ ] ;
4598+
4599+ // Exercise the bounded heap path.
4600+ let indices = lexsort_to_indices ( & input, Some ( 10 ) ) . unwrap ( ) ;
4601+ let expected = UInt32Array :: from_iter_values ( ( 90 ..100 ) . rev ( ) ) ;
4602+ assert_eq ! ( indices, expected) ;
4603+
4604+ // Exercise the existing partial-sort path.
4605+ let indices = lexsort_to_indices ( & input, Some ( 11 ) ) . unwrap ( ) ;
4606+ let expected = UInt32Array :: from_iter_values ( ( 89 ..100 ) . rev ( ) ) ;
4607+ assert_eq ! ( indices, expected) ;
4608+ }
4609+
44864610 #[ test]
44874611 fn test_partial_sort ( ) {
44884612 let mut before: Vec < & str > = vec ! [
@@ -4892,6 +5016,7 @@ mod tests {
48925016 }
48935017
48945018 #[ test]
5019+ #[ cfg_attr( miri, ignore) ] // Takes too long
48955020 fn fuzz_partition_validity ( ) {
48965021 let mut rng = StdRng :: seed_from_u64 ( 0xF00D_CAFE ) ;
48975022 for _ in 0 ..1_000 {
@@ -5100,6 +5225,7 @@ mod tests {
51005225
51015226 // Fuzz testing: generate random UTF-8 strings and verify sort correctness
51025227 #[ test]
5228+ #[ cfg_attr( miri, ignore) ] // Takes too long
51035229 fn test_fuzz_random_strings ( ) {
51045230 let mut rng = StdRng :: seed_from_u64 ( 42 ) ; // Fixed seed for reproducibility
51055231
0 commit comments