Skip to content

Commit 16fbfa8

Browse files
authored
bench(functions-aggregate): benchmark coalescing peer first_value into a struct (apache#23682) (apache#24559)
## Which issue does this PR close? - Part of apache#23600 (the `first_value`/`last_value` coalesce epic). ## Rationale for this change The `CoalesceFirstLast` optimizer rule (apache#23682) rewrites N peer `first_value(col ORDER BY o)` expressions that share one `ORDER BY` into a single `first_value(named_struct(...) ORDER BY o)`. The win is at the accumulator level: N independent argmax passes collapse into one struct-valued argmax — one per-row ordering compare instead of N, one slot per group instead of N. **This PR adds the benchmark that quantifies that win**, so apache#23682 can cite concrete numbers as its performance justification. Nothing in the suite measured this head-to-head before. ## What changes are included in this PR? Adds `coalesce_comparison_bench` to `functions-aggregate/benches/first_last.rs`, producing two cases in the same run: - `first_value coalesce_peers(i64,utf8,f64) separate x3` — three independent primitive `first_value` GroupsAccumulators (the pre-rewrite plan) - `first_value coalesce_peers(i64,utf8,f64) coalesced struct` — one struct-valued GroupsAccumulator carrying the same three columns (the post-rewrite plan) The struct path exercises the native nested `GroupsAccumulator` merged in apache#23628. Reuses the existing `prepare_typed_groups_accumulator` / `create_struct_array` helpers; no new dependencies or imports. ## Are these changes tested? Benchmark-only; compiles under `cargo check --benches`. Triggered `run benchmark first_last` on this PR for the head-to-head numbers — posted in a comment below.
1 parent 1bf24c9 commit 16fbfa8

1 file changed

Lines changed: 179 additions & 0 deletions

File tree

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

Lines changed: 179 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -452,6 +452,172 @@ fn create_list_of_struct_array(n: usize, list_len: usize, null_density: f32) ->
452452
))
453453
}
454454

455+
/// Drive one coalesce-peers variant: `separate xN` (pre-rewrite, one primitive
456+
/// accumulator per column) vs `coalesced struct` (post-rewrite, one struct
457+
/// accumulator). Each accumulator is primed with `worst_ord` (the always-losing
458+
/// ordering value), then fed one `ord` per iteration from `iter_ords`. Varying
459+
/// `iter_ords` selects which path dominates — see [`coalesce_comparison_bench`].
460+
#[expect(clippy::too_many_arguments)]
461+
fn run_coalesce_variant(
462+
c: &mut Criterion,
463+
name: &str,
464+
variant: &str,
465+
column_values: &[ArrayRef],
466+
struct_values: &ArrayRef,
467+
worst_ord: &ArrayRef,
468+
iter_ords: &[ArrayRef],
469+
group_indices: &[usize],
470+
num_groups: usize,
471+
) {
472+
// Pre-rewrite: one accumulator per column.
473+
c.bench_function(
474+
&format!("{name} separate x{} {variant}", column_values.len()),
475+
|b| {
476+
b.iter_batched(
477+
|| {
478+
column_values
479+
.iter()
480+
.map(|values| {
481+
let mut acc = prepare_typed_groups_accumulator(
482+
true,
483+
values.data_type().clone(),
484+
);
485+
acc.update_batch(
486+
&[Arc::clone(values), Arc::clone(worst_ord)],
487+
group_indices,
488+
None,
489+
num_groups,
490+
)
491+
.unwrap();
492+
acc
493+
})
494+
.collect::<Vec<_>>()
495+
},
496+
|mut accumulators| {
497+
for ord in iter_ords {
498+
for (acc, values) in accumulators.iter_mut().zip(column_values) {
499+
#[expect(clippy::unit_arg)]
500+
black_box(
501+
acc.update_batch(
502+
&[Arc::clone(values), Arc::clone(ord)],
503+
group_indices,
504+
None,
505+
num_groups,
506+
)
507+
.unwrap(),
508+
);
509+
}
510+
}
511+
},
512+
BatchSize::SmallInput,
513+
)
514+
},
515+
);
516+
517+
// Post-rewrite: a single struct-valued accumulator.
518+
c.bench_function(&format!("{name} coalesced struct {variant}"), |b| {
519+
b.iter_batched(
520+
|| {
521+
let mut acc = prepare_typed_groups_accumulator(
522+
true,
523+
struct_values.data_type().clone(),
524+
);
525+
acc.update_batch(
526+
&[Arc::clone(struct_values), Arc::clone(worst_ord)],
527+
group_indices,
528+
None,
529+
num_groups,
530+
)
531+
.unwrap();
532+
acc
533+
},
534+
|mut accumulator| {
535+
for ord in iter_ords {
536+
#[expect(clippy::unit_arg)]
537+
black_box(
538+
accumulator
539+
.update_batch(
540+
&[Arc::clone(struct_values), Arc::clone(ord)],
541+
group_indices,
542+
None,
543+
num_groups,
544+
)
545+
.unwrap(),
546+
);
547+
}
548+
},
549+
BatchSize::SmallInput,
550+
)
551+
});
552+
}
553+
554+
/// Head-to-head for the coalesce-peers rewrite: N independent primitive
555+
/// `first_value` accumulators (the pre-rewrite plan) vs one struct-valued
556+
/// accumulator carrying the same N columns (the post-rewrite plan). Runs two
557+
/// variants, since the two plans differ on two separable costs:
558+
///
559+
/// - `(winner stable)` reuses one `ord` every iteration. After the first
560+
/// iteration the running winner already holds the best value in `ord`, so
561+
/// this is dominated by compare-and-reject — the per-row ordering comparison
562+
/// the rewrite collapses (N compares -> 1).
563+
/// - `(winner changes)` feeds a distinct, strictly-decreasing `ord` per
564+
/// iteration so every row becomes a new winner (smaller ord wins; `worst_ord`
565+
/// = i64::MAX primes the loser). This forces the running value to be
566+
/// replaced+copied on every row, exercising the update path the winner-stable
567+
/// case skips — where the struct plan copies one wider row vs N narrow ones.
568+
#[expect(clippy::needless_pass_by_value)]
569+
fn coalesce_comparison_bench(
570+
c: &mut Criterion,
571+
name: &str,
572+
column_values: Vec<ArrayRef>,
573+
struct_values: ArrayRef,
574+
ord: ArrayRef,
575+
num_groups: usize,
576+
) {
577+
const ITERS: usize = 100;
578+
let n = ord.len();
579+
let group_indices: Vec<usize> = (0..n).map(|i| i % num_groups).collect();
580+
let worst_ord: ArrayRef = Arc::new(Int64Array::from(vec![i64::MAX; n]));
581+
582+
// Winner-stable: the same `ord` every iteration.
583+
let stable_ords: Vec<ArrayRef> = (0..ITERS).map(|_| Arc::clone(&ord)).collect();
584+
585+
// Winner-changing: strictly decreasing across (iteration, row), and below
586+
// `worst_ord`, so every row wins and updates the running value. Built once,
587+
// outside the timed loop.
588+
let changing_ords: Vec<ArrayRef> = (0..ITERS)
589+
.map(|k| {
590+
let base = i64::MAX - 1 - (k as i64) * (n as i64);
591+
Arc::new(Int64Array::from(
592+
(0..n as i64).map(|i| base - i).collect::<Vec<i64>>(),
593+
)) as ArrayRef
594+
})
595+
.collect();
596+
597+
run_coalesce_variant(
598+
c,
599+
name,
600+
"(winner stable)",
601+
&column_values,
602+
&struct_values,
603+
&worst_ord,
604+
&stable_ords,
605+
&group_indices,
606+
num_groups,
607+
);
608+
run_coalesce_variant(
609+
c,
610+
name,
611+
"(winner changes)",
612+
&column_values,
613+
&struct_values,
614+
&worst_ord,
615+
&changing_ords,
616+
&group_indices,
617+
num_groups,
618+
);
619+
}
620+
455621
fn first_last_nested_benchmark(c: &mut Criterion) {
456622
const N: usize = 65536;
457623
const NUM_GROUPS: usize = 1024;
@@ -510,6 +676,19 @@ fn first_last_nested_benchmark(c: &mut Criterion) {
510676
);
511677
}
512678
}
679+
// Coalesce-peers head-to-head on null-free columns.
680+
let a = Arc::new(create_primitive_array::<Int64Type>(N, 0.0)) as ArrayRef;
681+
let b = Arc::new(create_string_array_with_len::<i32>(N, 0.0, 16)) as ArrayRef;
682+
let d = Arc::new(create_primitive_array::<Float64Type>(N, 0.0)) as ArrayRef;
683+
let struct_values = create_struct_array(N, 0.0);
684+
coalesce_comparison_bench(
685+
c,
686+
"first_value coalesce_peers(i64,utf8,f64)",
687+
vec![a, b, d],
688+
struct_values,
689+
ord,
690+
NUM_GROUPS,
691+
);
513692
}
514693

515694
fn first_last_benchmark(c: &mut Criterion) {

0 commit comments

Comments
 (0)