This is an automated email from the ASF dual-hosted git repository.
etseidl 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 3566d07ee4 perf(parquet): scan DELTA_BYTE_ARRAY shared prefixes a
block at a time (#10549)
3566d07ee4 is described below
commit 3566d07ee451686d1d0f2ae2c46f7f0e7b4d6aaf
Author: Adrian Garcia Badaracco <[email protected]>
AuthorDate: Tue Aug 4 15:29:02 2026 -0500
perf(parquet): scan DELTA_BYTE_ARRAY shared prefixes a block at a time
(#10549)
> **Stacked on https://github.com/apache/arrow-rs/pull/10550.** This
branch is
> that PR's benchmark commit plus one commit of its own, so that the
numbers
> below are reproducible with `cargo bench` on this branch alone. Review
only
> the second commit here; the diff shrinks to
> `+139/-15` once #10550 merges and this rebases onto `main`.
# Which issue does this PR close?
None directly. Split out of
https://github.com/apache/arrow-rs/pull/10505 so that the correctness
fix there can be reviewed without an unrelated performance change
attached to it.
# Rationale for this change
`DELTA_BYTE_ARRAY` stores each value as the number of leading bytes it
shares with its predecessor plus the remaining suffix, so writing a
value runs a shared-prefix scan against the previous value. Both encoder
paths implement that scan as a byte-at-a-time loop:
- `DeltaByteArrayEncoder::put` in
`parquet/src/encodings/encoding/mod.rs` (the generic
`SerializedFileWriter` path)
- `FallbackEncoder::encode`'s `Delta` arm in
`parquet/src/arrow/arrow_writer/byte_array.rs` (the `ArrowWriter` path)
The scan runs once per value, and on exactly the data the encoding
exists for — near-identical consecutive values — it covers essentially
the whole value. That makes its throughput, not its per-call overhead,
the thing that matters, and a byte-at-a-time loop is the slowest way to
do it.
# What changes are included in this PR?
Extract the two duplicated loops into
`crate::util::prefix::common_prefix_length` and compare a 32-byte block
at a time instead of a byte at a time.
32 is the widest block that both aarch64 and x86-64 still expand inline;
at 64 bytes x86-64 drops to an out-of-line `bcmp` call, which costs more
than the extra width buys. Measured on aarch64, every width from 16 up
performs the same, so this sits in the middle of a flat optimum rather
than on a tuned peak.
No behavior change: the function returns the same prefix length the
byte-wise loops did, and no page layout, encoding, or file output
changes.
# Are these changes tested?
Existing coverage: the full `parquet` suite passes unmodified (1307
tests), including the `DELTA_BYTE_ARRAY` round-trip tests.
Those round trips are weaker evidence than they look, in two ways.
First, they never reach the new code path: `ByteArrayType::test` and
`FixedLenByteArrayType::test` feed random values, which share no prefix,
and the `ArrowWriter` cases write values a handful of bytes long — so
nothing in the suite writes two consecutive values sharing 32 bytes, and
the block loop never runs. Second, a round trip is structurally blind to
an under-counted prefix: the encoder just emits a correspondingly longer
suffix and the decoder reconstructs the same bytes either way. Only
over-counting shows up. `test_estimated_data_encoded_size` does assert
an exact encoded size, but on 2- and 3-byte values that can never enter
the block loop.
New coverage, unit level, in `parquet/src/util/prefix.rs`: the boundary
cases the block loop introduces — empty inputs, prefixes shorter than /
equal to / longer than one block, a mismatch in the first and last byte
of a block, and unequal lengths where one input is a strict prefix of
the other. Plus unequal lengths combined with a mismatch past a block
boundary (where truncating to the shorter length interacts with the
block loop), non-zero slice start offsets (callers pass sub-slices into
shared Arrow buffers, not freshly allocated `Vec`s), and a prefix ending
mid-UTF-8-codepoint — byte-level prefixes may split a multi-byte
character, which was true of the byte-wise scan too and is worth pinning
now that the scan is wider.
New coverage, end to end, for both call sites:
`test_delta_byte_array_long_shared_prefix{,_fixed_len}` in
`parquet/src/encodings/encoding/mod.rs` and
`delta_byte_array_long_shared_prefix` in
`parquet/src/arrow/arrow_writer/mod.rs`. Each writes values with a
1000-byte shared prefix — not a multiple of the 32-byte block, so the
scan has to resolve a partial block — and asserts on the prefix lengths
actually written, decoded back out of the page, rather than on a round
trip alone.
Those assertions were checked for power by mutation: dropping the
sub-block tail scan from `common_prefix_length` (so it under-counts by
up to 31 bytes) leaves all 156 `arrow::arrow_writer` tests passing on
`main`, and fails all three new tests.
Benchmarked with `parquet/benches/arrow_writer.rs`'s
`bench_delta_byte_array_writers`, added in #10512. Results in a comment
below.
# Are there any user-facing changes?
No API changes and no change to written output. `DELTA_BYTE_ARRAY`
writes get faster.
---------
Co-authored-by: Claude Opus 5 <[email protected]>
Co-authored-by: Ed Seidl <[email protected]>
---
parquet/src/arrow/arrow_writer/byte_array.rs | 10 +-
parquet/src/encodings/encoding/mod.rs | 10 +-
parquet/src/util/mod.rs | 1 +
parquet/src/util/prefix.rs | 133 +++++++++++++++++++++++++++
4 files changed, 139 insertions(+), 15 deletions(-)
diff --git a/parquet/src/arrow/arrow_writer/byte_array.rs
b/parquet/src/arrow/arrow_writer/byte_array.rs
index ea45edeea2..93a16f7693 100644
--- a/parquet/src/arrow/arrow_writer/byte_array.rs
+++ b/parquet/src/arrow/arrow_writer/byte_array.rs
@@ -30,6 +30,7 @@ use crate::geospatial::statistics::GeospatialStatistics;
use crate::schema::types::ColumnDescPtr;
use crate::util::bit_util::num_required_bits;
use crate::util::interner::{Interner, Storage};
+use crate::util::prefix::common_prefix_length;
use arrow_array::types::ByteArrayType;
use arrow_array::{
Array, ArrayAccessor, BinaryArray, BinaryViewArray, DictionaryArray,
FixedSizeBinaryArray,
@@ -201,15 +202,8 @@ impl FallbackEncoder {
for idx in indices {
let value = values.value(idx);
let value = value.as_ref();
- let mut prefix_length = 0;
-
- while prefix_length < last_value.len()
- && prefix_length < value.len()
- && last_value[prefix_length] == value[prefix_length]
- {
- prefix_length += 1;
- }
+ let prefix_length = common_prefix_length(last_value,
value);
let suffix_length = value.len() - prefix_length;
last_value.clear();
diff --git a/parquet/src/encodings/encoding/mod.rs
b/parquet/src/encodings/encoding/mod.rs
index eeabcf4ba5..06ad3ac10e 100644
--- a/parquet/src/encodings/encoding/mod.rs
+++ b/parquet/src/encodings/encoding/mod.rs
@@ -26,6 +26,7 @@ use crate::encodings::rle::RleEncoder;
use crate::errors::{ParquetError, Result};
use crate::schema::types::ColumnDescPtr;
use crate::util::bit_util::{BitWriter, num_required_bits};
+use crate::util::prefix::common_prefix_length;
use byte_stream_split_encoder::{ByteStreamSplitEncoder,
VariableWidthByteStreamSplitEncoder};
use bytes::Bytes;
@@ -698,13 +699,8 @@ impl<T: DataType> Encoder<T> for DeltaByteArrayEncoder<T> {
for byte_array in values {
let current = byte_array.data();
- // Maximum prefix length that is shared between previous value and
current
- // value
- let prefix_len = cmp::min(self.previous.len(), current.len());
- let mut match_len = 0;
- while match_len < prefix_len && self.previous[match_len] ==
current[match_len] {
- match_len += 1;
- }
+ // Number of leading bytes shared with the previous value
+ let match_len = common_prefix_length(&self.previous, current);
prefix_lengths.push(match_len as i32);
suffixes.push(byte_array.slice(match_len, byte_array.len() -
match_len));
// Update previous for the next prefix
diff --git a/parquet/src/util/mod.rs b/parquet/src/util/mod.rs
index 145cdd693e..4d54975313 100644
--- a/parquet/src/util/mod.rs
+++ b/parquet/src/util/mod.rs
@@ -19,6 +19,7 @@
pub mod bit_util;
mod bit_pack;
pub(crate) mod interner;
+pub(crate) mod prefix;
pub mod push_buffers;
#[cfg(any(test, feature = "test_common"))]
diff --git a/parquet/src/util/prefix.rs b/parquet/src/util/prefix.rs
new file mode 100644
index 0000000000..1e2c743aac
--- /dev/null
+++ b/parquet/src/util/prefix.rs
@@ -0,0 +1,133 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! Shared-prefix scanning for `DELTA_BYTE_ARRAY`.
+
+/// Returns the length in bytes of the longest common prefix of `a` and `b`.
+///
+/// `DELTA_BYTE_ARRAY` stores each value as the number of leading bytes it
+/// shares with its predecessor plus the remaining suffix, so this runs once
+/// per value written with that encoding. When consecutive values are
+/// near-identical — the case the encoding exists for — the scan covers
+/// essentially the whole value, which makes its throughput, not its overhead,
+/// the thing that matters.
+#[inline]
+pub(crate) fn common_prefix_length(a: &[u8], b: &[u8]) -> usize {
+ // Comparing a block at a time rather than a byte at a time is what keeps
+ // this off the critical path. 32 is the widest block that both aarch64
+ // and x86-64 still expand inline: at 64 bytes x86-64 drops to an
+ // out-of-line `bcmp` call, which costs more than the extra width buys.
+ // Measured on aarch64, every width from 16 up performs the same (~15x a
+ // byte-wise loop over a 2 MiB shared prefix), so this sits in the middle
+ // of a flat optimum rather than on a tuned peak.
+ const BLOCK: usize = 32;
+
+ let n = a.len().min(b.len());
+ let (a, b) = (&a[..n], &b[..n]);
+
+ let mut matched = 0;
+ for (x, y) in a.chunks_exact(BLOCK).zip(b.chunks_exact(BLOCK)) {
+ if x != y {
+ break;
+ }
+ matched += BLOCK;
+ }
+
+ // At most one block plus the sub-block tail is left unresolved: either the
+ // block the loop stopped on, or the remainder `chunks_exact` never
yielded.
+ matched
+ + a[matched..]
+ .iter()
+ .zip(&b[matched..])
+ .take_while(|(x, y)| x == y)
+ .count()
+}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+
+ /// The definition, kept deliberately naive, to check the fast path
against.
+ fn naive(a: &[u8], b: &[u8]) -> usize {
+ let mut i = 0;
+ while i < a.len() && i < b.len() && a[i] == b[i] {
+ i += 1;
+ }
+ i
+ }
+
+ #[test]
+ fn test_common_prefix_length_edge_cases() {
+ assert_eq!(common_prefix_length(b"", b""), 0);
+ assert_eq!(common_prefix_length(b"", b"abc"), 0);
+ assert_eq!(common_prefix_length(b"abc", b""), 0);
+ assert_eq!(common_prefix_length(b"abc", b"xyz"), 0);
+ assert_eq!(common_prefix_length(b"abc", b"abc"), 3);
+ // One value a strict prefix of the other, in both orders.
+ assert_eq!(common_prefix_length(b"abc", b"abcdef"), 3);
+ assert_eq!(common_prefix_length(b"abcdef", b"abc"), 3);
+ }
+
+ #[test]
+ fn test_common_prefix_length_around_block_boundaries() {
+ // Mismatches placed on, either side of, and well past the 32-byte
+ // block boundary the scan steps in.
+ for len in [31, 32, 33, 63, 64, 65, 127, 128, 129, 1024] {
+ for mismatch in 0..=len {
+ let a = vec![b'x'; len];
+ let mut b = a.clone();
+ if mismatch < len {
+ b[mismatch] = b'y';
+ }
+ let expected = if mismatch < len { mismatch } else { len };
+ assert_eq!(
+ common_prefix_length(&a, &b),
+ expected,
+ "len={len} mismatch={mismatch}"
+ );
+ assert_eq!(common_prefix_length(&a, &b), naive(&a, &b));
+ }
+ }
+ }
+
+ #[test]
+ fn test_common_prefix_length_unequal_lengths() {
+ // Result is capped by the shorter value even when the longer one
+ // continues to match, across block boundaries.
+ for a_len in 0..80usize {
+ for b_len in 0..80usize {
+ let a = vec![b'x'; a_len];
+ let b = vec![b'x'; b_len];
+ assert_eq!(common_prefix_length(&a, &b), a_len.min(b_len));
+ assert_eq!(common_prefix_length(&a, &b), naive(&a, &b));
+ }
+ }
+ }
+
+ #[test]
+ fn test_common_prefix_length_matches_naive_on_varied_data() {
+ // Non-uniform bytes, so a block compare cannot accidentally succeed
+ // on data a byte-wise scan would reject.
+ let a: Vec<u8> = (0..500u32).map(|i| (i * 7 % 251) as u8).collect();
+ for mismatch in 0..a.len() {
+ let mut b = a.clone();
+ b[mismatch] = b[mismatch].wrapping_add(1);
+ assert_eq!(common_prefix_length(&a, &b), naive(&a, &b));
+ assert_eq!(common_prefix_length(&a, &b), mismatch);
+ }
+ }
+}
