Skip to content

Commit 3a83281

Browse files
2010YOUY01kosiew
authored andcommitted
refactor(hash-aggr): Support spilling for ordered aggregation (apache#23657)
## Which issue does this PR close? <!-- We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes apache#123` indicates that this PR will close issue apache#123. --> Part of apache#22710 ## Rationale for this change <!-- Why are you proposing this change? If this is already explained clearly in the issue, then this section is not needed. Clearly explaining why changes are proposed helps reviewers understand your changes and offer better suggestions. --> This PR implements larger-than-memory execution for ordered partial and ordered final aggregation. These two modes are implemented first because: - apache#22710 splits ordered and unordered aggregation into separate implementations. - Unordered aggregation internally reuses ordered aggregation for its larger-than-memory execution logic. So larger-than-memory support for ordered aggregation become the groundwork for other aggregation modes. The high-level plan for two-stage ordered hash aggregation is: ``` AggregateExec(mode=final, ordered) --RepartitionExec(hash) ----AggregateExec(mode=partial, ordered) ``` #### Group keys are fully ordered (input ordered by `a, b`; query uses `GROUP BY a, b`) Execution must use bounded memory because only one group is active at any given time. Therefore, the implementation simply returns an execution error if a memory reservation fails. #### Group keys are partially ordered (input ordered by `a`; query uses `GROUP BY a, b`) At any given time, we must hold all groups for a particular value of `a` in memory, so it is possible to run out of memory. This is handled as follows: If the partial aggregate runs out of memory, it directly materializes the accumulated groups as aggregate states and emits them early to the final stage. The final aggregate continues aggregating until its memory budget is reached, then: 1. Sorts the aggregated batches by the group keys and writes them to disk. 2. Repeats this process until the input is exhausted. 3. Constructs a sort-preserving merge stream over all spill files. 4. Constructs an `OrderedFinalAggregateStream` using the sort-preserving merge stream as its input. The new stream's group keys are fully ordered, whereas those of the original stream were only partially ordered. It then evaluates this ordered stream to produce the final result. ### Design Tradeoffs Note that the same implementation is currently shared by two execution paths, controlled by flags: aggregation with fully ordered group keys and aggregation with partially ordered group keys. This is not an ideal pattern. However: - Fully ordered aggregation can later be split into a separate implementation with potentially more aggressive optimizations—for example, it does not require a hash table. The the current implementation only have to handle partially-ordered cases. - For now, the behavior remains consistent with the original implementation, allowing us to complete the migration sooner. ## What changes are included in this PR? <!-- There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR. --> The core changes are in `ordered_partial_stream.rs` and `ordered_final_stream.rs`, for the above algorithm. See code comments for implementation details. ## Are these changes tested? <!-- We typically require tests for all PRs in order to: 1. Prevent the code from being accidentally broken by subsequent changes 6. Serve as another way to document the expected behavior of the code If tests are not included in your PR, please explain why (for example, are they covered by existing tests)? --> After implementing this change, I checked the coverage using `cargo llvm-cov` and found that this feature was supported by the original implementation but was not covered by either regular tests or fuzz tests. This is a bit of a horror story. I think the old implementation is heavily multiplexed, so its overall line coverage is probably good. However, spilling for ordered aggregation follows a specific execution path that was never exercised. Therefore, this PR adds `slt` test coverage. I also think we need more fuzzing cases (filed apache#23658) ## Are there any user-facing changes? <!-- If there are user-facing changes then we may require documentation to be updated before approving the PR. --> <!-- If there are any breaking changes to public APIs, please add the `api change` label. -->
1 parent 449dee2 commit 3a83281

10 files changed

Lines changed: 1015 additions & 100 deletions

File tree

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

Lines changed: 56 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -81,6 +81,10 @@ pub(in crate::aggregates) struct OrderedAggregateTable<OrderedAggrMode> {
8181
/// Output schema: group columns followed by aggregate state or final values.
8282
pub(super) output_schema: SchemaRef,
8383

84+
/// Intermediate-state schema used when memory pressure requires the table
85+
/// to pass through or spill its current state.
86+
pub(super) state_schema: SchemaRef,
87+
8488
/// Maximum rows per emitted output batch, from config `batch_size`.
8589
pub(super) batch_size: usize,
8690

@@ -129,13 +133,14 @@ impl<AggrMode> OrderedAggregateTable<AggrMode> {
129133
)]
130134
pub(super) fn new_for_mode(
131135
agg: &AggregateExec,
132-
partition: usize,
133136
input_schema: &SchemaRef,
134137
output_schema: SchemaRef,
138+
state_schema: SchemaRef,
135139
batch_size: usize,
136140
input_order_mode: &InputOrderMode,
137141
aggregate_mode: &AggregateMode,
138142
filters: Vec<Option<Arc<dyn PhysicalExpr>>>,
143+
group_by_metrics: GroupByMetrics,
139144
) -> Result<Self> {
140145
assert_or_internal_err!(
141146
batch_size > 0,
@@ -168,8 +173,9 @@ impl<AggrMode> OrderedAggregateTable<AggrMode> {
168173

169174
Ok(Self {
170175
output_schema,
176+
state_schema,
171177
batch_size,
172-
group_by_metrics: GroupByMetrics::new(&agg.metrics, partition),
178+
group_by_metrics,
173179
buffer: OrderedAggregateTableBuffer {
174180
group_by: Arc::clone(&agg.group_by),
175181
group_ordering,
@@ -217,9 +223,19 @@ impl<AggrMode> OrderedAggregateTable<AggrMode> {
217223
self.buffer.group_ordering.input_done();
218224
}
219225

226+
/// Returns the ordering state used to decide how memory pressure is handled.
227+
pub(in crate::aggregates) fn group_ordering(&self) -> &GroupOrdering {
228+
&self.buffer.group_ordering
229+
}
230+
231+
/// Number of groups currently buffered.
232+
pub(in crate::aggregates) fn num_groups(&self) -> usize {
233+
self.buffer.group_values.len()
234+
}
235+
220236
/// Check if there is zero groups accumulated so far.
221237
pub(in crate::aggregates) fn is_empty(&self) -> bool {
222-
self.buffer.group_values.is_empty()
238+
self.num_groups() == 0
223239
}
224240

225241
/// All internal buffer's memory size.
@@ -234,6 +250,43 @@ impl<AggrMode> OrderedAggregateTable<AggrMode> {
234250
+ self.buffer.group_indices.allocated_size()
235251
}
236252

253+
pub(in crate::aggregates) fn group_by_metrics(&self) -> GroupByMetrics {
254+
self.group_by_metrics.clone()
255+
}
256+
257+
/// Takes every intermediate aggregate state and resets the table so it can
258+
/// continue with a new ordered input segment.
259+
///
260+
/// Unlike normal ordered emission, this operation is allowed to take the
261+
/// active (incomplete) groups. Partial aggregation can pass those states to
262+
/// its final stage, while final aggregation sorts and spills them before
263+
/// replay.
264+
pub(in crate::aggregates) fn take_state_batch(
265+
&mut self,
266+
) -> Result<Option<RecordBatch>> {
267+
if self.buffer.group_values.is_empty() {
268+
return Ok(None);
269+
}
270+
271+
let mut output = self.buffer.group_values.emit(EmitTo::All)?;
272+
for acc in &mut self.buffer.accumulators {
273+
output.extend(acc.state(EmitTo::All)?);
274+
}
275+
276+
let batch = RecordBatch::try_new(Arc::clone(&self.state_schema), output)?;
277+
debug_assert!(batch.num_rows() > 0);
278+
279+
// `emit(EmitTo::All)` resets accumulator state. Explicitly shrink the
280+
// key/index buffers too so the memory reservation can be released
281+
// before the batch is passed downstream or sorted for spilling.
282+
self.buffer.group_values.clear_shrink(0);
283+
self.buffer.group_indices.clear();
284+
self.buffer.group_indices.shrink_to_fit();
285+
self.buffer.group_ordering.reset();
286+
287+
Ok(Some(batch))
288+
}
289+
237290
/// Returns the [`EmitTo`], clamped to the specified batch size
238291
///
239292
/// Returns `(emit_to, should_remove_groups)`, where `emit_to` is the number

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

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -19,12 +19,15 @@
1919
//!
2020
//! See comments in [`super::ordered_partial_table`] for details.
2121
22+
use std::sync::Arc;
23+
2224
use arrow::datatypes::SchemaRef;
2325
use arrow::record_batch::RecordBatch;
2426
use datafusion_common::Result;
2527

2628
use crate::InputOrderMode;
2729
use crate::aggregates::aggregate_hash_table::FinalMarker;
30+
use crate::aggregates::group_values::GroupByMetrics;
2831
use crate::aggregates::{AggregateExec, AggregateMode};
2932

3033
use super::common_ordered::OrderedAggregateTable;
@@ -41,21 +44,22 @@ use super::common_ordered::OrderedAggregateTable;
4144
impl OrderedAggregateTable<FinalMarker> {
4245
pub(in crate::aggregates) fn new_with_input_order(
4346
agg: &AggregateExec,
44-
partition: usize,
4547
input_schema: &SchemaRef,
4648
output_schema: SchemaRef,
4749
batch_size: usize,
4850
input_order_mode: &InputOrderMode,
51+
group_by_metrics: GroupByMetrics,
4952
) -> Result<Self> {
5053
Self::new_for_mode(
5154
agg,
52-
partition,
5355
input_schema,
5456
output_schema,
57+
Arc::clone(input_schema),
5558
batch_size,
5659
input_order_mode,
5760
&AggregateMode::Final,
5861
vec![None; agg.aggr_expr.len()],
62+
group_by_metrics,
5963
)
6064
}
6165

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

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -29,12 +29,15 @@
2929
//! The implementation is separated from other aggregate tables because this
3030
//! execution path is likely to be optimized further in the future.
3131
32+
use std::sync::Arc;
33+
3234
use arrow::datatypes::SchemaRef;
3335
use arrow::record_batch::RecordBatch;
3436
use datafusion_common::Result;
3537

3638
use crate::aggregates::{
3739
AggregateExec, AggregateMode, aggregate_hash_table::PartialMarker,
40+
group_values::GroupByMetrics,
3841
};
3942

4043
use super::common_ordered::OrderedAggregateTable;
@@ -56,15 +59,18 @@ impl OrderedAggregateTable<PartialMarker> {
5659
batch_size: usize,
5760
) -> Result<Self> {
5861
let input_schema = agg.input().schema();
62+
let state_schema = Arc::clone(&output_schema);
63+
let group_by_metrics = GroupByMetrics::new(&agg.metrics, partition);
5964
Self::new_for_mode(
6065
agg,
61-
partition,
6266
&input_schema,
6367
output_schema,
68+
state_schema,
6469
batch_size,
6570
&agg.input_order_mode,
6671
&AggregateMode::Partial,
6772
agg.filter_expr.iter().cloned().collect(),
73+
group_by_metrics,
6874
)
6975
}
7076

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

Lines changed: 9 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1235,12 +1235,10 @@ impl AggregateExec {
12351235
&& self.limit_options_supported_by_hash_stream()
12361236
}
12371237

1238-
fn should_use_ordered_partial_aggregate_stream(&self, context: &TaskContext) -> bool {
1239-
// TODO: implement memory-limited path and remove this limitation
1240-
if matches!(context.memory_pool().memory_limit(), MemoryLimit::Finite(_)) {
1241-
return false;
1242-
}
1243-
1238+
fn should_use_ordered_partial_aggregate_stream(
1239+
&self,
1240+
_context: &TaskContext,
1241+
) -> bool {
12441242
self.mode == AggregateMode::Partial
12451243
&& self.input_order_mode != InputOrderMode::Linear
12461244
&& !self.group_by.is_true_no_grouping()
@@ -1291,12 +1289,7 @@ impl AggregateExec {
12911289
&& self.group_by.is_single()
12921290
}
12931291

1294-
fn should_use_ordered_final_aggregate_stream(&self, context: &TaskContext) -> bool {
1295-
// TODO: implement memory-limited path and remove this limitation
1296-
if matches!(context.memory_pool().memory_limit(), MemoryLimit::Finite(_)) {
1297-
return false;
1298-
}
1299-
1292+
fn should_use_ordered_final_aggregate_stream(&self, _context: &TaskContext) -> bool {
13001293
matches!(
13011294
self.mode,
13021295
AggregateMode::Final | AggregateMode::FinalPartitioned
@@ -3922,10 +3915,10 @@ mod tests {
39223915
+----------+-----------+-------------------------+
39233916
");
39243917

3925-
// Ordered streams don't implement memory limits yet.
3918+
// Ordered partial aggregation supports finite memory.
39263919
let finite_memory_task_ctx = new_finite_memory_migrated_hash_ctx(2, 1024 * 1024)?;
39273920
let stream = aggregate.execute_typed(0, &finite_memory_task_ctx)?;
3928-
assert!(matches!(stream, StreamType::GroupedHash(_)));
3921+
assert!(matches!(stream, StreamType::OrderedPartialAggregate(_)));
39293922

39303923
Ok(())
39313924
}
@@ -3999,10 +3992,10 @@ mod tests {
39993992
+-----+--------------+
40003993
");
40013994

4002-
// Ordered streams don't implement memory limits yet.
3995+
// Ordered final aggregation supports finite memory.
40033996
let finite_memory_task_ctx = new_finite_memory_migrated_hash_ctx(2, 1024 * 1024)?;
40043997
let stream = final_aggregate.execute_typed(0, &finite_memory_task_ctx)?;
4005-
assert!(matches!(stream, StreamType::GroupedHash(_)));
3998+
assert!(matches!(stream, StreamType::OrderedFinalAggregate(_)));
40063999

40074000
Ok(())
40084001
}

‎datafusion/physical-plan/src/aggregates/order/full.rs‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -115,6 +115,11 @@ impl GroupOrderingFull {
115115
self.state = State::Complete;
116116
}
117117

118+
/// Starts tracking a new fully ordered input segment.
119+
pub fn reset(&mut self) {
120+
self.state = State::Start;
121+
}
122+
118123
/// Called when new groups are added in a batch. See documentation
119124
/// on [`super::GroupOrdering::new_groups`]
120125
pub fn new_groups(&mut self, total_num_groups: usize) {

‎datafusion/physical-plan/src/aggregates/order/mod.rs‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -93,6 +93,20 @@ impl GroupOrdering {
9393
}
9494
}
9595

96+
/// Resets the ordering state while preserving the configured ordering mode.
97+
///
98+
/// Ordered partial aggregation uses this after passing intermediate states
99+
/// downstream, and ordered final aggregation uses it after spilling a run.
100+
/// In both cases the hash table is empty and can start tracking the next
101+
/// input batch from a fresh ordering state.
102+
pub fn reset(&mut self) {
103+
match self {
104+
GroupOrdering::None => {}
105+
GroupOrdering::Partial(partial) => partial.reset(),
106+
GroupOrdering::Full(full) => full.reset(),
107+
}
108+
}
109+
96110
/// Removes the first `n` groups from the internal state, shifting all
97111
/// existing indexes down by `n`.
98112
pub fn remove_groups(&mut self, n: usize) {

‎datafusion/physical-plan/src/aggregates/order/partial.rs‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -186,6 +186,12 @@ impl GroupOrderingPartial {
186186
};
187187
}
188188

189+
/// Starts tracking a new ordered input segment with the same sort-key
190+
/// columns.
191+
pub fn reset(&mut self) {
192+
self.state = State::Start;
193+
}
194+
189195
fn updated_sort_key(
190196
current_sort: usize,
191197
sort_key: Option<Vec<ScalarValue>>,

0 commit comments

Comments
 (0)