Use prefix first for comparisons, resort to data buffer for remaining data on equal values

[Dandandan]

I think we can also improve the non-inlined case with prefixes in the views, I will create an issue about it later.

Originally posted by @Dandandan in #7731 (comment)

I think we should be able to do most comparisons based on the prefix (4 bytes), rather than looking in the databuffer.
If the values are the same, we can look into the databuffer and compare the rest of the bytes.
This should avoid fetching most of the data, only for the comparisons that have equal 4 bytes.

[Dandandan]

@zhuqi-lucas

[zhuqi-lucas]

take

[zhuqi-lucas]

Thank you @Dandandan , take it now.

[alamb]

🚀

[alamb]

Now we are cooking! (Or "obessing over performance" as I like to day)

🚀

[Dandandan]

I feel using prefixes for kernels may really help a lot, probably even more for the real usage where values are spread out over different buffers. If we can avoid accessing e.g. 95% of the values this way, that may be a big win.

[zhuqi-lucas]

Thank you @Dandandan @alamb,
Exactly big win with prefix compare(convert to u128 kernel based compare) from the try with continue inlined compare improvement:
#7748

2.53 faster for lt StringViewArray StringViewArray inlined bytes

[zhuqi-lucas]

Next step i will try non-inlined case improvement for this ticket, thanks!

[zhuqi-lucas]

@Dandandan @alamb

I tried the patch for this ticket:

diff --git a/arrow-array/src/array/byte_view_array.rs b/arrow-array/src/array/byte_view_array.rs
index 713e275d18..20962abc9b 100644
--- a/arrow-array/src/array/byte_view_array.rs
+++ b/arrow-array/src/array/byte_view_array.rs
@@ -338,6 +338,15 @@ impl<T: ByteViewType + ?Sized> GenericByteViewArray<T> {
         std::slice::from_raw_parts((view as *const u128 as *const u8).wrapping_add(4), len)
     }
 
+
+    /// Returns the first 4-byte prefix of the inline value of the view.
+    /// # Safety
+    /// - The `view` must be a valid element from `Self::views()` that adheres to the view layout.
+    #[inline(always)]
+    pub unsafe fn inline_prefix(view: &u128) -> &[u32] {
+        std::slice::from_raw_parts((view as *const u128 as *const u32).wrapping_add(1), 1)
+    }
+
     /// Constructs a new iterator for iterating over the values of this array
     pub fn iter(&self) -> ArrayIter<&Self> {
         ArrayIter::new(self)
@@ -552,8 +561,8 @@ impl<T: ByteViewType + ?Sized> GenericByteViewArray<T> {
 
         // one of the string is larger than 12 bytes,
         // we then try to compare the inlined data first
-        let l_inlined_data = unsafe { GenericByteViewArray::<T>::inline_value(l_view, 4) };
-        let r_inlined_data = unsafe { GenericByteViewArray::<T>::inline_value(r_view, 4) };
+        let l_inlined_data = unsafe { GenericByteViewArray::<T>::inline_prefix(l_view) };
+        let r_inlined_data = unsafe { GenericByteViewArray::<T>::inline_prefix(r_view) };
         if r_inlined_data != l_inlined_data {
             return l_inlined_data.cmp(r_inlined_data);
         }

But no performance improvement for benchmark, currently our code already using 4 bytes inline to check:

 // one of the string is larger than 12 bytes,
        // we then try to compare the inlined data first
        let l_inlined_data = unsafe { GenericByteViewArray::<T>::inline_value(l_view, 4) };
        let r_inlined_data = unsafe { GenericByteViewArray::<T>::inline_value(r_view, 4) };
        if r_inlined_data != l_inlined_data {
            return l_inlined_data.cmp(r_inlined_data);
        }

As a try to change to u8 compare to u32 for the 4 bytes, we don't see performance improvement in the benchmark.

[zhuqi-lucas]

Also try similar patch with above, still no performance improvement from the benchmark:

diff --git a/arrow-array/src/array/byte_view_array.rs b/arrow-array/src/array/byte_view_array.rs
index 713e275d18..2022e5959e 100644
--- a/arrow-array/src/array/byte_view_array.rs
+++ b/arrow-array/src/array/byte_view_array.rs
@@ -552,10 +552,10 @@ impl<T: ByteViewType + ?Sized> GenericByteViewArray<T> {
 
         // one of the string is larger than 12 bytes,
         // we then try to compare the inlined data first
-        let l_inlined_data = unsafe { GenericByteViewArray::<T>::inline_value(l_view, 4) };
-        let r_inlined_data = unsafe { GenericByteViewArray::<T>::inline_value(r_view, 4) };
+        let l_inlined_data = (l_view >> 32) as u32;
+        let r_inlined_data = (r_view >> 32) as u32;
         if r_inlined_data != l_inlined_data {
-            return l_inlined_data.cmp(r_inlined_data);
+            return l_inlined_data.cmp(&r_inlined_data);
         }
 
         // unfortunately, we need to compare the full data

[Dandandan]

Ah, it seems already doing the prefix comparison 🤯 :)
Perhaps we can remove the double checks on the length or try request fewer bytes (skip the first 4 bytes already in prefix) but seems we can not gain much more I guess!

[zhuqi-lucas]

Thank you @Dandandan for double checking!