You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by ka...@apache.org on 2026/07/04 02:01:46 UTC
(datafusion) 01/01: Port final partition reuse onto candidate state machine
This is an automated email from the ASF dual-hosted git repository.
Rachelint pushed a commit to branch final-aggr-with-lazily-materialize-poc-candidate1
in repository https://gitbox.apache.org/repos/asf/datafusion.git
commit f36e94bf4422ff4d16940560945a5011ee6edc8b
Author: kamille <ka...@apache.org>
AuthorDate: Sat Jul 4 10:01:34 2026 +0800
Port final partition reuse onto candidate state machine
---
datafusion/expr-common/src/groups_accumulator.rs | 20 +
.../src/aggregate/groups_accumulator/accumulate.rs | 66 ++++
.../src/aggregate/groups_accumulator/prim_op.rs | 34 ++
datafusion/functions-aggregate/src/average.rs | 44 +++
datafusion/functions-aggregate/src/count.rs | 27 ++
.../src/aggregates/aggregate_hash_table/common.rs | 65 +++-
.../aggregates/aggregate_hash_table/final_table.rs | 77 +++-
.../src/aggregates/aggregate_hash_table/mod.rs | 3 +-
.../src/aggregates/group_values/mod.rs | 29 +-
.../aggregates/group_values/multi_group_by/mod.rs | 354 ++++++++++++++---
.../physical-plan/src/aggregates/hash_aggregate.rs | 432 ++++++++++++---------
datafusion/physical-plan/src/aggregates/mod.rs | 6 +-
.../physical-plan/src/aggregates/partition_runs.rs | 4 +-
13 files changed, 905 insertions(+), 256 deletions(-)
diff --git a/datafusion/expr-common/src/groups_accumulator.rs b/datafusion/expr-common/src/groups_accumulator.rs
index b021674cbe..63f2cda14d 100644
--- a/datafusion/expr-common/src/groups_accumulator.rs
+++ b/datafusion/expr-common/src/groups_accumulator.rs
@@ -194,6 +194,26 @@ pub trait GroupsAccumulator: Send + std::any::Any {
total_num_groups: usize,
) -> Result<()>;
+ /// Merges selected intermediate state rows into this accumulator's current state.
+ ///
+ /// `partition_indices` contains row indices into `values` and `group_indices`
+ /// that should be merged. This is used by final partition replay to avoid
+ /// materializing filtered state arrays.
+ fn merge_partitioned_batch(
+ &mut self,
+ _values: &[ArrayRef],
+ _group_indices: &[usize],
+ _partition_indices: &[usize],
+ _total_num_groups: usize,
+ ) -> Result<()> {
+ not_impl_err!("Partitioned grouped merge batch is not implemented")
+ }
+
+ /// Returns `true` if [`Self::merge_partitioned_batch`] is implemented.
+ fn supports_merge_partitioned_batch(&self) -> bool {
+ false
+ }
+
/// Converts an input batch directly to the intermediate aggregate state.
///
/// This is the equivalent of treating each input row as its own group. It
diff --git a/datafusion/functions-aggregate-common/src/aggregate/groups_accumulator/accumulate.rs b/datafusion/functions-aggregate-common/src/aggregate/groups_accumulator/accumulate.rs
index 09e1df4eae..02685827a0 100644
--- a/datafusion/functions-aggregate-common/src/aggregate/groups_accumulator/accumulate.rs
+++ b/datafusion/functions-aggregate-common/src/aggregate/groups_accumulator/accumulate.rs
@@ -189,6 +189,39 @@ impl NullState {
});
}
+ /// Invokes `value_fn(group_index, value)` for each selected non null
+ /// value while tracking which groups have seen inputs if necessary.
+ pub fn accumulate_by_indices<T, F>(
+ &mut self,
+ group_indices: &[usize],
+ values: &PrimitiveArray<T>,
+ partition_indices: &[usize],
+ total_num_groups: usize,
+ mut value_fn: F,
+ ) where
+ T: ArrowPrimitiveType + Send,
+ F: FnMut(usize, T::Native) + Send,
+ {
+ if let SeenValues::All { num_values } = &mut self.seen_values
+ && values.null_count() == 0
+ {
+ accumulate_by_indices(group_indices, values, partition_indices, value_fn);
+ *num_values = total_num_groups;
+ return;
+ }
+
+ let seen_values = self.seen_values.get_builder(total_num_groups);
+ accumulate_by_indices(
+ group_indices,
+ values,
+ partition_indices,
+ |group_index, value| {
+ seen_values.set_bit(group_index, true);
+ value_fn(group_index, value);
+ },
+ );
+ }
+
/// Invokes `value_fn(group_index, value)` for each non null, non
/// filtered value in `values`, while tracking which groups have
/// seen null inputs and which groups have seen any inputs, for
@@ -468,6 +501,39 @@ pub fn accumulate<T, F>(
}
}
+/// Invokes `value_fn(group_index, value)` for each selected non null value.
+pub fn accumulate_by_indices<T, F>(
+ group_indices: &[usize],
+ values: &PrimitiveArray<T>,
+ partition_indices: &[usize],
+ mut value_fn: F,
+) where
+ T: ArrowPrimitiveType + Send,
+ F: FnMut(usize, T::Native) + Send,
+{
+ assert_eq!(values.len(), group_indices.len());
+ let data = values.values();
+
+ match values.nulls() {
+ None => {
+ for &row_idx in partition_indices {
+ let group_index = group_indices[row_idx];
+ debug_assert_ne!(group_index, usize::MAX);
+ value_fn(group_index, data[row_idx]);
+ }
+ }
+ Some(nulls) => {
+ for &row_idx in partition_indices {
+ if nulls.is_valid(row_idx) {
+ let group_index = group_indices[row_idx];
+ debug_assert_ne!(group_index, usize::MAX);
+ value_fn(group_index, data[row_idx]);
+ }
+ }
+ }
+ }
+}
+
/// Accumulates with multiple accumulate(value) columns. (e.g. `corr(c1, c2)`)
///
/// This method assumes that for any input record index, if any of the value column
diff --git a/datafusion/functions-aggregate-common/src/aggregate/groups_accumulator/prim_op.rs b/datafusion/functions-aggregate-common/src/aggregate/groups_accumulator/prim_op.rs
index 474899d8f3..0fdb7a5f79 100644
--- a/datafusion/functions-aggregate-common/src/aggregate/groups_accumulator/prim_op.rs
+++ b/datafusion/functions-aggregate-common/src/aggregate/groups_accumulator/prim_op.rs
@@ -137,6 +137,40 @@ where
self.update_batch(values, group_indices, None, total_num_groups)
}
+ fn merge_partitioned_batch(
+ &mut self,
+ values: &[ArrayRef],
+ group_indices: &[usize],
+ partition_indices: &[usize],
+ total_num_groups: usize,
+ ) -> Result<()> {
+ assert_eq!(
+ values.len(),
+ 1,
+ "single argument to merge_partitioned_batch"
+ );
+ let values = values[0].as_primitive::<T>();
+
+ self.values.resize(total_num_groups, self.starting_value);
+ self.null_state.accumulate_by_indices(
+ group_indices,
+ values,
+ partition_indices,
+ total_num_groups,
+ |group_index, new_value| {
+ // SAFETY: group_index is guaranteed to be in bounds
+ let value = unsafe { self.values.get_unchecked_mut(group_index) };
+ (self.prim_fn)(value, new_value);
+ },
+ );
+
+ Ok(())
+ }
+
+ fn supports_merge_partitioned_batch(&self) -> bool {
+ true
+ }
+
/// Converts an input batch directly to a state batch
///
/// The state is:
diff --git a/datafusion/functions-aggregate/src/average.rs b/datafusion/functions-aggregate/src/average.rs
index 06c7694634..1182fd1e1c 100644
--- a/datafusion/functions-aggregate/src/average.rs
+++ b/datafusion/functions-aggregate/src/average.rs
@@ -945,6 +945,50 @@ where
Ok(())
}
+ fn merge_partitioned_batch(
+ &mut self,
+ values: &[ArrayRef],
+ group_indices: &[usize],
+ partition_indices: &[usize],
+ total_num_groups: usize,
+ ) -> Result<()> {
+ assert_eq!(values.len(), 2, "two arguments to merge_partitioned_batch");
+ let partial_counts = values[0].as_primitive::<UInt64Type>();
+ let partial_sums = values[1].as_primitive::<T>();
+
+ self.counts.resize(total_num_groups, 0);
+ self.null_state.accumulate_by_indices(
+ group_indices,
+ partial_counts,
+ partition_indices,
+ total_num_groups,
+ |group_index, partial_count| {
+ // SAFETY: group_index is guaranteed to be in bounds
+ let count = unsafe { self.counts.get_unchecked_mut(group_index) };
+ *count += partial_count;
+ },
+ );
+
+ self.sums.resize(total_num_groups, T::default_value());
+ self.null_state.accumulate_by_indices(
+ group_indices,
+ partial_sums,
+ partition_indices,
+ total_num_groups,
+ |group_index, new_value: <T as ArrowPrimitiveType>::Native| {
+ // SAFETY: group_index is guaranteed to be in bounds
+ let sum = unsafe { self.sums.get_unchecked_mut(group_index) };
+ *sum = sum.add_wrapping(new_value);
+ },
+ );
+
+ Ok(())
+ }
+
+ fn supports_merge_partitioned_batch(&self) -> bool {
+ true
+ }
+
fn convert_to_state(
&self,
values: &[ArrayRef],
diff --git a/datafusion/functions-aggregate/src/count.rs b/datafusion/functions-aggregate/src/count.rs
index f0ce8c82a1..897aeec49a 100644
--- a/datafusion/functions-aggregate/src/count.rs
+++ b/datafusion/functions-aggregate/src/count.rs
@@ -686,6 +686,33 @@ impl GroupsAccumulator for CountGroupsAccumulator {
Ok(())
}
+ fn merge_partitioned_batch(
+ &mut self,
+ values: &[ArrayRef],
+ group_indices: &[usize],
+ partition_indices: &[usize],
+ total_num_groups: usize,
+ ) -> Result<()> {
+ assert_eq!(values.len(), 1, "one argument to merge_partitioned_batch");
+ let partial_counts = values[0].as_primitive::<Int64Type>();
+
+ assert_eq!(partial_counts.null_count(), 0);
+ let partial_counts = partial_counts.values();
+
+ self.counts.resize(total_num_groups, 0);
+ for &row_idx in partition_indices {
+ let group_index = group_indices[row_idx];
+ debug_assert_ne!(group_index, usize::MAX);
+ self.counts[group_index] += partial_counts[row_idx];
+ }
+
+ Ok(())
+ }
+
+ fn supports_merge_partitioned_batch(&self) -> bool {
+ true
+ }
+
fn evaluate(&mut self, emit_to: EmitTo) -> Result<ArrayRef> {
let counts = emit_to.take_needed(&mut self.counts);
diff --git a/datafusion/physical-plan/src/aggregates/aggregate_hash_table/common.rs b/datafusion/physical-plan/src/aggregates/aggregate_hash_table/common.rs
index 24d3a8c5c6..c27394e25c 100644
--- a/datafusion/physical-plan/src/aggregates/aggregate_hash_table/common.rs
+++ b/datafusion/physical-plan/src/aggregates/aggregate_hash_table/common.rs
@@ -141,7 +141,7 @@ impl<AggrMode> AggregateHashTable<AggrMode> {
}
/// See comments in [`EvaluatedAggregateBatch`]
- pub(super) fn evaluate_batch(
+ pub(in crate::aggregates) fn evaluate_batch(
&self,
batch: &RecordBatch,
) -> Result<EvaluatedAggregateBatch> {
@@ -234,24 +234,55 @@ pub(super) struct HashAggregateAccumulator {
/// and `x > 0`.
///
/// These arrays can be passed directly to [`GroupsAccumulator`].
-pub(super) struct EvaluatedAccumulatorArgs {
+pub(in crate::aggregates) struct EvaluatedAccumulatorArgs {
/// Evaluated argument arrays. Some aggregate functions take multiple arguments.
- pub(super) arguments: Vec<ArrayRef>,
+ pub(in crate::aggregates) arguments: Vec<ArrayRef>,
/// Evaluated filter array, `Some` if the aggregate has a `FILTER` expression.
- pub(super) filter: Option<ArrayRef>,
+ pub(in crate::aggregates) filter: Option<ArrayRef>,
+}
+
+impl EvaluatedAccumulatorArgs {
+ pub(in crate::aggregates) fn memory_size(&self) -> usize {
+ self.arguments
+ .iter()
+ .map(|array| array.get_array_memory_size())
+ .sum::<usize>()
+ + self
+ .filter
+ .as_ref()
+ .map(|array| array.get_array_memory_size())
+ .unwrap_or_default()
+ }
}
/// Evaluated all group by keys and accumulator args.
///
/// e.g., `select k+1, sum(v*v) from t group by (k+1)`, this function evaluates
/// `k+1`, `v*v`
-pub(super) struct EvaluatedAggregateBatch {
+pub(in crate::aggregates) struct EvaluatedAggregateBatch {
/// One entry per grouping set; each entry contains all evaluated group key
/// arrays for the current input batch.
- pub(super) grouping_set_args: Vec<Vec<ArrayRef>>,
+ pub(in crate::aggregates) grouping_set_args: Vec<Vec<ArrayRef>>,
/// Evaluated arguments and filters, one entry per aggregate expression.
- pub(super) accumulator_args: Vec<EvaluatedAccumulatorArgs>,
+ pub(in crate::aggregates) accumulator_args: Vec<EvaluatedAccumulatorArgs>,
+}
+
+impl EvaluatedAggregateBatch {
+ pub(in crate::aggregates) fn memory_size(&self) -> usize {
+ let grouping_set_args_size = self
+ .grouping_set_args
+ .iter()
+ .flatten()
+ .map(|array| array.get_array_memory_size())
+ .sum::<usize>();
+ let accumulator_args_size = self
+ .accumulator_args
+ .iter()
+ .map(EvaluatedAccumulatorArgs::memory_size)
+ .sum::<usize>();
+ grouping_set_args_size + accumulator_args_size
+ }
}
/// Buffer for the aggregate hash table's group keys and accumulator states.
@@ -452,6 +483,26 @@ impl HashAggregateAccumulator {
.merge_batch(&values.arguments, group_indices, total_num_groups)
}
+ pub(super) fn merge_partitioned_batch(
+ &mut self,
+ values: &EvaluatedAccumulatorArgs,
+ group_indices: &[usize],
+ partition_indices: &[usize],
+ total_num_groups: usize,
+ ) -> Result<()> {
+ debug_assert!(values.filter.is_none());
+ self.accumulator.merge_partitioned_batch(
+ &values.arguments,
+ group_indices,
+ partition_indices,
+ total_num_groups,
+ )
+ }
+
+ pub(super) fn supports_merge_partitioned_batch(&self) -> bool {
+ self.accumulator.supports_merge_partitioned_batch()
+ }
+
/// Evaluating final aggregate results according to `EmitTo`, and reset inner
/// states. (e.g. after `evaluate(EmitTo::All)`, it returns all accumulated groups
/// , and clear the inner buffers)
diff --git a/datafusion/physical-plan/src/aggregates/aggregate_hash_table/final_table.rs b/datafusion/physical-plan/src/aggregates/aggregate_hash_table/final_table.rs
index b8933d7df1..7dceb37aa3 100644
--- a/datafusion/physical-plan/src/aggregates/aggregate_hash_table/final_table.rs
+++ b/datafusion/physical-plan/src/aggregates/aggregate_hash_table/final_table.rs
@@ -19,14 +19,14 @@ use std::sync::Arc;
use arrow::datatypes::SchemaRef;
use arrow::record_batch::RecordBatch;
-use datafusion_common::{Result, internal_err};
+use datafusion_common::{Result, assert_eq_or_internal_err, internal_err};
use datafusion_expr::EmitTo;
use crate::aggregates::AggregateExec;
use super::common::{
- AggregateHashTable, AggregateHashTableBuffer, AggregateHashTableState, FinalMarker,
- MaterializedAggregateOutput,
+ AggregateHashTable, AggregateHashTableBuffer, AggregateHashTableState,
+ EvaluatedAggregateBatch, FinalMarker, MaterializedAggregateOutput,
};
/// Methods specific to the aggregate hash table used in the final aggregation stage.
@@ -152,6 +152,77 @@ impl AggregateHashTable<FinalMarker> {
Ok(())
}
+ pub(in crate::aggregates) fn create_group_hashes(
+ &self,
+ evaluated_batch: &EvaluatedAggregateBatch,
+ ) -> Result<Vec<u64>> {
+ assert_eq_or_internal_err!(
+ evaluated_batch.grouping_set_args.len(),
+ 1,
+ "final partition replay expects a single grouping set"
+ );
+
+ let state = self.state.building();
+ let group_values = &evaluated_batch.grouping_set_args[0];
+ let mut hashes = Vec::new();
+ let timer = self.group_by_metrics.time_calculating_group_ids.timer();
+ state
+ .group_values
+ .create_hashes(group_values, &mut hashes)?;
+ drop(timer);
+ Ok(hashes)
+ }
+
+ pub(in crate::aggregates) fn aggregate_partitioned_evaluated_batch(
+ &mut self,
+ evaluated_batch: &EvaluatedAggregateBatch,
+ group_hashes: &[u64],
+ partition_indices: &[usize],
+ ) -> Result<()> {
+ assert_eq_or_internal_err!(
+ evaluated_batch.grouping_set_args.len(),
+ 1,
+ "final partition replay expects a single grouping set"
+ );
+
+ let state = self.state.building_mut();
+ let group_values = &evaluated_batch.grouping_set_args[0];
+
+ let timer = self.group_by_metrics.aggregation_time.timer();
+ state.group_values.intern_partitioned(
+ group_values,
+ group_hashes,
+ &mut state.batch_group_indices,
+ partition_indices,
+ )?;
+ let group_indices = &state.batch_group_indices;
+ let total_num_groups = state.group_values.len();
+
+ for (acc, values) in state
+ .accumulators
+ .iter_mut()
+ .zip(evaluated_batch.accumulator_args.iter())
+ {
+ acc.merge_partitioned_batch(
+ values,
+ group_indices,
+ partition_indices,
+ total_num_groups,
+ )?;
+ }
+ drop(timer);
+
+ Ok(())
+ }
+
+ pub(in crate::aggregates) fn supports_partitioned_merge(&self) -> bool {
+ let state = self.state.building();
+ state.group_values.supports_intern_partitioned()
+ && state
+ .accumulators
+ .iter()
+ .all(|acc| acc.supports_merge_partitioned_batch())
+ }
pub(in crate::aggregates) fn start_output(&mut self) -> Result<()> {
self.start_outputting();
Ok(())
diff --git a/datafusion/physical-plan/src/aggregates/aggregate_hash_table/mod.rs b/datafusion/physical-plan/src/aggregates/aggregate_hash_table/mod.rs
index eb152f4128..51311c878d 100644
--- a/datafusion/physical-plan/src/aggregates/aggregate_hash_table/mod.rs
+++ b/datafusion/physical-plan/src/aggregates/aggregate_hash_table/mod.rs
@@ -20,5 +20,6 @@ mod final_table;
mod partial_table;
pub(super) use common::{
- AggregateHashTable, FinalMarker, PartialMarker, PartialSkipMarker,
+ AggregateHashTable, EvaluatedAggregateBatch, FinalMarker, PartialMarker,
+ PartialSkipMarker,
};
diff --git a/datafusion/physical-plan/src/aggregates/group_values/mod.rs b/datafusion/physical-plan/src/aggregates/group_values/mod.rs
index ee253e5d7a..edf7d2eef2 100644
--- a/datafusion/physical-plan/src/aggregates/group_values/mod.rs
+++ b/datafusion/physical-plan/src/aggregates/group_values/mod.rs
@@ -24,7 +24,8 @@ use arrow::array::types::{
};
use arrow::array::{ArrayRef, downcast_primitive};
use arrow::datatypes::{DataType, SchemaRef, TimeUnit};
-use datafusion_common::Result;
+use datafusion_common::hash_utils::create_hashes;
+use datafusion_common::{Result, internal_err};
use datafusion_expr::EmitTo;
@@ -99,6 +100,32 @@ pub trait GroupValues: Send {
/// assigned.
fn intern(&mut self, cols: &[ArrayRef], groups: &mut Vec<usize>) -> Result<()>;
+ /// Calculates group ids for selected rows by row index.
+ fn intern_partitioned(
+ &mut self,
+ _cols: &[ArrayRef],
+ _hashes: &[u64],
+ _groups: &mut Vec<usize>,
+ _partition_indices: &[usize],
+ ) -> Result<()> {
+ internal_err!(
+ "partitioned GroupValues::intern is not supported by this implementation"
+ )
+ }
+
+ /// Computes hash values for group values before partitioned intern.
+ fn create_hashes(&self, cols: &[ArrayRef], hashes: &mut Vec<u64>) -> Result<()> {
+ hashes.clear();
+ hashes.resize(cols[0].len(), 0);
+ create_hashes(cols, &crate::aggregates::AGGREGATION_HASH_SEED, hashes)?;
+ Ok(())
+ }
+
+ /// Returns true if [`Self::intern_partitioned`] is supported.
+ fn supports_intern_partitioned(&self) -> bool {
+ false
+ }
+
/// Returns the number of bytes of memory used by this [`GroupValues`]
fn size(&self) -> usize;
diff --git a/datafusion/physical-plan/src/aggregates/group_values/multi_group_by/mod.rs b/datafusion/physical-plan/src/aggregates/group_values/multi_group_by/mod.rs
index 804b5158f3..98ed196b27 100644
--- a/datafusion/physical-plan/src/aggregates/group_values/multi_group_by/mod.rs
+++ b/datafusion/physical-plan/src/aggregates/group_values/multi_group_by/mod.rs
@@ -29,7 +29,7 @@ use crate::aggregates::group_values::multi_group_by::{
boolean::BooleanGroupValueBuilder, bytes::ByteGroupValueBuilder,
bytes_view::ByteViewGroupValueBuilder, primitive::PrimitiveGroupValueBuilder,
};
-use arrow::array::{Array, ArrayRef, BooleanBufferBuilder};
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBufferBuilder};
use arrow::compute::cast;
use arrow::datatypes::{
BinaryViewType, DataType, Date32Type, Date64Type, Decimal128Type, Field, Float32Type,
@@ -46,7 +46,7 @@ use datafusion_execution::memory_pool::proxy::{HashTableAllocExt, VecAllocExt};
use datafusion_expr::EmitTo;
use datafusion_physical_expr::binary_map::OutputType;
-use hashbrown::hash_table::HashTable;
+use hashbrown::hash_table::{Entry, HashTable};
const NON_INLINED_FLAG: u64 = 0x8000000000000000;
const VALUE_MASK: u64 = 0x7FFFFFFFFFFFFFFF;
@@ -215,6 +215,9 @@ pub struct GroupValuesColumn<const STREAMING: bool> {
/// [`GroupValuesRows`]: crate::aggregates::group_values::GroupValuesRows
group_values: Vec<Box<dyn GroupColumn>>,
+ /// Number of stored group rows.
+ num_groups: usize,
+
/// reused buffer to store hashes
hashes_buffer: Vec<u64>,
@@ -281,6 +284,7 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
vectorized_operation_buffers: VectorizedOperationBuffers::default(),
map_size: 0,
group_values,
+ num_groups: 0,
hashes_buffer: Default::default(),
random_state: crate::aggregates::AGGREGATION_HASH_SEED,
})
@@ -301,6 +305,13 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
Ok(v)
}
+ fn account_map_capacity_growth(&mut self, previous_capacity: usize) {
+ let current_capacity = self.map.capacity();
+ if current_capacity > previous_capacity {
+ self.map_size = current_capacity * size_of::<(u64, GroupIndexView)>();
+ }
+ }
+
// ========================================================================
// Scalarized intern
// ========================================================================
@@ -348,11 +359,22 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
&mut self,
cols: &[ArrayRef],
groups: &mut Vec<usize>,
+ opt_filter: Option<&BooleanArray>,
+ ) -> Result<()> {
+ self.scalarized_intern_impl(cols, opt_filter, groups)
+ }
+
+ fn scalarized_intern_impl(
+ &mut self,
+ cols: &[ArrayRef],
+ filter_array: Option<&BooleanArray>,
+ groups: &mut Vec<usize>,
) -> Result<()> {
let n_rows = cols[0].len();
// tracks to which group each of the input rows belongs
groups.clear();
+ groups.resize(n_rows, usize::MAX);
// 1.1 Calculate the group keys for the group values
let batch_hashes = &mut self.hashes_buffer;
@@ -361,6 +383,11 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
create_hashes(cols, &self.random_state, batch_hashes)?;
for (row, &target_hash) in batch_hashes.iter().enumerate() {
+ if filter_array
+ .is_some_and(|filter| !filter.is_valid(row) || !filter.value(row))
+ {
+ continue;
+ }
let entry = self
.map
.find_mut(target_hash, |(exist_hash, group_idx_view)| {
@@ -407,17 +434,12 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
// let group_idx = group_values.num_rows();
// group_values.push(group_rows.row(row));
- let mut checklen = 0;
- let group_idx = self.group_values[0].len();
+ let group_idx = self.num_groups;
for (i, group_value) in self.group_values.iter_mut().enumerate() {
group_value.append_val(&cols[i], row)?;
- let len = group_value.len();
- if i == 0 {
- checklen = len;
- } else {
- debug_assert_eq!(checklen, len);
- }
+ debug_assert_eq!(group_value.len(), group_idx + 1);
}
+ self.num_groups += 1;
// for hasher function, use precomputed hash value
self.map.insert_accounted(
@@ -428,7 +450,75 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
group_idx
}
};
- groups.push(group_idx);
+ groups[row] = group_idx;
+ }
+
+ Ok(())
+ }
+
+ fn scalarized_intern_partitioned_impl(
+ &mut self,
+ cols: &[ArrayRef],
+ batch_hashes: &[u64],
+ partition_indices: &[usize],
+ groups: &mut Vec<usize>,
+ ) -> Result<()> {
+ let n_rows = cols[0].len();
+ groups.clear();
+ groups.resize(n_rows, usize::MAX);
+
+ for &row in partition_indices {
+ let target_hash = batch_hashes[row];
+ let entry = self
+ .map
+ .find_mut(target_hash, |(exist_hash, group_idx_view)| {
+ debug_assert!(!group_idx_view.is_non_inlined());
+ if target_hash != *exist_hash {
+ return false;
+ }
+
+ fn check_row_equal(
+ array_row: &dyn GroupColumn,
+ lhs_row: usize,
+ array: &ArrayRef,
+ rhs_row: usize,
+ ) -> bool {
+ array_row.equal_to(lhs_row, array, rhs_row)
+ }
+
+ for (idx, group_val) in self.group_values.iter().enumerate() {
+ if !check_row_equal(
+ group_val.as_ref(),
+ group_idx_view.value() as usize,
+ &cols[idx],
+ row,
+ ) {
+ return false;
+ }
+ }
+
+ true
+ });
+
+ let group_idx = match entry {
+ Some((_hash, group_idx_view)) => group_idx_view.value() as usize,
+ None => {
+ let group_idx = self.num_groups;
+ for (idx, group_value) in self.group_values.iter_mut().enumerate() {
+ group_value.append_val(&cols[idx], row)?;
+ debug_assert_eq!(group_value.len(), group_idx + 1);
+ }
+ self.num_groups += 1;
+
+ self.map.insert_accounted(
+ (target_hash, GroupIndexView::new_inlined(group_idx as u64)),
+ |(hash, _group_index)| *hash,
+ &mut self.map_size,
+ );
+ group_idx
+ }
+ };
+ groups[row] = group_idx;
}
Ok(())
@@ -449,6 +539,16 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
&mut self,
cols: &[ArrayRef],
groups: &mut Vec<usize>,
+ opt_filter: Option<&BooleanArray>,
+ ) -> Result<()> {
+ self.vectorized_intern_impl(cols, opt_filter, groups)
+ }
+
+ fn vectorized_intern_impl(
+ &mut self,
+ cols: &[ArrayRef],
+ filter_array: Option<&BooleanArray>,
+ groups: &mut Vec<usize>,
) -> Result<()> {
let n_rows = cols[0].len();
@@ -482,7 +582,7 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
//
// 1. Collect vectorized context by checking hash values of `cols` in `map`
- self.collect_vectorized_process_context(&batch_hashes, groups);
+ self.collect_vectorized_process_context(&batch_hashes, filter_array, groups);
// 2. Perform `vectorized_append`
self.vectorized_append(cols)?;
@@ -499,6 +599,30 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
Ok(())
}
+ fn vectorized_intern_partitioned_impl(
+ &mut self,
+ cols: &[ArrayRef],
+ batch_hashes: &[u64],
+ partition_indices: &[usize],
+ groups: &mut Vec<usize>,
+ ) -> Result<()> {
+ let n_rows = cols[0].len();
+
+ groups.clear();
+ groups.resize(n_rows, usize::MAX);
+
+ self.collect_vectorized_process_context_partitioned(
+ batch_hashes,
+ partition_indices,
+ groups,
+ );
+ self.vectorized_append(cols)?;
+ self.vectorized_equal_to(cols, groups);
+ self.scalarized_intern_remaining(cols, batch_hashes, groups)?;
+
+ Ok(())
+ }
+
/// Collect vectorized context by checking hash values of `cols` in `map`
///
/// 1. If bucket not found
@@ -515,6 +639,7 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
fn collect_vectorized_process_context(
&mut self,
batch_hashes: &[u64],
+ filter_array: Option<&BooleanArray>,
groups: &mut [usize],
) {
self.vectorized_operation_buffers.append_row_indices.clear();
@@ -526,35 +651,42 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
.clear();
for (row, &target_hash) in batch_hashes.iter().enumerate() {
- let entry = self
- .map
- .find(target_hash, |(exist_hash, _)| target_hash == *exist_hash);
+ if filter_array
+ .is_some_and(|filter| !filter.is_valid(row) || !filter.value(row))
+ {
+ continue;
+ }
- let Some((_, group_index_view)) = entry else {
- // 1. Bucket not found case
- // Build `new inlined group index view`
- let current_group_idx = self.group_values[0].len()
- + self.vectorized_operation_buffers.append_row_indices.len();
- let group_index_view =
- GroupIndexView::new_inlined(current_group_idx as u64);
-
- // Insert the `group index view` and its hash into `map`
- // for hasher function, use precomputed hash value
- self.map.insert_accounted(
- (target_hash, group_index_view),
- |(hash, _)| *hash,
- &mut self.map_size,
- );
+ let previous_capacity = self.map.capacity();
+ let group_index_view = match self.map.entry(
+ target_hash,
+ |(exist_hash, _)| target_hash == *exist_hash,
+ |(hash, _)| *hash,
+ ) {
+ Entry::Occupied(entry) => entry.get().1,
+ Entry::Vacant(entry) => {
+ // 1. Bucket not found case
+ // Build `new inlined group index view`
+ let current_group_idx = self.num_groups
+ + self.vectorized_operation_buffers.append_row_indices.len();
+ let group_index_view =
+ GroupIndexView::new_inlined(current_group_idx as u64);
+
+ // Insert the `group index view` and its hash into `map`
+ // for hasher function, use precomputed hash value
+ entry.insert((target_hash, group_index_view));
+ self.account_map_capacity_growth(previous_capacity);
- // Add row index to `vectorized_append_row_indices`
- self.vectorized_operation_buffers
- .append_row_indices
- .push(row);
+ // Add row index to `vectorized_append_row_indices`
+ self.vectorized_operation_buffers
+ .append_row_indices
+ .push(row);
- // Set group index to row in `groups`
- groups[row] = current_group_idx;
+ // Set group index to row in `groups`
+ groups[row] = current_group_idx;
- continue;
+ continue;
+ }
};
// 2. bucket found
@@ -584,6 +716,69 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
}
}
+ fn collect_vectorized_process_context_partitioned(
+ &mut self,
+ batch_hashes: &[u64],
+ partition_indices: &[usize],
+ groups: &mut [usize],
+ ) {
+ self.vectorized_operation_buffers.append_row_indices.clear();
+ self.vectorized_operation_buffers
+ .equal_to_row_indices
+ .clear();
+ self.vectorized_operation_buffers
+ .equal_to_group_indices
+ .clear();
+
+ for &row in partition_indices {
+ let target_hash = batch_hashes[row];
+ let previous_capacity = self.map.capacity();
+ let group_index_view = match self.map.entry(
+ target_hash,
+ |(exist_hash, _)| target_hash == *exist_hash,
+ |(hash, _)| *hash,
+ ) {
+ Entry::Occupied(entry) => entry.get().1,
+ Entry::Vacant(entry) => {
+ let current_group_idx = self.num_groups
+ + self.vectorized_operation_buffers.append_row_indices.len();
+ let group_index_view =
+ GroupIndexView::new_inlined(current_group_idx as u64);
+
+ entry.insert((target_hash, group_index_view));
+ self.account_map_capacity_growth(previous_capacity);
+
+ self.vectorized_operation_buffers
+ .append_row_indices
+ .push(row);
+ groups[row] = current_group_idx;
+
+ continue;
+ }
+ };
+
+ if group_index_view.is_non_inlined() {
+ let list_offset = group_index_view.value() as usize;
+ let group_index_list = &self.group_index_lists[list_offset];
+
+ self.vectorized_operation_buffers
+ .equal_to_group_indices
+ .extend_from_slice(group_index_list);
+ self.vectorized_operation_buffers
+ .equal_to_row_indices
+ .extend(std::iter::repeat_n(row, group_index_list.len()));
+ } else {
+ let group_index = group_index_view.value() as usize;
+ self.vectorized_operation_buffers
+ .equal_to_row_indices
+ .push(row);
+ self.vectorized_operation_buffers
+ .equal_to_group_indices
+ .push(group_index);
+ }
+ }
+ }
+
/// Perform `vectorized_append`` for `rows` in `vectorized_append_row_indices`
fn vectorized_append(&mut self, cols: &[ArrayRef]) -> Result<()> {
if self
@@ -594,13 +789,16 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
return Ok(());
}
+ let num_new_groups = self.vectorized_operation_buffers.append_row_indices.len();
let iter = self.group_values.iter_mut().zip(cols.iter());
for (group_column, col) in iter {
group_column.vectorized_append(
col,
&self.vectorized_operation_buffers.append_row_indices,
)?;
+ debug_assert_eq!(group_column.len(), self.num_groups + num_new_groups);
}
+ self.num_groups += num_new_groups;
Ok(())
}
@@ -779,17 +977,12 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
}
// Insert the `row` to `group_values` before checking `next row`
- let group_idx = self.group_values[0].len();
- let mut checklen = 0;
+ let group_idx = self.num_groups;
for (i, group_value) in self.group_values.iter_mut().enumerate() {
group_value.append_val(&cols[i], row)?;
- let len = group_value.len();
- if i == 0 {
- checklen = len;
- } else {
- debug_assert_eq!(checklen, len);
- }
+ debug_assert_eq!(group_value.len(), group_idx + 1);
}
+ self.num_groups += 1;
// Check if the `view` is `inlined` or `non-inlined`
if group_index_view.is_non_inlined() {
@@ -1083,12 +1276,40 @@ impl<const STREAMING: bool> GroupValues for GroupValuesColumn<STREAMING> {
// `self.group_values` populated with one builder per schema field,
// so no lazy initialization is needed here.
if !STREAMING {
- self.vectorized_intern(cols, groups)
+ self.vectorized_intern(cols, groups, None)
} else {
- self.scalarized_intern(cols, groups)
+ self.scalarized_intern(cols, groups, None)
}
}
+ fn intern_partitioned(
+ &mut self,
+ cols: &[ArrayRef],
+ hashes: &[u64],
+ groups: &mut Vec<usize>,
+ partition_indices: &[usize],
+ ) -> Result<()> {
+ if !STREAMING {
+ self.vectorized_intern_partitioned_impl(
+ cols,
+ hashes,
+ partition_indices,
+ groups,
+ )
+ } else {
+ self.scalarized_intern_partitioned_impl(
+ cols,
+ hashes,
+ partition_indices,
+ groups,
+ )
+ }
+ }
+
+ fn supports_intern_partitioned(&self) -> bool {
+ true
+ }
+
fn size(&self) -> usize {
let group_values_size: usize = self.group_values.iter().map(|v| v.size()).sum();
group_values_size + self.map_size + self.hashes_buffer.allocated_size()
@@ -1099,11 +1320,7 @@ impl<const STREAMING: bool> GroupValues for GroupValuesColumn<STREAMING> {
}
fn len(&self) -> usize {
- if self.group_values.is_empty() {
- return 0;
- }
-
- self.group_values[0].len()
+ self.num_groups
}
fn emit(&mut self, emit_to: EmitTo) -> Result<Vec<ArrayRef>> {
@@ -1117,6 +1334,7 @@ impl<const STREAMING: bool> GroupValues for GroupValuesColumn<STREAMING> {
// a real Result rather than panicking.
let fresh = Self::build_group_columns(&self.schema)?;
let group_values = mem::replace(&mut self.group_values, fresh);
+ self.num_groups = 0;
group_values
.into_iter()
@@ -1192,6 +1410,10 @@ impl<const STREAMING: bool> GroupValues for GroupValuesColumn<STREAMING> {
if !STREAMING {
self.group_index_lists.truncate(next_new_list_offset);
}
+ self.num_groups = self
+ .num_groups
+ .checked_sub(n)
+ .expect("EmitTo::First cannot emit more groups than stored");
output
}
@@ -1221,6 +1443,7 @@ impl<const STREAMING: bool> GroupValues for GroupValuesColumn<STREAMING> {
// `clear_shrink` is infallible by trait signature.
self.group_values = Self::build_group_columns(&self.schema)
.expect("schema previously validated in try_new");
+ self.num_groups = 0;
self.map.clear();
// self.map.shrink_to(num_rows, |_| 0); // hasher does not matter since the map is cleared
self.map_size = self.map.capacity() * size_of::<(u64, usize)>();
@@ -1352,6 +1575,33 @@ mod tests {
}
}
+ #[test]
+ fn group_values_column_intern_partitioned_skips_unlisted_rows() {
+ let schema = Arc::new(Schema::new(vec![
+ Field::new("a", DataType::Int64, false),
+ Field::new("b", DataType::Utf8View, false),
+ ]));
+ let cols = vec![
+ Arc::new(Int64Array::from(vec![1, 2, 1, 3])) as ArrayRef,
+ Arc::new(StringViewArray::from(vec!["x", "y", "x", "z"])) as ArrayRef,
+ ];
+ let partition_indices = vec![0, 2, 3];
+ let mut group_values = GroupValuesColumn::<false>::try_new(schema).unwrap();
+ let mut groups = Vec::new();
+ let mut hashes = Vec::new();
+
+ group_values.create_hashes(&cols, &mut hashes).unwrap();
+ group_values
+ .intern_partitioned(&cols, &hashes, &mut groups, &partition_indices)
+ .unwrap();
+
+ assert_eq!(groups.len(), 4);
+ assert_eq!(groups[0], groups[2]);
+ assert_eq!(groups[1], usize::MAX);
+ assert_ne!(groups[0], groups[3]);
+ assert_eq!(group_values.len(), 2);
+ }
+
#[test]
fn supported_schema_rejects_mix_of_supported_and_unsupported() {
// One Float16 column among supported columns flips the whole
diff --git a/datafusion/physical-plan/src/aggregates/hash_aggregate.rs b/datafusion/physical-plan/src/aggregates/hash_aggregate.rs
index 0a090e5afa..6a68c5f749 100644
--- a/datafusion/physical-plan/src/aggregates/hash_aggregate.rs
+++ b/datafusion/physical-plan/src/aggregates/hash_aggregate.rs
@@ -25,13 +25,16 @@
//!
//! See issue for details: <https://github.com/apache/datafusion/issues/22710>
-use std::collections::BTreeMap;
+use std::collections::{BTreeMap, BTreeSet};
+use std::mem::size_of;
use std::ops::ControlFlow;
use std::sync::Arc;
use std::task::{Context, Poll};
+use arrow::array::Array;
use arrow::datatypes::SchemaRef;
use arrow::record_batch::RecordBatch;
+use datafusion_common::cast::as_uint32_array;
use datafusion_common::utils::memory::get_record_batch_memory_size;
use datafusion_common::{DataFusionError, Result, internal_err};
use datafusion_execution::TaskContext;
@@ -39,101 +42,172 @@ use datafusion_execution::memory_pool::{MemoryConsumer, MemoryReservation};
use futures::stream::{Stream, StreamExt};
use super::aggregate_hash_table::{
- AggregateHashTable, FinalMarker, PartialMarker, PartialSkipMarker,
+ AggregateHashTable, EvaluatedAggregateBatch, FinalMarker, PartialMarker,
+ PartialSkipMarker,
};
use super::skip_partial::SkipAggregationProbe;
-use super::{
- AggregateExec, SubpartitionReorderBuffer, partition_runs, reorder_by_subpartition,
-};
+use super::{AggregateExec, subpartition_column_index};
use crate::metrics::{
BaselineMetrics, MetricBuilder, MetricCategory, RecordOutput, SpillMetrics,
};
use crate::stream::EmptyRecordBatchStream;
use crate::{InputOrderMode, RecordBatchStream, SendableRecordBatchStream, metrics};
-struct BucketStream {
- schema: SchemaRef,
- iter: std::vec::IntoIter<RecordBatch>,
+struct BufferedFinalPartitionBatch {
+ batch: RecordBatch,
+ evaluated_batch: EvaluatedAggregateBatch,
+ group_hashes: Vec<u64>,
}
-impl Stream for BucketStream {
- type Item = Result<RecordBatch>;
-
- fn poll_next(
- self: std::pin::Pin<&mut Self>,
- _cx: &mut Context<'_>,
- ) -> Poll<Option<Self::Item>> {
- Poll::Ready(self.get_mut().iter.next().map(Ok))
+impl BufferedFinalPartitionBatch {
+ fn new(
+ batch: RecordBatch,
+ evaluated_batch: EvaluatedAggregateBatch,
+ group_hashes: Vec<u64>,
+ ) -> Self {
+ Self {
+ batch,
+ evaluated_batch,
+ group_hashes,
+ }
}
-}
-impl RecordBatchStream for BucketStream {
- fn schema(&self) -> SchemaRef {
- Arc::clone(&self.schema)
+ fn memory_size(&self) -> usize {
+ let group_hashes_size = self.group_hashes.capacity() * size_of::<u64>();
+ get_record_batch_memory_size(&self.batch)
+ + self.evaluated_batch.memory_size()
+ + group_hashes_size
}
}
struct FinalPartitionRunState {
- runs: BTreeMap<usize, Vec<RecordBatch>>,
- run_sizes: BTreeMap<usize, usize>,
+ batches: Vec<BufferedFinalPartitionBatch>,
+ run_batch_indices: BTreeMap<usize, Vec<usize>>,
+ subpartition_column_idx: Option<usize>,
total_runs_size: usize,
- replaying_run_size: usize,
is_draining: bool,
- subpartition_reorder_buffer: SubpartitionReorderBuffer,
+ partition_indices_buffer: Vec<usize>,
}
impl FinalPartitionRunState {
fn new() -> Self {
Self {
- runs: BTreeMap::new(),
- run_sizes: BTreeMap::new(),
+ batches: Vec::new(),
+ run_batch_indices: BTreeMap::new(),
+ subpartition_column_idx: None,
total_runs_size: 0,
- replaying_run_size: 0,
is_draining: false,
- subpartition_reorder_buffer: SubpartitionReorderBuffer::new(),
+ partition_indices_buffer: Vec::new(),
}
}
fn total_size(&self) -> usize {
- self.total_runs_size + self.replaying_run_size
+ self.total_runs_size
}
- fn stage_batch(&mut self, batch: RecordBatch, partition_id: usize) -> usize {
- let batch_size = get_record_batch_memory_size(&batch);
- self.runs.entry(partition_id).or_default().push(batch);
- *self.run_sizes.entry(partition_id).or_default() += batch_size;
+ fn has_buffered_runs(&self) -> bool {
+ !self.batches.is_empty()
+ }
+
+ fn stage_batch(
+ &mut self,
+ batch: RecordBatch,
+ evaluated_batch: EvaluatedAggregateBatch,
+ group_hashes: Vec<u64>,
+ ) -> Result<usize> {
+ let subpartition_column_idx = match self.subpartition_column_idx {
+ Some(idx) => idx,
+ None => {
+ let idx =
+ subpartition_column_index(batch.schema_ref()).ok_or_else(|| {
+ DataFusionError::Internal(
+ "missing hash aggregate subpartition column".to_string(),
+ )
+ })?;
+ self.subpartition_column_idx = Some(idx);
+ idx
+ }
+ };
+ let subpartitions =
+ as_uint32_array(batch.column(subpartition_column_idx).as_ref())?;
+ if subpartitions.null_count() != 0 {
+ return internal_err!(
+ "Hash aggregate subpartition column must not contain nulls"
+ );
+ }
+
+ let batch_idx = self.batches.len();
+ let mut batch_partitions = BTreeSet::new();
+ for relative_partition in subpartitions.values().iter().copied() {
+ let relative_partition = relative_partition as usize;
+ if batch_partitions.insert(relative_partition) {
+ self.run_batch_indices
+ .entry(relative_partition)
+ .or_default()
+ .push(batch_idx);
+ }
+ }
+
+ let buffered_batch =
+ BufferedFinalPartitionBatch::new(batch, evaluated_batch, group_hashes);
+ let batch_size = buffered_batch.memory_size();
self.total_runs_size += batch_size;
- batch_size
+ self.batches.push(buffered_batch);
+ Ok(batch_size)
}
fn begin_replay(&mut self) {
self.is_draining = true;
}
- fn finish_replaying_run(&mut self) {
- self.replaying_run_size = 0;
- }
-
fn next_partition_id(&self) -> Option<usize> {
- self.runs
+ self.run_batch_indices
.first_key_value()
.map(|(partition_id, _)| *partition_id)
}
- fn take_run(&mut self, partition_id: usize) -> Result<Vec<RecordBatch>> {
- let runs = self.runs.remove(&partition_id).ok_or_else(|| {
- DataFusionError::Internal(format!(
- "Missing buffered runs for final aggregate partition {partition_id}"
- ))
- })?;
- let run_size = self.run_sizes.remove(&partition_id).ok_or_else(|| {
+ fn take_partition_batch_indices(
+ &mut self,
+ partition_id: usize,
+ ) -> Result<Vec<usize>> {
+ self.run_batch_indices.remove(&partition_id).ok_or_else(|| {
DataFusionError::Internal(format!(
- "Missing buffered run size for final aggregate partition {partition_id}"
+ "Missing buffered batch indices for final aggregate partition {partition_id}"
))
- })?;
- self.total_runs_size -= run_size;
- self.replaying_run_size = run_size;
- Ok(runs)
+ })
+ }
+
+ fn finish_partition_replay(&mut self) {
+ if self.run_batch_indices.is_empty() {
+ self.batches.clear();
+ self.subpartition_column_idx = None;
+ self.total_runs_size = 0;
+ }
+ }
+
+ fn build_partition_indices(
+ &mut self,
+ batch_idx: usize,
+ partition_id: usize,
+ ) -> Result<Vec<usize>> {
+ let batch = &self.batches[batch_idx].batch;
+ let subpartition_column_idx = self
+ .subpartition_column_idx
+ .expect("subpartition column index should be initialized");
+ let subpartitions =
+ as_uint32_array(batch.column(subpartition_column_idx).as_ref())?;
+ self.partition_indices_buffer.clear();
+ for (row_idx, value) in subpartitions.values().iter().copied().enumerate() {
+ if value as usize == partition_id {
+ self.partition_indices_buffer.push(row_idx);
+ }
+ }
+ Ok(std::mem::take(&mut self.partition_indices_buffer))
+ }
+
+ fn return_partition_indices(&mut self, mut partition_indices: Vec<usize>) {
+ partition_indices.clear();
+ self.partition_indices_buffer = partition_indices;
}
}
@@ -879,7 +953,7 @@ impl FinalHashAggregateStream {
if self
.partition_run_state
.as_ref()
- .is_some_and(|state| state.is_draining || !state.runs.is_empty())
+ .is_some_and(|state| state.is_draining || state.has_buffered_runs())
{
return false;
}
@@ -888,54 +962,42 @@ impl FinalHashAggregateStream {
.is_some_and(|limit| limit <= hash_table.building_group_count())
}
- fn should_buffer_partition_runs(&self) -> bool {
- self.partition_run_state
- .as_ref()
- .is_some_and(|state| !state.is_draining)
+ fn should_buffer_partition_runs(
+ &self,
+ hash_table: &AggregateHashTable<FinalMarker>,
+ ) -> bool {
+ hash_table.supports_partitioned_merge()
+ && self
+ .partition_run_state
+ .as_ref()
+ .is_some_and(|state| !state.is_draining)
}
- fn stage_partition_runs(&mut self, batch: &RecordBatch) -> Result<Option<usize>> {
- if let Some(state) = self.partition_run_state.as_mut()
- && let Some(batch) =
- reorder_by_subpartition(batch, &mut state.subpartition_reorder_buffer)?
- {
- let mut offset = 0;
- let mut staged_memory = 0;
- let num_runs = state.subpartition_reorder_buffer.runs().len();
- for run_idx in 0..num_runs {
- let run = state.subpartition_reorder_buffer.runs()[run_idx];
- let run_batch = batch.slice(offset, run.len);
- offset += run.len;
- staged_memory += state.stage_batch(run_batch, run.relative_partition);
- }
- return Ok(Some(staged_memory));
- }
-
- let Some(runs) = partition_runs(batch.schema_ref())? else {
+ fn stage_partition_runs(
+ &mut self,
+ hash_table: &AggregateHashTable<FinalMarker>,
+ batch: &RecordBatch,
+ ) -> Result<Option<usize>> {
+ if subpartition_column_index(batch.schema_ref()).is_none() {
if self
.partition_run_state
.as_ref()
- .is_some_and(|state| !state.runs.is_empty())
+ .is_some_and(FinalPartitionRunState::has_buffered_runs)
{
return internal_err!(
- "missing partition run metadata for final partitioned aggregation after buffered runs have started"
+ "missing subpartition column for final partitioned aggregation after buffered batches have started"
);
}
return Ok(None);
- };
-
- let mut offset = 0;
- let mut staged_memory = 0;
- for run in runs {
- let run_batch = batch.slice(offset, run.len);
- offset += run.len;
- staged_memory += self
- .partition_run_state
- .as_mut()
- .map(|state| state.stage_batch(run_batch, run.relative_partition))
- .unwrap_or(0);
}
- Ok(Some(staged_memory))
+
+ let evaluated_batch = hash_table.evaluate_batch(batch)?;
+ let group_hashes = hash_table.create_group_hashes(&evaluated_batch)?;
+
+ self.partition_run_state
+ .as_mut()
+ .map(|state| state.stage_batch(batch.clone(), evaluated_batch, group_hashes))
+ .transpose()
}
fn reserve_staged_partition_runs(
@@ -972,20 +1034,6 @@ impl FinalHashAggregateStream {
self.load_next_partition_run(hash_table)
}
- fn finish_partition_run_replay(
- &mut self,
- mut hash_table: AggregateHashTable<FinalMarker>,
- ) -> Result<FinalHashAggregateState> {
- self.start_output(&mut hash_table)?;
-
- if let Some(state) = self.partition_run_state.as_mut() {
- state.finish_replaying_run();
- }
-
- self.update_memory_reservation(Some(&hash_table))?;
- Ok(FinalHashAggregateState::ProducingOutput { hash_table })
- }
-
fn next_state_after_partition_output(
&mut self,
hash_table: AggregateHashTable<FinalMarker>,
@@ -1003,41 +1051,68 @@ impl FinalHashAggregateStream {
fn load_next_partition_run(
&mut self,
- hash_table: AggregateHashTable<FinalMarker>,
+ mut hash_table: AggregateHashTable<FinalMarker>,
) -> Result<FinalHashAggregateState> {
let next_partition_id = self
.partition_run_state
.as_ref()
.and_then(FinalPartitionRunState::next_partition_id);
- if let Some(partition_id) = next_partition_id {
- let runs = self
- .partition_run_state
- .as_mut()
- .ok_or_else(|| {
+ let Some(partition_id) = next_partition_id else {
+ let input_schema = self.input.schema();
+ self.input = Box::pin(EmptyRecordBatchStream::new(input_schema));
+ self.update_memory_reservation(None)?;
+ return Ok(FinalHashAggregateState::Done);
+ };
+
+ let batch_indices = self
+ .partition_run_state
+ .as_mut()
+ .ok_or_else(|| {
+ DataFusionError::Internal(
+ "missing partition run state while replaying final aggregate runs"
+ .to_string(),
+ )
+ })?
+ .take_partition_batch_indices(partition_id)?;
+
+ for batch_idx in batch_indices {
+ let partition_indices = {
+ let state = self.partition_run_state.as_mut().ok_or_else(|| {
+ DataFusionError::Internal(
+ "missing partition run state while building final aggregate partition indices"
+ .to_string(),
+ )
+ })?;
+ state.build_partition_indices(batch_idx, partition_id)?
+ };
+
+ debug_assert!(!partition_indices.is_empty());
+ let buffered_batch = {
+ let state = self.partition_run_state.as_ref().ok_or_else(|| {
DataFusionError::Internal(
"missing partition run state while replaying final aggregate runs"
.to_string(),
)
- })?
- .take_run(partition_id)?;
- let schema = runs.first().map(|batch| batch.schema()).ok_or_else(|| {
- DataFusionError::Internal(format!(
- "Buffered runs for final aggregate partition {partition_id} were unexpectedly empty"
- ))
- })?;
- self.input = Box::pin(BucketStream {
- schema,
- iter: runs.into_iter(),
- });
- self.update_memory_reservation(Some(&hash_table))?;
- Ok(FinalHashAggregateState::ReadingInput { hash_table })
- } else {
- let input_schema = self.input.schema();
- self.input = Box::pin(EmptyRecordBatchStream::new(input_schema));
- self.update_memory_reservation(None)?;
- Ok(FinalHashAggregateState::Done)
+ })?;
+ &state.batches[batch_idx]
+ };
+ hash_table.aggregate_partitioned_evaluated_batch(
+ &buffered_batch.evaluated_batch,
+ &buffered_batch.group_hashes,
+ &partition_indices,
+ )?;
+ if let Some(state) = self.partition_run_state.as_mut() {
+ state.return_partition_indices(partition_indices);
+ }
+ }
+
+ if let Some(state) = self.partition_run_state.as_mut() {
+ state.finish_partition_replay();
}
+ self.start_output(&mut hash_table)?;
+ self.update_memory_reservation(Some(&hash_table))?;
+ Ok(FinalHashAggregateState::ProducingOutput { hash_table })
}
fn update_memory_reservation(
@@ -1070,44 +1145,13 @@ impl FinalHashAggregateStream {
hash_table.start_output()
}
- // FinalPartitioned inputs may arrive as coalesced batches with partition run
- // metadata. The rows are already grouped by relative aggregate partition inside
- // each batch, but multiple relative partitions can share the same output stream.
- //
- // Original input stream:
- //
- // batch A rows: [ p0 ][ p1 ] metadata: [(p0, len), (p1, len)]
- // batch B rows: [ p0 ][ p1 ] metadata: [(p0, len), (p1, len)]
- //
- // Buffer by relative aggregate partition while reading the original stream:
- //
- // FinalPartitionRunState.runs
- // +----+-----------------------------+
- // | p0 | [ A.p0 slice, B.p0 slice ] |
- // | p1 | [ A.p1 slice, B.p1 slice ] |
- // +----+-----------------------------+
- //
- // Replay after the original stream ends:
- //
- // p0 slices -> fresh final hash table -> output p0 groups
- // p1 slices -> fresh final hash table -> output p1 groups
+ // FinalPartitioned inputs may carry an internal subpartition column. If the
+ // group value implementation supports filtered interning, the stream buffers
+ // those batches and replays one relative aggregate partition at a time using
+ // a reusable final hash table plus per-partition filters.
//
- // This keeps equal group keys from different relative aggregate partitions from
- // being merged together, while still merging the same group key within one
- // relative aggregate partition.
- //
- // State transitions:
- //
- // Reading original input
- // + metadata -> buffer slices, keep ReadingInput
- // + no metadata -> normal aggregate_batch path
- // + input done -> begin_partition_run_replay(...)
- //
- // Reading BucketStream(pN)
- // + input done -> finish_partition_run_replay(...) -> ProducingOutput(pN)
- //
- // ProducingOutput(pN)
- // + output done -> load_next_partition_run(fresh table) or Done
+ // If filtered interning is not supported, this optimization is skipped
+ // entirely and input batches are processed by the normal aggregate path.
//
/// Handle ReadingInput state - aggregate partial state batches into the hash table.
///
@@ -1131,7 +1175,7 @@ impl FinalHashAggregateStream {
let elapsed_compute = self.baseline_metrics.elapsed_compute().clone();
let timer = elapsed_compute.timer();
- if self.should_buffer_partition_runs() {
+ if self.should_buffer_partition_runs(original_state.hash_table()) {
if original_state.hash_table().building_group_count() != 0 {
timer.done();
return ControlFlow::Break((
@@ -1142,7 +1186,7 @@ impl FinalHashAggregateStream {
));
}
- match self.stage_partition_runs(&batch) {
+ match self.stage_partition_runs(original_state.hash_table(), &batch) {
Ok(Some(batch_memory)) => {
let result = self.reserve_staged_partition_runs(
batch_memory,
@@ -1211,10 +1255,7 @@ impl FinalHashAggregateStream {
let elapsed_compute = self.baseline_metrics.elapsed_compute().clone();
let timer = elapsed_compute.timer();
let result = match self.partition_run_state.as_ref() {
- Some(state) if state.is_draining => {
- self.finish_partition_run_replay(original_state.into_hash_table())
- }
- Some(state) if !state.runs.is_empty() => {
+ Some(state) if !state.run_batch_indices.is_empty() => {
self.begin_partition_run_replay(original_state.into_hash_table())
}
_ => self
@@ -1376,7 +1417,8 @@ mod tests {
use super::*;
use crate::aggregates::{
- AggregateMode, PartitionRun, PhysicalGroupBy, set_partition_runs_metadata,
+ AggregateMode, PartitionRun, PhysicalGroupBy, append_subpartition_column,
+ subpartition_schema,
};
use crate::execution_plan::ExecutionPlan;
use crate::test::TestMemoryExec;
@@ -1398,39 +1440,45 @@ mod tests {
async fn test_final_hash_stream_replays_partition_runs() -> Result<()> {
let schema = Arc::new(Schema::new(vec![
Field::new("group_col", DataType::Int32, false),
+ Field::new("group_col2", DataType::Int32, false),
Field::new("value", DataType::Int64, false),
]));
- let make_batch = |groups: Vec<i32>, values: Vec<i64>| {
+ let make_batch = |groups: Vec<i32>, group2: Vec<i32>, values: Vec<i64>| {
RecordBatch::try_new(
Arc::clone(&schema),
vec![
Arc::new(Int32Array::from(groups)) as ArrayRef,
+ Arc::new(Int32Array::from(group2)) as ArrayRef,
Arc::new(Int64Array::from(values)) as ArrayRef,
],
)
};
+ let input_schema = subpartition_schema(&schema);
let input_batches = vec![
- set_partition_runs_metadata(
- make_batch(vec![1, 2, 1], vec![2, 5, 11])?,
+ append_subpartition_column(
+ &make_batch(vec![1, 2, 1], vec![10, 10, 10], vec![2, 5, 11])?,
&[PartitionRun::new(0, 2)?, PartitionRun::new(1, 1)?],
)?,
- set_partition_runs_metadata(
- make_batch(vec![1, 3, 1, 3], vec![3, 7, 1, 9])?,
+ append_subpartition_column(
+ &make_batch(vec![1, 3, 1, 3], vec![10, 10, 10, 10], vec![3, 7, 1, 9])?,
&[PartitionRun::new(0, 2)?, PartitionRun::new(1, 2)?],
)?,
];
- let input =
- TestMemoryExec::try_new_exec(&[input_batches], Arc::clone(&schema), None)?;
+ let input = TestMemoryExec::try_new_exec(
+ &[input_batches],
+ Arc::clone(&input_schema),
+ None,
+ )?;
let input =
Arc::new(TestMemoryExec::update_cache(&input)) as Arc<dyn ExecutionPlan>;
- let group_by = PhysicalGroupBy::new_single(vec![(
- col("group_col", &schema)?,
- "group_col".to_string(),
- )]);
+ let group_by = PhysicalGroupBy::new_single(vec![
+ (col("group_col", &schema)?, "group_col".to_string()),
+ (col("group_col2", &schema)?, "group_col2".to_string()),
+ ]);
let aggr_expr = vec![Arc::new(
AggregateExprBuilder::new(sum_udaf(), vec![col("value", &schema)?])
.schema(Arc::clone(&schema))
@@ -1443,7 +1491,7 @@ mod tests {
aggr_expr,
vec![None],
input,
- Arc::clone(&schema),
+ Arc::clone(&input_schema),
)?;
let task_ctx = Arc::new(TaskContext::default());
@@ -1456,23 +1504,33 @@ mod tests {
.as_any()
.downcast_ref::<Int32Array>()
.expect("group column should be Int32");
- let sums = batch
+ let group2 = batch
.column(1)
.as_any()
+ .downcast_ref::<Int32Array>()
+ .expect("second group column should be Int32");
+ let sums = batch
+ .column(2)
+ .as_any()
.downcast_ref::<Int64Array>()
.expect("sum column should be Int64");
for row in 0..batch.num_rows() {
- actual.push((groups.value(row), sums.value(row)));
+ actual.push((groups.value(row), group2.value(row), sums.value(row)));
}
}
actual.sort_unstable();
- assert_eq!(actual, vec![(1, 5), (1, 12), (2, 5), (3, 7), (3, 9)]);
+ assert_eq!(
+ actual,
+ vec![(1, 10, 5), (1, 10, 12), (2, 10, 5), (3, 10, 7), (3, 10, 9),]
+ );
assert!(
stream
.partition_run_state
.as_ref()
- .is_some_and(|state| state.runs.is_empty() && state.is_draining)
+ .is_some_and(
+ |state| state.run_batch_indices.is_empty() && state.is_draining
+ )
);
Ok(())
diff --git a/datafusion/physical-plan/src/aggregates/mod.rs b/datafusion/physical-plan/src/aggregates/mod.rs
index 336910ff35..e1d5a3cd85 100644
--- a/datafusion/physical-plan/src/aggregates/mod.rs
+++ b/datafusion/physical-plan/src/aggregates/mod.rs
@@ -69,11 +69,9 @@ use datafusion_physical_expr_common::sort_expr::{
use datafusion_expr::utils::AggregateOrderSensitivity;
use datafusion_physical_expr_common::utils::evaluate_expressions_to_arrays;
use itertools::Itertools;
-#[cfg(test)]
-pub(crate) use partition_runs::set_partition_runs_metadata;
pub(crate) use partition_runs::{
- PartitionRun, SubpartitionReorderBuffer, append_subpartition_column, partition_runs,
- reorder_by_subpartition, subpartition_schema,
+ PartitionRun, append_subpartition_column, subpartition_column_index,
+ subpartition_schema,
};
use topk::hash_table::is_supported_hash_key_type;
use topk::heap::is_supported_heap_type;
diff --git a/datafusion/physical-plan/src/aggregates/partition_runs.rs b/datafusion/physical-plan/src/aggregates/partition_runs.rs
index afc5567acb..e4c9fba50f 100644
--- a/datafusion/physical-plan/src/aggregates/partition_runs.rs
+++ b/datafusion/physical-plan/src/aggregates/partition_runs.rs
@@ -15,6 +15,8 @@
// specific language governing permissions and limitations
// under the License.
+#![allow(dead_code)]
+
//! Internal helpers for hash aggregate repartition subpartitions.
//!
//! This module does NOT perform repartitioning or aggregation. It only owns the
@@ -325,7 +327,7 @@ pub(crate) fn set_partition_runs_metadata(
Ok(batch)
}
-fn subpartition_column_index(schema: &Schema) -> Option<usize> {
+pub(crate) fn subpartition_column_index(schema: &Schema) -> Option<usize> {
schema
.fields()
.iter()
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org