This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] 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 68cd02d3f9 bench(arrow): cover filtering of nested list types (#11871)
68cd02d3f9 is described below
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);
