Repository navigation
Commit 32dd1d2
authored
fix: size aggregate spill batches by bytes as well as rows (apache#25853)
## Which issue does this PR close?
- Closes apache#25851.
## Rationale for this change
A grouped aggregate whose groups carry large state, such as `array_agg`
over a low-cardinality key, fails with `ResourcesExhausted` after it
spills, even though each group fits in memory and the same data spread
over many small groups succeeds.
Spilling writes the aggregate state in batches of at most `batch_size`
rows, whatever their size in bytes. With fewer groups than `batch_size`,
every group lands in one batch, and everything after the spill has to
hold that batch at once:
- With a single spill file, replay reads the batch directly and its
table must hold every group at once. In the reproducer from the issue,
that is 225 MB of state in a 128 MB pool, although each group is about
28 MB.
- With several spill files, the merge reserves twice the largest batch
of each file. When that does not fit, it tries to split the file, which
first reserves twice the batch it is about to split. Even with small
spilled batches, the merge combines rows until it has `batch_size` of
them, rebuilding a batch of large groups.
## What changes are included in this PR?
Aggregate spilling and replay now bound their batches by bytes as well
as rows, with a target of 1 MiB (`SPILL_BATCH_TARGET_BYTES`):
- `IncrementalSortIterator::with_max_batch_bytes` cuts the sorted state
into chunks by the size each row takes once spilled, so a batch only
exceeds the target when it holds a single larger group. Row sizes come
from the new `SpilledRowSizes`, which counts view values as they are
written after compaction and nested values by their elements.
- `StreamingMergeBuilder::with_max_batch_bytes` makes the merge emit a
batch once its rows reach the target, estimated from the average row
size of the batches they come from, as well as at `batch_size` rows. It
applies to every pass of the multi-level merge, so rows of small groups
still merge in batches of `batch_size` rows.
- Dictionaries whose values are mostly unique (fewer than two keys per
value) count the values their keys reference, and each chunk holds only
those values, since `take` keeps every value of a dictionary.
Dictionaries whose values many keys share count only their keys and stay
shared, as on `main`, so that each chunk does not write its own copy of
them.
- Replay compacts the views and dictionaries of the nested columns of
merged batches (`gc_nested_arrays`). A merged batch references the
buffers of every batch its rows come from, and `array_agg` keeps the
lists it merges until its group completes.
Both new options are crate-private and only used by aggregate spilling
and replay; other merges are unchanged. The intermediate merge sizing
from apache#25428 now receives the largest row count of the batches each run
actually wrote. This applies to every stream built on `AggregateSpill`
(hash and ordered, final and single-stage). The legacy
`GroupedHashAggregateStream`, used only when
`datafusion.execution.enable_migration_aggregate` is `false`, is
unchanged.
## What is the testing strategy for this PR?
- New Case I in `aggregate_memory_spill.slt`, with a 24 MB limit, where
`EXPLAIN ANALYZE` assertions check that each query spilled. All of these
fail on `main` with `ResourcesExhausted`:
- `array_agg` over 32 groups of about 2 MB each, with two partitions
(one spill file per partition) and with one partition (several spill
files, merged).
- 14 large groups, adjacent in key order, spilled together with 62,500
small groups.
- Runs of large groups followed by a run of small groups.
- `array_agg` over dictionary-encoded values, with two partitions and
with one.
- `string_agg` with one partition.
- `array_agg` over dictionary values that each repeat within one group,
at 8 MB.
- Unit tests for `SpilledRowSizes` (including views that share bytes,
nested views, fixed-width rows, and dictionaries of unique, shared and
no values), for byte-limited chunks in `IncrementalSortIterator` and
their dictionaries, for byte-limited merges of spill files, and for
dictionary compaction.
With `datafusion-cli -m 128M`, the reproducer from the issue now returns
16 groups and 3,000,000 values, and so does the variant from the issue's
additional context. The reproducer with 3,000 one-value groups added,
`array_agg` over dictionary-encoded Parquet strings, and the reproducer
with its values cast to `Dictionary(Int32, Utf8)`, which fail on `main`,
also succeed.
Performance compared with `main`:
- `external_aggr` (TPC-H SF1, integer keys): no case is slower; 7 are
unchanged and 1 is 1.06x faster.
- A spilling `GROUP BY` over 5M string keys at 256 MB is unchanged (0.61
s against 0.62 s).
- 8M small groups plus 200 large `array_agg` groups take 0.80 s at 128
MB, against 2.99 s on `main`. There `main` spills 26M rows (1 GB) while
merging its runs, and this PR spills each of the 8M rows once. At 512
MB, where both spill twice, this PR takes 1.00 s against 0.96 s, from
measuring the rows of the spilled batch that holds the large groups.
- `sort_preserving_merge` shows no change beyond run-to-run noise.
Merges without a byte limit only check that none is set.
- `array_agg` over a dictionary of 100 distinct values (2M rows, 100K
groups, 24 MB) spills the same 10.5 MB (20-byte values) and 14.7 MB
(200-byte values) as `main`, in the same time.
## Are there any user-facing changes?
Aggregations whose groups have large state can now complete under memory
limits where they previously failed after spilling. No API or
configuration changes.1 parent 52a8cd9 commit 32dd1d2
10 files changed
Lines changed: 1336 additions & 35 deletions
File tree
- datafusion
- physical-plan/src
- aggregates
- sorts
- spill
- sqllogictest/test_files
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
40 | 40 | | |
41 | 41 | | |
42 | 42 | | |
43 | | - | |
44 | | - | |
| 43 | + | |
| 44 | + | |
45 | 45 | | |
46 | 46 | | |
47 | 47 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
14 | 14 | | |
15 | 15 | | |
16 | 16 | | |
| 17 | + | |
17 | 18 | | |
18 | 19 | | |
19 | 20 | | |
| |||
23 | 24 | | |
24 | 25 | | |
25 | 26 | | |
| 27 | + | |
26 | 28 | | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
| 37 | + | |
| 38 | + | |
| 39 | + | |
27 | 40 | | |
28 | 41 | | |
29 | 42 | | |
| |||
210 | 223 | | |
211 | 224 | | |
212 | 225 | | |
213 | | - | |
| 226 | + | |
214 | 227 | | |
215 | 228 | | |
216 | 229 | | |
217 | 230 | | |
218 | | - | |
| 231 | + | |
| 232 | + | |
| 233 | + | |
| 234 | + | |
| 235 | + | |
| 236 | + | |
| 237 | + | |
219 | 238 | | |
220 | 239 | | |
221 | 240 | | |
| |||
289 | 308 | | |
290 | 309 | | |
291 | 310 | | |
| 311 | + | |
292 | 312 | | |
293 | 313 | | |
294 | 314 | | |
295 | 315 | | |
| 316 | + | |
| 317 | + | |
| 318 | + | |
| 319 | + | |
| 320 | + | |
| 321 | + | |
| 322 | + | |
| 323 | + | |
| 324 | + | |
296 | 325 | | |
297 | 326 | | |
298 | 327 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
85 | 85 | | |
86 | 86 | | |
87 | 87 | | |
88 | | - | |
89 | | - | |
| 88 | + | |
| 89 | + | |
90 | 90 | | |
91 | 91 | | |
92 | 92 | | |
| |||
99 | 99 | | |
100 | 100 | | |
101 | 101 | | |
102 | | - | |
| 102 | + | |
103 | 103 | | |
104 | 104 | | |
105 | 105 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
73 | 73 | | |
74 | 74 | | |
75 | 75 | | |
| 76 | + | |
| 77 | + | |
| 78 | + | |
| 79 | + | |
| 80 | + | |
| 81 | + | |
| 82 | + | |
| 83 | + | |
| 84 | + | |
| 85 | + | |
76 | 86 | | |
77 | 87 | | |
78 | 88 | | |
| |||
133 | 143 | | |
134 | 144 | | |
135 | 145 | | |
| 146 | + | |
| 147 | + | |
| 148 | + | |
136 | 149 | | |
137 | 150 | | |
138 | 151 | | |
139 | 152 | | |
140 | 153 | | |
| 154 | + | |
| 155 | + | |
| 156 | + | |
| 157 | + | |
| 158 | + | |
| 159 | + | |
| 160 | + | |
| 161 | + | |
141 | 162 | | |
142 | 163 | | |
143 | 164 | | |
| |||
171 | 192 | | |
172 | 193 | | |
173 | 194 | | |
174 | | - | |
| 195 | + | |
| 196 | + | |
| 197 | + | |
| 198 | + | |
| 199 | + | |
| 200 | + | |
| 201 | + | |
175 | 202 | | |
176 | 203 | | |
177 | 204 | | |
178 | 205 | | |
179 | 206 | | |
180 | 207 | | |
181 | 208 | | |
182 | | - | |
| 209 | + | |
| 210 | + | |
| 211 | + | |
| 212 | + | |
183 | 213 | | |
184 | 214 | | |
185 | 215 | | |
| |||
237 | 267 | | |
238 | 268 | | |
239 | 269 | | |
| 270 | + | |
| 271 | + | |
| 272 | + | |
240 | 273 | | |
241 | 274 | | |
242 | 275 | | |
243 | 276 | | |
244 | 277 | | |
245 | 278 | | |
246 | 279 | | |
247 | | - | |
| 280 | + | |
| 281 | + | |
| 282 | + | |
| 283 | + | |
| 284 | + | |
248 | 285 | | |
249 | 286 | | |
250 | 287 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
141 | 141 | | |
142 | 142 | | |
143 | 143 | | |
| 144 | + | |
| 145 | + | |
144 | 146 | | |
145 | 147 | | |
146 | 148 | | |
| |||
185 | 187 | | |
186 | 188 | | |
187 | 189 | | |
| 190 | + | |
188 | 191 | | |
189 | 192 | | |
190 | 193 | | |
| |||
199 | 202 | | |
200 | 203 | | |
201 | 204 | | |
| 205 | + | |
| 206 | + | |
| 207 | + | |
| 208 | + | |
| 209 | + | |
| 210 | + | |
| 211 | + | |
202 | 212 | | |
203 | 213 | | |
204 | 214 | | |
| |||
529 | 539 | | |
530 | 540 | | |
531 | 541 | | |
532 | | - | |
| 542 | + | |
| 543 | + | |
533 | 544 | | |
534 | 545 | | |
535 | 546 | | |
| |||
0 commit comments