You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@arrow.apache.org by gi...@apache.org on 2026/10/19 23:43:08 UTC
(arrow-rs) branch main updated: perf(arrow-cmp): add fast paths to dictionary_cmp (#11407)
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/arrow-rs.git
The following commit(s) were added to refs/heads/main by this push:
new 5c70030eaa perf(arrow-cmp): add fast paths to dictionary_cmp (#11407)
5c70030eaa is described below
commit 5c70030eaab45ea8427861ffcbe2dc95d2e118c8
Author: RIchard Baah <13...@users.noreply.github.com>
AuthorDate: Mon Oct 19 19:40:51 2026 +0000
perf(arrow-cmp): add fast paths to dictionary_cmp (#11407)
# Which issue does this PR close?
Closes #11413.
# Rationale
Dictionary comparisons go through a generic value comparator for every
row. For byte-backed dictionaries, resolving the keys and comparing the
values directly avoids that overhead.
# What changed?
Adds fast paths for matching `Utf8`, `LargeUtf8`, `Binary`,
`LargeBinary`, and `FixedSizeBinary` dictionary values. Other value
types continue to use the generic path.
The current `dict_cmp` benchmarks are around 14–19% faster.
# Testing
Added tests for comparison results, null ordering, fixed-size binary
values, and out-of-bounds indices.
---
arrow-cmp/src/lib.rs | 322 +++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 322 insertions(+)
diff --git a/arrow-cmp/src/lib.rs b/arrow-cmp/src/lib.rs
index 2bbb8854b1..8d13a22efc 100644
--- a/arrow-cmp/src/lib.rs
+++ b/arrow-cmp/src/lib.rs
@@ -220,6 +220,25 @@ fn compare_dict<K: ArrowDictionaryKeyType>(
) -> Result<DynComparator, ArrowError> {
let left = left.as_dictionary::<K>();
let right = right.as_dictionary::<K>();
+ let value_dtype = left.values().data_type();
+ if value_dtype == right.values().data_type() {
+ match value_dtype {
+ DataType::Utf8 => return Ok(compare_dict_bytes::<K, Utf8Type>(left, right, opts)),
+ DataType::LargeUtf8 => {
+ return Ok(compare_dict_bytes::<K, LargeUtf8Type>(left, right, opts));
+ }
+ DataType::Binary => {
+ return Ok(compare_dict_bytes::<K, BinaryType>(left, right, opts));
+ }
+ DataType::LargeBinary => {
+ return Ok(compare_dict_bytes::<K, LargeBinaryType>(left, right, opts));
+ }
+ DataType::FixedSizeBinary(_) => {
+ return Ok(compare_dict_fixed_size_binary::<K>(left, right, opts));
+ }
+ _ => {}
+ }
+ }
let c_opts = child_opts(opts);
let cmp = make_comparator(left.values().as_ref(), right.values().as_ref(), c_opts)?;
@@ -234,6 +253,56 @@ fn compare_dict<K: ArrowDictionaryKeyType>(
Ok(f)
}
+fn compare_dict_bytes<K: ArrowDictionaryKeyType, T: ByteArrayType>(
+ left: &DictionaryArray<K>,
+ right: &DictionaryArray<K>,
+ opts: SortOptions,
+) -> DynComparator {
+ let left_values = left.values().as_bytes::<T>().clone();
+ let right_values = right.values().as_bytes::<T>().clone();
+ let left_keys = left.keys().values().clone();
+ let right_keys = right.keys().values().clone();
+ compare(left, right, opts, move |left_row, right_row| {
+ let left_key = left_keys[left_row].as_usize();
+ let right_key = right_keys[right_row].as_usize();
+ debug_assert!(left_key < left_values.len() && right_key < right_values.len());
+ // SAFETY: `compare` calls this only for rows that are valid on both sides, and
+ // `DictionaryArray` guarantees that every valid key indexes into its values.
+ let (left_bytes, right_bytes): (&[u8], &[u8]) = unsafe {
+ (
+ left_values.value_unchecked(left_key).as_ref(),
+ right_values.value_unchecked(right_key).as_ref(),
+ )
+ };
+ left_bytes.cmp(right_bytes)
+ })
+}
+
+fn compare_dict_fixed_size_binary<K: ArrowDictionaryKeyType>(
+ left: &DictionaryArray<K>,
+ right: &DictionaryArray<K>,
+ opts: SortOptions,
+) -> DynComparator {
+ let left_values = left.values().as_fixed_size_binary().clone();
+ let right_values = right.values().as_fixed_size_binary().clone();
+ let left_keys = left.keys().values().clone();
+ let right_keys = right.keys().values().clone();
+ compare(left, right, opts, move |left_row, right_row| {
+ let left_key = left_keys[left_row].as_usize();
+ let right_key = right_keys[right_row].as_usize();
+ debug_assert!(left_key < left_values.len() && right_key < right_values.len());
+ // SAFETY: `compare` calls this only for rows that are valid on both sides, and
+ // `DictionaryArray` guarantees that every valid key indexes into its values.
+ let (left_bytes, right_bytes) = unsafe {
+ (
+ left_values.value_unchecked(left_key),
+ right_values.value_unchecked(right_key),
+ )
+ };
+ left_bytes.cmp(right_bytes)
+ })
+}
+
fn compare_list<O: OffsetSizeTrait>(
left: &dyn Array,
right: &dyn Array,
@@ -798,6 +867,259 @@ mod tests {
assert_eq!(Ordering::Greater, cmp(1, 3));
}
+ #[test]
+ fn dict_fixed_size_binary_fast_path_derefs_values_both_directions() {
+ let shared_keys = || Int32Array::from(vec![0_i32, 1]);
+ let left_values =
+ FixedSizeBinaryArray::try_from_iter([b"zz".as_ref(), b"aa".as_ref()].into_iter())
+ .unwrap();
+ let right_values =
+ FixedSizeBinaryArray::try_from_iter([b"aa".as_ref(), b"zz".as_ref()].into_iter())
+ .unwrap();
+ let left = DictionaryArray::<Int32Type>::new(shared_keys(), Arc::new(left_values));
+ let right = DictionaryArray::<Int32Type>::new(shared_keys(), Arc::new(right_values));
+
+ let ascending = make_comparator(&left, &right, SortOptions::default()).unwrap();
+ assert_eq!(ascending(0, 0), Ordering::Greater);
+ assert_eq!(ascending(1, 1), Ordering::Less);
+
+ let descending = make_comparator(
+ &left,
+ &right,
+ SortOptions {
+ descending: true,
+ nulls_first: true,
+ },
+ )
+ .unwrap();
+ assert_eq!(descending(0, 0), Ordering::Less);
+ assert_eq!(descending(1, 1), Ordering::Greater);
+ }
+
+ fn dict_bytes_fast_path_derefs_values_both_directions_impl<T: ByteArrayType>() {
+ let shared_keys = || Int32Array::from(vec![0_i32, 1]);
+ let left_values =
+ GenericByteArray::<T>::new(OffsetBuffer::from_lengths([1, 1]), b"za".into(), None);
+ let right_values =
+ GenericByteArray::<T>::new(OffsetBuffer::from_lengths([1, 1]), b"az".into(), None);
+ let left = DictionaryArray::<Int32Type>::new(shared_keys(), Arc::new(left_values));
+ let right = DictionaryArray::<Int32Type>::new(shared_keys(), Arc::new(right_values));
+
+ let ascending = make_comparator(&left, &right, SortOptions::default()).unwrap();
+ assert_eq!(ascending(0, 0), Ordering::Greater);
+ assert_eq!(ascending(1, 1), Ordering::Less);
+
+ let descending = make_comparator(
+ &left,
+ &right,
+ SortOptions {
+ descending: true,
+ nulls_first: true,
+ },
+ )
+ .unwrap();
+ assert_eq!(descending(0, 0), Ordering::Less);
+ assert_eq!(descending(1, 1), Ordering::Greater);
+ }
+
+ #[test]
+ fn dict_bytes_fast_path_derefs_values_both_directions() {
+ dict_bytes_fast_path_derefs_values_both_directions_impl::<Utf8Type>();
+ dict_bytes_fast_path_derefs_values_both_directions_impl::<LargeUtf8Type>();
+ dict_bytes_fast_path_derefs_values_both_directions_impl::<BinaryType>();
+ dict_bytes_fast_path_derefs_values_both_directions_impl::<LargeBinaryType>();
+ }
+
+ fn dict_bytes_handles_key_and_value_nulls_impl<T: ByteArrayType>() {
+ // Left carries a logical null via a null KEY at row 1.
+ let left_keys = Int32Array::from(vec![Some(0_i32), None, Some(1)]);
+ let left_values = GenericByteArray::<T>::new(
+ OffsetBuffer::from_lengths([5, 6]),
+ b"applebanana".into(),
+ None,
+ );
+ let left = DictionaryArray::<Int32Type>::new(left_keys, Arc::new(left_values));
+
+ // Right carries a logical null via a null VALUE referenced at row 1.
+ let right_keys = Int32Array::from(vec![Some(0_i32), Some(1), Some(0)]);
+ let right_values = GenericByteArray::<T>::new(
+ OffsetBuffer::from_lengths([5, 0]),
+ b"apple".into(),
+ Some(NullBuffer::from(vec![true, false])),
+ );
+ let right = DictionaryArray::<Int32Type>::new(right_keys, Arc::new(right_values));
+
+ let cmp = make_comparator(&left, &right, SortOptions::default()).unwrap();
+ assert_eq!(cmp(0, 0), Ordering::Equal); // apple vs apple
+ assert_eq!(cmp(1, 0), Ordering::Less); // null-key < apple (nulls_first)
+ assert_eq!(cmp(0, 1), Ordering::Greater); // apple > null-value (nulls_first)
+ assert_eq!(cmp(1, 1), Ordering::Equal); // null-key vs null-value
+ }
+
+ #[test]
+ fn dict_bytes_handles_key_and_value_nulls() {
+ dict_bytes_handles_key_and_value_nulls_impl::<Utf8Type>();
+ dict_bytes_handles_key_and_value_nulls_impl::<LargeUtf8Type>();
+ dict_bytes_handles_key_and_value_nulls_impl::<BinaryType>();
+ dict_bytes_handles_key_and_value_nulls_impl::<LargeBinaryType>();
+ }
+
+ fn dict_bytes_sort_options_with_nulls_impl<T: ByteArrayType>() {
+ // row 1 is null on both sides (null key on left, null value on right)
+ let null_row_on_left = Int32Array::from(vec![Some(0_i32), None, Some(1)]);
+ let left_values = GenericByteArray::<T>::new(
+ OffsetBuffer::from_lengths([5, 6]),
+ b"applebanana".into(),
+ None,
+ );
+ let left = DictionaryArray::<Int32Type>::new(null_row_on_left, Arc::new(left_values));
+
+ let keys_pointing_at_null = Int32Array::from(vec![Some(0_i32), Some(1), Some(0)]);
+ let right_values = GenericByteArray::<T>::new(
+ OffsetBuffer::from_lengths([6, 0]),
+ b"cherry".into(),
+ Some(NullBuffer::from(vec![true, false])),
+ );
+ let right =
+ DictionaryArray::<Int32Type>::new(keys_pointing_at_null, Arc::new(right_values));
+
+ let asc_nulls_last = SortOptions {
+ descending: false,
+ nulls_first: false,
+ };
+ let desc_nulls_first = SortOptions {
+ descending: true,
+ nulls_first: true,
+ };
+ let desc_nulls_last = SortOptions {
+ descending: true,
+ nulls_first: false,
+ };
+
+ let cmp = make_comparator(&left, &right, asc_nulls_last).unwrap();
+ assert_eq!(cmp(0, 0), Ordering::Less); // apple < cherry
+ assert_eq!(cmp(1, 0), Ordering::Greater); // null > cherry (nulls last)
+ assert_eq!(cmp(0, 1), Ordering::Less); // apple < null (nulls last)
+ assert_eq!(cmp(1, 1), Ordering::Equal);
+
+ let cmp = make_comparator(&left, &right, desc_nulls_first).unwrap();
+ assert_eq!(cmp(0, 0), Ordering::Greater); // apple vs cherry reversed
+ assert_eq!(cmp(1, 0), Ordering::Less); // null < cherry (nulls first, unaffected by desc)
+ assert_eq!(cmp(0, 1), Ordering::Greater); // apple > null (nulls first)
+ assert_eq!(cmp(1, 1), Ordering::Equal);
+
+ let cmp = make_comparator(&left, &right, desc_nulls_last).unwrap();
+ assert_eq!(cmp(0, 0), Ordering::Greater); // apple vs cherry reversed
+ assert_eq!(cmp(1, 0), Ordering::Greater); // null > cherry (nulls last)
+ assert_eq!(cmp(0, 1), Ordering::Less); // apple < null (nulls last)
+ assert_eq!(cmp(1, 1), Ordering::Equal);
+ }
+
+ #[test]
+ fn dict_bytes_sort_options_with_nulls() {
+ dict_bytes_sort_options_with_nulls_impl::<Utf8Type>();
+ dict_bytes_sort_options_with_nulls_impl::<LargeUtf8Type>();
+ dict_bytes_sort_options_with_nulls_impl::<BinaryType>();
+ dict_bytes_sort_options_with_nulls_impl::<LargeBinaryType>();
+ }
+
+ fn dict_bytes_fast_path_panics_on_out_of_bounds_row_impl<T: ByteArrayType>() {
+ let two_row_keys = Int32Array::from(vec![0_i32, 1]);
+ let values =
+ GenericByteArray::<T>::new(OffsetBuffer::from_lengths([1, 1]), b"ab".into(), None);
+ let dict = DictionaryArray::<Int32Type>::new(two_row_keys, Arc::new(values));
+
+ let cmp = make_comparator(&dict, &dict, SortOptions::default()).unwrap();
+ cmp(2, 0);
+ }
+
+ #[test]
+ #[should_panic(expected = "index out of bounds")]
+ fn dict_utf8_fast_path_panics_on_out_of_bounds_row() {
+ dict_bytes_fast_path_panics_on_out_of_bounds_row_impl::<Utf8Type>();
+ }
+
+ #[test]
+ #[should_panic(expected = "index out of bounds")]
+ fn dict_large_utf8_fast_path_panics_on_out_of_bounds_row() {
+ dict_bytes_fast_path_panics_on_out_of_bounds_row_impl::<LargeUtf8Type>();
+ }
+
+ #[test]
+ #[should_panic(expected = "index out of bounds")]
+ fn dict_binary_fast_path_panics_on_out_of_bounds_row() {
+ dict_bytes_fast_path_panics_on_out_of_bounds_row_impl::<BinaryType>();
+ }
+
+ #[test]
+ #[should_panic(expected = "index out of bounds")]
+ fn dict_large_binary_fast_path_panics_on_out_of_bounds_row() {
+ dict_bytes_fast_path_panics_on_out_of_bounds_row_impl::<LargeBinaryType>();
+ }
+
+ #[test]
+ #[should_panic(expected = "index out of bounds")]
+ fn dict_fixed_size_binary_fast_path_panics_on_out_of_bounds_row() {
+ let two_row_keys = Int32Array::from(vec![0_i32, 1]);
+ let values = Arc::new(
+ FixedSizeBinaryArray::try_from_iter([b"aa".as_ref(), b"bb".as_ref()].into_iter())
+ .unwrap(),
+ );
+ let dict = DictionaryArray::<Int32Type>::new(two_row_keys, values);
+
+ let cmp = make_comparator(&dict, &dict, SortOptions::default()).unwrap();
+ cmp(2, 0);
+ }
+
+ #[test]
+ fn dict_fixed_size_binary_sort_options_with_nulls() {
+ let null_row_on_left = Int32Array::from(vec![Some(0_i32), None, Some(1)]);
+ let left_values =
+ FixedSizeBinaryArray::try_from_iter([b"aa".as_ref(), b"bb".as_ref()].into_iter())
+ .unwrap();
+ let left = DictionaryArray::<Int32Type>::new(null_row_on_left, Arc::new(left_values));
+
+ let keys_pointing_at_null = Int32Array::from(vec![Some(0_i32), Some(1), Some(0)]);
+ let right_values = FixedSizeBinaryArray::try_from_sparse_iter_with_size(
+ [Some(b"cc".as_ref()), None].into_iter(),
+ 2,
+ )
+ .unwrap();
+ let right =
+ DictionaryArray::<Int32Type>::new(keys_pointing_at_null, Arc::new(right_values));
+
+ let asc_nulls_last = SortOptions {
+ descending: false,
+ nulls_first: false,
+ };
+ let desc_nulls_first = SortOptions {
+ descending: true,
+ nulls_first: true,
+ };
+ let desc_nulls_last = SortOptions {
+ descending: true,
+ nulls_first: false,
+ };
+
+ let cmp = make_comparator(&left, &right, asc_nulls_last).unwrap();
+ assert_eq!(cmp(0, 0), Ordering::Less); // "aa" < "cc"
+ assert_eq!(cmp(1, 0), Ordering::Greater); // null > "cc" (nulls last)
+ assert_eq!(cmp(0, 1), Ordering::Less); // "aa" < null (nulls last)
+ assert_eq!(cmp(1, 1), Ordering::Equal);
+
+ let cmp = make_comparator(&left, &right, desc_nulls_first).unwrap();
+ assert_eq!(cmp(0, 0), Ordering::Greater); // "aa" vs "cc" reversed
+ assert_eq!(cmp(1, 0), Ordering::Less); // null < "cc" (nulls first)
+ assert_eq!(cmp(0, 1), Ordering::Greater); // "aa" > null (nulls first)
+ assert_eq!(cmp(1, 1), Ordering::Equal);
+
+ let cmp = make_comparator(&left, &right, desc_nulls_last).unwrap();
+ assert_eq!(cmp(0, 0), Ordering::Greater); // "aa" vs "cc" reversed
+ assert_eq!(cmp(1, 0), Ordering::Greater); // null > "cc" (nulls last)
+ assert_eq!(cmp(0, 1), Ordering::Less); // "aa" < null (nulls last)
+ assert_eq!(cmp(1, 1), Ordering::Equal);
+ }
+
#[test]
fn test_primitive_dict() {
let values = Int32Array::from(vec![1_i32, 0, 2, 5]);