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