This is an automated email from the ASF dual-hosted git repository.
alamb 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 d1a428cfba Speed up filter some more (up to 2x) (#8868)
d1a428cfba is described below
commit d1a428cfbac756fea58b2c58d44b4eb385feccc2
Author: Daniël Heres <[email protected]>
AuthorDate: Wed Nov 19 15:01:12 2025 +0100
Speed up filter some more (up to 2x) (#8868)
# Which issue does this PR close?
- Closes #8865
# Rationale for this change
Removing the bounds check makes a quite big impact on filter performance
```
filter context i32 (kept 1/2)
time: [10.757 µs 10.818 µs 10.921 µs]
change: [−48.453% −48.235% −47.968%] (p = 0.00 <
0.05)
Performance has improved.
Found 7 outliers among 100 measurements (7.00%)
6 (6.00%) high mild
1 (1.00%) high severe
filter context i32 high selectivity (kept 1023/1024)
time: [6.3936 µs 6.4445 µs 6.5095 µs]
change: [−3.2534% −0.5845% +1.7088%] (p = 0.68 >
0.05)
No change in performance detected.
Found 5 outliers among 100 measurements (5.00%)
5 (5.00%) high severe
filter context i32 low selectivity (kept 1/1024)
time: [134.12 ns 135.27 ns 136.82 ns]
change: [−14.101% −12.837% −11.698%] (p = 0.00 <
0.05)
Performance has improved.
Found 3 outliers among 100 measurements (3.00%)
3 (3.00%) high severe
filter context i32 w NULLs (kept 1/2)
time: [31.751 µs 32.030 µs 32.421 µs]
change: [−34.482% −33.493% −32.603%] (p = 0.00 <
0.05)
Performance has improved.
Found 4 outliers among 100 measurements (4.00%)
1 (1.00%) high mild
3 (3.00%) high severe
Benchmarking filter context i32 w NULLs high selectivity (kept 1023/1024):
Collecting 100 samples in estimated 5.0255 s (646k iterafilter context i32 w
NULLs high selectivity (kept 1023/1024)
time: [7.7275 µs 7.7428 µs 7.7580 µs]
change: [−0.5696% −0.2057% +0.1352%] (p = 0.26 >
0.05)
No change in performance detected.
Found 8 outliers among 100 measurements (8.00%)
5 (5.00%) high mild
3 (3.00%) high severe
Benchmarking filter context i32 w NULLs low selectivity (kept 1/1024):
Collecting 100 samples in estimated 5.0008 s (16M iterationsfilter context i32
w NULLs low selectivity (kept 1/1024)
time: [310.15 ns 311.84 ns 313.43 ns]
change: [−11.840% −11.364% −10.853%] (p = 0.00 <
0.05)
Performance has improved.
```
# What changes are included in this PR?
There is no need to duplicate the description in the issue here but it
is sometimes worth providing a summary of the individual changes in this
PR.
# Are these changes tested?
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
2. Serve as another way to document the expected behavior of the code
If tests are not included in your PR, please explain why (for example,
are they covered by existing tests)?
# Are there any user-facing changes?
If there are user-facing changes then we may require documentation to be
updated before approving the PR.
If there are any breaking changes to public APIs, please call them out.
---
arrow-select/src/filter.rs | 47 ++++++++++++++++++++++++++++++++++++----------
1 file changed, 37 insertions(+), 10 deletions(-)
diff --git a/arrow-select/src/filter.rs b/arrow-select/src/filter.rs
index 290e3695fd..e0e0fef716 100644
--- a/arrow-select/src/filter.rs
+++ b/arrow-select/src/filter.rs
@@ -529,20 +529,24 @@ fn filter_null_mask(
fn filter_bits(buffer: &BooleanBuffer, predicate: &FilterPredicate) -> Buffer {
let src = buffer.values();
let offset = buffer.offset();
+ assert!(buffer.len() >= predicate.filter.len());
match &predicate.strategy {
IterationStrategy::IndexIterator => {
- let bits = IndexIterator::new(&predicate.filter, predicate.count)
- .map(|src_idx| bit_util::get_bit(src, src_idx + offset));
+ let bits =
+ // SAFETY: IndexIterator uses the filter predicate to derive
indices
+ IndexIterator::new(&predicate.filter,
predicate.count).map(|src_idx| unsafe {
+ bit_util::get_bit_raw(buffer.values().as_ptr(), src_idx +
offset)
+ });
// SAFETY: `IndexIterator` reports its size correctly
unsafe { MutableBuffer::from_trusted_len_iter_bool(bits).into() }
}
IterationStrategy::Indices(indices) => {
- let bits = indices
- .iter()
- .map(|src_idx| bit_util::get_bit(src, *src_idx + offset));
-
+ // SAFETY: indices were derived from the filter predicate
+ let bits = indices.iter().map(|src_idx| unsafe {
+ bit_util::get_bit_raw(buffer.values().as_ptr(), *src_idx +
offset)
+ });
// SAFETY: `Vec::iter()` reports its size correctly
unsafe { MutableBuffer::from_trusted_len_iter_bool(bits).into() }
}
@@ -588,25 +592,30 @@ fn filter_native<T: ArrowNativeType>(values: &[T],
predicate: &FilterPredicate)
IterationStrategy::SlicesIterator => {
let mut buffer = Vec::with_capacity(predicate.count);
for (start, end) in SlicesIterator::new(&predicate.filter) {
- buffer.extend_from_slice(&values[start..end]);
+ // SAFETY: indices were derived from the filter predicate
+ buffer.extend_from_slice(unsafe {
values.get_unchecked(start..end) });
}
buffer.into()
}
IterationStrategy::Slices(slices) => {
let mut buffer = Vec::with_capacity(predicate.count);
for (start, end) in slices {
- buffer.extend_from_slice(&values[*start..*end]);
+ // SAFETY: indices were derived from the filter predicate
+ buffer.extend_from_slice(unsafe {
values.get_unchecked(*start..*end) });
}
buffer.into()
}
IterationStrategy::IndexIterator => {
- let iter = IndexIterator::new(&predicate.filter,
predicate.count).map(|x| values[x]);
+ // SAFETY: indices were derived from the filter predicate
+ let iter = IndexIterator::new(&predicate.filter, predicate.count)
+ .map(|x| unsafe { *values.get_unchecked(x) });
// SAFETY: IndexIterator is trusted length
unsafe { MutableBuffer::from_trusted_len_iter(iter) }.into()
}
IterationStrategy::Indices(indices) => {
- let iter = indices.iter().map(|x| values[*x]);
+ // SAFETY: indices were derived from the filter predicate
+ let iter = indices.iter().map(|x| unsafe {
*values.get_unchecked(*x) });
iter.collect::<Vec<_>>().into()
}
IterationStrategy::All | IterationStrategy::None => unreachable!(),
@@ -2252,4 +2261,22 @@ mod tests {
// The filtered batch should have 2 rows (the 1st and 3rd)
assert_eq!(filtered_batch.num_rows(), 2);
}
+
+ #[test]
+ #[should_panic]
+ fn test_filter_bits_too_large() {
+ let buffer = BooleanBuffer::from(vec![false; 8]);
+ let predicate = BooleanArray::from(vec![true; 9]);
+ let filter = FilterBuilder::new(&predicate).build();
+ filter_bits(&buffer, &filter);
+ }
+
+ #[test]
+ #[should_panic]
+ fn test_filter_native_too_large() {
+ let values = vec![1; 8];
+ let predicate = BooleanArray::from(vec![false; 9]);
+ let filter = FilterBuilder::new(&predicate).build();
+ filter_native(&values, &filter);
+ }
}
