Skip to content

Commit a72327b

Browse files
Rachel IntRachel Int
authored andcommitted
fix: split aggregate partitions in coalescer
1 parent 36befa2 commit a72327b

3 files changed

Lines changed: 263 additions & 38 deletions

File tree

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

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -70,6 +70,7 @@ use datafusion_expr::utils::AggregateOrderSensitivity;
7070
use datafusion_physical_expr_common::utils::evaluate_expressions_to_arrays;
7171
use itertools::Itertools;
7272
pub(crate) use partition_runs::{
73+
PartitionRun, append_subpartition_column, partition_runs_from_column,
7374
relative_partition, relative_partition_schema, with_relative_partition,
7475
};
7576
use topk::hash_table::is_supported_hash_key_type;

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

Lines changed: 141 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -26,12 +26,132 @@
2626
2727
use std::sync::Arc;
2828

29-
use arrow::array::RecordBatch;
30-
use arrow::datatypes::{Schema, SchemaRef};
31-
use datafusion_common::{DataFusionError, Result};
29+
use arrow::array::{Array, ArrayRef, RecordBatch, RecordBatchOptions, UInt32Array};
30+
use arrow::datatypes::{DataType, Field, Schema, SchemaRef};
31+
use datafusion_common::cast::as_uint32_array;
32+
use datafusion_common::{DataFusionError, Result, internal_err};
3233

3334
const AGGR_RELATIVE_PARTITION_METADATA_KEY: &str =
3435
"datafusion.internal.hash_aggr_relative_partition";
36+
const AGGR_SUBPARTITION_COLUMN_NAME: &str =
37+
"__datafusion_internal_hash_aggr_subpartition";
38+
39+
/// A contiguous run of rows for one relative aggregate partition.
40+
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
41+
pub(crate) struct PartitionRun {
42+
/// Relative aggregate partition inside one output partition.
43+
pub relative_partition: usize,
44+
/// Number of contiguous rows in this run.
45+
pub len: usize,
46+
}
47+
48+
impl PartitionRun {
49+
/// Create a non-empty partition run.
50+
pub(crate) fn new(relative_partition: usize, len: usize) -> Result<Self> {
51+
if len == 0 {
52+
return internal_err!("Hash aggregate partition run length must be nonzero");
53+
}
54+
Ok(Self {
55+
relative_partition,
56+
len,
57+
})
58+
}
59+
}
60+
61+
/// Return a schema with the internal subpartition column appended.
62+
fn subpartition_schema(schema: &SchemaRef) -> SchemaRef {
63+
let mut fields = schema.fields().iter().cloned().collect::<Vec<_>>();
64+
fields.push(Arc::new(Field::new(
65+
AGGR_SUBPARTITION_COLUMN_NAME,
66+
DataType::UInt32,
67+
false,
68+
)));
69+
Arc::new(Schema::new_with_metadata(fields, schema.metadata().clone()))
70+
}
71+
72+
/// Append an internal subpartition column using `runs`.
73+
pub(crate) fn append_subpartition_column(
74+
batch: &RecordBatch,
75+
runs: &[PartitionRun],
76+
) -> Result<RecordBatch> {
77+
let mut values = Vec::with_capacity(batch.num_rows());
78+
for run in runs {
79+
let relative_partition =
80+
u32::try_from(run.relative_partition).map_err(|err| {
81+
DataFusionError::Internal(format!(
82+
"Hash aggregate relative partition does not fit UInt32: {err}"
83+
))
84+
})?;
85+
values.extend(std::iter::repeat_n(relative_partition, run.len));
86+
}
87+
88+
let mut columns = batch.columns().to_vec();
89+
columns.push(Arc::new(UInt32Array::from(values)) as ArrayRef);
90+
let options = RecordBatchOptions::new().with_row_count(Some(batch.num_rows()));
91+
RecordBatch::try_new_with_options(
92+
subpartition_schema(batch.schema_ref()),
93+
columns,
94+
&options,
95+
)
96+
.map_err(Into::into)
97+
}
98+
99+
/// Strip the internal subpartition column and return its contiguous runs.
100+
pub(crate) fn partition_runs_from_column(
101+
batch: RecordBatch,
102+
) -> Result<(RecordBatch, Vec<PartitionRun>)> {
103+
let subpartition_idx = batch.num_columns().checked_sub(1).ok_or_else(|| {
104+
DataFusionError::Internal(
105+
"Missing relative partition column for partitioned batch coalescing"
106+
.to_string(),
107+
)
108+
})?;
109+
if batch.schema().field(subpartition_idx).name() != AGGR_SUBPARTITION_COLUMN_NAME {
110+
return internal_err!(
111+
"Missing relative partition column for partitioned batch coalescing"
112+
);
113+
}
114+
let subpartitions = as_uint32_array(batch.column(subpartition_idx).as_ref())?;
115+
if subpartitions.null_count() != 0 {
116+
return internal_err!(
117+
"Hash aggregate subpartition column must not contain nulls"
118+
);
119+
}
120+
121+
let mut runs = Vec::new();
122+
let mut values = subpartitions.values().iter().copied();
123+
if let Some(first_partition) = values.next() {
124+
let mut current_partition = first_partition as usize;
125+
let mut current_len = 1;
126+
for relative_partition in values {
127+
let relative_partition = relative_partition as usize;
128+
if relative_partition == current_partition {
129+
current_len += 1;
130+
} else {
131+
runs.push(PartitionRun::new(current_partition, current_len)?);
132+
current_partition = relative_partition;
133+
current_len = 1;
134+
}
135+
}
136+
runs.push(PartitionRun::new(current_partition, current_len)?);
137+
}
138+
139+
let (source_schema, mut columns, num_rows) = batch.into_parts();
140+
let fields = source_schema
141+
.fields()
142+
.iter()
143+
.take(subpartition_idx)
144+
.cloned()
145+
.collect::<Vec<_>>();
146+
let schema = Arc::new(Schema::new_with_metadata(
147+
fields,
148+
source_schema.metadata().clone(),
149+
));
150+
columns.pop();
151+
let options = RecordBatchOptions::new().with_row_count(Some(num_rows));
152+
let stripped_batch = RecordBatch::try_new_with_options(schema, columns, &options)?;
153+
Ok((stripped_batch, runs))
154+
}
35155

36156
/// Return a schema carrying `relative_partition` as internal metadata.
37157
pub(crate) fn relative_partition_schema(
@@ -96,4 +216,22 @@ mod tests {
96216
assert_eq!(relative_partition(batch.schema_ref())?, Some(3));
97217
Ok(())
98218
}
219+
220+
#[test]
221+
fn subpartition_column_round_trip() -> Result<()> {
222+
let schema =
223+
Arc::new(Schema::new(vec![Field::new("a", DataType::UInt32, false)]));
224+
let batch = RecordBatch::try_new(
225+
schema,
226+
vec![Arc::new(UInt32Array::from(vec![10, 11, 12, 13]))],
227+
)?;
228+
let expected_runs = vec![PartitionRun::new(0, 2)?, PartitionRun::new(1, 2)?];
229+
230+
let batch = append_subpartition_column(&batch, &expected_runs)?;
231+
let (batch, actual_runs) = partition_runs_from_column(batch)?;
232+
233+
assert_eq!(batch.num_columns(), 1);
234+
assert_eq!(actual_runs, expected_runs);
235+
Ok(())
236+
}
99237
}

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

Lines changed: 121 additions & 35 deletions
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,7 @@ use super::{
3232
DisplayAs, ExecutionPlanProperties, RecordBatchStream, SendableRecordBatchStream,
3333
};
3434
use crate::aggregates::{
35+
PartitionRun, append_subpartition_column, partition_runs_from_column,
3536
relative_partition, relative_partition_schema, with_relative_partition,
3637
};
3738
use crate::coalesce::LimitedBatchCoalescer;
@@ -347,20 +348,21 @@ impl PartitionedLimitedBatchCoalescer {
347348
}
348349

349350
fn push_batch(&mut self, batch: RecordBatch) -> Result<()> {
350-
let relative_partition =
351-
relative_partition(batch.schema_ref())?.ok_or_else(|| {
352-
DataFusionError::Internal(
353-
"Missing relative partition metadata for partitioned batch coalescing"
354-
.to_string(),
355-
)
356-
})?;
351+
let (batch, runs) = partition_runs_from_column(batch)?;
357352
let num_relative_partitions = self.coalescers.len();
358-
let coalescer = self.coalescers.get_mut(relative_partition).ok_or_else(|| {
359-
DataFusionError::Internal(format!(
360-
"Relative partition {relative_partition} exceeds configured partition count {num_relative_partitions}"
361-
))
362-
})?;
363-
coalescer.push_batch(batch)?;
353+
let mut offset = 0;
354+
for run in runs {
355+
let relative_partition = run.relative_partition;
356+
let coalescer = self.coalescers.get_mut(relative_partition).ok_or_else(|| {
357+
DataFusionError::Internal(format!(
358+
"Relative partition {relative_partition} exceeds configured partition count {num_relative_partitions}"
359+
))
360+
})?;
361+
let run_batch =
362+
with_relative_partition(batch.slice(offset, run.len), relative_partition);
363+
coalescer.push_batch(run_batch)?;
364+
offset += run.len;
365+
}
364366
Ok(())
365367
}
366368

@@ -1113,12 +1115,89 @@ impl BatchPartitioner {
11131115

11141116
partition_timer.done();
11151117

1116-
Self::partition_grouped_take(batch, indices, timer, |aggr_partition| {
1117-
(
1118+
Self::partition_hash_aggregate_grouped_take(
1119+
batch,
1120+
indices,
1121+
timer,
1122+
max_aggr_partition_factor,
1123+
)
1124+
}
1125+
1126+
fn partition_hash_aggregate_grouped_take(
1127+
batch: &RecordBatch,
1128+
indices: &mut [Vec<u32>],
1129+
timer: &metrics::Time,
1130+
max_aggr_partition_factor: usize,
1131+
) -> Result<Vec<Result<(usize, usize, RecordBatch)>>> {
1132+
let mut output_ranges = Vec::with_capacity(indices.len());
1133+
let mut reordered_indices = Vec::with_capacity(batch.num_rows());
1134+
1135+
for (aggr_partition, p_indices) in indices.iter_mut().enumerate() {
1136+
if p_indices.is_empty() {
1137+
continue;
1138+
}
1139+
1140+
let start = reordered_indices.len();
1141+
reordered_indices.extend_from_slice(p_indices);
1142+
output_ranges.push((
11181143
aggr_partition / max_aggr_partition_factor,
1119-
aggr_partition % max_aggr_partition_factor,
1120-
)
1121-
})
1144+
PartitionRun::new(
1145+
aggr_partition % max_aggr_partition_factor,
1146+
p_indices.len(),
1147+
)?,
1148+
start,
1149+
));
1150+
p_indices.clear();
1151+
}
1152+
1153+
if reordered_indices.is_empty() {
1154+
return Ok(vec![]);
1155+
}
1156+
1157+
let batches = {
1158+
let _timer = timer.timer();
1159+
let indices_array: PrimitiveArray<UInt32Type> = reordered_indices.into();
1160+
let columns = take_arrays(batch.columns(), &indices_array, None)?;
1161+
1162+
let mut options = RecordBatchOptions::new();
1163+
options = options.with_row_count(Some(indices_array.len()));
1164+
let reordered_batch =
1165+
RecordBatch::try_new_with_options(batch.schema(), columns, &options)?;
1166+
1167+
let mut output_batches = Vec::new();
1168+
let mut current_output_partition = None;
1169+
let mut current_start = 0;
1170+
let mut current_len = 0;
1171+
let mut current_runs = Vec::new();
1172+
1173+
for (output_partition, run, start) in output_ranges {
1174+
if current_output_partition != Some(output_partition) {
1175+
if let Some(partition) = current_output_partition {
1176+
let batch = reordered_batch.slice(current_start, current_len);
1177+
let batch = append_subpartition_column(&batch, &current_runs)?;
1178+
output_batches.push(Ok((partition, 0, batch)));
1179+
}
1180+
1181+
current_output_partition = Some(output_partition);
1182+
current_start = start;
1183+
current_len = 0;
1184+
current_runs.clear();
1185+
}
1186+
1187+
current_len += run.len;
1188+
current_runs.push(run);
1189+
}
1190+
1191+
if let Some(partition) = current_output_partition {
1192+
let batch = reordered_batch.slice(current_start, current_len);
1193+
let batch = append_subpartition_column(&batch, &current_runs)?;
1194+
output_batches.push(Ok((partition, 0, batch)));
1195+
}
1196+
1197+
output_batches
1198+
};
1199+
1200+
Ok(batches)
11221201
}
11231202

11241203
fn partition_grouped_take(
@@ -2023,12 +2102,7 @@ impl RepartitionExec {
20232102
}
20242103

20252104
for res in partitioner.partition_iter_with_relative_partition(batch)? {
2026-
let (partition, relative_partition, batch) = res?;
2027-
let batch = if max_aggr_partition_factor > 1 {
2028-
with_relative_partition(batch, relative_partition)
2029-
} else {
2030-
batch
2031-
};
2105+
let (partition, _relative_partition, batch) = res?;
20322106

20332107
let timer = metrics.send_time[partition].timer();
20342108
// if there is still a receiver, send to it
@@ -2382,18 +2456,20 @@ mod tests {
23822456
fn partitioned_coalescer_keeps_relative_partitions_separate() -> Result<()> {
23832457
let schema =
23842458
Arc::new(Schema::new(vec![Field::new("c0", DataType::UInt32, false)]));
2385-
let make_batch = |relative_partition, values: Vec<u32>| {
2459+
let make_batch = |values: Vec<u32>, runs: &[PartitionRun]| {
23862460
let batch = RecordBatch::try_new(
23872461
Arc::clone(&schema),
23882462
vec![Arc::new(UInt32Array::from(values))],
23892463
)?;
2390-
Ok::<_, DataFusionError>(with_relative_partition(batch, relative_partition))
2464+
append_subpartition_column(&batch, runs)
23912465
};
23922466
let mut coalescer = PartitionedLimitedBatchCoalescer::new(&schema, 4, 2);
23932467

2394-
coalescer.push_batch(make_batch(0, vec![0, 1])?)?;
2395-
coalescer.push_batch(make_batch(1, vec![10, 11])?)?;
2396-
coalescer.push_batch(make_batch(0, vec![2, 3])?)?;
2468+
coalescer.push_batch(make_batch(
2469+
vec![0, 1, 10, 11],
2470+
&[PartitionRun::new(0, 2)?, PartitionRun::new(1, 2)?],
2471+
)?)?;
2472+
coalescer.push_batch(make_batch(vec![2, 3], &[PartitionRun::new(0, 2)?])?)?;
23972473

23982474
let partition_zero = coalescer.next_completed_batch().unwrap();
23992475
assert_eq!(partition_zero.num_rows(), 4);
@@ -2409,10 +2485,9 @@ mod tests {
24092485
}
24102486

24112487
// Covers hash aggregate partitioning mapping multiple aggregate partitions
2412-
// back to one output partition while returning each relative partition as
2413-
// its own batch.
2488+
// back to one output partition through an internal subpartition column.
24142489
#[test]
2415-
fn test_hash_aggregate_partitioner_returns_relative_partitions() -> Result<()> {
2490+
fn test_hash_aggregate_partitioner_appends_subpartition_column() -> Result<()> {
24162491
let schema =
24172492
Arc::new(Schema::new(vec![Field::new("c0", DataType::UInt32, false)]));
24182493
let batch = RecordBatch::try_new(
@@ -2432,10 +2507,21 @@ mod tests {
24322507
for result in partitioner.partition_iter_with_relative_partition(batch)? {
24332508
let (partition, relative_partition, batch) = result?;
24342509
assert!(partition < 2);
2435-
assert!(relative_partition < 4);
2436-
assert_eq!(batch.num_columns(), 1);
2510+
assert_eq!(relative_partition, 0);
2511+
assert_eq!(batch.num_columns(), 2);
24372512
num_rows += batch.num_rows();
2438-
seen[partition][relative_partition] = true;
2513+
2514+
let subpartitions = batch
2515+
.column(1)
2516+
.as_any()
2517+
.downcast_ref::<UInt32Array>()
2518+
.expect("subpartition column should be UInt32");
2519+
for value in subpartitions.iter() {
2520+
let value =
2521+
value.expect("subpartition value should not be null") as usize;
2522+
assert!(value < 4);
2523+
seen[partition][value] = true;
2524+
}
24392525
}
24402526

24412527
assert_eq!(num_rows, 128);

0 commit comments

Comments
 (0)