Repository navigation
Commit 320a7d2
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
- datafusion
- physical-expr/src/equivalence
- properties
- physical-plan/src
- aggregates
- repartition
- sorts
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| 9 | + | |
| 10 | + | |
| 11 | + | |
| 12 | + | |
| 13 | + | |
| 14 | + | |
| 15 | + | |
| 16 | + | |
| 17 | + | |
| 18 | + | |
| 19 | + | |
| 20 | + | |
| 21 | + | |
| 22 | + | |
| 23 | + | |
| 24 | + | |
| 25 | + | |
| 26 | + | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
| 37 | + | |
| 38 | + | |
| 39 | + | |
| 40 | + | |
| 41 | + | |
| 42 | + | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
| 46 | + | |
| 47 | + | |
| 48 | + | |
| 49 | + | |
| 50 | + | |
| 51 | + | |
| 52 | + | |
| 53 | + | |
| 54 | + | |
| 55 | + | |
| 56 | + | |
| 57 | + | |
| 58 | + | |
| 59 | + | |
| 60 | + | |
| 61 | + | |
| 62 | + | |
| 63 | + | |
| 64 | + | |
| 65 | + | |
| 66 | + | |
| 67 | + | |
| 68 | + | |
| 69 | + | |
| 70 | + | |
| 71 | + | |
| 72 | + | |
| 73 | + | |
| 74 | + | |
| 75 | + | |
| 76 | + | |
| 77 | + | |
| 78 | + | |
| 79 | + | |
| 80 | + | |
| 81 | + | |
| 82 | + | |
| 83 | + | |
| 84 | + | |
| 85 | + | |
| 86 | + | |
| 87 | + | |
| 88 | + | |
| 89 | + | |
| 90 | + | |
| 91 | + | |
| 92 | + | |
| 93 | + | |
| 94 | + | |
| 95 | + | |
| 96 | + | |
| 97 | + | |
| 98 | + | |
| 99 | + | |
| 100 | + | |
| 101 | + | |
| 102 | + | |
| 103 | + | |
| 104 | + | |
| 105 | + | |
| 106 | + | |
| 107 | + | |
| 108 | + | |
| 109 | + | |
| 110 | + | |
| 111 | + | |
| 112 | + | |
| 113 | + | |
| 114 | + | |
| 115 | + | |
| 116 | + | |
| 117 | + | |
| 118 | + | |
| 119 | + | |
| 120 | + | |
| 121 | + | |
| 122 | + | |
| 123 | + | |
| 124 | + | |
| 125 | + | |
| 126 | + | |
| 127 | + | |
| 128 | + | |
| 129 | + | |
| 130 | + | |
| 131 | + | |
| 132 | + | |
| 133 | + | |
| 134 | + | |
| 135 | + | |
| 136 | + | |
| 137 | + | |
| 138 | + | |
| 139 | + | |
| 140 | + | |
| 141 | + | |
| 142 | + | |
| 143 | + | |
| 144 | + | |
| 145 | + | |
| 146 | + | |
| 147 | + | |
| 148 | + | |
| 149 | + | |
| 150 | + | |
| 151 | + | |
| 152 | + | |
| 153 | + | |
| 154 | + | |
| 155 | + | |
| 156 | + | |
| 157 | + | |
| 158 | + | |
| 159 | + | |
| 160 | + | |
| 161 | + | |
| 162 | + | |
| 163 | + | |
| 164 | + | |
| 165 | + | |
| 166 | + | |
| 167 | + | |
| 168 | + | |
| 169 | + | |
| 170 | + | |
| 171 | + | |
| 172 | + | |
| 173 | + | |
| 174 | + | |
| 175 | + | |
| 176 | + | |
| 177 | + | |
| 178 | + | |
| 179 | + | |
| 180 | + | |
| 181 | + | |
| 182 | + | |
| 183 | + | |
| 184 | + | |
| 185 | + | |
| 186 | + | |
| 187 | + | |
| 188 | + | |
| 189 | + | |
| 190 | + | |
| 191 | + | |
| 192 | + | |
0 commit comments