Skip to content

Commit f47429e

Browse files
jayzhan211Omega359
authored andcommitted
perf: materialize completed groups once in OrderedSingleAggregateStream (apache#25984)
## Which issue does this PR close? - Related to apache#25157. No new issue: this is the Single-mode counterpart of the regression that apache#25639 fixed for `OrderedFinalAggregateStream` (and apache#25312 for `OrderedPartialAggregateStream`). ## Rationale for this change With the default `enable_migration_aggregate = true`, an ordered single-stage aggregate is very slow when its sort prefix completes many groups at once. On the apache#25157 repro (10M rows sorted by `d_year`, 5 distinct `d_year` values, so ~2M groups complete at each boundary) with `target_partitions = 1`, the plan is ```text AggregateExec: mode=Single, gby=[], aggr=[count(1)] AggregateExec: mode=Single, gby=[d_year, brand, class, cat, manu, cnt, amt], aggr=[], ordering_mode=PartiallySorted([0]) ``` and the query takes 8.2 s on main and 0.55 s with this PR. `OrderedSingleAggregateStream` still took completed groups out of the live table `batch_size` rows at a time. Each `EmitTo::First(batch_size)` costs O(groups in the table), because group values are shifted and accumulators split off their tail. The stream also emitted at most one batch per input batch, so a large completed prefix was drained at EOF in O(N²/batch_size). ## What changes are included in this PR? - `OrderedSingleAggregateStream` materializes all completed groups once, then emits `batch_size` slices of that batch before it reads more input. A new `Outputting` state replaces `ProducingOutput`. This follows apache#25312 and apache#25639. - The materialized batch stays reserved together with the table until its last slice is handed off. If it cannot be reserved, it is handed off whole. Spilling is unchanged. - `OrderedAggregateTable<SingleMarker>::take_completed_result_batch` replaces `next_output_batch`. This PR removes the `batch_size` cap in `next_output_batch_inner` and the table's `batch_size` field, because nothing else uses them. ## What is the testing strategy for this PR? New unit tests in `ordered_single_stream.rs`, both failing on main: - `completed_groups_are_emitted_in_batch_size_slices`: with `batch_size = 4`, one key boundary completes 43 groups. All of them are emitted before more input is read, and so are the groups completed at EOF. Every batch has at most `batch_size` rows, each group appears exactly once with the correct sum, and the reservation returns to 0. - `completed_groups_are_handed_off_whole_under_memory_pressure`: the memory limit is set one byte below the unlimited peak. The completed groups are then handed off as one batch without spilling, the results are correct, and the reservation returns to 0. Existing coverage passes: the `aggregates` unit tests, all sqllogictests, and the extended test suite. ### Benchmarks Apple M4 Pro. Both `datafusion-cli` binaries use the `release-nonlto` profile: one built from this branch, one from its base 801b017. Each query file runs its query 3 times. The base and PR binaries were run alternately for 5 rounds, and the table shows the median of 15 runs. | Case (`target_partitions`) | main | PR | PR / main | |---|---|---|---| | apache#25157 repro (1) | 8.170 s | 0.552 s | 0.07 | | apache#25157 repro (8), which does not use this stream | 0.410 s | 0.401 s | 0.98 | | 20M rows sorted by `k = v / 4`, `GROUP BY k` (`Sorted`, ≤ `batch_size` groups completed per batch) (1) | 0.318 s | 0.318 s | 1.00 | | Same file, `GROUP BY k, x % 3` (`PartiallySorted([0])`) (1) | 0.573 s | 0.562 s | 0.98 | | Peak RSS (`/usr/bin/time -l`), apache#25157 repro (1), median of 3 | 500 MB | 434 MB | | The `ordered_group_values` criterion bench, group `fully_ordered_aggregate_exec` (Single mode, `Sorted` input), uses the same profile and 5 alternating rounds. It shows the median of the criterion point estimates. | Bench | main | PR | PR / main | |---|---|---|---| | int_run1 | 824.9 µs | 794.7 µs | 0.96 | | int_run8 | 402.8 µs | 405.9 µs | 1.01 | | int_run128 | 331.0 µs | 334.8 µs | 1.01 | | int_run8192 | 288.3 µs | 292.0 µs | 1.01 | | string_run1 | 1615.6 µs | 1591.4 µs | 0.99 | | string_run8 | 734.2 µs | 728.1 µs | 0.99 | | string_run128 | 582.7 µs | 585.1 µs | 1.00 | | string_run8192 | 526.6 µs | 524.0 µs | 1.00 | ## Are there any user-facing changes? Ordered single-stage aggregation is faster. Query results and public APIs are unchanged.
1 parent cdc5fd7 commit f47429e

8 files changed

Lines changed: 303 additions & 152 deletions

File tree

‎datafusion/physical-plan/benches/ordered_group_values.rs‎

Lines changed: 65 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,8 @@
1919
//! existing streaming hash table on identical batches. Include emission and
2020
//! cross-batch continuation, not just lookup. Input preparation is untimed.
2121
//! The physical-plan benchmark includes aggregation but excludes SQL planning,
22-
//! sorting and I/O; the data already has a proven ordering.
22+
//! sorting and I/O; the data already has a proven ordering. A partially
23+
//! ordered case covers ordered prefixes that complete many groups at once.
2324
2425
use std::hint::black_box;
2526
use std::sync::Arc;
@@ -186,6 +187,8 @@ fn check_case(schema: &SchemaRef, batches: &[Vec<ArrayRef>]) -> (usize, usize) {
186187
fn aggregate_plan(
187188
schema: &SchemaRef,
188189
keys: Vec<Vec<ArrayRef>>,
190+
sort_columns: &[&str],
191+
input_order_mode: &InputOrderMode,
189192
) -> Arc<dyn ExecutionPlan> {
190193
let mut fields = schema.fields().to_vec();
191194
fields.push(Arc::new(Field::new("v", DataType::Int64, false)));
@@ -197,10 +200,11 @@ fn aggregate_plan(
197200
RecordBatch::try_new(Arc::clone(&schema), cols).unwrap()
198201
})
199202
.collect::<Vec<_>>();
200-
let ordering = LexOrdering::new(vec![
201-
PhysicalSortExpr::new_default(col("a", &schema).unwrap()),
202-
PhysicalSortExpr::new_default(col("b", &schema).unwrap()),
203-
])
203+
let ordering = LexOrdering::new(
204+
sort_columns
205+
.iter()
206+
.map(|name| PhysicalSortExpr::new_default(col(name, &schema).unwrap())),
207+
)
204208
.unwrap();
205209
let input =
206210
TestMemoryExec::try_new_exec(&[batches], Arc::clone(&schema), None).unwrap();
@@ -228,7 +232,7 @@ fn aggregate_plan(
228232
schema,
229233
)
230234
.unwrap();
231-
assert_eq!(plan.input_order_mode(), &InputOrderMode::Sorted);
235+
assert_eq!(plan.input_order_mode(), input_order_mode);
232236
Arc::new(plan)
233237
}
234238

@@ -241,7 +245,8 @@ fn aggregation(c: &mut Criterion) {
241245
for strings in [false, true] {
242246
for run_length in [1, 8, 128, 8192] {
243247
let (schema, keys) = inputs(run_length, 8192, strings);
244-
let plan = aggregate_plan(&schema, keys);
248+
let plan =
249+
aggregate_plan(&schema, keys, &["a", "b"], &InputOrderMode::Sorted);
245250
let name =
246251
format!("{}_run{run_length}", if strings { "string" } else { "int" });
247252
group.bench_function(name, |b| {
@@ -261,5 +266,57 @@ fn aggregation(c: &mut Criterion) {
261266
group.finish();
262267
}
263268

264-
criterion_group!(benches, grouping, aggregation);
269+
/// Input ordered by `a` only. Each `a` value has 32768 distinct `b` values, so
270+
/// every `a` boundary completes four default batches of groups at once.
271+
fn partially_ordered_aggregation(c: &mut Criterion) {
272+
const GROUPS_PER_KEY: usize = 32768;
273+
let schema = Arc::new(Schema::new(vec![
274+
Field::new("a", DataType::Int32, false),
275+
Field::new("b", DataType::Int32, false),
276+
]));
277+
let keys = (0..ROWS)
278+
.step_by(8192)
279+
.map(|start| {
280+
let rows = start..(start + 8192).min(ROWS);
281+
let a: ArrayRef = Arc::new(Int32Array::from_iter_values(
282+
rows.clone().map(|row| (row / GROUPS_PER_KEY) as i32),
283+
));
284+
let b: ArrayRef = Arc::new(Int32Array::from_iter_values(
285+
rows.map(|row| (row % GROUPS_PER_KEY) as i32),
286+
));
287+
vec![a, b]
288+
})
289+
.collect();
290+
let plan = aggregate_plan(
291+
&schema,
292+
keys,
293+
&["a"],
294+
&InputOrderMode::PartiallySorted(vec![0]),
295+
);
296+
let runtime = Runtime::new().unwrap();
297+
let mut group = c.benchmark_group("partially_ordered_aggregate_exec");
298+
group.sample_size(10);
299+
group.warm_up_time(Duration::from_millis(250));
300+
group.measurement_time(Duration::from_secs(1));
301+
group.bench_function("groups_per_key32768", |b| {
302+
b.iter(|| {
303+
black_box(
304+
runtime
305+
.block_on(collect(
306+
Arc::clone(&plan),
307+
Arc::new(TaskContext::default()),
308+
))
309+
.unwrap(),
310+
)
311+
});
312+
});
313+
group.finish();
314+
}
315+
316+
criterion_group!(
317+
benches,
318+
grouping,
319+
aggregation,
320+
partially_ordered_aggregation
321+
);
265322
criterion_main!(benches);

‎datafusion/physical-plan/src/aggregates/aggregate_hash_table/common_ordered.rs‎

Lines changed: 4 additions & 47 deletions
Original file line numberDiff line numberDiff line change
@@ -24,7 +24,6 @@ use std::sync::Arc;
2424
use arrow::datatypes::SchemaRef;
2525
use arrow::record_batch::RecordBatch;
2626
use datafusion_common::Result;
27-
use datafusion_common::assert_or_internal_err;
2827
use datafusion_execution::memory_pool::proxy::VecAllocExt;
2928
use datafusion_expr::{AggregateMetrics, EmitTo};
3029

@@ -128,9 +127,6 @@ pub(in crate::aggregates) struct OrderedAggregateTable<OrderedAggrMode> {
128127
/// to pass through or spill its current state.
129128
pub(super) state_schema: SchemaRef,
130129

131-
/// Maximum rows per emitted output batch, from config `batch_size`.
132-
pub(super) batch_size: usize,
133-
134130
/// Grouping and accumulator-specific timing metrics.
135131
pub(super) group_by_metrics: GroupByMetrics,
136132

@@ -188,17 +184,11 @@ impl<AggrMode> OrderedAggregateTable<AggrMode> {
188184
input_schema: &SchemaRef,
189185
output_schema: SchemaRef,
190186
state_schema: SchemaRef,
191-
batch_size: usize,
192187
input_order_mode: &InputOrderMode,
193188
aggregate_mode: &AggregateMode,
194189
filters: Vec<Option<Arc<dyn PhysicalExpr>>>,
195190
metrics: OrderedAggregateTableMetrics,
196191
) -> Result<Self> {
197-
assert_or_internal_err!(
198-
batch_size > 0,
199-
"OrderedAggregateTable requires config batch_size >= 1"
200-
);
201-
202192
let group_ordering = GroupOrdering::try_new(input_order_mode)?;
203193
let group_schema = agg.group_by().group_schema(input_schema)?;
204194
let group_values = new_group_values(group_schema, &group_ordering)?;
@@ -229,7 +219,6 @@ impl<AggrMode> OrderedAggregateTable<AggrMode> {
229219
Ok(Self {
230220
output_schema,
231221
state_schema,
232-
batch_size,
233222
group_by_metrics: metrics.group_by,
234223
aggregate_argument_metrics: metrics.aggregate_arguments,
235224
aggregate_accumulator_metrics: metrics.accumulator,
@@ -418,38 +407,8 @@ impl<AggrMode> OrderedAggregateTable<AggrMode> {
418407
Ok(())
419408
}
420409

421-
/// Emits groups allowed by `GroupOrdering`, leaving only the current
422-
/// unfinished ordered-key range buffered.
423-
///
424-
/// Each aggregation mode chooses a different `materialize_accumulator_fn`
425-
/// according to its semantics. For example, partial aggregation emits
426-
/// partial states to feed the final stage, so it uses
427-
/// [`datafusion_expr::GroupsAccumulator::state`].
428-
pub(super) fn next_output_batch_inner(
429-
&mut self,
430-
materialize_accumulator_fn: MaterializeAccumulatorFn,
431-
accumulator_phase: AccumulatorPhase,
432-
) -> Result<Option<RecordBatch>> {
433-
if self.buffer.group_values.is_empty() {
434-
return Ok(None);
435-
}
436-
437-
let Some(emit_to) = self.buffer.group_ordering.emit_to() else {
438-
return Ok(None);
439-
};
440-
let emit_to = match emit_to {
441-
EmitTo::First(n) => EmitTo::First(n.min(self.batch_size)),
442-
EmitTo::All if self.num_groups() > self.batch_size => {
443-
EmitTo::First(self.batch_size)
444-
}
445-
EmitTo::All => EmitTo::All,
446-
};
447-
self.materialize_groups(emit_to, materialize_accumulator_fn, accumulator_phase)
448-
.map(Some)
449-
}
450-
451410
/// Removes the selected groups once and materializes their output columns.
452-
/// The caller chooses the completed prefix and any output-size limit.
411+
/// The caller chooses the completed prefix.
453412
pub(super) fn materialize_groups(
454413
&mut self,
455414
emit_to: EmitTo,
@@ -459,11 +418,9 @@ impl<AggrMode> OrderedAggregateTable<AggrMode> {
459418
let accumulator_metrics = Arc::clone(&self.aggregate_accumulator_metrics);
460419
let output = self.group_by_metrics.time_emitting(|| {
461420
let mut output = self.buffer.group_values.emit(emit_to)?;
462-
// EOF can also emit a prefix when a caller limits its batch size,
463-
// but the completed ordering state no longer tracks group indexes.
464-
if let EmitTo::First(n) = emit_to
465-
&& matches!(self.buffer.group_ordering.emit_to(), Some(EmitTo::First(_)))
466-
{
421+
// `EmitTo::All` is only used after `input_done`, when the ordering
422+
// state no longer tracks group indexes.
423+
if let EmitTo::First(n) = emit_to {
467424
self.buffer.group_ordering.remove_groups(n);
468425
}
469426

‎datafusion/physical-plan/src/aggregates/aggregate_hash_table/ordered_final_table.rs‎

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -46,7 +46,6 @@ impl OrderedAggregateTable<FinalMarker> {
4646
agg: &AggregateExec,
4747
input_schema: &SchemaRef,
4848
output_schema: SchemaRef,
49-
batch_size: usize,
5049
input_order_mode: &InputOrderMode,
5150
metrics: OrderedAggregateTableMetrics,
5251
) -> Result<Self> {
@@ -55,7 +54,6 @@ impl OrderedAggregateTable<FinalMarker> {
5554
input_schema,
5655
output_schema,
5756
Arc::clone(input_schema),
58-
batch_size,
5957
input_order_mode,
6058
&AggregateMode::Final,
6159
vec![None; agg.aggr_expr().len()],

‎datafusion/physical-plan/src/aggregates/aggregate_hash_table/ordered_partial_table.rs‎

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -57,7 +57,6 @@ impl OrderedAggregateTable<PartialMarker> {
5757
agg: &AggregateExec,
5858
partition: usize,
5959
output_schema: SchemaRef,
60-
batch_size: usize,
6160
) -> Result<Self> {
6261
let input_schema = agg.input().schema();
6362
let state_schema = Arc::clone(&output_schema);
@@ -67,7 +66,6 @@ impl OrderedAggregateTable<PartialMarker> {
6766
&input_schema,
6867
output_schema,
6968
state_schema,
70-
batch_size,
7169
&agg.input_order_mode,
7270
&AggregateMode::Partial,
7371
agg.filter_expr().to_vec(),

‎datafusion/physical-plan/src/aggregates/aggregate_hash_table/ordered_single_table.rs‎

Lines changed: 14 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -44,7 +44,6 @@ impl OrderedAggregateTable<SingleMarker> {
4444
partition: usize,
4545
output_schema: SchemaRef,
4646
state_schema: SchemaRef,
47-
batch_size: usize,
4847
) -> Result<Self> {
4948
debug_assert!(matches!(
5049
agg.mode,
@@ -58,7 +57,6 @@ impl OrderedAggregateTable<SingleMarker> {
5857
&input_schema,
5958
output_schema,
6059
state_schema,
61-
batch_size,
6260
&agg.input_order_mode,
6361
&agg.mode,
6462
agg.filter_expr().to_vec(),
@@ -80,14 +78,24 @@ impl OrderedAggregateTable<SingleMarker> {
8078
)
8179
}
8280

83-
/// Emits the next batch of final aggregate values for groups proven complete
84-
/// by the input ordering.
85-
pub(in crate::aggregates) fn next_output_batch(
81+
/// Materializes final results for all groups proven complete by the input
82+
/// ordering, leaving the active ordered-key range in the table.
83+
///
84+
/// Returns None if there are no completed groups.
85+
pub(in crate::aggregates) fn take_completed_result_batch(
8686
&mut self,
8787
) -> Result<Option<RecordBatch>> {
88-
self.next_output_batch_inner(
88+
if self.is_empty() {
89+
return Ok(None);
90+
}
91+
let Some(emit_to) = self.group_ordering().emit_to() else {
92+
return Ok(None);
93+
};
94+
self.materialize_groups(
95+
emit_to,
8996
HashAggregateAccumulator::evaluate_to_columns,
9097
AccumulatorPhase::Evaluate,
9198
)
99+
.map(Some)
92100
}
93101
}

‎datafusion/physical-plan/src/aggregates/ordered_final_stream.rs‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -189,7 +189,6 @@ impl OrderedFinalAggregateStream {
189189
agg,
190190
&input_schema,
191191
Arc::clone(&schema),
192-
batch_size,
193192
input_order_mode,
194193
metrics,
195194
)?;

‎datafusion/physical-plan/src/aggregates/ordered_partial_stream.rs‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -161,7 +161,6 @@ impl OrderedPartialAggregateStream {
161161
agg,
162162
partition,
163163
Arc::clone(&schema),
164-
batch_size,
165164
)?;
166165
let reservation =
167166
MemoryConsumer::new(format!("OrderedPartialAggregateStream[{partition}]"))

0 commit comments

Comments
 (0)