Skip to content

Commit 07483c1

Browse files
authored
feat: preserving grouped state reads (apache#24714)
## Which issue does this PR close? - Closes: apache#24602 ## Rationale for this change Long-lived grouped aggregation state currently must be drained and rebuilt to read a subset of groups. Preserving reads avoid that full-state round trip. Although the diff is quite large, the conceptual change is fairly contained. Most of the code updates apply the same preserving-read contract across DataFusion’s existing `GroupColumn` and `GroupsAccumulator` implementations. ## What changes are included in this PR? - Adds validated `GroupSelection` API for all groups or ordered group indices. - Adds optional preserving-read APIs and capability checks to `GroupValues` and `GroupsAccumulator`. - Implements selected reads for built-in group values and grouped accumulators. - Documents the required `GroupColumn` migration. ## Are these changes tested? Yes ## Are there any user-facing changes? `GroupColumn::values_preserving` is a new required public trait method, so this is technically a breaking change. However, I think the downstream impact is low since `GroupColumn` seems to be a fairly low-level trait, and DataFusion doesn't expose a public path for supplying a custom implementation to `GroupValuesColumn`
1 parent 739974b commit 07483c1

33 files changed

Lines changed: 2212 additions & 259 deletions

File tree

‎datafusion/expr-common/src/groups_accumulator.rs‎

Lines changed: 162 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -18,7 +18,7 @@
1818
//! Vectorized [`GroupsAccumulator`]
1919
2020
use arrow::array::{ArrayRef, BooleanArray};
21-
use datafusion_common::{Result, utils::split_vec_min_alloc};
21+
use datafusion_common::{Result, exec_err, not_impl_err, utils::split_vec_min_alloc};
2222

2323
/// Describes how many rows should be emitted during grouping.
2424
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
@@ -50,6 +50,91 @@ impl EmitTo {
5050
}
5151
}
5252

53+
/// Selects groups for a non-destructive grouped aggregation read.
54+
///
55+
/// Unlike [`EmitTo`], this selection does not remove groups or change their
56+
/// indices. Selections created by [`Self::try_from_indices`] preserve the
57+
/// requested order and support duplicate indices.
58+
///
59+
/// A selection is validated once when it is constructed and can then be reused
60+
/// for the group values and accumulators participating in the same snapshot.
61+
/// Construct a new selection if the number or indexing of those groups changes.
62+
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
63+
pub struct GroupSelection<'a> {
64+
total_num_groups: usize,
65+
indices: Option<&'a [usize]>,
66+
}
67+
68+
impl<'a> GroupSelection<'a> {
69+
/// Selects all `total_num_groups` groups in group-index order.
70+
pub fn all(total_num_groups: usize) -> Self {
71+
Self {
72+
total_num_groups,
73+
indices: None,
74+
}
75+
}
76+
77+
/// Selects groups in the order specified by `indices`.
78+
///
79+
/// Returns an error if an index is not less than `total_num_groups`. Empty
80+
/// selections are valid, and duplicate indices are preserved.
81+
pub fn try_from_indices(
82+
indices: &'a [usize],
83+
total_num_groups: usize,
84+
) -> Result<Self> {
85+
if let Some(index) = indices.iter().find(|&&index| index >= total_num_groups) {
86+
return exec_err!(
87+
"Group index {index} is out of bounds for {total_num_groups} groups"
88+
);
89+
}
90+
Ok(Self {
91+
total_num_groups,
92+
indices: Some(indices),
93+
})
94+
}
95+
96+
/// Returns the group count against which this selection was constructed.
97+
pub fn total_num_groups(self) -> usize {
98+
self.total_num_groups
99+
}
100+
101+
/// Ensures this selection is being applied to the same number of groups
102+
/// against which it was constructed.
103+
///
104+
/// Preserving-read implementations should call this method with their
105+
/// stored group count before using [`Self::iter`]. This check is `O(1)`;
106+
/// the selected indices were already checked by [`Self::try_from_indices`].
107+
pub fn validate_num_groups(self, actual_num_groups: usize) -> Result<()> {
108+
if actual_num_groups != self.total_num_groups {
109+
return exec_err!(
110+
"Group selection was constructed for {} groups but applied to {actual_num_groups} groups",
111+
self.total_num_groups
112+
);
113+
}
114+
Ok(())
115+
}
116+
117+
/// Returns the number of selected groups.
118+
pub fn len(self) -> usize {
119+
self.indices
120+
.map_or(self.total_num_groups, |indices| indices.len())
121+
}
122+
123+
/// Returns `true` if no groups are selected.
124+
pub fn is_empty(self) -> bool {
125+
self.len() == 0
126+
}
127+
128+
/// Returns the selected group indices in output order.
129+
pub fn iter(self) -> impl Iterator<Item = usize> + 'a {
130+
let (all, indices): (_, &'a [usize]) = match self.indices {
131+
None => (0..self.total_num_groups, &[]),
132+
Some(indices) => (0..0, indices),
133+
};
134+
all.chain(indices.iter().copied())
135+
}
136+
}
137+
53138
/// `GroupsAccumulator` implements a single aggregate (e.g. AVG) and
54139
/// stores the state for *all* groups internally.
55140
///
@@ -154,6 +239,27 @@ pub trait GroupsAccumulator: Send + std::any::Any {
154239
/// `n`. See [`EmitTo::First`] for more details.
155240
fn evaluate(&mut self, emit_to: EmitTo) -> Result<ArrayRef>;
156241

242+
/// Returns final aggregate values without changing the logical state or
243+
/// group indices.
244+
///
245+
/// Rows are returned in the order specified by `selection`. An empty
246+
/// selection returns a correctly typed array with no rows.
247+
///
248+
/// This method requires exclusive access because implementations may mutate
249+
/// internal caches or builders. However, repeated calls and later updates
250+
/// must observe the same logical accumulator state.
251+
fn evaluate_preserving(
252+
&mut self,
253+
_selection: GroupSelection<'_>,
254+
) -> Result<ArrayRef> {
255+
not_impl_err!("Preserving grouped evaluation is not implemented")
256+
}
257+
258+
/// Returns `true` if [`Self::evaluate_preserving`] is implemented.
259+
fn supports_evaluate_preserving(&self) -> bool {
260+
false
261+
}
262+
157263
/// Returns the intermediate aggregate state for this accumulator,
158264
/// used for multi-phase grouping, resetting its internal state.
159265
///
@@ -172,6 +278,28 @@ pub trait GroupsAccumulator: Send + std::any::Any {
172278
/// [`Accumulator::state`]: crate::accumulator::Accumulator::state
173279
fn state(&mut self, emit_to: EmitTo) -> Result<Vec<ArrayRef>>;
174280

281+
/// Returns intermediate aggregate state without changing the logical state
282+
/// or group indices.
283+
///
284+
/// Each returned array has one row per selected group, in the order
285+
/// specified by `selection`. An empty selection returns the normal number
286+
/// of correctly typed state arrays, each with no rows.
287+
///
288+
/// This method requires exclusive access because implementations may mutate
289+
/// internal caches or builders. However, repeated calls and later updates
290+
/// must observe the same logical accumulator state.
291+
fn state_preserving(
292+
&mut self,
293+
_selection: GroupSelection<'_>,
294+
) -> Result<Vec<ArrayRef>> {
295+
not_impl_err!("Preserving grouped state is not implemented")
296+
}
297+
298+
/// Returns `true` if [`Self::state_preserving`] is implemented.
299+
fn supports_state_preserving(&self) -> bool {
300+
false
301+
}
302+
175303
/// Merges intermediate state (the output from [`Self::state`])
176304
/// into this accumulator's current state.
177305
///
@@ -247,7 +375,7 @@ pub trait GroupsAccumulator: Send + std::any::Any {
247375

248376
#[cfg(test)]
249377
mod tests {
250-
use super::EmitTo;
378+
use super::{EmitTo, GroupSelection};
251379

252380
/// When `n` is small relative to `len`, the old `split_off(n) + swap` pattern had
253381
/// two allocation problems:
@@ -293,4 +421,36 @@ mod tests {
293421
original_capacity,
294422
);
295423
}
424+
425+
#[test]
426+
fn group_selection_is_validated_once_and_reusable() {
427+
let values = [10, 20, 30, 40];
428+
let selected =
429+
GroupSelection::try_from_indices(&[3, 1, 3], values.len()).unwrap();
430+
assert_eq!(selected.total_num_groups(), values.len());
431+
assert_eq!(selected.len(), 3);
432+
assert_eq!(
433+
selected
434+
.iter()
435+
.map(|index| values[index])
436+
.collect::<Vec<_>>(),
437+
vec![40, 20, 40]
438+
);
439+
selected.validate_num_groups(values.len()).unwrap();
440+
let error = selected.validate_num_groups(values.len() - 1).unwrap_err();
441+
assert!(error.to_string().contains("constructed for 4 groups"));
442+
443+
let all = GroupSelection::all(values.len());
444+
assert_eq!(
445+
all.iter().map(|index| values[index]).collect::<Vec<_>>(),
446+
values
447+
);
448+
449+
let empty = GroupSelection::try_from_indices(&[], values.len()).unwrap();
450+
assert!(empty.is_empty());
451+
assert!(empty.iter().next().is_none());
452+
453+
let error = GroupSelection::try_from_indices(&[4], values.len()).unwrap_err();
454+
assert!(error.to_string().contains("out of bounds"));
455+
}
296456
}

‎datafusion/expr/src/lib.rs‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -103,7 +103,9 @@ pub use datafusion_doc::{
103103
};
104104
pub use datafusion_expr_common::accumulator::Accumulator;
105105
pub use datafusion_expr_common::columnar_value::ColumnarValue;
106-
pub use datafusion_expr_common::groups_accumulator::{EmitTo, GroupsAccumulator};
106+
pub use datafusion_expr_common::groups_accumulator::{
107+
EmitTo, GroupSelection, GroupsAccumulator,
108+
};
107109
pub use datafusion_expr_common::operator::Operator;
108110
pub use datafusion_expr_common::placement::ExpressionPlacement;
109111
pub use datafusion_expr_common::signature::{

‎datafusion/functions-aggregate-common/src/aggregate/count_distinct/groups.rs‎

Lines changed: 60 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -23,7 +23,9 @@ use arrow::buffer::{OffsetBuffer, ScalarBuffer};
2323
use arrow::datatypes::{ArrowPrimitiveType, Field};
2424
use datafusion_common::HashSet;
2525
use datafusion_common::hash_utils::RandomState;
26-
use datafusion_expr_common::groups_accumulator::{EmitTo, GroupsAccumulator};
26+
use datafusion_expr_common::groups_accumulator::{
27+
EmitTo, GroupSelection, GroupsAccumulator,
28+
};
2729
use std::hash::Hash;
2830
use std::mem::size_of;
2931
use std::sync::Arc;
@@ -103,6 +105,22 @@ where
103105
Ok(Arc::new(Int64Array::from(counts)))
104106
}
105107

108+
fn evaluate_preserving(
109+
&mut self,
110+
selection: GroupSelection<'_>,
111+
) -> datafusion_common::Result<ArrayRef> {
112+
selection.validate_num_groups(self.counts.len())?;
113+
let counts = selection
114+
.iter()
115+
.map(|index| self.counts[index])
116+
.collect::<Vec<_>>();
117+
Ok(Arc::new(Int64Array::from(counts)))
118+
}
119+
120+
fn supports_evaluate_preserving(&self) -> bool {
121+
true
122+
}
123+
106124
fn state(&mut self, emit_to: EmitTo) -> datafusion_common::Result<Vec<ArrayRef>> {
107125
let num_emitted = match emit_to {
108126
EmitTo::All => self.counts.len(),
@@ -221,6 +239,47 @@ mod tests {
221239
use arrow::datatypes::Int32Type;
222240
use datafusion_common::Result;
223241

242+
#[test]
243+
fn preserving_reads_keep_distinct_state() -> Result<()> {
244+
let mut accumulator = PrimitiveDistinctCountGroupsAccumulator::<Int32Type>::new();
245+
let values = Arc::new(Int32Array::from(vec![
246+
Some(1),
247+
Some(2),
248+
Some(1),
249+
None,
250+
Some(3),
251+
]));
252+
accumulator.update_batch(&[values], &[0, 0, 1, 2, 2], None, 4)?;
253+
254+
let selection = GroupSelection::try_from_indices(&[2, 0, 3, 2], 4)?;
255+
let expected = Int64Array::from(vec![1, 2, 0, 1]);
256+
for _ in 0..2 {
257+
assert_eq!(
258+
accumulator
259+
.evaluate_preserving(selection)?
260+
.as_primitive::<arrow::datatypes::Int64Type>(),
261+
&expected
262+
);
263+
}
264+
assert!(
265+
accumulator
266+
.evaluate_preserving(GroupSelection::try_from_indices(&[], 4)?)?
267+
.is_empty()
268+
);
269+
270+
let values = Arc::new(Int32Array::from(vec![2, 4, 1]));
271+
accumulator.update_batch(&[values], &[0, 0, 1], None, 4)?;
272+
assert_eq!(
273+
accumulator
274+
.evaluate_preserving(GroupSelection::all(4))?
275+
.as_primitive::<arrow::datatypes::Int64Type>(),
276+
&Int64Array::from(vec![3, 1, 1, 0])
277+
);
278+
assert!(accumulator.supports_evaluate_preserving());
279+
assert!(!accumulator.supports_state_preserving());
280+
Ok(())
281+
}
282+
224283
#[test]
225284
fn convert_to_state_roundtrips_through_merge() -> Result<()> {
226285
let values = Arc::new(Int32Array::from(vec![

‎datafusion/functions-aggregate-common/src/aggregate/groups_accumulator.rs‎

Lines changed: 79 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -34,7 +34,9 @@ use arrow::{
3434
};
3535
use datafusion_common::{Result, ScalarValue, arrow_datafusion_err};
3636
use datafusion_expr_common::accumulator::Accumulator;
37-
use datafusion_expr_common::groups_accumulator::{EmitTo, GroupsAccumulator};
37+
use datafusion_expr_common::groups_accumulator::{
38+
EmitTo, GroupSelection, GroupsAccumulator,
39+
};
3840

3941
/// An adapter that implements [`GroupsAccumulator`] for any [`Accumulator`]
4042
///
@@ -335,6 +337,34 @@ impl GroupsAccumulator for GroupsAccumulatorAdapter {
335337
result
336338
}
337339

340+
fn evaluate_preserving(&mut self, selection: GroupSelection<'_>) -> Result<ArrayRef> {
341+
selection.validate_num_groups(self.states.len())?;
342+
let selected_len = selection.len();
343+
if selected_len == 0 {
344+
// ScalarValue::iter_to_array needs at least one value to infer the
345+
// output type, so evaluate a temporary empty accumulator.
346+
let mut accumulator = (self.factory)()?;
347+
return Ok(ScalarValue::iter_to_array([accumulator.evaluate()?])?.slice(0, 0));
348+
}
349+
350+
let mut results = Vec::with_capacity(selected_len);
351+
for group_index in selection.iter() {
352+
let (result, size_pre, size_post) = {
353+
let state = &mut self.states[group_index];
354+
let size_pre = state.size();
355+
let result = state.accumulator.evaluate()?;
356+
(result, size_pre, state.size())
357+
};
358+
self.adjust_allocation(size_pre, size_post);
359+
results.push(result);
360+
}
361+
ScalarValue::iter_to_array(results)
362+
}
363+
364+
fn supports_evaluate_preserving(&self) -> bool {
365+
true
366+
}
367+
338368
// filtered_null_mask(opt_filter, &values);
339369
fn state(&mut self, emit_to: EmitTo) -> Result<Vec<ArrayRef>> {
340370
let vec_size_pre = self.states.allocated_size();
@@ -499,3 +529,51 @@ pub(crate) fn slice_and_maybe_filter(
499529
Ok(sliced_arrays)
500530
}
501531
}
532+
533+
#[cfg(test)]
534+
mod tests {
535+
use std::sync::Arc;
536+
537+
use super::*;
538+
use crate::min_max::MaxAccumulator;
539+
use arrow::array::{AsArray, Int64Array};
540+
use arrow::datatypes::{DataType, Int64Type};
541+
542+
#[test]
543+
fn adapter_preserving_evaluation_uses_accumulator_contract() -> Result<()> {
544+
let mut accumulator = GroupsAccumulatorAdapter::new(|| {
545+
Ok(Box::new(MaxAccumulator::try_new(&DataType::Int64)?)
546+
as Box<dyn Accumulator>)
547+
});
548+
let values = Arc::new(Int64Array::from(vec![Some(1), Some(5), Some(2), None]));
549+
accumulator.update_batch(&[values], &[0, 0, 1, 2], None, 4)?;
550+
551+
let selection = GroupSelection::try_from_indices(&[1, 0, 3, 1], 4)?;
552+
let expected = Int64Array::from(vec![Some(2), Some(5), None, Some(2)]);
553+
for _ in 0..2 {
554+
assert_eq!(
555+
accumulator
556+
.evaluate_preserving(selection)?
557+
.as_primitive::<Int64Type>(),
558+
&expected
559+
);
560+
}
561+
562+
let empty =
563+
accumulator.evaluate_preserving(GroupSelection::try_from_indices(&[], 4)?)?;
564+
assert_eq!(empty.data_type(), &DataType::Int64);
565+
assert!(empty.is_empty());
566+
567+
let values = Arc::new(Int64Array::from(vec![7, 4, 9]));
568+
accumulator.update_batch(&[values], &[0, 2, 3], None, 4)?;
569+
assert_eq!(
570+
accumulator
571+
.evaluate_preserving(GroupSelection::all(4))?
572+
.as_primitive::<Int64Type>(),
573+
&Int64Array::from(vec![Some(7), Some(2), Some(4), Some(9)])
574+
);
575+
assert!(accumulator.supports_evaluate_preserving());
576+
assert!(!accumulator.supports_state_preserving());
577+
Ok(())
578+
}
579+
}

0 commit comments

Comments
 (0)