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/15 06:52:09 UTC
(arrow-rs) branch gh-readonly-queue/main/pr-11143-cbb18415d61e01905fd56ceea4fbc811372d3b98 created (now 6aa1dd2c0c)
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a change to branch gh-readonly-queue/main/pr-11143-cbb18415d61e01905fd56ceea4fbc811372d3b98
in repository https://gitbox.apache.org/repos/asf/arrow-rs.git
at 6aa1dd2c0c Speed up DELTA_BINARY_PACKED skip (#11143)
This branch includes the following new commits:
new 6aa1dd2c0c Speed up DELTA_BINARY_PACKED skip (#11143)
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
(arrow-rs) 01/01: Speed up DELTA_BINARY_PACKED skip (#11143)
Posted by gi...@apache.org.
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 <ja...@qq.com>
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 <et...@users.noreply.github.com>
---
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;
}