You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "neilconway (via GitHub)" <gi...@apache.org> on 2026/09/25 16:41:13 UTC
[PR] perf: Optimize `array_filter` [datafusion]
neilconway opened a new pull request, #25754:
URL: https://github.com/apache/datafusion/pull/25754
## Which issue does this PR close?
- N/A
## Rationale for this change
After applying the predicate to the input list, `array_filter` has to compute two things: the row offsets for the result list, and the "keep" bitmap to pass to Arrow's `filter` kernel to copy the result values.
When the predicate returned one or more NULLs, the previous implementation computed row offsets with a bit-by-bit loop over the result of applying the predicate, which is relatively slow. We can do better by first converting the predicate result bitmap into the "keep" bitmap (normalizing NULLs to cleared bits), and then using the keep bitmap to compute row offsets. This last step can be done with Arrow's `count_set_bits_offset`, which uses popcount to do outperform a simple bit-by-bit loop.
Along the way, avoid creating two transient copies of the input row offset buffer. The previous code built a vector of adjusted row offsets to account for slicing of the input list; we can instead account for slicing without an additional data structure but instead by subtracting the first offset value from each row offset. This matches how sliced inputs are typically handled elsewhere.
Benchmarks: (M4 Max)
- int32/keep10/no_nulls, 3.383 → 2.505 µs, −26.0%
- int32/keep50/no_nulls, 4.236 → 3.393 µs, −19.9%
- int32/keep90/no_nulls, 4.669 → 3.830 µs, −18.0%
- int32/keep50/null_elements25, 8.406 → 4.430 µs, −47.3%
- int32/keep_null_elements, 4.104 → 3.263 µs, −20.5%
- int32/keep50/null_rows50, 5.427 → 3.458 µs, −36.3%
- int32/keep50/null_rows99, 1.140 → 1.132 µs, −0.7%
- utf8/keep10/no_nulls, 11.246 → 10.390 µs, −7.6%
- utf8/keep50/no_nulls, 19.738 → 18.736 µs, −5.1%
- utf8/keep90/no_nulls, 14.289 → 13.456 µs, −5.8%
- utf8/keep50/null_elements25, 24.502 → 20.354 µs, −16.9%
- utf8/keep_null_elements, 6.838 → 6.032 µs, −11.8%
- utf8/keep50/null_rows50, 13.233 → 11.068 µs, −16.4%
- utf8/keep50/null_rows99, 1.252 → 1.237 µs, −1.2%
- utf8_view/keep10/no_nulls, 6.323 → 6.063 µs, −4.1%
- utf8_view/keep50/no_nulls, 7.173 → 6.990 µs, −2.5%
- utf8_view/keep90/no_nulls, 7.843 → 7.522 µs, −4.1%
- utf8_view/keep50/null_elements25, 11.256 → 7.872 µs, −30.1%
- utf8_view/keep_null_elements, 4.083 → 3.339 µs, −18.2%
- utf8_view/keep50/null_rows50, 6.865 → 5.169 µs, −24.7%
- utf8_view/keep50/null_rows99, 1.239 → 1.224 µs, −1.2%
- utf8/wide_128, 18.384 → 18.013 µs, −2.0%
- utf8/variable_0_to_32, 19.724 → 18.733 µs, −5.0%
- int32/large_1m/null_elements25, 3474.170 → 1067.504 µs, −69.3%
- scalar/true, 0.562 → 0.474 µs, −15.7%*
- scalar/false, 0.704 → 0.630 µs, −10.6%
- scalar/null, 0.727 → 0.653 µs, −10.2%
- int32/keep_all, 4.370 → 2.473 µs, −43.4%
- int32/keep_none, 3.416 → 2.588 µs, −24.2%
- int32/captured_column, 5.917 → 5.229 µs, −11.6%
- int32/keep50/null_rows50/hidden_storage, 6.760 → 4.735 µs, −30.0%
- utf8/sliced, 24.296 → 20.197 µs, −16.9%
- utf8/large_list, 24.351 → 20.462 µs, −16.0%
## What changes are included in this PR?
* Optimize computing row offsets for result, when predicate returns NULLs
* Avoid needless copy/allocation for adjusted input row offsets
* Add fast-paths for when the predicate selects all elements or no elements
* Refactor `List` and `LargeList` into a single implementation, parameterized on offset type
* Add benchmark for `array_filter`
## What is the testing strategy for this PR?
Existing tests pass, test coverage expanded.
## Are there any user-facing changes?
No.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize `array_filter` [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #25754:
URL: https://github.com/apache/datafusion/pull/25754#issuecomment-6189978176
Benchmark for [this request](https://github.com/apache/datafusion/pull/25754#issuecomment-6189926055) failed before finishing (Kubernetes reason: `BackoffLimitExceeded`).
Benchmarks requested: `array_filter`
<details><summary>Runner log (last 40 lines)</summary>
```
2026-10-15T10:29:04.262350Z INFO runner starting benchmark runner bench_type=Datafusion, pr_url=https://github.com/apache/datafusion/pull/25754, benchmarks=array_filter
2026-10-15T10:29:04.336973Z INFO benchmark_controller::runner::bench_datafusion === Cloning PR branch ===
2026-10-15T10:29:04.336992Z INFO benchmark_controller::runner::shell running command cmd=git, args=["clone", "--depth=200", "https://github.com/apache/datafusion.git", "/workspace/datafusion-branch"], cwd="/"
2026-10-15T10:29:09.347408Z INFO benchmark_controller::runner::shell running command cmd=git, args=["fetch", "origin", "refs/pull/25754/head:neilc/refactor-array-filter", "main"], cwd="/workspace/datafusion-branch"
2026-10-15T10:29:29.354183Z INFO benchmark_controller::runner::shell running command cmd=git, args=["checkout", "neilc/refactor-array-filter"], cwd="/workspace/datafusion-branch"
2026-10-15T10:29:34.355484Z INFO benchmark_controller::runner::shell running command cmd=git, args=["merge-base", "HEAD", "origin/main"], cwd="/workspace/datafusion-branch"
2026-10-15T10:29:39.357834Z ERROR runner benchmark failed error=git merge-base: git merge-base HEAD origin/main exited with code 1
stdout:
stderr:
```
</details>
<details><summary>Kubernetes message</summary>
```
Job has reached the specified backoff limit
```
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize `array_filter` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on code in PR #25754:
URL: https://github.com/apache/datafusion/pull/25754#discussion_r4284866860
##########
datafusion/functions-nested/src/utils.rs:
##########
@@ -529,6 +579,59 @@ pub(crate) mod tests {
use arrow::datatypes::Int64Type;
use datafusion_common::utils::SingleRowListArrayBuilder;
+ /// Compare `prepare_list_filter` with a per-row reference on a sliced list
+ /// with the given row lengths and validity, returning the input and output
+ /// bitmaps so callers can check whether the input was reused.
+ fn check_list_filter<O: OffsetSizeTrait>(
+ lengths: [usize; 8],
+ valid: [bool; 8],
+ ) -> (BooleanBuffer, BooleanBuffer) {
+ let list = GenericListArray::<O>::new(
+ Arc::new(Field::new_list_field(DataType::Int32, true)),
+ OffsetBuffer::from_lengths(lengths),
+ // The helper must permit selecting NULL elements.
+ arrow::array::new_null_array(&DataType::Int32, lengths.iter().sum()),
+ Some(NullBuffer::from(valid.to_vec())),
+ )
+ .slice(1, 7);
+ let (first, len) = offset_span(list.offsets());
+ // Use an offset that is not a multiple of the bitmap's three-bit period.
+ let keep = BooleanBuffer::collect_bool(len + 1, |i| i % 3 != 0).slice(1, len);
+ let mut expected = keep.iter().collect::<Vec<_>>();
+ let mut expected_offsets = vec![0];
+ for (row, window) in list.offsets().windows(2).enumerate() {
+ let start = window[0].as_usize() - first;
+ let end = window[1].as_usize() - first;
+ if list.is_null(row) {
+ expected[start..end].fill(false);
+ }
+ expected_offsets.push(expected[..end].iter().filter(|&&v| v).count());
+ }
+ let (offsets, mask) = prepare_list_filter(&list, &keep);
+ assert_eq!(mask.iter().collect::<Vec<_>>(), expected);
+ assert_eq!(
+ offsets.iter().map(|o| o.as_usize()).collect::<Vec<_>>(),
+ expected_offsets
+ );
+ (keep, mask)
+ }
+
+ #[test]
+ fn list_filter_mask_handles_slices_and_hidden_elements() {
+ let valid = [true, false, true, false, false, true, true, false];
+ // After slicing off the first row: an empty NULL row, a NULL row storing
+ // an element after a valid row, consecutive NULL rows, and a trailing one.
+ let hidden = [2, 0, 2, 1, 2, 0, 3, 2];
Review Comment:
Good idea, thanks! Done.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize `array_filter` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on code in PR #25754:
URL: https://github.com/apache/datafusion/pull/25754#discussion_r4289998528
##########
datafusion/functions-nested/src/array_filter.rs:
##########
@@ -408,7 +382,103 @@ mod tests {
lit(true),
)
.unwrap();
- assert_eq!(res.as_list::<i32>(), &list);
+ assert_reuses_input(res.as_list::<i32>(), &list);
+ }
+
+ #[test]
+ fn filter_sliced_null_elements_and_rows() {
Review Comment:
Thanks! Added.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize `array_filter` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on code in PR #25754:
URL: https://github.com/apache/datafusion/pull/25754#discussion_r4290032980
##########
datafusion/functions-nested/src/utils.rs:
##########
@@ -50,6 +50,103 @@ pub(crate) fn empty_list_values<O: OffsetSizeTrait>(
))
}
+/// Build result row offsets and exclude elements stored under NULL list rows.
+///
+/// `keep` is a bitmap identifying which elements in the list's visible span
+/// should be preserved. The returned bitmap uses the same indexing, with bits
+/// for NULL list rows cleared. Selected elements may themselves be NULL; their
+/// validity is the caller's responsibility when copying values.
+pub(crate) fn prepare_list_filter<O: OffsetSizeTrait>(
+ list: &GenericListArray<O>,
+ keep: &BooleanBuffer,
+) -> (OffsetBuffer<O>, BooleanBuffer) {
+ let list_offsets = list.offsets();
+ let (first_offset, span_len) = offset_span(list_offsets);
+ debug_assert_eq!(keep.len(), span_len);
+ let mut offsets = Vec::with_capacity(list.len() + 1);
+ offsets.push(O::zero());
+ let mut kept_count = 0;
+ // Count the set bits before each row end in one pass over `keep`, which
+ // stays cheap for short rows.
+ let mut set_bits = SetBitCounter::new(keep.bit_chunks().iter_padded());
+ // Set bits stored under NULL rows, which the result does not keep.
+ let mut hidden_count = 0;
+ // NULL list rows are usually empty, so reuse `keep` until a NULL row stores
+ // elements. Copy the bits of the preceding rows when that first happens.
+ let mut keep_mask: Option<BooleanBufferBuilder> = None;
+ for (row, window) in list_offsets.windows(2).enumerate() {
Review Comment:
Thanks for the suggestion! Splitting out the no-NULL-row case gives some nice wins: narrow_2 −40%, keep_all −24% and keep10 −20%.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize `array_filter` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on code in PR #25754:
URL: https://github.com/apache/datafusion/pull/25754#discussion_r4284912649
##########
datafusion/functions-nested/benches/array_filter.rs:
##########
@@ -0,0 +1,371 @@
+// 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.
+
+use std::{hint::black_box, sync::Arc};
+
+use arrow::array::{
+ Array, ArrayRef, Int32Array, ListArray, RecordBatch, StringArray, StringViewArray,
+ UInt64Array,
+};
+use arrow::buffer::{NullBuffer, OffsetBuffer};
+use arrow::compute::{cast, take};
+use arrow::datatypes::{DataType, Field, Schema};
+use criterion::{Criterion, SamplingMode, criterion_group, criterion_main};
+use datafusion_common::{DFSchema, ScalarValue};
+use datafusion_expr::{
+ Expr, col, execution_props::ExecutionProps, expr::LambdaVariable, lambda, lit,
+ physical_planning_context::PhysicalPlanningContext,
+};
+use datafusion_functions_nested::expr_fn::array_filter;
+use datafusion_physical_expr::create_physical_expr;
+use rand::{Rng, SeedableRng, rngs::StdRng};
+
+// Inputs are built by hand rather than from SQL literals so the bench can cover
+// sliced arrays and elements stored under NULL list rows.
+// Defaults: 256 rows of 16 elements, seeded random values, no NULL list rows.
+struct Case {
+ kind: DataType,
+ rows: usize,
+ width: usize,
+ element_nulls: f64,
+ row_nulls: f64,
+ // NULL list rows keep their elements, which evaluation must strip.
+ hidden_storage: bool,
+ predicate: Predicate,
+ variable: bool,
+ sliced: bool,
+ large_list: bool,
+}
+
+#[derive(Clone, Copy)]
+enum Predicate {
+ LessThan(i32),
+ Scalar(Option<bool>),
+ IsNull,
+ Captured,
+}
+
+impl Default for Case {
+ fn default() -> Self {
+ Self {
+ kind: DataType::Int32,
+ rows: 256,
+ width: 16,
+ element_nulls: 0.0,
+ row_nulls: 0.0,
+ hidden_storage: false,
+ predicate: Predicate::LessThan(50),
+ variable: false,
+ sliced: false,
+ large_list: false,
+ }
+ }
+}
+
+fn string_value(value: i32) -> String {
+ format!("{value:03}-array-filter-value")
+}
+
+// Evaluate a planned projection, including lambda evaluation, on an in-memory
+// batch. Constructing inputs and planning are outside the timed loop.
+fn bench_case(c: &mut Criterion, name: &str, case: &Case) {
+ let mut rng = StdRng::seed_from_u64(42);
+ let row_valid = (0..case.rows)
+ .map(|_| !rng.random_bool(case.row_nulls))
+ .collect::<Vec<_>>();
+ let lengths = (0..case.rows)
+ .map(|row| {
+ if !row_valid[row] && !case.hidden_storage {
+ 0
+ } else if case.variable {
+ (row * 17) % (2 * case.width + 1)
+ } else {
+ case.width
+ }
+ })
+ .collect::<Vec<_>>();
+ let values = (0..lengths.iter().sum())
+ .map(|_| {
+ let value = rng.random_range(0..100);
+ (!rng.random_bool(case.element_nulls)).then_some(value)
+ })
+ .collect::<Vec<_>>();
+ let elements: ArrayRef = match case.kind {
+ DataType::Int32 => Arc::new(Int32Array::from(values.clone())),
+ DataType::Utf8 => Arc::new(StringArray::from_iter(
+ values.iter().map(|v| v.map(string_value)),
+ )),
+ DataType::Utf8View => Arc::new(StringViewArray::from_iter(
+ values.iter().map(|v| v.map(string_value)),
+ )),
+ _ => unreachable!(),
+ };
+ let row_nulls = (case.row_nulls != 0.0).then(|| NullBuffer::from(row_valid.clone()));
+ let field = Arc::new(Field::new_list_field(case.kind.clone(), true));
+ let list = ListArray::new(
+ Arc::clone(&field),
+ OffsetBuffer::from_lengths(lengths),
+ Arc::clone(&elements),
+ row_nulls,
+ );
+ let list = if case.sliced {
+ list.slice(1, case.rows - 2)
+ } else {
+ list
+ };
+ let first_row = usize::from(case.sliced);
+ let thresholds = (first_row..first_row + list.len())
+ .map(|row| (row % 100) as i32)
+ .collect::<Vec<_>>();
+
+ // Independently check logical output before timing, including NULL elements
+ // deliberately retained by IS NULL and values hidden by NULL list rows.
+ let mut selected = Vec::new();
+ let mut result_lengths = Vec::new();
+ for (row, offsets) in list.offsets().windows(2).enumerate() {
+ let before = selected.len();
+ if row_valid[first_row + row] {
+ let (start, end) = (offsets[0] as usize, offsets[1] as usize);
+ for (index, value) in (start..).zip(&values[start..end]) {
+ let keep = match case.predicate {
+ Predicate::LessThan(limit) => value.is_some_and(|v| v < limit),
+ Predicate::Scalar(value) => value == Some(true),
+ Predicate::IsNull => value.is_none(),
+ Predicate::Captured => value.is_some_and(|v| v < thresholds[row]),
+ };
+ if keep {
+ selected.push(index as u64);
+ }
+ }
+ }
+ result_lengths.push(selected.len() - before);
+ }
+ let expected = ListArray::new(
+ Arc::clone(&field),
+ OffsetBuffer::<i32>::from_lengths(result_lengths),
+ take(elements.as_ref(), &UInt64Array::from(selected), None).unwrap(),
+ list.nulls().cloned(),
+ );
+ let mut input = Arc::new(list) as ArrayRef;
+ let mut expected = Arc::new(expected) as ArrayRef;
+ if case.large_list {
+ let data_type = DataType::LargeList(Arc::clone(&field));
+ input = cast(&input, &data_type).unwrap();
+ expected = cast(&expected, &data_type).unwrap();
+ }
+ let schema = Arc::new(Schema::new(vec![
+ Field::new("list", input.data_type().clone(), true),
+ Field::new("threshold", DataType::Int32, false),
+ ]));
+ let batch = RecordBatch::try_new(
+ Arc::clone(&schema),
+ vec![input, Arc::new(Int32Array::from(thresholds))],
+ )
+ .unwrap();
+ let v = Expr::LambdaVariable(LambdaVariable::new("v".into(), Some(field)));
+ let body = match case.predicate {
+ Predicate::LessThan(limit) => {
+ let limit = if case.kind == DataType::Int32 {
+ lit(limit)
+ } else {
+ lit(ScalarValue::new_utf8(string_value(limit))
+ .cast_to(&case.kind)
+ .unwrap())
+ };
+ v.lt(limit)
+ }
+ Predicate::Scalar(value) => lit(ScalarValue::Boolean(value)),
+ Predicate::IsNull => v.is_null(),
+ Predicate::Captured => v.lt(col("threshold")),
+ };
+ let expression = create_physical_expr(
+ &array_filter(col("list"), lambda(["v"], body)),
+ &DFSchema::try_from(schema).unwrap(),
+ &ExecutionProps::new(),
+ &PhysicalPlanningContext::default(),
+ )
+ .unwrap();
+ let output = expression
+ .evaluate(&batch)
+ .unwrap()
+ .into_array(batch.num_rows())
+ .unwrap();
+ assert_eq!(output.as_ref(), expected.as_ref(), "{name}");
+ output.to_data().validate_full().unwrap();
+
+ let mut group = c.benchmark_group("array_filter");
+ group.sampling_mode(SamplingMode::Flat);
+ group.bench_function(name, |b| {
+ b.iter(|| black_box(expression.evaluate(black_box(&batch)).unwrap()))
+ });
+ group.finish();
+}
+
+fn criterion_benchmark(c: &mut Criterion) {
+ for (kind, name) in [
+ (DataType::Int32, "int32"),
+ (DataType::Utf8, "utf8"),
+ (DataType::Utf8View, "utf8_view"),
+ ] {
+ for keep in [10, 50, 90] {
+ bench_case(
+ c,
+ &format!("{name}/keep{keep}/no_nulls"),
+ &Case {
+ kind: kind.clone(),
+ predicate: Predicate::LessThan(keep),
+ ..Case::default()
+ },
+ );
+ }
+ // 25% NULL elements make comparison results nullable. Half of the
+ // remaining elements pass, so approximately 37.5% of all slots survive.
+ bench_case(
+ c,
+ &format!("{name}/keep50/null_elements25"),
+ &Case {
+ kind: kind.clone(),
+ element_nulls: 0.25,
+ ..Case::default()
+ },
+ );
+ // IS NULL is cheap to evaluate, so list reconstruction dominates.
+ bench_case(
+ c,
+ &format!("{name}/keep_null_elements"),
+ &Case {
+ kind: kind.clone(),
+ predicate: Predicate::IsNull,
+ element_nulls: 0.25,
+ ..Case::default()
+ },
+ );
+ for percent in [50, 99] {
+ bench_case(
+ c,
+ &format!("{name}/keep50/null_rows{percent}"),
+ &Case {
+ kind: kind.clone(),
+ row_nulls: f64::from(percent) / 100.0,
+ element_nulls: 0.25,
+ ..Case::default()
+ },
+ );
+ }
+ }
+ for (name, case) in [
Review Comment:
Good idea! I added this benchmark. The results here suggested that Arrow's `count_set_bits_offset` has some setup overhead that hurts for small inputs; I switched instead to a small helper that does the set-bit counting that we need in a single pass. Happily this seems slightly faster than the `count_set_bits_offset` across the board.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize `array_filter` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on code in PR #25754:
URL: https://github.com/apache/datafusion/pull/25754#discussion_r4295129121
##########
datafusion/functions-nested/src/utils.rs:
##########
@@ -529,6 +626,79 @@ pub(crate) mod tests {
use arrow::datatypes::Int64Type;
use datafusion_common::utils::SingleRowListArrayBuilder;
+ /// Compare `prepare_list_filter` with a per-row reference on a sliced list
+ /// with the given row lengths and validity, returning the input and output
+ /// bitmaps so callers can check whether the input was reused.
+ fn check_list_filter<O: OffsetSizeTrait>(
Review Comment:
Thanks, fixed!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize `array_filter` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on PR #25754:
URL: https://github.com/apache/datafusion/pull/25754#issuecomment-6195679079
Thanks for the review, @kosiew !
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize `array_filter` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on PR #25754:
URL: https://github.com/apache/datafusion/pull/25754#issuecomment-6216492510
@comphead Thanks for the review!
I fixed the bench capacity nit you mentioned. Good point about possibly using `SetBitCounter` in `array_compact`; I'll take a look at that as a possible followup PR.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize `array_filter` [datafusion]
Posted by "kosiew (via GitHub)" <gi...@apache.org>.
kosiew commented on PR #25754:
URL: https://github.com/apache/datafusion/pull/25754#issuecomment-6190093882
run benchmark array_filter
```yaml
baseline:
ref: "f721b9567f"
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize `array_filter` [datafusion]
Posted by "comphead (via GitHub)" <gi...@apache.org>.
comphead commented on code in PR #25754:
URL: https://github.com/apache/datafusion/pull/25754#discussion_r4285410058
##########
datafusion/functions-nested/src/utils.rs:
##########
@@ -50,6 +50,103 @@ pub(crate) fn empty_list_values<O: OffsetSizeTrait>(
))
}
+/// Build result row offsets and exclude elements stored under NULL list rows.
+///
+/// `keep` is a bitmap identifying which elements in the list's visible span
+/// should be preserved. The returned bitmap uses the same indexing, with bits
+/// for NULL list rows cleared. Selected elements may themselves be NULL; their
+/// validity is the caller's responsibility when copying values.
+pub(crate) fn prepare_list_filter<O: OffsetSizeTrait>(
+ list: &GenericListArray<O>,
+ keep: &BooleanBuffer,
+) -> (OffsetBuffer<O>, BooleanBuffer) {
+ let list_offsets = list.offsets();
+ let (first_offset, span_len) = offset_span(list_offsets);
+ debug_assert_eq!(keep.len(), span_len);
+ let mut offsets = Vec::with_capacity(list.len() + 1);
+ offsets.push(O::zero());
+ let mut kept_count = 0;
+ // Count the set bits before each row end in one pass over `keep`, which
+ // stays cheap for short rows.
+ let mut set_bits = SetBitCounter::new(keep.bit_chunks().iter_padded());
+ // Set bits stored under NULL rows, which the result does not keep.
+ let mut hidden_count = 0;
+ // NULL list rows are usually empty, so reuse `keep` until a NULL row stores
+ // elements. Copy the bits of the preceding rows when that first happens.
+ let mut keep_mask: Option<BooleanBufferBuilder> = None;
+ for (row, window) in list_offsets.windows(2).enumerate() {
Review Comment:
Optional and not measured. `narrow_2` gains 16% where the 16-wide case with the same NULL density gains 43%, so per-row bookkeeping looks like what remains. When `list.null_count() == 0` there are no hidden elements, so `list.is_valid(row)`, `hidden_count` and `keep_mask` do nothing and the loop is one `set_bits.count_before(end)` per row with `keep` returned as is. Splitting that case out would also keep the common path short. Worth a quick try on `narrow_2` before deciding.
##########
datafusion/functions-nested/src/utils.rs:
##########
@@ -50,6 +50,103 @@ pub(crate) fn empty_list_values<O: OffsetSizeTrait>(
))
}
+/// Build result row offsets and exclude elements stored under NULL list rows.
+///
+/// `keep` is a bitmap identifying which elements in the list's visible span
+/// should be preserved. The returned bitmap uses the same indexing, with bits
+/// for NULL list rows cleared. Selected elements may themselves be NULL; their
+/// validity is the caller's responsibility when copying values.
+pub(crate) fn prepare_list_filter<O: OffsetSizeTrait>(
+ list: &GenericListArray<O>,
+ keep: &BooleanBuffer,
+) -> (OffsetBuffer<O>, BooleanBuffer) {
+ let list_offsets = list.offsets();
+ let (first_offset, span_len) = offset_span(list_offsets);
+ debug_assert_eq!(keep.len(), span_len);
+ let mut offsets = Vec::with_capacity(list.len() + 1);
+ offsets.push(O::zero());
+ let mut kept_count = 0;
+ // Count the set bits before each row end in one pass over `keep`, which
+ // stays cheap for short rows.
+ let mut set_bits = SetBitCounter::new(keep.bit_chunks().iter_padded());
+ // Set bits stored under NULL rows, which the result does not keep.
+ let mut hidden_count = 0;
+ // NULL list rows are usually empty, so reuse `keep` until a NULL row stores
+ // elements. Copy the bits of the preceding rows when that first happens.
+ let mut keep_mask: Option<BooleanBufferBuilder> = None;
+ for (row, window) in list_offsets.windows(2).enumerate() {
+ let start = window[0].as_usize() - first_offset;
+ let end = window[1].as_usize() - first_offset;
+ let len = end - start;
+ let bit_start = keep.offset() + start;
+ if list.is_valid(row) {
+ kept_count = set_bits.count_before(end) - hidden_count;
+ if let Some(keep_mask) = &mut keep_mask {
+ keep_mask.append_packed_range(bit_start..bit_start + len, keep.values());
+ }
+ } else if len != 0 {
+ let set_before_row = set_bits.count_before(start);
+ hidden_count += set_bits.count_before(end) - set_before_row;
+ keep_mask
+ .get_or_insert_with(|| {
+ let mut builder = BooleanBufferBuilder::new(keep.len());
+ builder.append_packed_range(keep.offset()..bit_start, keep.values());
+ builder
+ })
+ .append_n(len, false);
+ }
+ offsets.push(O::usize_as(kept_count));
+ }
+ let keep_mask = keep_mask
+ .map(BooleanBufferBuilder::build)
+ .unwrap_or_else(|| keep.clone());
+ debug_assert_eq!(keep_mask.len(), keep.len());
+ // SAFETY: offsets start at zero and `kept_count` never decreases. The count
+ // cannot exceed the input's element span, which fits in `O`, so converting
+ // it to `O` cannot overflow.
+ let offsets = unsafe { OffsetBuffer::new_unchecked(offsets.into()) };
Review Comment:
`array_compact` builds the same kind of offsets with the checked `OffsetBuffer::new` and keeps `unsafe` for the UTF-8 byte copy. Here the checked constructor is one linear scan over `list.len() + 1` offsets. Is the unchecked version measurably faster on `int32/narrow_2/null_elements25`, where per-row cost is highest? If it is within noise, I would use `OffsetBuffer::new` and drop the `unsafe` block and its SAFETY comment.
##########
datafusion/functions-nested/src/utils.rs:
##########
@@ -529,6 +626,79 @@ pub(crate) mod tests {
use arrow::datatypes::Int64Type;
use datafusion_common::utils::SingleRowListArrayBuilder;
+ /// Compare `prepare_list_filter` with a per-row reference on a sliced list
+ /// with the given row lengths and validity, returning the input and output
+ /// bitmaps so callers can check whether the input was reused.
+ fn check_list_filter<O: OffsetSizeTrait>(
Review Comment:
`check_list_filter` is a good oracle but it runs four fixed shapes. The logic is stateful across rows (word crossings, the first hidden row triggering the lazy copy, `hidden_count` carried forward), so a seeded loop over random row lengths (0 to about 130), validity, `keep` density and slice `(offset, len)` against the same reference, for `i32` and `i64`, would reach orderings these arrays cannot. `rand` is already a dev-dependency of this crate.
##########
datafusion/functions-nested/src/array_filter.rs:
##########
@@ -408,7 +382,103 @@ mod tests {
lit(true),
)
.unwrap();
- assert_eq!(res.as_list::<i32>(), &list);
+ assert_reuses_input(res.as_list::<i32>(), &list);
+ }
+
+ #[test]
+ fn filter_sliced_null_elements_and_rows() {
Review Comment:
Missing case: a predicate that selects only elements stored under a NULL row, for example `[[1, 2], NULL (stores 99, 100), [3]]` with `v > 50`. `keep` then has set bits but `kept_count` is 0, so `filter_list` returns through `empty_list_values` after `hidden_count` was subtracted. Neither this test nor `filter_does_not_copy_values_underlying_null_rows` leaves the result empty while a NULL row holds passing values. A second case where every visible element passes but a NULL row stores elements would pin that the early `original_list` return is not taken (`kept_count < flattened_values.len()`).
##########
datafusion/functions-nested/src/lambda_utils.rs:
##########
@@ -152,12 +151,10 @@ impl EvaluatedListLambda {
self.original_list.nulls()
}
- pub(crate) fn row_range(&self, i: usize) -> (usize, usize) {
- (self.row_offsets[i], self.row_offsets[i + 1])
- }
-
- pub(crate) fn adjusted_offsets<O: OffsetSizeTrait>(&self) -> OffsetBuffer<O> {
- OffsetBuffer::from_lengths(self.row_offsets.windows(2).map(|w| w[1] - w[0]))
+ /// Row boundaries within `flattened_values`, including the elements that
+ /// NULL rows store. Functions that walk elements row by row compute this once.
+ pub(crate) fn row_offsets(&self) -> Result<Vec<usize>> {
+ adjusted_row_offsets(&self.original_list)
Review Comment:
`array_first` and `array_any_match` still pay for the two copies this PR removes from `array_filter`. `adjusted_row_offsets` calls `adjust_offsets_for_slice`, which builds an adjusted `OffsetBuffer`, and then `collect()` copies it again into a `Vec<usize>`. Mapping the original offsets minus the first one straight into the `Vec<usize>` would leave one allocation.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize `array_filter` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on PR #25754:
URL: https://github.com/apache/datafusion/pull/25754#issuecomment-5836045988
FYI @saadtajwar @comphead
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize `array_filter` [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #25754:
URL: https://github.com/apache/datafusion/pull/25754#issuecomment-6190168248
🤖 Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/25754#issuecomment-6190093882)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c6190093882-3437-h222x 6.12.94+ #1 SMP Fri Aug 21 08:00:16 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
Comparing neilc/refactor-array-filter (39d794dc7ebe67c7b226f9014bb1c0d661c2bccc) to f721b9567f [diff](https://github.com/apache/datafusion/compare/f721b9567f086800f576de213eeca297eadfeb29..39d794dc7ebe67c7b226f9014bb1c0d661c2bccc)
<details><summary>Run configuration</summary>
```yaml
run benchmark array_filter
baseline:
ref: "f721b9567f"
```
</details>
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize `array_filter` [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #25754:
URL: https://github.com/apache/datafusion/pull/25754#issuecomment-6195859427
🤖 Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/25754#issuecomment-6195802799)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c6195802799-3467-pzd66 6.12.94+ #1 SMP Fri Aug 21 08:00:16 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
Comparing neilc/refactor-array-filter (021c8fd889245f56eaf8f28d9884e76f4bfe0536) to f721b9567f [diff](https://github.com/apache/datafusion/compare/f721b9567f086800f576de213eeca297eadfeb29..021c8fd889245f56eaf8f28d9884e76f4bfe0536)
<details><summary>Run configuration</summary>
```yaml
run benchmark array_filter
baseline:
ref: "f721b9567f"
```
</details>
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize `array_filter` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on PR #25754:
URL: https://github.com/apache/datafusion/pull/25754#issuecomment-6195802799
run benchmark array_filter
```yaml
baseline:
ref: "f721b9567f"
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize `array_filter` [datafusion]
Posted by "kosiew (via GitHub)" <gi...@apache.org>.
kosiew commented on PR #25754:
URL: https://github.com/apache/datafusion/pull/25754#issuecomment-6189926055
run benchmark array_filter
```yaml
baseline:
ref: "f721b9567f"
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize `array_filter` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on PR #25754:
URL: https://github.com/apache/datafusion/pull/25754#issuecomment-5835996622
This could be refactored to share some code with `array_compact` (e.g., computing result row offsets from the validity bitmap), but when I tried that, it was hard to get optimal performance for both call-sites, so I'll defer that for now.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize `array_filter` [datafusion]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #25754:
URL: https://github.com/apache/datafusion/pull/25754#issuecomment-5836365933
## [Codecov](https://app.codecov.io/gh/apache/datafusion/pull/25754?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
:x: Patch coverage is `97.27273%` with `6 lines` in your changes missing coverage. Please review.
:white_check_mark: Project coverage is 82.50%. Comparing base ([`5719930`](https://app.codecov.io/gh/apache/datafusion/commit/5719930666fb590b318cd286cbb00cc473efe244?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`b182159`](https://app.codecov.io/gh/apache/datafusion/commit/b182159343c42e3b2426d711503bce3920cedceb?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
:warning: Report is 2 commits behind head on main.
| [Files with missing lines](https://app.codecov.io/gh/apache/datafusion/pull/25754?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
|---|---|---|
| [datafusion/functions-nested/src/array\_filter.rs](https://app.codecov.io/gh/apache/datafusion/pull/25754?src=pr&el=tree&filepath=datafusion%2Ffunctions-nested%2Fsrc%2Farray_filter.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9mdW5jdGlvbnMtbmVzdGVkL3NyYy9hcnJheV9maWx0ZXIucnM=) | 96.96% | [1 Missing and 3 partials :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/25754?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [datafusion/functions-nested/src/array\_any\_match.rs](https://app.codecov.io/gh/apache/datafusion/pull/25754?src=pr&el=tree&filepath=datafusion%2Ffunctions-nested%2Fsrc%2Farray_any_match.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9mdW5jdGlvbnMtbmVzdGVkL3NyYy9hcnJheV9hbnlfbWF0Y2gucnM=) | 66.66% | [0 Missing and 1 partial :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/25754?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [datafusion/functions-nested/src/array\_first.rs](https://app.codecov.io/gh/apache/datafusion/pull/25754?src=pr&el=tree&filepath=datafusion%2Ffunctions-nested%2Fsrc%2Farray_first.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9mdW5jdGlvbnMtbmVzdGVkL3NyYy9hcnJheV9maXJzdC5ycw==) | 80.00% | [0 Missing and 1 partial :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/25754?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## main #25754 +/- ##
========================================
Coverage 82.49% 82.50%
========================================
Files 1140 1140
Lines 438499 438664 +165
Branches 438499 438664 +165
========================================
+ Hits 361754 361907 +153
- Misses 54873 54876 +3
- Partials 21872 21881 +9
```
</details>
[:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/datafusion/pull/25754?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
<details><summary> :rocket: New features to boost your workflow: </summary>
- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
- :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize `array_filter` [datafusion]
Posted by "kosiew (via GitHub)" <gi...@apache.org>.
kosiew commented on code in PR #25754:
URL: https://github.com/apache/datafusion/pull/25754#discussion_r4282017165
##########
datafusion/functions-nested/src/utils.rs:
##########
@@ -529,6 +579,59 @@ pub(crate) mod tests {
use arrow::datatypes::Int64Type;
use datafusion_common::utils::SingleRowListArrayBuilder;
+ /// Compare `prepare_list_filter` with a per-row reference on a sliced list
+ /// with the given row lengths and validity, returning the input and output
+ /// bitmaps so callers can check whether the input was reused.
+ fn check_list_filter<O: OffsetSizeTrait>(
+ lengths: [usize; 8],
+ valid: [bool; 8],
+ ) -> (BooleanBuffer, BooleanBuffer) {
+ let list = GenericListArray::<O>::new(
+ Arc::new(Field::new_list_field(DataType::Int32, true)),
+ OffsetBuffer::from_lengths(lengths),
+ // The helper must permit selecting NULL elements.
+ arrow::array::new_null_array(&DataType::Int32, lengths.iter().sum()),
+ Some(NullBuffer::from(valid.to_vec())),
+ )
+ .slice(1, 7);
+ let (first, len) = offset_span(list.offsets());
+ // Use an offset that is not a multiple of the bitmap's three-bit period.
+ let keep = BooleanBuffer::collect_bool(len + 1, |i| i % 3 != 0).slice(1, len);
+ let mut expected = keep.iter().collect::<Vec<_>>();
+ let mut expected_offsets = vec![0];
+ for (row, window) in list.offsets().windows(2).enumerate() {
+ let start = window[0].as_usize() - first;
+ let end = window[1].as_usize() - first;
+ if list.is_null(row) {
+ expected[start..end].fill(false);
+ }
+ expected_offsets.push(expected[..end].iter().filter(|&&v| v).count());
+ }
+ let (offsets, mask) = prepare_list_filter(&list, &keep);
+ assert_eq!(mask.iter().collect::<Vec<_>>(), expected);
+ assert_eq!(
+ offsets.iter().map(|o| o.as_usize()).collect::<Vec<_>>(),
+ expected_offsets
+ );
+ (keep, mask)
+ }
+
+ #[test]
+ fn list_filter_mask_handles_slices_and_hidden_elements() {
+ let valid = [true, false, true, false, false, true, true, false];
+ // After slicing off the first row: an empty NULL row, a NULL row storing
+ // an element after a valid row, consecutive NULL rows, and a trailing one.
+ let hidden = [2, 0, 2, 1, 2, 0, 3, 2];
Review Comment:
Could we add a test case that crosses 64-bit bitmap boundaries for both offset types? For example, lengths `[2, 0, 63, 65, 64, 0, 65, 2]` with the existing validity array would exercise sliced bitmaps and hidden elements across word boundaries. The current cases cover only short bitmaps, so this would give us more confidence in the packed range copying.
##########
datafusion/functions-nested/benches/array_filter.rs:
##########
@@ -0,0 +1,371 @@
+// 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.
+
+use std::{hint::black_box, sync::Arc};
+
+use arrow::array::{
+ Array, ArrayRef, Int32Array, ListArray, RecordBatch, StringArray, StringViewArray,
+ UInt64Array,
+};
+use arrow::buffer::{NullBuffer, OffsetBuffer};
+use arrow::compute::{cast, take};
+use arrow::datatypes::{DataType, Field, Schema};
+use criterion::{Criterion, SamplingMode, criterion_group, criterion_main};
+use datafusion_common::{DFSchema, ScalarValue};
+use datafusion_expr::{
+ Expr, col, execution_props::ExecutionProps, expr::LambdaVariable, lambda, lit,
+ physical_planning_context::PhysicalPlanningContext,
+};
+use datafusion_functions_nested::expr_fn::array_filter;
+use datafusion_physical_expr::create_physical_expr;
+use rand::{Rng, SeedableRng, rngs::StdRng};
+
+// Inputs are built by hand rather than from SQL literals so the bench can cover
+// sliced arrays and elements stored under NULL list rows.
+// Defaults: 256 rows of 16 elements, seeded random values, no NULL list rows.
+struct Case {
+ kind: DataType,
+ rows: usize,
+ width: usize,
+ element_nulls: f64,
+ row_nulls: f64,
+ // NULL list rows keep their elements, which evaluation must strip.
+ hidden_storage: bool,
+ predicate: Predicate,
+ variable: bool,
+ sliced: bool,
+ large_list: bool,
+}
+
+#[derive(Clone, Copy)]
+enum Predicate {
+ LessThan(i32),
+ Scalar(Option<bool>),
+ IsNull,
+ Captured,
+}
+
+impl Default for Case {
+ fn default() -> Self {
+ Self {
+ kind: DataType::Int32,
+ rows: 256,
+ width: 16,
+ element_nulls: 0.0,
+ row_nulls: 0.0,
+ hidden_storage: false,
+ predicate: Predicate::LessThan(50),
+ variable: false,
+ sliced: false,
+ large_list: false,
+ }
+ }
+}
+
+fn string_value(value: i32) -> String {
+ format!("{value:03}-array-filter-value")
+}
+
+// Evaluate a planned projection, including lambda evaluation, on an in-memory
+// batch. Constructing inputs and planning are outside the timed loop.
+fn bench_case(c: &mut Criterion, name: &str, case: &Case) {
+ let mut rng = StdRng::seed_from_u64(42);
+ let row_valid = (0..case.rows)
+ .map(|_| !rng.random_bool(case.row_nulls))
+ .collect::<Vec<_>>();
+ let lengths = (0..case.rows)
+ .map(|row| {
+ if !row_valid[row] && !case.hidden_storage {
+ 0
+ } else if case.variable {
+ (row * 17) % (2 * case.width + 1)
+ } else {
+ case.width
+ }
+ })
+ .collect::<Vec<_>>();
+ let values = (0..lengths.iter().sum())
+ .map(|_| {
+ let value = rng.random_range(0..100);
+ (!rng.random_bool(case.element_nulls)).then_some(value)
+ })
+ .collect::<Vec<_>>();
+ let elements: ArrayRef = match case.kind {
+ DataType::Int32 => Arc::new(Int32Array::from(values.clone())),
+ DataType::Utf8 => Arc::new(StringArray::from_iter(
+ values.iter().map(|v| v.map(string_value)),
+ )),
+ DataType::Utf8View => Arc::new(StringViewArray::from_iter(
+ values.iter().map(|v| v.map(string_value)),
+ )),
+ _ => unreachable!(),
+ };
+ let row_nulls = (case.row_nulls != 0.0).then(|| NullBuffer::from(row_valid.clone()));
+ let field = Arc::new(Field::new_list_field(case.kind.clone(), true));
+ let list = ListArray::new(
+ Arc::clone(&field),
+ OffsetBuffer::from_lengths(lengths),
+ Arc::clone(&elements),
+ row_nulls,
+ );
+ let list = if case.sliced {
+ list.slice(1, case.rows - 2)
+ } else {
+ list
+ };
+ let first_row = usize::from(case.sliced);
+ let thresholds = (first_row..first_row + list.len())
+ .map(|row| (row % 100) as i32)
+ .collect::<Vec<_>>();
+
+ // Independently check logical output before timing, including NULL elements
+ // deliberately retained by IS NULL and values hidden by NULL list rows.
+ let mut selected = Vec::new();
+ let mut result_lengths = Vec::new();
+ for (row, offsets) in list.offsets().windows(2).enumerate() {
+ let before = selected.len();
+ if row_valid[first_row + row] {
+ let (start, end) = (offsets[0] as usize, offsets[1] as usize);
+ for (index, value) in (start..).zip(&values[start..end]) {
+ let keep = match case.predicate {
+ Predicate::LessThan(limit) => value.is_some_and(|v| v < limit),
+ Predicate::Scalar(value) => value == Some(true),
+ Predicate::IsNull => value.is_none(),
+ Predicate::Captured => value.is_some_and(|v| v < thresholds[row]),
+ };
+ if keep {
+ selected.push(index as u64);
+ }
+ }
+ }
+ result_lengths.push(selected.len() - before);
+ }
+ let expected = ListArray::new(
+ Arc::clone(&field),
+ OffsetBuffer::<i32>::from_lengths(result_lengths),
+ take(elements.as_ref(), &UInt64Array::from(selected), None).unwrap(),
+ list.nulls().cloned(),
+ );
+ let mut input = Arc::new(list) as ArrayRef;
+ let mut expected = Arc::new(expected) as ArrayRef;
+ if case.large_list {
+ let data_type = DataType::LargeList(Arc::clone(&field));
+ input = cast(&input, &data_type).unwrap();
+ expected = cast(&expected, &data_type).unwrap();
+ }
+ let schema = Arc::new(Schema::new(vec![
+ Field::new("list", input.data_type().clone(), true),
+ Field::new("threshold", DataType::Int32, false),
+ ]));
+ let batch = RecordBatch::try_new(
+ Arc::clone(&schema),
+ vec![input, Arc::new(Int32Array::from(thresholds))],
+ )
+ .unwrap();
+ let v = Expr::LambdaVariable(LambdaVariable::new("v".into(), Some(field)));
+ let body = match case.predicate {
+ Predicate::LessThan(limit) => {
+ let limit = if case.kind == DataType::Int32 {
+ lit(limit)
+ } else {
+ lit(ScalarValue::new_utf8(string_value(limit))
+ .cast_to(&case.kind)
+ .unwrap())
+ };
+ v.lt(limit)
+ }
+ Predicate::Scalar(value) => lit(ScalarValue::Boolean(value)),
+ Predicate::IsNull => v.is_null(),
+ Predicate::Captured => v.lt(col("threshold")),
+ };
+ let expression = create_physical_expr(
+ &array_filter(col("list"), lambda(["v"], body)),
+ &DFSchema::try_from(schema).unwrap(),
+ &ExecutionProps::new(),
+ &PhysicalPlanningContext::default(),
+ )
+ .unwrap();
+ let output = expression
+ .evaluate(&batch)
+ .unwrap()
+ .into_array(batch.num_rows())
+ .unwrap();
+ assert_eq!(output.as_ref(), expected.as_ref(), "{name}");
+ output.to_data().validate_full().unwrap();
+
+ let mut group = c.benchmark_group("array_filter");
+ group.sampling_mode(SamplingMode::Flat);
+ group.bench_function(name, |b| {
+ b.iter(|| black_box(expression.evaluate(black_box(&batch)).unwrap()))
+ });
+ group.finish();
+}
+
+fn criterion_benchmark(c: &mut Criterion) {
+ for (kind, name) in [
+ (DataType::Int32, "int32"),
+ (DataType::Utf8, "utf8"),
+ (DataType::Utf8View, "utf8_view"),
+ ] {
+ for keep in [10, 50, 90] {
+ bench_case(
+ c,
+ &format!("{name}/keep{keep}/no_nulls"),
+ &Case {
+ kind: kind.clone(),
+ predicate: Predicate::LessThan(keep),
+ ..Case::default()
+ },
+ );
+ }
+ // 25% NULL elements make comparison results nullable. Half of the
+ // remaining elements pass, so approximately 37.5% of all slots survive.
+ bench_case(
+ c,
+ &format!("{name}/keep50/null_elements25"),
+ &Case {
+ kind: kind.clone(),
+ element_nulls: 0.25,
+ ..Case::default()
+ },
+ );
+ // IS NULL is cheap to evaluate, so list reconstruction dominates.
+ bench_case(
+ c,
+ &format!("{name}/keep_null_elements"),
+ &Case {
+ kind: kind.clone(),
+ predicate: Predicate::IsNull,
+ element_nulls: 0.25,
+ ..Case::default()
+ },
+ );
+ for percent in [50, 99] {
+ bench_case(
+ c,
+ &format!("{name}/keep50/null_rows{percent}"),
+ &Case {
+ kind: kind.clone(),
+ row_nulls: f64::from(percent) / 100.0,
+ element_nulls: 0.25,
+ ..Case::default()
+ },
+ );
+ }
+ }
+ for (name, case) in [
Review Comment:
Could we also benchmark short Int32 lists, such as 2,048 rows with 2 elements each and some NULL elements? The current numeric benchmarks use width 16, so a narrower case would help measure per-row bookkeeping and popcount overhead when there are many rows relative to the total number of elements.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize `array_filter` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on code in PR #25754:
URL: https://github.com/apache/datafusion/pull/25754#discussion_r4290006270
##########
datafusion/functions-nested/src/lambda_utils.rs:
##########
@@ -152,12 +151,10 @@ impl EvaluatedListLambda {
self.original_list.nulls()
}
- pub(crate) fn row_range(&self, i: usize) -> (usize, usize) {
- (self.row_offsets[i], self.row_offsets[i + 1])
- }
-
- pub(crate) fn adjusted_offsets<O: OffsetSizeTrait>(&self) -> OffsetBuffer<O> {
- OffsetBuffer::from_lengths(self.row_offsets.windows(2).map(|w| w[1] - w[0]))
+ /// Row boundaries within `flattened_values`, including the elements that
+ /// NULL rows store. Functions that walk elements row by row compute this once.
+ pub(crate) fn row_offsets(&self) -> Result<Vec<usize>> {
+ adjusted_row_offsets(&self.original_list)
Review Comment:
Thanks, fixed.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize `array_filter` [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #25754:
URL: https://github.com/apache/datafusion/pull/25754#issuecomment-6196135536
🤖 Benchmark completed (GKE) | [trigger](https://github.com/apache/datafusion/pull/25754#issuecomment-6195802799)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
Comparing neilc/refactor-array-filter (021c8fd889245f56eaf8f28d9884e76f4bfe0536) to f721b9567f [diff](https://github.com/apache/datafusion/compare/f721b9567f086800f576de213eeca297eadfeb29..021c8fd889245f56eaf8f28d9884e76f4bfe0536)
<details><summary>Run configuration</summary>
```yaml
run benchmark array_filter
baseline:
ref: "f721b9567f"
```
</details>
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Details</summary>
<p>
```
group HEAD neilc_refactor-array-filter
----- ---- ---------------------------
array_filter/int32/captured_column 1.47 12.8±0.06µs ? ?/sec 1.00 8.7±0.02µs ? ?/sec
array_filter/int32/keep10/no_nulls 1.81 9.1±0.06µs ? ?/sec 1.00 5.0±0.00µs ? ?/sec
array_filter/int32/keep50/no_nulls 1.64 10.5±0.06µs ? ?/sec 1.00 6.4±0.01µs ? ?/sec
array_filter/int32/keep50/null_elements25 1.27 10.2±0.01µs ? ?/sec 1.00 8.0±0.01µs ? ?/sec
array_filter/int32/keep50/null_rows50 1.19 7.0±0.01µs ? ?/sec 1.00 5.9±0.01µs ? ?/sec
array_filter/int32/keep50/null_rows50/hidden_storage 1.13 9.5±0.03µs ? ?/sec 1.00 8.4±0.01µs ? ?/sec
array_filter/int32/keep50/null_rows99 1.00 2.2±0.01µs ? ?/sec 1.01 2.2±0.01µs ? ?/sec
array_filter/int32/keep90/no_nulls 1.68 10.1±0.06µs ? ?/sec 1.00 6.0±0.01µs ? ?/sec
array_filter/int32/keep_all 1.94 8.8±0.06µs ? ?/sec 1.00 4.5±0.01µs ? ?/sec
array_filter/int32/keep_none 1.78 9.1±0.06µs ? ?/sec 1.00 5.1±0.01µs ? ?/sec
array_filter/int32/keep_null_elements 1.70 9.9±0.06µs ? ?/sec 1.00 5.8±0.00µs ? ?/sec
array_filter/int32/large_1m/null_elements25 2.36 4.3±0.01ms ? ?/sec 1.00 1801.5±5.70µs ? ?/sec
array_filter/int32/narrow_2/null_elements25 1.00 24.3±0.01µs ? ?/sec
array_filter/scalar/false 1.12 1232.6±4.81ns ? ?/sec 1.00 1098.5±8.58ns ? ?/sec
array_filter/scalar/null 1.10 1211.0±9.51ns ? ?/sec 1.00 1097.9±7.66ns ? ?/sec
array_filter/scalar/true 1.13 731.9±2.68ns ? ?/sec 1.00 645.3±3.05ns ? ?/sec
array_filter/utf8/keep10/no_nulls 1.23 21.0±0.08µs ? ?/sec 1.00 17.1±0.02µs ? ?/sec
array_filter/utf8/keep50/no_nulls 1.13 29.6±0.14µs ? ?/sec 1.00 26.3±0.09µs ? ?/sec
array_filter/utf8/keep50/null_elements25 1.05 27.8±0.06µs ? ?/sec 1.00 26.3±0.16µs ? ?/sec
array_filter/utf8/keep50/null_rows50 1.06 14.9±0.03µs ? ?/sec 1.00 14.1±0.03µs ? ?/sec
array_filter/utf8/keep50/null_rows99 1.00 2.3±0.01µs ? ?/sec 1.01 2.3±0.00µs ? ?/sec
array_filter/utf8/keep90/no_nulls 1.14 29.4±0.07µs ? ?/sec 1.00 25.8±0.04µs ? ?/sec
array_filter/utf8/keep_null_elements 1.45 13.0±0.07µs ? ?/sec 1.00 9.0±0.01µs ? ?/sec
array_filter/utf8/large_list 1.09 27.8±0.06µs ? ?/sec 1.00 25.6±0.14µs ? ?/sec
array_filter/utf8/sliced 1.08 27.7±0.07µs ? ?/sec 1.00 25.5±0.08µs ? ?/sec
array_filter/utf8/variable_0_to_32 1.16 29.6±0.17µs ? ?/sec 1.00 25.6±0.10µs ? ?/sec
array_filter/utf8/wide_128 1.01 24.2±0.13µs ? ?/sec 1.00 24.0±0.09µs ? ?/sec
array_filter/utf8_view/keep10/no_nulls 1.43 13.5±0.06µs ? ?/sec 1.00 9.4±0.01µs ? ?/sec
array_filter/utf8_view/keep50/no_nulls 1.40 15.0±0.06µs ? ?/sec 1.00 10.7±0.01µs ? ?/sec
array_filter/utf8_view/keep50/null_elements25 1.17 15.2±0.01µs ? ?/sec 1.00 12.9±0.01µs ? ?/sec
array_filter/utf8_view/keep50/null_rows50 1.13 9.5±0.01µs ? ?/sec 1.00 8.4±0.01µs ? ?/sec
array_filter/utf8_view/keep50/null_rows99 1.02 2.4±0.01µs ? ?/sec 1.00 2.3±0.00µs ? ?/sec
array_filter/utf8_view/keep90/no_nulls 1.37 14.7±0.07µs ? ?/sec 1.00 10.7±0.01µs ? ?/sec
array_filter/utf8_view/keep_null_elements 1.68 10.1±0.07µs ? ?/sec 1.00 6.0±0.01µs ? ?/sec
```
</p>
</details>
<details><summary>Resource Usage</summary>
**array_filter — base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 385.1s |
| Peak memory | 60.7 MiB |
| Avg memory | 30.3 MiB |
| CPU user | 383.8s |
| CPU sys | 0.3s |
| Peak spill | 0 B |
**array_filter — branch**
| Metric | Value |
|--------|-------|
| Wall time | 410.1s |
| Peak memory | 59.6 MiB |
| Avg memory | 30.8 MiB |
| CPU user | 391.0s |
| CPU sys | 0.2s |
| Peak spill | 0 B |
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize `array_filter` [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #25754:
URL: https://github.com/apache/datafusion/pull/25754#issuecomment-6190522617
🤖 Benchmark completed (GKE) | [trigger](https://github.com/apache/datafusion/pull/25754#issuecomment-6190093882)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
Comparing neilc/refactor-array-filter (39d794dc7ebe67c7b226f9014bb1c0d661c2bccc) to f721b9567f [diff](https://github.com/apache/datafusion/compare/f721b9567f086800f576de213eeca297eadfeb29..39d794dc7ebe67c7b226f9014bb1c0d661c2bccc)
<details><summary>Run configuration</summary>
```yaml
run benchmark array_filter
baseline:
ref: "f721b9567f"
```
</details>
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Details</summary>
<p>
```
group HEAD neilc_refactor-array-filter
----- ---- ---------------------------
array_filter/int32/captured_column 1.38 12.8±0.07µs ? ?/sec 1.00 9.3±0.16µs ? ?/sec
array_filter/int32/keep10/no_nulls 1.63 9.1±0.06µs ? ?/sec 1.00 5.6±0.17µs ? ?/sec
array_filter/int32/keep50/no_nulls 1.51 10.4±0.05µs ? ?/sec 1.00 6.9±0.17µs ? ?/sec
array_filter/int32/keep50/null_elements25 1.18 10.2±0.02µs ? ?/sec 1.00 8.6±0.16µs ? ?/sec
array_filter/int32/keep50/null_rows50 1.13 7.0±0.01µs ? ?/sec 1.00 6.2±0.02µs ? ?/sec
array_filter/int32/keep50/null_rows50/hidden_storage 1.09 9.5±0.02µs ? ?/sec 1.00 8.7±0.01µs ? ?/sec
array_filter/int32/keep50/null_rows99 1.00 2.2±0.01µs ? ?/sec 1.00 2.2±0.02µs ? ?/sec
array_filter/int32/keep90/no_nulls 1.54 10.1±0.06µs ? ?/sec 1.00 6.6±0.16µs ? ?/sec
array_filter/int32/keep_all 1.72 8.8±0.06µs ? ?/sec 1.00 5.1±0.16µs ? ?/sec
array_filter/int32/keep_none 1.63 9.1±0.06µs ? ?/sec 1.00 5.6±0.16µs ? ?/sec
array_filter/int32/keep_null_elements 1.56 10.0±0.06µs ? ?/sec 1.00 6.4±0.16µs ? ?/sec
array_filter/int32/large_1m/null_elements25 2.20 4.2±0.01ms ? ?/sec 1.00 1928.0±43.90µs ? ?/sec
array_filter/scalar/false 1.09 1195.6±8.21ns ? ?/sec 1.00 1099.9±7.32ns ? ?/sec
array_filter/scalar/null 1.11 1221.1±14.73ns ? ?/sec 1.00 1104.1±9.86ns ? ?/sec
array_filter/scalar/true 1.15 735.8±10.61ns ? ?/sec 1.00 637.6±4.78ns ? ?/sec
array_filter/utf8/keep10/no_nulls 1.20 21.1±0.07µs ? ?/sec 1.00 17.6±0.15µs ? ?/sec
array_filter/utf8/keep50/no_nulls 1.12 30.5±0.21µs ? ?/sec 1.00 27.3±0.12µs ? ?/sec
array_filter/utf8/keep50/null_elements25 1.04 27.5±0.15µs ? ?/sec 1.00 26.5±0.12µs ? ?/sec
array_filter/utf8/keep50/null_rows50 1.06 15.0±0.07µs ? ?/sec 1.00 14.2±0.02µs ? ?/sec
array_filter/utf8/keep50/null_rows99 1.02 2.3±0.01µs ? ?/sec 1.00 2.3±0.01µs ? ?/sec
array_filter/utf8/keep90/no_nulls 1.12 29.3±0.07µs ? ?/sec 1.00 26.2±0.17µs ? ?/sec
array_filter/utf8/keep_null_elements 1.29 13.1±0.07µs ? ?/sec 1.00 10.1±0.17µs ? ?/sec
array_filter/utf8/large_list 1.06 27.7±0.12µs ? ?/sec 1.00 26.1±0.23µs ? ?/sec
array_filter/utf8/sliced 1.07 27.3±0.13µs ? ?/sec 1.00 25.7±0.15µs ? ?/sec
array_filter/utf8/variable_0_to_32 1.10 29.2±0.14µs ? ?/sec 1.00 26.6±0.16µs ? ?/sec
array_filter/utf8/wide_128 1.00 24.4±0.26µs ? ?/sec 1.01 24.8±0.13µs ? ?/sec
array_filter/utf8_view/keep10/no_nulls 1.35 13.4±0.06µs ? ?/sec 1.00 9.9±0.16µs ? ?/sec
array_filter/utf8_view/keep50/no_nulls 1.29 15.0±0.06µs ? ?/sec 1.00 11.6±0.17µs ? ?/sec
array_filter/utf8_view/keep50/null_elements25 1.12 15.3±0.01µs ? ?/sec 1.00 13.6±0.17µs ? ?/sec
array_filter/utf8_view/keep50/null_rows50 1.09 9.6±0.02µs ? ?/sec 1.00 8.8±0.02µs ? ?/sec
array_filter/utf8_view/keep50/null_rows99 1.00 2.3±0.01µs ? ?/sec 1.00 2.3±0.01µs ? ?/sec
array_filter/utf8_view/keep90/no_nulls 1.32 14.7±0.06µs ? ?/sec 1.00 11.2±0.16µs ? ?/sec
array_filter/utf8_view/keep_null_elements 1.53 10.1±0.07µs ? ?/sec 1.00 6.6±0.16µs ? ?/sec
```
</p>
</details>
<details><summary>Resource Usage</summary>
**array_filter — base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 650.1s |
| Peak memory | 62.5 MiB |
| Avg memory | 20.3 MiB |
| CPU user | 383.3s |
| CPU sys | 0.3s |
| Peak spill | 0 B |
**array_filter — branch**
| Metric | Value |
|--------|-------|
| Wall time | 630.1s |
| Peak memory | 54.4 MiB |
| Avg memory | 18.7 MiB |
| CPU user | 379.8s |
| CPU sys | 0.3s |
| Peak spill | 0 B |
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize `array_filter` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on code in PR #25754:
URL: https://github.com/apache/datafusion/pull/25754#discussion_r4289989273
##########
datafusion/functions-nested/src/utils.rs:
##########
@@ -50,6 +50,103 @@ pub(crate) fn empty_list_values<O: OffsetSizeTrait>(
))
}
+/// Build result row offsets and exclude elements stored under NULL list rows.
+///
+/// `keep` is a bitmap identifying which elements in the list's visible span
+/// should be preserved. The returned bitmap uses the same indexing, with bits
+/// for NULL list rows cleared. Selected elements may themselves be NULL; their
+/// validity is the caller's responsibility when copying values.
+pub(crate) fn prepare_list_filter<O: OffsetSizeTrait>(
+ list: &GenericListArray<O>,
+ keep: &BooleanBuffer,
+) -> (OffsetBuffer<O>, BooleanBuffer) {
+ let list_offsets = list.offsets();
+ let (first_offset, span_len) = offset_span(list_offsets);
+ debug_assert_eq!(keep.len(), span_len);
+ let mut offsets = Vec::with_capacity(list.len() + 1);
+ offsets.push(O::zero());
+ let mut kept_count = 0;
+ // Count the set bits before each row end in one pass over `keep`, which
+ // stays cheap for short rows.
+ let mut set_bits = SetBitCounter::new(keep.bit_chunks().iter_padded());
+ // Set bits stored under NULL rows, which the result does not keep.
+ let mut hidden_count = 0;
+ // NULL list rows are usually empty, so reuse `keep` until a NULL row stores
+ // elements. Copy the bits of the preceding rows when that first happens.
+ let mut keep_mask: Option<BooleanBufferBuilder> = None;
+ for (row, window) in list_offsets.windows(2).enumerate() {
+ let start = window[0].as_usize() - first_offset;
+ let end = window[1].as_usize() - first_offset;
+ let len = end - start;
+ let bit_start = keep.offset() + start;
+ if list.is_valid(row) {
+ kept_count = set_bits.count_before(end) - hidden_count;
+ if let Some(keep_mask) = &mut keep_mask {
+ keep_mask.append_packed_range(bit_start..bit_start + len, keep.values());
+ }
+ } else if len != 0 {
+ let set_before_row = set_bits.count_before(start);
+ hidden_count += set_bits.count_before(end) - set_before_row;
+ keep_mask
+ .get_or_insert_with(|| {
+ let mut builder = BooleanBufferBuilder::new(keep.len());
+ builder.append_packed_range(keep.offset()..bit_start, keep.values());
+ builder
+ })
+ .append_n(len, false);
+ }
+ offsets.push(O::usize_as(kept_count));
+ }
+ let keep_mask = keep_mask
+ .map(BooleanBufferBuilder::build)
+ .unwrap_or_else(|| keep.clone());
+ debug_assert_eq!(keep_mask.len(), keep.len());
+ // SAFETY: offsets start at zero and `kept_count` never decreases. The count
+ // cannot exceed the input's element span, which fits in `O`, so converting
+ // it to `O` cannot overflow.
+ let offsets = unsafe { OffsetBuffer::new_unchecked(offsets.into()) };
Review Comment:
I measured and found the checked constructor was about 8% slower, so I kept `new_unchecked`.
##########
datafusion/functions-nested/src/utils.rs:
##########
@@ -50,6 +50,103 @@ pub(crate) fn empty_list_values<O: OffsetSizeTrait>(
))
}
+/// Build result row offsets and exclude elements stored under NULL list rows.
+///
+/// `keep` is a bitmap identifying which elements in the list's visible span
+/// should be preserved. The returned bitmap uses the same indexing, with bits
+/// for NULL list rows cleared. Selected elements may themselves be NULL; their
+/// validity is the caller's responsibility when copying values.
+pub(crate) fn prepare_list_filter<O: OffsetSizeTrait>(
+ list: &GenericListArray<O>,
+ keep: &BooleanBuffer,
+) -> (OffsetBuffer<O>, BooleanBuffer) {
+ let list_offsets = list.offsets();
+ let (first_offset, span_len) = offset_span(list_offsets);
+ debug_assert_eq!(keep.len(), span_len);
+ let mut offsets = Vec::with_capacity(list.len() + 1);
+ offsets.push(O::zero());
+ let mut kept_count = 0;
+ // Count the set bits before each row end in one pass over `keep`, which
+ // stays cheap for short rows.
+ let mut set_bits = SetBitCounter::new(keep.bit_chunks().iter_padded());
+ // Set bits stored under NULL rows, which the result does not keep.
+ let mut hidden_count = 0;
+ // NULL list rows are usually empty, so reuse `keep` until a NULL row stores
+ // elements. Copy the bits of the preceding rows when that first happens.
+ let mut keep_mask: Option<BooleanBufferBuilder> = None;
+ for (row, window) in list_offsets.windows(2).enumerate() {
+ let start = window[0].as_usize() - first_offset;
+ let end = window[1].as_usize() - first_offset;
+ let len = end - start;
+ let bit_start = keep.offset() + start;
+ if list.is_valid(row) {
+ kept_count = set_bits.count_before(end) - hidden_count;
+ if let Some(keep_mask) = &mut keep_mask {
+ keep_mask.append_packed_range(bit_start..bit_start + len, keep.values());
+ }
+ } else if len != 0 {
+ let set_before_row = set_bits.count_before(start);
+ hidden_count += set_bits.count_before(end) - set_before_row;
+ keep_mask
+ .get_or_insert_with(|| {
+ let mut builder = BooleanBufferBuilder::new(keep.len());
+ builder.append_packed_range(keep.offset()..bit_start, keep.values());
+ builder
+ })
+ .append_n(len, false);
+ }
+ offsets.push(O::usize_as(kept_count));
+ }
+ let keep_mask = keep_mask
+ .map(BooleanBufferBuilder::build)
+ .unwrap_or_else(|| keep.clone());
+ debug_assert_eq!(keep_mask.len(), keep.len());
+ // SAFETY: offsets start at zero and `kept_count` never decreases. The count
+ // cannot exceed the input's element span, which fits in `O`, so converting
+ // it to `O` cannot overflow.
+ let offsets = unsafe { OffsetBuffer::new_unchecked(offsets.into()) };
Review Comment:
I measured and found the checked constructor was about 8% slower (M4 Max), so I kept `new_unchecked`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Optimize `array_filter` [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway merged PR #25754:
URL: https://github.com/apache/datafusion/pull/25754
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org