Skip to content

Commit d54ce65

Browse files
puneetdixit200Puneet DixitCopilot
authored
perf: optimize arrays_zip perfect list zips (apache#22285)
## Which issue does this PR close? - Closes apache#22225. ## Rationale for this change `arrays_zip` currently uses the general `MutableArrayData` path even when all regular `ListArray` inputs are already perfectly aligned. In that case, the output list offsets match the inputs and each struct child column can reuse the corresponding input values array instead of copying one row at a time. ## What changes are included in this PR? - Add a fast path for perfect regular `ListArray` zips that reuses the first input's offsets and clones the input values arrays into the output struct children. - Keep the existing general path for ragged inputs, `LargeList`, `FixedSizeList`, `Null` inputs, and null rows that would require padding. - Add unit coverage for offset/value reuse, zero-length null rows, and null rows with hidden values falling back to the general path. - Rename the no-null benchmark case to `arrays_zip_perfect_zip_8192`. ## Are these changes tested? Yes. Local checks run: - `cargo fmt --all` - `cargo test -p datafusion-functions-nested` - `cargo clippy -p datafusion-functions-nested --all-targets --all-features -- -D warnings` - `CARGO_TARGET_DIR=C:\df-target cargo clippy --all-targets --all-features -- -D warnings` - `CARGO_TARGET_DIR=C:\df-target cargo bench -p datafusion-functions-nested --bench arrays_zip -- --warm-up-time 1 --measurement-time 2 --sample-size 10` Latest local benchmark sample: - `arrays_zip_perfect_zip_8192`: `11.234 ?s 11.600 ?s 12.045 ?s` - `arrays_zip_10pct_nulls_8192`: `4.3463 ms 4.5531 ms 4.7898 ms` ## Are there any user-facing changes? No. This is an internal performance optimization with the same `arrays_zip` output semantics. ## Review follow-up validation 2026-05-21: - `cargo fmt --all --check` passed after formatting. - `cargo test -p datafusion-functions-nested perfect_zip_uses_supplied_field_names --lib` could not compile locally because this Windows GNU toolchain is missing `dlltool.exe`. - `cargo clippy -p datafusion-functions-nested --all-targets -- -D warnings` hit the same local `dlltool.exe` toolchain blocker before checking the crate. --------- Co-authored-by: Puneet Dixit <[email protected]> Co-authored-by: Copilot Autofix powered by AI <[email protected]> Co-authored-by: puneetdixit200 <[email protected]>
1 parent 7b7429d commit d54ce65

2 files changed

Lines changed: 290 additions & 6 deletions

File tree

‎datafusion/functions-nested/benches/arrays_zip.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -109,7 +109,7 @@ fn bench_arrays_zip(c: &mut Criterion, name: &str, null_density: f64) {
109109
}
110110

111111
fn criterion_benchmark(c: &mut Criterion) {
112-
bench_arrays_zip(c, "arrays_zip_no_nulls_8192", 0.0);
112+
bench_arrays_zip(c, "arrays_zip_perfect_zip_8192", 0.0);
113113
bench_arrays_zip(c, "arrays_zip_10pct_nulls_8192", 0.1);
114114
}
115115

‎datafusion/functions-nested/src/arrays_zip.rs‎

Lines changed: 289 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -22,7 +22,7 @@ use arrow::array::{
2222
Array, ArrayRef, Capacities, ListArray, MutableArrayData, NullBufferBuilder,
2323
StructArray, new_null_array,
2424
};
25-
use arrow::buffer::OffsetBuffer;
25+
use arrow::buffer::{NullBuffer, OffsetBuffer};
2626
use arrow::datatypes::DataType::{FixedSizeList, LargeList, List, Null};
2727
use arrow::datatypes::{DataType, Field, Fields};
2828
use datafusion_common::cast::{
@@ -44,7 +44,7 @@ struct ListColumnView {
4444
/// Pre-computed per-row start offsets (length = num_rows + 1).
4545
offsets: Vec<usize>,
4646
/// Null bitmap from the input array (None means no nulls).
47-
nulls: Option<arrow::buffer::NullBuffer>,
47+
nulls: Option<NullBuffer>,
4848
}
4949

5050
impl ListColumnView {
@@ -130,7 +130,7 @@ impl ScalarUDFImpl for ArraysZip {
130130
return exec_err!("arrays_zip expects array arguments, got {dt}");
131131
}
132132
};
133-
fields.push(Field::new(format!("{}", i + 1), element_type, true));
133+
fields.push(Field::new(arrays_zip_field_name(i), element_type, true));
134134
}
135135

136136
Ok(List(Arc::new(Field::new_list_field(
@@ -163,8 +163,13 @@ fn arrays_zip_inner(args: &[ArrayRef]) -> Result<ArrayRef> {
163163
return exec_err!("arrays_zip requires at least one argument");
164164
}
165165

166+
let field_names = arrays_zip_field_names(args.len());
166167
let num_rows = args[0].len();
167168

169+
if let Some(result) = try_perfect_list_zip(args, &field_names)? {
170+
return Ok(result);
171+
}
172+
168173
// Build a type-erased ListColumnView for each argument.
169174
// None means the argument is Null-typed (all nulls, no backing data).
170175
let mut views: Vec<Option<ListColumnView>> = Vec::with_capacity(args.len());
@@ -225,8 +230,8 @@ fn arrays_zip_inner(args: &[ArrayRef]) -> Result<ArrayRef> {
225230

226231
let struct_fields: Fields = element_types
227232
.iter()
228-
.enumerate()
229-
.map(|(i, dt)| Field::new(format!("{}", i + 1), dt.clone(), true))
233+
.zip(field_names.iter())
234+
.map(|(dt, name)| Field::new(name.clone(), dt.clone(), true))
230235
.collect::<Vec<_>>()
231236
.into();
232237

@@ -327,3 +332,282 @@ fn arrays_zip_inner(args: &[ArrayRef]) -> Result<ArrayRef> {
327332

328333
Ok(Arc::new(result))
329334
}
335+
336+
fn arrays_zip_field_name(index: usize) -> String {
337+
(index + 1).to_string()
338+
}
339+
340+
fn arrays_zip_field_names(len: usize) -> Vec<String> {
341+
(0..len).map(arrays_zip_field_name).collect()
342+
}
343+
344+
/// Fast path for regular List inputs whose existing buffers already match the
345+
/// zipped output: all offsets and values lengths match, and null rows cover no
346+
/// values. This lets us reuse offsets and child values instead of rebuilding.
347+
fn try_perfect_list_zip(
348+
args: &[ArrayRef],
349+
field_names: &[String],
350+
) -> Result<Option<ArrayRef>> {
351+
debug_assert_eq!(args.len(), field_names.len());
352+
353+
let mut list_arrays = Vec::with_capacity(args.len());
354+
let mut struct_fields = Vec::with_capacity(args.len());
355+
356+
for (arg, field_name) in args.iter().zip(field_names) {
357+
let arr = match arg.data_type() {
358+
List(field) => {
359+
struct_fields.push(Field::new(
360+
field_name.clone(),
361+
field.data_type().clone(),
362+
true,
363+
));
364+
as_list_array(arg)?
365+
}
366+
_ => return Ok(None),
367+
};
368+
369+
list_arrays.push(arr);
370+
}
371+
372+
let first = list_arrays[0];
373+
let num_rows = first.len();
374+
let offsets = first.offsets().clone();
375+
let values_len = first.values().len();
376+
377+
// Reusing the child arrays is only valid when every list uses the exact
378+
// same row boundaries and exposes the same total number of child values.
379+
for arr in &list_arrays {
380+
if arr.values().len() != values_len || arr.offsets() != &offsets {
381+
return Ok(None);
382+
}
383+
}
384+
385+
let nulls = if list_arrays.iter().any(|arr| arr.null_count() != 0) {
386+
let first_nulls = first.nulls();
387+
if list_arrays.iter().all(|arr| arr.nulls() == first_nulls) {
388+
first_nulls.cloned()
389+
} else {
390+
// Match the general path: arrays_zip only marks an output row null
391+
// when every concrete input list is null. Mixed null and non-null
392+
// empty lists still produce a non-null empty list, but mixed null
393+
// rows with values must fall back to preserve field-level nulls.
394+
let mut null_builder = NullBufferBuilder::new(num_rows);
395+
for row_idx in 0..num_rows {
396+
let mut all_null = true;
397+
398+
for arr in &list_arrays {
399+
if arr.is_null(row_idx) {
400+
if arr.offsets()[row_idx + 1] != arr.offsets()[row_idx] {
401+
return Ok(None);
402+
}
403+
} else {
404+
all_null = false;
405+
}
406+
}
407+
408+
if all_null {
409+
null_builder.append_null();
410+
} else {
411+
null_builder.append_non_null();
412+
}
413+
}
414+
415+
null_builder.finish()
416+
}
417+
} else {
418+
None
419+
};
420+
421+
let struct_columns = list_arrays
422+
.iter()
423+
.map(|arr| Arc::clone(arr.values()))
424+
.collect::<Vec<_>>();
425+
let struct_array =
426+
StructArray::try_new(Fields::from(struct_fields), struct_columns, None)?;
427+
let result = ListArray::try_new(
428+
Arc::new(Field::new_list_field(
429+
struct_array.data_type().clone(),
430+
true,
431+
)),
432+
offsets,
433+
Arc::new(struct_array),
434+
nulls,
435+
)?;
436+
437+
Ok(Some(Arc::new(result)))
438+
}
439+
440+
#[cfg(test)]
441+
mod tests {
442+
use super::*;
443+
use arrow::array::Int64Array;
444+
use arrow::buffer::NullBuffer;
445+
446+
fn list(values: Vec<i64>, offsets: Vec<i32>) -> Arc<ListArray> {
447+
list_with_validity(values, offsets, None)
448+
}
449+
450+
fn list_with_validity(
451+
values: Vec<i64>,
452+
offsets: Vec<i32>,
453+
valid: Option<Vec<bool>>,
454+
) -> Arc<ListArray> {
455+
Arc::new(
456+
ListArray::try_new(
457+
Arc::new(Field::new_list_field(DataType::Int64, true)),
458+
OffsetBuffer::new(offsets.into()),
459+
Arc::new(Int64Array::from(values)),
460+
valid.map(NullBuffer::from),
461+
)
462+
.unwrap(),
463+
)
464+
}
465+
466+
#[test]
467+
fn perfect_zip_reuses_input_values_and_offsets() {
468+
let left = list(vec![1, 2, 3, 4, 5, 6], vec![0, 2, 3, 6]);
469+
let right = list(vec![10, 20, 30, 40, 50, 60], vec![0, 2, 3, 6]);
470+
471+
let result = arrays_zip_inner(&[
472+
Arc::clone(&left) as ArrayRef,
473+
Arc::clone(&right) as ArrayRef,
474+
])
475+
.unwrap();
476+
let result = result.as_any().downcast_ref::<ListArray>().unwrap();
477+
let values = result
478+
.values()
479+
.as_any()
480+
.downcast_ref::<StructArray>()
481+
.unwrap();
482+
483+
assert!(result.offsets().ptr_eq(left.offsets()));
484+
assert!(Arc::ptr_eq(values.column(0), left.values()));
485+
assert!(Arc::ptr_eq(values.column(1), right.values()));
486+
}
487+
488+
#[test]
489+
fn perfect_zip_uses_supplied_field_names() {
490+
let left = list(vec![1, 2, 3], vec![0, 1, 3]);
491+
let right = list(vec![10, 20, 30], vec![0, 1, 3]);
492+
let field_names = vec!["left".to_string(), "right".to_string()];
493+
494+
let result = try_perfect_list_zip(
495+
&[
496+
Arc::clone(&left) as ArrayRef,
497+
Arc::clone(&right) as ArrayRef,
498+
],
499+
&field_names,
500+
)
501+
.unwrap()
502+
.unwrap();
503+
let result = result.as_any().downcast_ref::<ListArray>().unwrap();
504+
let values = result
505+
.values()
506+
.as_any()
507+
.downcast_ref::<StructArray>()
508+
.unwrap();
509+
let names = values
510+
.fields()
511+
.iter()
512+
.map(|field| field.name().as_str())
513+
.collect::<Vec<_>>();
514+
515+
assert_eq!(names, vec!["left", "right"]);
516+
}
517+
518+
#[test]
519+
fn perfect_zip_reuses_zero_length_null_rows() {
520+
let left = list_with_validity(
521+
vec![1, 2, 3, 4],
522+
vec![0, 2, 2, 4],
523+
Some(vec![true, false, true]),
524+
);
525+
let right = list_with_validity(
526+
vec![10, 20, 30, 40],
527+
vec![0, 2, 2, 4],
528+
Some(vec![true, false, true]),
529+
);
530+
531+
let result = arrays_zip_inner(&[
532+
Arc::clone(&left) as ArrayRef,
533+
Arc::clone(&right) as ArrayRef,
534+
])
535+
.unwrap();
536+
let result = result.as_any().downcast_ref::<ListArray>().unwrap();
537+
538+
assert!(result.offsets().ptr_eq(left.offsets()));
539+
assert!(result.is_null(1));
540+
}
541+
542+
#[test]
543+
fn perfect_zip_preserves_mixed_null_empty_rows() {
544+
let left =
545+
list_with_validity(vec![], vec![0, 0, 0, 0], Some(vec![false, true, false]));
546+
let right =
547+
list_with_validity(vec![], vec![0, 0, 0, 0], Some(vec![true, false, false]));
548+
549+
let result = arrays_zip_inner(&[
550+
Arc::clone(&left) as ArrayRef,
551+
Arc::clone(&right) as ArrayRef,
552+
])
553+
.unwrap();
554+
let result = result.as_any().downcast_ref::<ListArray>().unwrap();
555+
556+
assert!(result.offsets().ptr_eq(left.offsets()));
557+
assert!(!result.is_null(0));
558+
assert!(!result.is_null(1));
559+
assert!(result.is_null(2));
560+
}
561+
562+
#[test]
563+
fn perfect_zip_reuses_null_rows_with_hidden_values() {
564+
let left =
565+
list_with_validity(vec![1, 2, 3, 4], vec![0, 2, 4], Some(vec![true, false]));
566+
let right = list_with_validity(
567+
vec![10, 20, 30, 40],
568+
vec![0, 2, 4],
569+
Some(vec![true, false]),
570+
);
571+
572+
let result = arrays_zip_inner(&[
573+
Arc::clone(&left) as ArrayRef,
574+
Arc::clone(&right) as ArrayRef,
575+
])
576+
.unwrap();
577+
let result = result.as_any().downcast_ref::<ListArray>().unwrap();
578+
579+
assert!(result.offsets().ptr_eq(left.offsets()));
580+
assert_eq!(result.value_offsets(), &[0, 2, 4]);
581+
assert!(result.is_null(1));
582+
}
583+
584+
#[test]
585+
fn mixed_null_row_with_hidden_values_uses_general_path() {
586+
let left =
587+
list_with_validity(vec![1, 2, 3, 4], vec![0, 2, 4], Some(vec![true, false]));
588+
let right = list_with_validity(
589+
vec![10, 20, 30, 40],
590+
vec![0, 2, 4],
591+
Some(vec![true, true]),
592+
);
593+
594+
let result = arrays_zip_inner(&[
595+
Arc::clone(&left) as ArrayRef,
596+
Arc::clone(&right) as ArrayRef,
597+
])
598+
.unwrap();
599+
let result = result.as_any().downcast_ref::<ListArray>().unwrap();
600+
let values = result
601+
.values()
602+
.as_any()
603+
.downcast_ref::<StructArray>()
604+
.unwrap();
605+
606+
assert!(!result.offsets().ptr_eq(left.offsets()));
607+
assert_eq!(result.value_offsets(), &[0, 2, 4]);
608+
assert!(values.column(0).is_null(2));
609+
assert!(values.column(0).is_null(3));
610+
assert!(!values.column(1).is_null(2));
611+
assert!(!values.column(1).is_null(3));
612+
}
613+
}

0 commit comments

Comments
 (0)