Skip to content

Commit b74ad84

Browse files
committed
perf(arrow-ord): Avoid full index materialization for small-limit lexsorts
1 parent fd1c5b3 commit b74ad84

1 file changed

Lines changed: 154 additions & 28 deletions

File tree

‎arrow-ord/src/sort.rs‎

Lines changed: 154 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -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
10041104
pub fn partial_sort<T, F>(v: &mut [T], limit: usize, mut is_less: F)
10051105
where
@@ -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

Comments
 (0)