Skip to content

Commit 431355f

Browse files
authored
perf(functions-aggregate): coalesce small ordered ARRAY_AGG batches (apache#25497)
## Which issue does this PR close? - Closes apache#25199 ## Rationale for this change apache#24392 changed OrderSensitiveArrayAggAccumulator to retain payloads as Arrow arrays instead of converting each value to a ScalarValue. This significantly reduced memory usage for reasonably sized input batches. However, the accumulator currently stores one ArrayRef per update_batch() call. Each array has a fixed cost from its ArrayData, buffer allocation, and Arc, regardless of how many rows it contains. Ordered `ARRAY_AGG` does not support a native `GroupsAccumulator` because `groups_accumulator_supported` requires `order_bys` to be empty. Grouped execution therefore falls back to `GroupsAccumulatorAdapter`, which calls `update_batch()` once per group per input batch. With a high-cardinality `GROUP BY`, these calls often contain only one or two rows. Without this change, each call retains a separate `ArrayRef`, so the accumulator pays the fixed per-array allocation cost for many small Arrow arrays, increasing the per-row memory footprint. ## What changes are included in this PR? - Coalesce consecutive small ordered `ARRAY_AGG` payload batches when the combined batch has at most 64 rows and the combined payload buffers use at most 4 KiB. - Add tests for the row threshold, batch and entry indices, ordering across coalesced batches, and coalescing during partial-state `merge_batch()`. - Add `Dictionary<Int8, Utf8>` and `Utf8View` tests that coalesce beyond 64 input rows and verify the evaluated order. - Add a `Utf8` test confirming that large payloads remain in separate batches. - Add ordered `ARRAY_AGG` benchmarks for random and preordered input with 1, 8, 64, and 2,048 rows per `update_batch()`. - Add an update-only benchmark with 4 KiB `Utf8` values and one row per call, using a generalized benchmark fixture that supports `Utf8` payloads. ### Retained memory Retained memory was measured using `Accumulator::size()` after inserting 2,048 Int64 payloads with an Int64 ordering key and before calling evaluate(). The same measurement code was used for the baseline after [apache#24392](apache#24392) and for this change. | Rows/update | Batches | Total retained (with this change) | Bytes/row (with this change) | Total retained (baseline [apache#24392](https://github.com/apache/datafusion/pull/24392)| Bytes/row (baseline [apache#24392](apache#24392)) | | ----------: | ------: | --------------------------------: | ---------------------------: | ----------------------------------------------------------------------------------- | ------------------------------------------------------------------------------ | | 1 | 32 | 104,701 B | 51.12 B/row | 445,181 B | 217.37 B/row | | 8 | 32 | 90,365 B | 44.12 B/row | 115,453 B | 56.37 B/row | | 64 | 32 | 88,573 B | 43.25 B/row | 88,573 B | 43.25 B/row | | 2048 | 1 | 84,901 B | 41.46 B/row | 84,901 B | 41.46 B/row | The worst-case one-row update footprint decreases from 217.37 B/row to 51.12 B/row. Inputs already at or above the 64-row coalescing threshold retain the existing memory footprint. ### Benchmark The `ordered_array_agg` Criterion benchmarks had been tested with following comment for this pr and `main`: ```bash cargo bench -p datafusion-functions-aggregate --bench array_agg -- ordered_array_agg` ``` Each Int64 case processes 2,048 rows, using 1, 8, 64, or 2,048 rows per `update_batch()` call. The inputs are either preordered or shuffled with a fixed seed. Timing includes creating the accumulator, calling `update_batch()`, and calling `evaluate()`. The wide-payload case processes 2,048 Utf8 values of 4 KiB each, one row per `update_batch()` call. It does not include `evaluate()`. | Benchmark case | main (µs) | PR (µs) | | :--- | ---: | ---: | | i64 ordered,1 row/update | 1,527.20 | 779.37 (-48.97%) | | i64 random,1 row/update | 2,207.60 | 1,052.50 (-52.32%) | | i64 ordered,8 rows/update | 221.42 | 133.85 (-39.55%) | | i64 random,8 rows/update | 454.68 | 363.10 (-20.14%) | | i64 ordered,64 rows/update | 50.37 | 50.44 (+0.14%) | | i64 random,64 rows/update | 258.03 | 262.51 (+1.74%) | | i64 ordered,2,048 rows/update | 18.68 | 19.00 (+1.71%) | | i64 random,2,048 rows/update | 228.52 | 236.29 (+3.40%) | | Utf8 4 KiB,1 row/update(update_batches only) | 2,417.90 | 2,642.90 (+9.31%) | ## Are these changes tested? Added unit tests covering: - coalescing small batches exactly up to the threshold; - creating a new batch when the threshold would be exceeded; - preserving the correct batch_idx and row_idx for entries; - sorting values across multiple coalesced batches; - coalescing small partial-state payloads passed through merge_batch(). Added Criterion benchmarks for ordered ARRAY_AGG using random and preordered input with 1, 8, 64, and 2,048 rows per update_batch(). The following commands have been executed and passed: - `cargo test -p datafusion-functions-aggregate --lib array_agg::tests` - ` cargo clippy -p datafusion-functions-aggregate --all-targets --all-features -- -D warnings` - `cargo bench -p datafusion-functions-aggregate --bench array_agg --no-run` - `cargo bench -p datafusion-functions-aggregate --bench array_agg -- ordered_array_agg` - `cargo test --profile=ci --test sqllogictests` - `cargo test -p datafusion` - `cargo test -p datafusion-cli` ## Are there any user-facing changes? No
1 parent b73054a commit 431355f

2 files changed

Lines changed: 598 additions & 16 deletions

File tree

‎datafusion/functions-aggregate/benches/array_agg.rs‎

Lines changed: 235 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -19,21 +19,25 @@ use std::hint::black_box;
1919
use std::sync::Arc;
2020

2121
use arrow::array::{
22-
Array, ArrayRef, ArrowPrimitiveType, AsArray, ListArray, NullBufferBuilder,
23-
StringArray,
22+
Array, ArrayRef, ArrowPrimitiveType, AsArray, Int64Array, ListArray,
23+
NullBufferBuilder, StringArray,
2424
};
25-
use arrow::datatypes::{DataType, Field, Int64Type};
26-
use criterion::{Criterion, criterion_group, criterion_main};
27-
use datafusion_expr::Accumulator;
25+
use arrow::datatypes::{DataType, Field, FieldRef, Int64Type, Schema};
26+
use criterion::{BatchSize, Criterion, criterion_group, criterion_main};
27+
use datafusion_expr::function::AccumulatorArgs;
28+
use datafusion_expr::{Accumulator, AggregateUDFImpl};
2829
use datafusion_functions_aggregate::array_agg::{
29-
ArrayAggAccumulator, DistinctArrayAggAccumulator,
30+
ArrayAgg, ArrayAggAccumulator, DistinctArrayAggAccumulator,
3031
};
32+
use datafusion_physical_expr::{PhysicalSortExpr, expressions::col};
33+
use datafusion_physical_expr_common::physical_expr::PhysicalExpr;
3134

3235
use arrow::buffer::OffsetBuffer;
3336
use arrow::util::bench_util::create_primitive_array;
3437
use rand::Rng;
3538
use rand::SeedableRng;
3639
use rand::prelude::StdRng;
40+
use rand::seq::SliceRandom;
3741

3842
/// Returns fixed seedable RNG
3943
pub fn seedable_rng() -> StdRng {
@@ -288,5 +292,229 @@ fn distinct_array_agg_benchmark(c: &mut Criterion) {
288292
);
289293
}
290294

291-
criterion_group!(benches, array_agg_benchmark, distinct_array_agg_benchmark);
295+
/// Precomputes the schema, physical expressions, sort expression, and aggregate
296+
/// metadata so each benchmark iteration can focus on accumulator operations.
297+
struct OrderedArrayAggBenchFixture {
298+
schema: Schema,
299+
value_expr: Arc<dyn PhysicalExpr>,
300+
value_field: FieldRef,
301+
order_by: PhysicalSortExpr,
302+
array_agg: Arc<dyn AggregateUDFImpl>,
303+
return_field: FieldRef,
304+
}
305+
306+
impl OrderedArrayAggBenchFixture {
307+
fn new(value_type: &DataType, input_preordered: bool) -> Self {
308+
let schema = Schema::new(vec![
309+
Field::new("value", value_type.clone(), false),
310+
Field::new("ordering", DataType::Int64, false),
311+
]);
312+
313+
let value_expr = col("value", &schema).unwrap();
314+
let ordering_expr = col("ordering", &schema).unwrap();
315+
316+
let value_field = value_expr.return_field(&schema).unwrap();
317+
318+
let order_by = PhysicalSortExpr::new(
319+
ordering_expr,
320+
arrow::compute::SortOptions {
321+
descending: false,
322+
nulls_first: false,
323+
},
324+
);
325+
326+
let array_agg = Arc::new(ArrayAgg::default())
327+
.with_beneficial_ordering(input_preordered)
328+
.unwrap()
329+
.unwrap();
330+
331+
let return_field = Field::new(
332+
"array_agg",
333+
DataType::List(Field::new_list_field(value_type.clone(), true).into()),
334+
true,
335+
)
336+
.into();
337+
338+
Self {
339+
schema,
340+
value_expr,
341+
value_field,
342+
order_by,
343+
array_agg,
344+
return_field,
345+
}
346+
}
347+
fn create_accumulator(&self) -> Box<dyn Accumulator> {
348+
self.array_agg
349+
.accumulator(AccumulatorArgs {
350+
return_field: Arc::clone(&self.return_field),
351+
schema: &self.schema,
352+
expr_fields: std::slice::from_ref(&self.value_field),
353+
ignore_nulls: false,
354+
order_bys: std::slice::from_ref(&self.order_by),
355+
is_reversed: false,
356+
name: "array_agg(value ORDER BY ordering)",
357+
is_distinct: false,
358+
exprs: std::slice::from_ref(&self.value_expr),
359+
})
360+
.unwrap()
361+
}
362+
}
363+
364+
const ORDERED_ARRAY_AGG_ROWS: usize = 2048;
365+
366+
fn create_ordered_array_agg_batches(
367+
rows_per_batch: usize,
368+
input_preordered: bool,
369+
) -> Vec<[ArrayRef; 2]> {
370+
assert!(
371+
rows_per_batch > 0,
372+
"rows_per_batch must be greater than zero"
373+
);
374+
375+
let upper_value: i64 = ORDERED_ARRAY_AGG_ROWS.try_into().unwrap();
376+
let mut values = (0..upper_value).collect::<Vec<i64>>();
377+
378+
if !input_preordered {
379+
let mut rng = StdRng::seed_from_u64(42);
380+
values.shuffle(&mut rng);
381+
}
382+
383+
values
384+
.chunks(rows_per_batch)
385+
.map(|batch_values| {
386+
let values = Arc::new(Int64Array::from(batch_values.to_vec())) as ArrayRef;
387+
388+
[
389+
Arc::clone(&values),
390+
values, // Reuse the payload values as ordering keys.
391+
]
392+
})
393+
.collect()
394+
}
395+
396+
fn ordered_array_agg_bench(
397+
c: &mut Criterion,
398+
name: &str,
399+
value_type: &DataType,
400+
batches: &[[ArrayRef; 2]],
401+
input_preordered: bool,
402+
) {
403+
c.bench_function(name, |b| {
404+
let fixture = OrderedArrayAggBenchFixture::new(value_type, input_preordered);
405+
b.iter(|| {
406+
let mut accumulator = fixture.create_accumulator();
407+
408+
for batch in batches {
409+
accumulator
410+
.update_batch(batch)
411+
.expect("update_batch should succeed");
412+
}
413+
414+
let result = accumulator.evaluate().expect("evaluate should succeed");
415+
416+
black_box(result);
417+
})
418+
});
419+
}
420+
421+
fn ordered_array_agg_benchmark(c: &mut Criterion) {
422+
for rows_per_batch in [1, 8, 64, ORDERED_ARRAY_AGG_ROWS] {
423+
let ordered_batches = create_ordered_array_agg_batches(rows_per_batch, true);
424+
ordered_array_agg_bench(
425+
c,
426+
&format!(
427+
"ordered_array_agg i64 ordered input, \
428+
{rows_per_batch} rows per update_batch"
429+
),
430+
&DataType::Int64,
431+
&ordered_batches,
432+
true,
433+
);
434+
let shuffled_batches = create_ordered_array_agg_batches(rows_per_batch, false);
435+
ordered_array_agg_bench(
436+
c,
437+
&format!(
438+
"ordered_array_agg i64 random input, \
439+
{rows_per_batch} rows per update_batch"
440+
),
441+
&DataType::Int64,
442+
&shuffled_batches,
443+
false,
444+
);
445+
}
446+
}
447+
448+
/// Creates preordered batches with a 4 KiB Utf8 payload per row.
449+
fn create_wide_utf8_batches(rows_per_batch: usize) -> Vec<[ArrayRef; 2]> {
450+
assert!(
451+
rows_per_batch > 0,
452+
"rows_per_batch must be greater than zero"
453+
);
454+
455+
let values = vec!["x".repeat(4 * 1_024); ORDERED_ARRAY_AGG_ROWS];
456+
457+
values
458+
.chunks(rows_per_batch)
459+
.enumerate()
460+
.map(|(idx, batch_values)| {
461+
let payload =
462+
Arc::new(StringArray::from_iter_values(batch_values.iter())) as ArrayRef;
463+
let start = idx * rows_per_batch;
464+
let ordering_values = Arc::new(Int64Array::from(
465+
(start..start + batch_values.len())
466+
.map(|row| i64::try_from(row).unwrap())
467+
.collect::<Vec<_>>(),
468+
)) as ArrayRef;
469+
470+
[payload, ordering_values]
471+
})
472+
.collect()
473+
}
474+
475+
fn ordered_array_agg_update_only_bench(
476+
c: &mut Criterion,
477+
name: &str,
478+
value_type: &DataType,
479+
batches: &[[ArrayRef; 2]],
480+
input_preordered: bool,
481+
) {
482+
let fixture = OrderedArrayAggBenchFixture::new(value_type, input_preordered);
483+
484+
c.bench_function(name, |b| {
485+
b.iter_batched(
486+
|| fixture.create_accumulator(),
487+
|mut accumulator| {
488+
for batch in batches {
489+
accumulator
490+
.update_batch(batch)
491+
.expect("update_batch should succeed");
492+
}
493+
494+
// Return the accumulator so Criterion drops it after timing the updates.
495+
accumulator
496+
},
497+
BatchSize::PerIteration,
498+
);
499+
});
500+
}
501+
502+
fn ordered_array_agg_wide_utf8_benchmark(c: &mut Criterion) {
503+
let ordered_batches = create_wide_utf8_batches(1);
504+
ordered_array_agg_update_only_bench(
505+
c,
506+
"ordered_array_agg utf8 4 KiB, 1 row per update_batch",
507+
&DataType::Utf8,
508+
&ordered_batches,
509+
true,
510+
);
511+
}
512+
513+
criterion_group!(
514+
benches,
515+
array_agg_benchmark,
516+
distinct_array_agg_benchmark,
517+
ordered_array_agg_benchmark,
518+
ordered_array_agg_wide_utf8_benchmark
519+
);
292520
criterion_main!(benches);

0 commit comments

Comments
 (0)