This is an automated email from the ASF dual-hosted git repository. github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-11871-901a171dbf03341a79d35bdb495332384590e236 in repository https://gitbox.apache.org/repos/asf/arrow-rs.git
commit 68cd02d3f9c27f9b3d3bf3bf747e0276fddcd87a Author: Mikhail Zabaluev <[email protected]> AuthorDate: Tue Oct 27 03:58:04 2026 +0000 bench(arrow): cover filtering of nested list types (#11871) # Which issue does this PR close? - Part of #11839 # Rationale for this change `List`, `LargeList`, `FixedSizeList` and `Map` currently have no native `filter` kernel and go through the `MutableArrayData` fallback. There are no benchmarks for filtering these types, so there is nothing to compare the upcoming native kernels against. # What changes are included in this PR? New cases in `arrow/benches/filter_kernels.rs`, each at 1/2, 1023/1024 and 1/1024 selectivity, with both a plain and a prebuilt (`filter context`) predicate: - `list<i32>` - `list<struct<i64, utf8>>` - ~~`struct<8 x i64, list<struct<i64, utf8>>>`: the column shape from apache/datafusion#26581, with up to 64 (about 32 on average) items per row~~ - `fixed_size_list<i32>` and `fixed_size_list<struct<i64, utf8>>` - `map<utf8, i64>` The existing `bench_util` helpers are reused where they fit. Small local helpers build the struct-valued lists. # Are these changes tested? Benchmarks only. Current numbers on `main` (Apple M4 Pro, plain predicate): | case | kept 1/2 | kept 1023/1024 | kept 1/1024 | |---|---|---|---| | list\<i32\> w NULLs | 576 µs | 96 µs | 2.9 µs | | list\<struct\<i64, utf8\>\> w NULLs | 1.47 ms | 1.46 ms | 6.3 µs | | struct\<8 x i64, list\<struct\<i64, utf8\>\>\> w NULLs | 3.85 ms | 6.04 ms | 13.4 µs | | fixed_size_list\<i32\> w NULLs | 413 µs | 39 µs | 2.6 µs | | fixed_size_list\<struct\<i64, utf8\>\> | 903 µs | 444 µs | 4.9 µs | | map\<utf8, i64\> w NULLs | 1.50 ms | 2.88 ms | 5.9 µs | Some 1023/1024 cases are slower than the 1/2 cases. The struct and map rows show this most clearly. # Are there any significant user-facing changes? No. 🤖 Generated with [Claude Code](https://claude.com/claude-code) --------- Co-authored-by: Claude Opus 5.5 <[email protected]> Co-authored-by: RIchard Baah <[email protected]> --- arrow/benches/filter_kernels.rs | 80 ++++++++++++++++++++++++++++++++++++++++- 1 file changed, 79 insertions(+), 1 deletion(-) diff --git a/arrow/benches/filter_kernels.rs b/arrow/benches/filter_kernels.rs index 8d7403ae04..8b2d454233 100644 --- a/arrow/benches/filter_kernels.rs +++ b/arrow/benches/filter_kernels.rs @@ -23,10 +23,14 @@ use arrow::util::bench_util::*; use arrow::array::*; use arrow::compute::filter; use arrow::compute::{and, is_not_null}; -use arrow::datatypes::{Field, Float32Type, Int32Type, Int64Type, Schema, UInt8Type}; +use arrow::datatypes::{ + DataType, Field, Fields, Float32Type, Int32Type, Int64Type, Schema, UInt8Type, +}; use arrow_array::types::Decimal128Type; +use arrow_buffer::{NullBuffer, OffsetBuffer}; use criterion::{Criterion, criterion_group, criterion_main}; +use rand::{RngExt, SeedableRng, rngs::StdRng}; use std::hint; fn bench_filter(data_array: &dyn Array, filter_array: &BooleanArray) { @@ -37,6 +41,39 @@ fn bench_built_filter(array: &dyn Array, filter: &FilterPredicate) { hint::black_box(filter.filter(array).unwrap()); } +/// Creates a `Struct<x: Int64, y: Utf8>` array of `len` rows +fn create_xy_struct_array(len: usize) -> StructArray { + let fields = Fields::from(vec![ + Field::new("x", DataType::Int64, true), + Field::new("y", DataType::Utf8, true), + ]); + let x = create_primitive_array::<Int64Type>(len, 0.1); + let y = create_string_array_with_max_len::<i32>(len, 0.1, 16); + StructArray::new(fields, vec![Arc::new(x), Arc::new(y)], None) +} + +/// Creates a `List<Struct<x: Int64, y: Utf8>>` array of `size` rows, each +/// with a random number of elements in `0..=max_list_size` +fn create_struct_list_array(size: usize, null_density: f32, max_list_size: usize) -> ListArray { + let mut rng = StdRng::seed_from_u64(42); + let lengths: Vec<usize> = (0..size) + .map(|_| rng.random_range(0..=max_list_size)) + .collect(); + let values = create_xy_struct_array(lengths.iter().sum()); + let offsets = OffsetBuffer::<i32>::from_lengths(lengths); + let nulls = (null_density > 0.0) + .then(|| NullBuffer::from_iter((0..size).map(|_| rng.random::<f32>() >= null_density))); + let field = Arc::new(Field::new_list_field(values.data_type().clone(), true)); + ListArray::new(field, offsets, Arc::new(values), nulls) +} + +/// Creates a `FixedSizeList<Struct<x: Int64, y: Utf8>>` array of `size` rows +fn create_struct_fixed_size_list_array(size: usize, list_size: i32) -> FixedSizeListArray { + let values = create_xy_struct_array(size * list_size as usize); + let field = Arc::new(Field::new_list_field(values.data_type().clone(), true)); + FixedSizeListArray::new(field, list_size, Arc::new(values), None) +} + fn add_benchmark(c: &mut Criterion) { let size = 65536; let filter_array = create_boolean_array(size, 0.0, 0.5); @@ -336,6 +373,47 @@ fn add_benchmark(c: &mut Criterion) { c.bench_function("filter run array low selectivity (kept 1/1024)", |b| { b.iter(|| bench_built_filter(&data_array, &sparse_filter)) }); + + let mut add_benchmark_for_nested = |name: &str, data_array: &dyn Array| { + c.bench_function(&format!("filter {name} (kept 1/2)"), |b| { + b.iter(|| bench_filter(data_array, &filter_array)) + }); + c.bench_function( + &format!("filter {name} high selectivity (kept 1023/1024)"), + |b| b.iter(|| bench_filter(data_array, &dense_filter_array)), + ); + c.bench_function( + &format!("filter {name} low selectivity (kept 1/1024)"), + |b| b.iter(|| bench_filter(data_array, &sparse_filter_array)), + ); + + c.bench_function(&format!("filter context {name} (kept 1/2)"), |b| { + b.iter(|| bench_built_filter(data_array, &filter)) + }); + c.bench_function( + &format!("filter context {name} high selectivity (kept 1023/1024)"), + |b| b.iter(|| bench_built_filter(data_array, &dense_filter)), + ); + c.bench_function( + &format!("filter context {name} low selectivity (kept 1/1024)"), + |b| b.iter(|| bench_built_filter(data_array, &sparse_filter)), + ); + }; + + let data_array = create_primitive_list_array::<i32, Int32Type>(size, 0.1, 0.1, 16); + add_benchmark_for_nested("list<i32> w NULLs", &data_array); + + let data_array = create_struct_list_array(size, 0.1, 16); + add_benchmark_for_nested("list<struct<i64, utf8>> w NULLs", &data_array); + + let data_array = create_primitive_fixed_size_list_array::<Int32Type>(size, 0.1, 0.1, 8); + add_benchmark_for_nested("fixed_size_list<i32> w NULLs", &data_array); + + let data_array = create_struct_fixed_size_list_array(size, 8); + add_benchmark_for_nested("fixed_size_list<struct<i64, utf8>>", &data_array); + + let data_array = create_string_map_array::<Int64Type>(size, 0.1, 16, 8); + add_benchmark_for_nested("map<utf8, i64> w NULLs", &data_array); } criterion_group!(benches, add_benchmark);
