This is an automated email from the ASF dual-hosted git repository. github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-11143-cbb18415d61e01905fd56ceea4fbc811372d3b98 in repository https://gitbox.apache.org/repos/asf/arrow-rs.git
commit 6aa1dd2c0c141c9ce390f52a78cf9844c0184686 Author: flashmouse <[email protected]> AuthorDate: Thu Oct 15 04:52:09 2026 +0000 Speed up DELTA_BINARY_PACKED skip (#11143) # Which issue does this PR close? - Closes #11142 . # Rationale for this change <!-- Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed. Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes. --> # What changes are included in this PR? change ``DeltaBitPackDecoder::skip `` to: ``` last_value += n * min_delta + sum(residuals) ``` # Are these changes tested? ran existed ut: ``` cargo test -p parquet test_skip_delta_bit_packed ``` ran benchmark: ``` cargo bench -p parquet \ --features arrow,test_common,experimental \ --bench arrow_reader \ -- 'binary packed skip(, mandatory, no NULLs| stepped increasing value| increasing value)$' \ --measurement-time 3 \ --warm-up-time 1 \ --sample-size 20 \ --baseline main ``` ``` arrow_array_reader/Int32Array/binary packed skip, mandatory, no NULLs time: [35.381 µs 35.417 µs 35.454 µs] change: [−16.884% −15.704% −14.829%] (p = 0.00 < 0.05) Performance has improved. Found 2 outliers among 20 measurements (10.00%) 1 (5.00%) high mild 1 (5.00%) high severe arrow_array_reader/Int32Array/binary packed skip increasing value time: [17.208 µs 17.229 µs 17.259 µs] change: [−0.3198% +0.1156% +0.7165%] (p = 0.69 > 0.05) No change in performance detected. Found 1 outliers among 20 measurements (5.00%) 1 (5.00%) high severe arrow_array_reader/Int32Array/binary packed skip stepped increasing value time: [31.327 µs 31.509 µs 31.708 µs] change: [−14.695% −13.945% −13.224%] (p = 0.00 < 0.05) Performance has improved. arrow_array_reader/UInt8Array/binary packed skip, mandatory, no NULLs time: [36.620 µs 36.706 µs 36.802 µs] change: [−15.317% −14.833% −14.321%] (p = 0.00 < 0.05) Performance has improved. Found 3 outliers among 20 measurements (15.00%) 2 (10.00%) high mild 1 (5.00%) high severe arrow_array_reader/UInt8Array/binary packed skip increasing value time: [18.237 µs 18.263 µs 18.286 µs] change: [−0.8678% −0.4662% −0.0417%] (p = 0.03 < 0.05) Change within noise threshold. Found 1 outliers among 20 measurements (5.00%) 1 (5.00%) high severe arrow_array_reader/UInt8Array/binary packed skip stepped increasing value time: [32.784 µs 33.176 µs 33.651 µs] change: [−18.678% −15.370% −13.186%] (p = 0.00 < 0.05) Performance has improved. Found 2 outliers among 20 measurements (10.00%) 2 (10.00%) high mild arrow_array_reader/Int8Array/binary packed skip, mandatory, no NULLs time: [34.291 µs 34.502 µs 34.856 µs] change: [−16.577% −16.135% −15.635%] (p = 0.00 < 0.05) Performance has improved. Found 4 outliers among 20 measurements (20.00%) 1 (5.00%) low mild 1 (5.00%) high mild 2 (10.00%) high severe arrow_array_reader/Int8Array/binary packed skip increasing value time: [18.297 µs 18.326 µs 18.359 µs] change: [−1.5190% −0.8557% −0.2655%] (p = 0.01 < 0.05) Change within noise threshold. Found 2 outliers among 20 measurements (10.00%) 1 (5.00%) high mild 1 (5.00%) high severe arrow_array_reader/Int8Array/binary packed skip stepped increasing value time: [32.527 µs 32.615 µs 32.709 µs] change: [−16.539% −15.777% −15.023%] (p = 0.00 < 0.05) Performance has improved. Found 2 outliers among 20 measurements (10.00%) 2 (10.00%) high mild arrow_array_reader/UInt16Array/binary packed skip, mandatory, no NULLs time: [38.351 µs 38.522 µs 38.785 µs] change: [−16.236% −14.975% −13.900%] (p = 0.00 < 0.05) Performance has improved. Found 3 outliers among 20 measurements (15.00%) 2 (10.00%) high mild 1 (5.00%) high severe arrow_array_reader/UInt16Array/binary packed skip increasing value time: [18.560 µs 19.019 µs 19.931 µs] change: [−0.6576% +1.3471% +4.6113%] (p = 0.48 > 0.05) No change in performance detected. Found 3 outliers among 20 measurements (15.00%) 2 (10.00%) high mild 1 (5.00%) high severe arrow_array_reader/UInt16Array/binary packed skip stepped increasing value time: [32.512 µs 32.677 µs 32.909 µs] change: [−16.598% −15.848% −15.063%] (p = 0.00 < 0.05) Performance has improved. arrow_array_reader/Int16Array/binary packed skip, mandatory, no NULLs time: [34.771 µs 34.822 µs 34.879 µs] change: [−17.338% −16.748% −16.184%] (p = 0.00 < 0.05) Performance has improved. Found 3 outliers among 20 measurements (15.00%) 1 (5.00%) low mild 1 (5.00%) high mild 1 (5.00%) high severe arrow_array_reader/Int16Array/binary packed skip increasing value time: [18.513 µs 18.666 µs 18.907 µs] change: [−0.4697% +2.5387% +8.0680%] (p = 0.33 > 0.05) No change in performance detected. Found 3 outliers among 20 measurements (15.00%) 3 (15.00%) high severe arrow_array_reader/Int16Array/binary packed skip stepped increasing value time: [32.784 µs 32.998 µs 33.239 µs] change: [−15.854% −15.053% −14.247%] (p = 0.00 < 0.05) Performance has improved. arrow_array_reader/UInt32Array/binary packed skip, mandatory, no NULLs time: [35.367 µs 36.238 µs 37.865 µs] change: [−19.347% −16.554% −13.953%] (p = 0.00 < 0.05) Performance has improved. Found 4 outliers among 20 measurements (20.00%) 4 (20.00%) high severe arrow_array_reader/UInt32Array/binary packed skip increasing value time: [17.156 µs 17.282 µs 17.484 µs] change: [−11.783% −4.3866% +0.2920%] (p = 0.29 > 0.05) No change in performance detected. Found 3 outliers among 20 measurements (15.00%) 3 (15.00%) high severe arrow_array_reader/UInt32Array/binary packed skip stepped increasing value time: [31.254 µs 31.357 µs 31.495 µs] change: [−17.542% −16.736% −15.954%] (p = 0.00 < 0.05) Performance has improved. arrow_array_reader/Int64Array/binary packed skip, mandatory, no NULLs time: [38.707 µs 38.783 µs 38.867 µs] change: [−18.958% −15.537% −8.8432%] (p = 0.00 < 0.05) Performance has improved. Found 2 outliers among 20 measurements (10.00%) 2 (10.00%) high severe arrow_array_reader/Int64Array/binary packed skip increasing value time: [19.648 µs 19.683 µs 19.727 µs] change: [−1.1204% −0.5616% +0.0540%] (p = 0.07 > 0.05) No change in performance detected. Found 2 outliers among 20 measurements (10.00%) 1 (5.00%) high mild 1 (5.00%) high severe arrow_array_reader/Int64Array/binary packed skip stepped increasing value time: [30.935 µs 31.068 µs 31.317 µs] change: [−14.075% −13.355% −12.473%] (p = 0.00 < 0.05) Performance has improved. Found 2 outliers among 20 measurements (10.00%) 2 (10.00%) high severe arrow_array_reader/UInt64Array/binary packed skip, mandatory, no NULLs time: [38.809 µs 38.898 µs 38.977 µs] change: [−18.463% −18.034% −17.462%] (p = 0.00 < 0.05) Performance has improved. Found 3 outliers among 20 measurements (15.00%) 1 (5.00%) low mild 1 (5.00%) high mild 1 (5.00%) high severe arrow_array_reader/UInt64Array/binary packed skip increasing value time: [19.726 µs 19.766 µs 19.810 µs] change: [−1.2898% −0.7679% −0.1036%] (p = 0.01 < 0.05) Change within noise threshold. Found 1 outliers among 20 measurements (5.00%) 1 (5.00%) high severe arrow_array_reader/UInt64Array/binary packed skip stepped increasing value time: [30.988 µs 31.356 µs 31.712 µs] change: [−14.999% −14.343% −13.623%] (p = 0.00 < 0.05) Performance has improved. Found 2 outliers among 20 measurements (10.00%) 1 (5.00%) high mild 1 (5.00%) high severe arrow_array_reader/INT32/Decimal128Array/binary packed skip, mandatory, no NULLs time: [48.439 µs 48.481 µs 48.533 µs] change: [−9.1162% −8.3940% −7.6386%] (p = 0.00 < 0.05) Performance has improved. Found 2 outliers among 20 measurements (10.00%) 1 (5.00%) high mild 1 (5.00%) high severe arrow_array_reader/INT32/Decimal128Array/binary packed skip increasing value time: [30.470 µs 30.525 µs 30.587 µs] change: [+7.8913% +9.5110% +11.024%] (p = 0.00 < 0.05) Performance has regressed. Found 1 outliers among 20 measurements (5.00%) 1 (5.00%) high severe arrow_array_reader/INT32/Decimal128Array/binary packed skip stepped increasing value time: [44.930 µs 45.499 µs 46.267 µs] change: [−10.609% −8.6403% −6.7066%] (p = 0.00 < 0.05) Performance has improved. Found 2 outliers among 20 measurements (10.00%) 1 (5.00%) high mild 1 (5.00%) high severe arrow_array_reader/INT64/Decimal128Array/binary packed skip, mandatory, no NULLs time: [47.276 µs 47.448 µs 47.649 µs] change: [−17.295% −16.545% −15.692%] (p = 0.00 < 0.05) Performance has improved. Found 2 outliers among 20 measurements (10.00%) 1 (5.00%) high mild 1 (5.00%) high severe arrow_array_reader/INT64/Decimal128Array/binary packed skip increasing value time: [29.379 µs 29.674 µs 30.047 µs] change: [−2.9777% −1.6166% −0.1183%] (p = 0.04 < 0.05) Change within noise threshold. Found 1 outliers among 20 measurements (5.00%) 1 (5.00%) high mild arrow_array_reader/INT64/Decimal128Array/binary packed skip stepped increasing value time: [41.020 µs 41.316 µs 41.718 µs] change: [−12.063% −10.787% −9.5841%] (p = 0.00 < 0.05) Performance has improved. ``` # Are there any user-facing changes? no Co-authored-by: Ed Seidl <[email protected]> --- parquet/src/encodings/decoding.rs | 28 +++++++++++++--------------- 1 file changed, 13 insertions(+), 15 deletions(-) diff --git a/parquet/src/encodings/decoding.rs b/parquet/src/encodings/decoding.rs index 379819d55a..6346f205e4 100644 --- a/parquet/src/encodings/decoding.rs +++ b/parquet/src/encodings/decoding.rs @@ -18,7 +18,7 @@ //! Contains all supported decoders for Parquet. use bytes::Bytes; -use num_traits::{FromPrimitive, WrappingAdd}; +use num_traits::{FromPrimitive, WrappingAdd, WrappingMul}; use std::{cmp, marker::PhantomData, mem}; use super::rle::{MAX_RLE_DICTIONARY_BIT_WIDTH, RleDecoder}; @@ -670,7 +670,7 @@ where impl<T: DataType> Decoder<T> for DeltaBitPackDecoder<T> where - T::T: Default + FromPrimitive + BitPacking + WrappingAdd + Copy, + T::T: Default + FromPrimitive + BitPacking + WrappingAdd + WrappingMul + Copy, { // # of total values is derived from encoding #[inline] @@ -904,19 +904,17 @@ where )); } - if min_delta == 0 { - for v in &mut skip_buffer[0..skip_count] { - *v = v.wrapping_add(&self.last_value); - self.last_value = *v; - } - } else { - for v in &mut skip_buffer[0..skip_count] { - *v = v - .wrapping_add(&self.min_delta) - .wrapping_add(&self.last_value); - self.last_value = *v; - } - } + let residual_sum = skip_buffer[0..skip_count] + .iter() + .copied() + .fold(T::T::default(), |sum, residual| sum.wrapping_add(&residual)); + let step_count = T::T::from_usize(skip_count) + .ok_or_else(|| general_err!("delta*n overflow in skip"))?; + let total_delta = self + .min_delta + .wrapping_mul(&step_count) + .wrapping_add(&residual_sum); + self.last_value = self.last_value.wrapping_add(&total_delta); skipped_in_mini_block += batch_to_skip; }
