Skip to content

Commit 9f49d10

Browse files
committed
perf: normalize only the child range a sliced list references
normalize_nested_floats rebuilt a list's whole child array, but a sliced list keeps its child whole, and explode hands out slices of one child array for a whole input batch. Rebuild only the range the offsets reference, at every depth, and rebase the offsets onto it. The float_arrays bench gains array_distinct and array_union cases over whole and sliced lists.
1 parent 7de7145 commit 9f49d10

3 files changed

Lines changed: 151 additions & 16 deletions

File tree

‎native/spark-expr/benches/float_arrays.rs‎

Lines changed: 61 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,10 @@
1818
//! Compare Comet's float `sort_array` and `array_remove` with DataFusion's `array_sort` and
1919
//! `array_remove_all` on doubles without zeros or NaNs, where both return the same arrays, which
2020
//! is checked before timing; special-value semantics belong in tests.
21+
//!
22+
//! Comet's `array_distinct` and `array_union` normalize their arguments and then call DataFusion's
23+
//! kernels. Their `_sliced` cases pass a slice of a longer list, as `explode` returns, to show
24+
//! that the normalization covers only the rows of the slice.
2125
2226
use arrow::array::{Array, ArrayRef, Float64Array, ListArray};
2327
use arrow::buffer::{NullBuffer, OffsetBuffer};
@@ -26,9 +30,12 @@ use criterion::{criterion_group, criterion_main, BenchmarkId, Criterion};
2630
use datafusion::common::config::ConfigOptions;
2731
use datafusion::common::ScalarValue;
2832
use datafusion::functions_nested::remove::array_remove_all_udf;
33+
use datafusion::functions_nested::set_ops::{array_distinct_udf, array_union_udf};
2934
use datafusion::functions_nested::sort::array_sort_udf;
3035
use datafusion::logical_expr::{ColumnarValue, ScalarFunctionArgs, ScalarUDF};
31-
use datafusion_comet_spark_expr::{SparkArrayRemove, SparkFloatArrayContains, SparkSortArray};
36+
use datafusion_comet_spark_expr::{
37+
SparkArrayRemove, SparkArraySetOp, SparkFloatArrayContains, SparkSortArray,
38+
};
3239
use datafusion_spark::function::array::array_contains::SparkArrayContains;
3340
use std::hint::black_box;
3441
use std::sync::Arc;
@@ -41,22 +48,28 @@ fn value(i: usize) -> f64 {
4148
((i * 7919) % 101) as f64 * 0.5 + 1.0
4249
}
4350

44-
/// `ROWS` lists of `len` doubles, with every tenth list and every seventh element null if
51+
/// `rows` lists of `len` doubles, with every tenth list and every seventh element null if
4552
/// `nulls`.
46-
fn lists(len: usize, nulls: bool) -> ArrayRef {
53+
fn lists(rows: usize, len: usize, nulls: bool) -> ArrayRef {
4754
let values = if nulls {
48-
Float64Array::from_iter((0..ROWS * len).map(|i| (i % 7 != 0).then(|| value(i))))
55+
Float64Array::from_iter((0..rows * len).map(|i| (i % 7 != 0).then(|| value(i))))
4956
} else {
50-
Float64Array::from_iter_values((0..ROWS * len).map(value))
57+
Float64Array::from_iter_values((0..rows * len).map(value))
5158
};
5259
Arc::new(ListArray::new(
5360
Arc::new(Field::new_list_field(DataType::Float64, true)),
54-
OffsetBuffer::from_lengths(std::iter::repeat_n(len, ROWS)),
61+
OffsetBuffer::from_lengths(std::iter::repeat_n(len, rows)),
5562
Arc::new(values),
56-
nulls.then(|| NullBuffer::from_iter((0..ROWS).map(|row| row % 10 != 0))),
63+
nulls.then(|| NullBuffer::from_iter((0..rows).map(|row| row % 10 != 0))),
5764
))
5865
}
5966

67+
/// `ROWS` lists sliced from the middle of 16 times as many. `explode` of a list of lists returns
68+
/// slices like this, one per output batch, which all keep the same child array.
69+
fn sliced_lists(len: usize, nulls: bool) -> ArrayRef {
70+
lists(16 * ROWS, len, nulls).slice(8 * ROWS, ROWS)
71+
}
72+
6073
fn args(args: Vec<ColumnarValue>, list: &ArrayRef) -> ScalarFunctionArgs {
6174
ScalarFunctionArgs {
6275
arg_fields: args
@@ -81,9 +94,12 @@ fn criterion_benchmark(c: &mut Criterion) {
8194
// The native path other element types take: array_has plus Spark's null semantics.
8295
let datafusion_contains = Arc::new(ScalarUDF::new_from_impl(SparkArrayContains::default()));
8396
let (datafusion_sort, datafusion_remove) = (array_sort_udf(), array_remove_all_udf());
97+
let comet_distinct = ScalarUDF::new_from_impl(SparkArraySetOp::distinct());
98+
let comet_union = ScalarUDF::new_from_impl(SparkArraySetOp::union());
99+
let (datafusion_distinct, datafusion_union) = (array_distinct_udf(), array_union_udf());
84100
for len in [8, 50] {
85101
for nulls in [false, true] {
86-
let list = lists(len, nulls);
102+
let list = lists(ROWS, len, nulls);
87103
let data = format!("len={len}_null={nulls}");
88104
let column = ColumnarValue::Array(Arc::clone(&list));
89105
let scalar = |value: ScalarValue| ColumnarValue::Scalar(value);
@@ -121,9 +137,17 @@ fn criterion_benchmark(c: &mut Criterion) {
121137
let row_values =
122138
Float64Array::from_iter_values((0..ROWS).map(|row| value(row * len + 1)));
123139
let contains_column_args = args(
124-
vec![column, ColumnarValue::Array(Arc::new(row_values))],
140+
vec![column.clone(), ColumnarValue::Array(Arc::new(row_values))],
125141
&list,
126142
);
143+
let distinct_args = args(vec![column.clone()], &list);
144+
// A union of a list with itself: the right side adds no elements, but it is still
145+
// normalized and looked up.
146+
let union_args = args(vec![column.clone(), column], &list);
147+
let sliced = sliced_lists(len, nulls);
148+
let sliced_column = ColumnarValue::Array(Arc::clone(&sliced));
149+
let sliced_distinct_args = args(vec![sliced_column.clone()], &sliced);
150+
let sliced_union_args = args(vec![sliced_column.clone(), sliced_column], &sliced);
127151
let cases = [
128152
(
129153
"sort_array",
@@ -160,6 +184,34 @@ fn criterion_benchmark(c: &mut Criterion) {
160184
&contains_column_args,
161185
&contains_column_args,
162186
),
187+
(
188+
"array_distinct",
189+
&comet_distinct,
190+
&datafusion_distinct,
191+
&distinct_args,
192+
&distinct_args,
193+
),
194+
(
195+
"array_distinct_sliced",
196+
&comet_distinct,
197+
&datafusion_distinct,
198+
&sliced_distinct_args,
199+
&sliced_distinct_args,
200+
),
201+
(
202+
"array_union",
203+
&comet_union,
204+
&datafusion_union,
205+
&union_args,
206+
&union_args,
207+
),
208+
(
209+
"array_union_sliced",
210+
&comet_union,
211+
&datafusion_union,
212+
&sliced_union_args,
213+
&sliced_union_args,
214+
),
163215
];
164216
for (op, comet, datafusion, comet_args, datafusion_args) in cases {
165217
let evaluate = |udf: &ScalarUDF, args: &ScalarFunctionArgs| {

‎native/spark-expr/src/array_funcs/array_set_ops.rs‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -195,6 +195,35 @@ mod tests {
195195
Ok(())
196196
}
197197

198+
/// A sliced argument keeps its whole child array, which the normalization trims, so the
199+
/// rows outside the slice must not leak into the result.
200+
#[test]
201+
fn sliced_input() -> Result<()> {
202+
let left = list(&[
203+
Some(vec![Some(NEGATIVE_NAN), Some(3.0)]),
204+
Some(vec![Some(-0.0), Some(f64::NAN), Some(0.0)]),
205+
None,
206+
Some(vec![Some(PAYLOAD_NAN)]),
207+
])
208+
.slice(1, 2);
209+
let result = invoke_arrays(SparkArraySetOp::distinct(), vec![Arc::clone(&left)])?;
210+
assert_eq!(bits(&result), vec![Some(vec![Some(ZERO), Some(NAN)]), None]);
211+
212+
let right = list(&[
213+
Some(vec![Some(-0.0)]),
214+
Some(vec![Some(NEGATIVE_NAN), Some(1.0)]),
215+
Some(vec![Some(2.0)]),
216+
])
217+
.slice(1, 2);
218+
let result = invoke_arrays(SparkArraySetOp::union(), vec![left, right])?;
219+
let expected = vec![
220+
Some(vec![Some(ZERO), Some(NAN), Some(1.0f64.to_bits())]),
221+
None,
222+
];
223+
assert_eq!(bits(&result), expected);
224+
Ok(())
225+
}
226+
198227
#[test]
199228
fn nested_floats_are_normalized() -> Result<()> {
200229
let input = structs(&[-0.0, 0.0, NEGATIVE_NAN, f64::NAN]);

‎native/spark-expr/src/float_semantics/normalize.rs‎

Lines changed: 61 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -18,8 +18,9 @@
1818
use super::normalize_float;
1919
use arrow::array::{
2020
Array, ArrayRef, AsArray, FixedSizeListArray, Float32Array, Float64Array, LargeListArray,
21-
ListArray, StructArray,
21+
ListArray, OffsetSizeTrait, StructArray,
2222
};
23+
use arrow::buffer::OffsetBuffer;
2324
use arrow::datatypes::{DataType, Float32Type, Float64Type, Schema};
2425
use arrow::record_batch::RecordBatch;
2526
use datafusion::common::{Result, ScalarValue};
@@ -291,6 +292,10 @@ pub(crate) fn is_nested_with_float_leaf(dt: &DataType) -> bool {
291292
/// keeps the rebuild proportional to the float data, and it also leaves empty structs alone:
292293
/// `StructArray::new` cannot infer a length from zero columns and would panic. An empty struct
293294
/// reaches this code through Iceberg's `_partition` metadata column on an unpartitioned table.
295+
///
296+
/// A list is rebuilt over only the part of its child array that its offsets reference. A sliced
297+
/// list keeps its whole child array, and `explode` returns slices of one child array for a whole
298+
/// input batch, so rebuilding the child as is would copy all of it for every slice.
294299
pub fn normalize_nested_floats(array: &ArrayRef) -> ArrayRef {
295300
if !has_float_leaf(array.data_type()) {
296301
return Arc::clone(array);
@@ -300,21 +305,21 @@ pub fn normalize_nested_floats(array: &ArrayRef) -> ArrayRef {
300305
DataType::Float32 | DataType::Float64 => normalize_floats(array),
301306
DataType::List(field) => {
302307
let list = array.as_list::<i32>();
303-
let normalized_values = normalize_nested_floats(list.values());
308+
let (offsets, values) = referenced_values(list.offsets(), list.values());
304309
Arc::new(ListArray::new(
305310
Arc::clone(field),
306-
list.offsets().clone(),
307-
normalized_values,
311+
offsets,
312+
normalize_nested_floats(&values),
308313
list.nulls().cloned(),
309314
))
310315
}
311316
DataType::LargeList(field) => {
312317
let list = array.as_list::<i64>();
313-
let normalized_values = normalize_nested_floats(list.values());
318+
let (offsets, values) = referenced_values(list.offsets(), list.values());
314319
Arc::new(LargeListArray::new(
315320
Arc::clone(field),
316-
list.offsets().clone(),
317-
normalized_values,
321+
offsets,
322+
normalize_nested_floats(&values),
318323
list.nulls().cloned(),
319324
))
320325
}
@@ -342,6 +347,23 @@ pub fn normalize_nested_floats(array: &ArrayRef) -> ArrayRef {
342347
}
343348
}
344349

350+
/// The part of a list's child array that `offsets` references, with the offsets rebased onto it.
351+
/// The child is returned as is when the offsets span all of it.
352+
fn referenced_values<O: OffsetSizeTrait>(
353+
offsets: &OffsetBuffer<O>,
354+
values: &ArrayRef,
355+
) -> (OffsetBuffer<O>, ArrayRef) {
356+
let start = offsets[0].as_usize();
357+
let end = offsets[offsets.len() - 1].as_usize();
358+
if start == 0 && end == values.len() {
359+
return (offsets.clone(), Arc::clone(values));
360+
}
361+
(
362+
OffsetBuffer::from_lengths(offsets.lengths()),
363+
values.slice(start, end - start),
364+
)
365+
}
366+
345367
#[cfg(test)]
346368
mod tests {
347369
use super::*;
@@ -718,6 +740,38 @@ mod tests {
718740
assert_eq!(inner.value(1).to_bits(), f64::NAN.to_bits());
719741
}
720742

743+
/// A sliced list keeps its whole child array. Only the part its rows reference is rebuilt, at
744+
/// every depth, and the rows keep their values and nulls.
745+
#[test]
746+
fn test_normalize_sliced_list_rebuilds_only_referenced_values() {
747+
let rows = (0..8).map(|i| (i != 4).then(|| vec![Some(-0.0), Some(i as f64)]));
748+
let list = ListArray::from_iter_primitive::<Float64Type, _, _>(rows);
749+
let sliced: ArrayRef = Arc::new(list.slice(3, 3));
750+
751+
let normalized = normalize_nested_floats(&sliced);
752+
let normalized = normalized.as_list::<i32>();
753+
assert_eq!(normalized.offsets().as_ref(), &[0, 2, 2, 4]);
754+
assert!(normalized.is_null(1));
755+
let values = normalized.values().as_primitive::<Float64Type>();
756+
let bits: Vec<u64> = values.values().iter().map(|v| v.to_bits()).collect();
757+
assert_eq!(bits, [0.0f64, 3.0, 0.0, 5.0].map(f64::to_bits));
758+
759+
// Slicing the outer list of a list of lists keeps the inner list whole.
760+
let field = Arc::new(Field::new_list_field(list.data_type().clone(), true));
761+
let outer = ListArray::new(
762+
field,
763+
OffsetBuffer::from_lengths([1; 8]),
764+
Arc::new(list),
765+
None,
766+
);
767+
let sliced: ArrayRef = Arc::new(outer.slice(3, 3));
768+
769+
let normalized = normalize_nested_floats(&sliced);
770+
let inner = normalized.as_list::<i32>().values().as_list::<i32>();
771+
assert_eq!(inner.offsets().as_ref(), &[0, 2, 2, 4]);
772+
assert_eq!(inner.values().len(), 4);
773+
}
774+
721775
/// An empty struct sibling of a float field must survive normalization. Iceberg exposes
722776
/// `_partition` as `struct<>` on an unpartitioned table, and rebuilding it would panic
723777
/// because `StructArray::new` cannot infer a length from zero columns.

0 commit comments

Comments
 (0)