Skip to content

Commit 320a7d2

Browse files
authored
feat: add grouping equivalence properties (apache#24698)
## Which issue does this PR relate to? - Part of apache#24438. - Builds on apache#24737 and apache#24697, both merged. ## Rationale for this change Aggregation can recognize completed groups when all rows with the same grouping-key tuple occur in one contiguous run within a partition. Sorted input provides this guarantee, and the runs can also appear in an arbitrary order: ```text AAABBBCCCC -> ordered and grouped CCCAAABBB -> grouped; each group can be completed when its run ends AAABBBAACC -> A appears in separate runs ``` This PR represents that guarantee in `EquivalenceProperties`, allowing execution-plan producers to declare grouping tuples and consumers to check whether an input satisfies a grouping requirement. ## What changes are included in this PR? ### Semantics and propagation A grouping assertion describes a complete expression tuple within every output partition. `[a, b]` and `[b, a]` identify the same groups. The guarantee applies to the complete pair; a guarantee for a subset such as `[a]` requires its own proof. Grouping assertions are correctness guarantees supplied by producers. DataFusion trusts the asserted row layout. Producers can declare derived tuples such as `[bhandle, date_bin(timestamp)]` directly. - Store grouping tuples alongside ordering, equality, and constant information in `EquivalenceProperties`. - Normalize tuples using expression equivalences and constants, removing duplicate expressions. - Check grouping requirements against declared tuples and grouping implied by lexicographical ordering prefixes. - Project a tuple when every expression can be represented in the output, including explicitly declared derived expressions. - Remap grouping expressions during schema replacement. - Preserve a declared grouping tuple through `UnionExec` when every input satisfies it, explicitly or through ordering. - Clear explicit grouping assertions at aggregation, sorting, repartitioning, and partition-merging boundaries where execution can invalidate them. ### Public API additions - `GroupingEquivalenceClass` represents complete grouping tuples and supports construction, insertion, lookup, clearing, schema rewriting, iteration, and display. - `EquivalenceProperties::{geq_class, normalized_geq_class, add_grouping, add_groupings, clear_groupings, grouping_satisfy}` expose grouping metadata and its analysis. - `TestMemoryExec::try_with_grouping_information` attaches grouping assertions in physical-plan tests and examples. Execution-plan producers attach these assertions through the `EquivalenceProperties` held by `PlanProperties`. The follow-up apache#24497 consumes them to derive `GroupClusteringMode::Full` for eligible aggregates. ## Stack 1. [apache#24737 — test: cover unsorted contiguous groups in one partition](apache#24737) (merged) 2. [apache#24697 — refactor: use group clustering terminology in aggregate execution](apache#24697) (merged) 3. [apache#24698 — feat: add grouping equivalence properties](apache#24698) ← **this PR** 4. [apache#24497 — feat: stream aggregates over grouped input](apache#24497) ## What is the testing strategy for this PR? Tests cover complete-tuple semantics, equivalent permutations, normalization through equivalences and constants, ordering-derived grouping, complete and incomplete projection mappings, explicitly declared derived expressions, operator boundaries, and UNION propagation with selective tuple retention, mixed grouping/ordering proofs, schema rewrites, and input permutations. `aggregate_clears_explicit_grouping` covers partial and single aggregation with reordered and aliased grouping keys. Both cases fail without the aggregate boundary clear and pass with it. Local validation passed the extended workspace suite, including 2,997 physical-plan tests and 546 SQL logic files, and all-target/all-feature Clippy with warnings denied. ## Are there any user-facing changes? Yes. The additive Rust APIs above let plan producers describe contiguous grouping tuples and let consumers evaluate grouping requirements. The streaming aggregate optimization follows in apache#24497. ## Review this layer [View this PR's diff](https://github.com/apache/datafusion/pull/24698/files)
1 parent 4591113 commit 320a7d2

11 files changed

Lines changed: 1050 additions & 36 deletions

File tree

Lines changed: 192 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,192 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3+
// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4+
5+
use std::fmt::Display;
6+
use std::ops::Deref;
7+
use std::sync::Arc;
8+
use std::vec::IntoIter;
9+
10+
use crate::PhysicalExpr;
11+
use crate::expressions::with_new_schema;
12+
13+
use arrow::datatypes::SchemaRef;
14+
use datafusion_common::{HashSet, Result};
15+
use datafusion_physical_expr_common::physical_expr::format_physical_expr_list;
16+
17+
/// A set of grouping tuples that are known to describe contiguous rows.
18+
///
19+
/// Each entry is a complete grouping tuple. For example, `[a, b]` means that,
20+
/// within each output partition, all rows having the same values for both `a`
21+
/// and `b` occur in one contiguous run. The runs themselves may occur in any
22+
/// order. Contiguity applies to the complete partition stream, not separately
23+
/// to each record batch.
24+
///
25+
/// Expression order within an entry is not significant: `[a, b]` and `[b, a]`
26+
/// describe the same grouping. Entries do not imply properties for subsets;
27+
/// `[a, b]` alone says nothing about whether all rows with the same `a` are
28+
/// contiguous.
29+
#[derive(Clone, Debug, Default)]
30+
pub struct GroupingEquivalenceClass {
31+
groupings: Vec<Vec<Arc<dyn PhysicalExpr>>>,
32+
}
33+
34+
impl GroupingEquivalenceClass {
35+
/// Clears all groupings in this equivalence class.
36+
pub fn clear(&mut self) {
37+
self.groupings.clear();
38+
}
39+
40+
/// Creates a grouping equivalence class, discarding empty and duplicate
41+
/// entries and duplicate expressions within each entry.
42+
pub fn new(
43+
groupings: impl IntoIterator<Item = impl IntoIterator<Item = Arc<dyn PhysicalExpr>>>,
44+
) -> Self {
45+
let mut result = Self::default();
46+
result.add_groupings(groupings);
47+
result
48+
}
49+
50+
/// Adds grouping tuples to this equivalence class.
51+
pub fn add_groupings(
52+
&mut self,
53+
groupings: impl IntoIterator<Item = impl IntoIterator<Item = Arc<dyn PhysicalExpr>>>,
54+
) {
55+
for grouping in groupings {
56+
let mut seen = HashSet::new();
57+
let grouping = grouping
58+
.into_iter()
59+
.filter(|expr| seen.insert(Arc::clone(expr)))
60+
.collect::<Vec<_>>();
61+
if !grouping.is_empty() && !self.contains(&grouping) {
62+
self.groupings.push(grouping);
63+
}
64+
}
65+
}
66+
67+
/// Returns whether this class contains the complete grouping tuple.
68+
pub fn contains(&self, grouping: &[Arc<dyn PhysicalExpr>]) -> bool {
69+
self.groupings
70+
.iter()
71+
.any(|candidate| same_grouping(candidate, grouping))
72+
}
73+
74+
/// Rewrites all expressions to reference an aligned schema.
75+
pub fn with_new_schema(self, schema: &SchemaRef) -> Result<Self> {
76+
let groupings = self.groupings.into_iter().map(|grouping| {
77+
grouping
78+
.into_iter()
79+
.map(|expr| with_new_schema(expr, schema))
80+
.collect::<Result<Vec<_>>>()
81+
});
82+
Ok(Self::new(groupings.collect::<Result<Vec<_>>>()?))
83+
}
84+
}
85+
86+
fn same_grouping(lhs: &[Arc<dyn PhysicalExpr>], rhs: &[Arc<dyn PhysicalExpr>]) -> bool {
87+
lhs.iter()
88+
.all(|lhs_expr| rhs.iter().any(|rhs_expr| lhs_expr.eq(rhs_expr)))
89+
&& rhs
90+
.iter()
91+
.all(|rhs_expr| lhs.iter().any(|lhs_expr| rhs_expr.eq(lhs_expr)))
92+
}
93+
94+
impl PartialEq for GroupingEquivalenceClass {
95+
fn eq(&self, other: &Self) -> bool {
96+
self.groupings.len() == other.groupings.len()
97+
&& self
98+
.groupings
99+
.iter()
100+
.all(|grouping| other.contains(grouping))
101+
}
102+
}
103+
104+
impl Eq for GroupingEquivalenceClass {}
105+
106+
impl Deref for GroupingEquivalenceClass {
107+
type Target = [Vec<Arc<dyn PhysicalExpr>>];
108+
109+
fn deref(&self) -> &Self::Target {
110+
self.groupings.as_slice()
111+
}
112+
}
113+
114+
impl From<Vec<Vec<Arc<dyn PhysicalExpr>>>> for GroupingEquivalenceClass {
115+
fn from(groupings: Vec<Vec<Arc<dyn PhysicalExpr>>>) -> Self {
116+
Self::new(groupings)
117+
}
118+
}
119+
120+
/// Converts the grouping equivalence class into an iterator of complete
121+
/// grouping tuples.
122+
impl IntoIterator for GroupingEquivalenceClass {
123+
type Item = Vec<Arc<dyn PhysicalExpr>>;
124+
type IntoIter = IntoIter<Self::Item>;
125+
126+
fn into_iter(self) -> Self::IntoIter {
127+
self.groupings.into_iter()
128+
}
129+
}
130+
131+
impl From<GroupingEquivalenceClass> for Vec<Vec<Arc<dyn PhysicalExpr>>> {
132+
fn from(geq_class: GroupingEquivalenceClass) -> Self {
133+
geq_class.groupings
134+
}
135+
}
136+
137+
impl Display for GroupingEquivalenceClass {
138+
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
139+
write!(f, "[")?;
140+
let mut groupings = self.groupings.iter();
141+
if let Some(grouping) = groupings.next() {
142+
write!(f, "{}", format_physical_expr_list(grouping))?;
143+
}
144+
for grouping in groupings {
145+
write!(f, ", {}", format_physical_expr_list(grouping))?;
146+
}
147+
write!(f, "]")
148+
}
149+
}
150+
151+
#[cfg(test)]
152+
mod tests {
153+
use super::*;
154+
use crate::expressions::Column;
155+
156+
#[test]
157+
fn grouping_equality_ignores_expression_and_entry_order() {
158+
let a = Arc::new(Column::new("a", 0)) as Arc<dyn PhysicalExpr>;
159+
let b = Arc::new(Column::new("b", 1)) as Arc<dyn PhysicalExpr>;
160+
let c = Arc::new(Column::new("c", 2)) as Arc<dyn PhysicalExpr>;
161+
162+
let lhs = GroupingEquivalenceClass::new([
163+
vec![Arc::clone(&a), Arc::clone(&b)],
164+
vec![Arc::clone(&c)],
165+
]);
166+
let rhs = GroupingEquivalenceClass::new([
167+
vec![Arc::clone(&c)],
168+
vec![Arc::clone(&b), Arc::clone(&a)],
169+
]);
170+
171+
assert_eq!(lhs, rhs);
172+
// The same expressions in different tuples describe different guarantees.
173+
assert_ne!(lhs, GroupingEquivalenceClass::new([vec![a, c], vec![b]]));
174+
}
175+
176+
#[test]
177+
fn grouping_deduplicates_entries_and_expressions() {
178+
let a = Arc::new(Column::new("a", 0)) as Arc<dyn PhysicalExpr>;
179+
let b = Arc::new(Column::new("b", 1)) as Arc<dyn PhysicalExpr>;
180+
181+
let groupings = GroupingEquivalenceClass::new([
182+
vec![Arc::clone(&a), Arc::clone(&a), Arc::clone(&b)],
183+
vec![Arc::clone(&b), Arc::clone(&a)],
184+
vec![],
185+
]);
186+
187+
assert_eq!(groupings.len(), 1);
188+
assert_eq!(groupings[0].len(), 2);
189+
assert!(groupings.contains(&[Arc::clone(&a), Arc::clone(&a), Arc::clone(&b),]));
190+
assert_eq!(groupings.to_string(), "[[a@0, b@1]]");
191+
}
192+
}

0 commit comments

Comments
 (0)