Repository navigation
Commit 431355f
authored
perf(functions-aggregate): coalesce small ordered ARRAY_AGG batches (apache#25497)
## Which issue does this PR close?
- Closes apache#25199
## Rationale for this change
apache#24392 changed OrderSensitiveArrayAggAccumulator to retain payloads as
Arrow arrays instead of converting each value to a ScalarValue. This
significantly reduced memory usage for reasonably sized input batches.
However, the accumulator currently stores one ArrayRef per
update_batch() call. Each array has a fixed cost from its ArrayData,
buffer allocation, and Arc, regardless of how many rows it contains.
Ordered `ARRAY_AGG` does not support a native `GroupsAccumulator`
because `groups_accumulator_supported` requires `order_bys` to be empty.
Grouped execution therefore falls back to `GroupsAccumulatorAdapter`,
which calls `update_batch()` once per group per input batch.
With a high-cardinality `GROUP BY`, these calls often contain only one
or two rows. Without this change, each call retains a separate
`ArrayRef`, so the accumulator pays the fixed per-array allocation cost
for many small Arrow arrays, increasing the per-row memory footprint.
## What changes are included in this PR?
- Coalesce consecutive small ordered `ARRAY_AGG` payload batches when
the combined batch has at most 64 rows and the combined payload buffers
use at most 4 KiB.
- Add tests for the row threshold, batch and entry indices, ordering
across coalesced batches, and coalescing during
partial-state `merge_batch()`.
- Add `Dictionary<Int8, Utf8>` and `Utf8View` tests that coalesce beyond
64 input rows and verify the evaluated order.
- Add a `Utf8` test confirming that large payloads remain in separate
batches.
- Add ordered `ARRAY_AGG` benchmarks for random and preordered input
with 1, 8, 64, and 2,048 rows per
`update_batch()`.
- Add an update-only benchmark with 4 KiB `Utf8` values and one row per
call, using a generalized benchmark fixture that supports `Utf8`
payloads.
### Retained memory
Retained memory was measured using `Accumulator::size()` after inserting
2,048 Int64 payloads with an Int64 ordering key and before calling
evaluate(). The same measurement code was used for the baseline after
[apache#24392](apache#24392) and for this
change.
| Rows/update | Batches | Total retained (with this change) | Bytes/row
(with this change) | Total retained (baseline
[apache#24392](https://github.com/apache/datafusion/pull/24392)| Bytes/row
(baseline [apache#24392](apache#24392)) |
| ----------: | ------: | --------------------------------: |
---------------------------: |
-----------------------------------------------------------------------------------
|
------------------------------------------------------------------------------
|
| 1 | 32 | 104,701 B | 51.12 B/row | 445,181 B | 217.37 B/row |
| 8 | 32 | 90,365 B | 44.12 B/row | 115,453 B | 56.37 B/row |
| 64 | 32 | 88,573 B | 43.25 B/row | 88,573 B | 43.25 B/row |
| 2048 | 1 | 84,901 B | 41.46 B/row | 84,901 B | 41.46 B/row |
The worst-case one-row update footprint decreases from 217.37 B/row to
51.12 B/row. Inputs already at or above the 64-row coalescing threshold
retain the existing memory footprint.
### Benchmark
The `ordered_array_agg` Criterion benchmarks had been tested with
following comment for this pr and `main`:
```bash
cargo bench -p datafusion-functions-aggregate --bench array_agg -- ordered_array_agg`
```
Each Int64 case processes 2,048 rows, using 1, 8, 64, or 2,048 rows per
`update_batch()` call. The inputs are either preordered or shuffled with
a fixed seed. Timing includes creating the accumulator, calling
`update_batch()`, and calling `evaluate()`.
The wide-payload case processes 2,048 Utf8 values of 4 KiB each, one row
per `update_batch()` call. It does not include `evaluate()`.
| Benchmark case | main (µs) | PR (µs) |
| :--- | ---: | ---: |
| i64 ordered,1 row/update | 1,527.20 | 779.37 (-48.97%) |
| i64 random,1 row/update | 2,207.60 | 1,052.50 (-52.32%) |
| i64 ordered,8 rows/update | 221.42 | 133.85 (-39.55%) |
| i64 random,8 rows/update | 454.68 | 363.10 (-20.14%) |
| i64 ordered,64 rows/update | 50.37 | 50.44 (+0.14%) |
| i64 random,64 rows/update | 258.03 | 262.51 (+1.74%) |
| i64 ordered,2,048 rows/update | 18.68 | 19.00 (+1.71%) |
| i64 random,2,048 rows/update | 228.52 | 236.29 (+3.40%) |
| Utf8 4 KiB,1 row/update(update_batches only) | 2,417.90 | 2,642.90
(+9.31%) |
## Are these changes tested?
Added unit tests covering:
- coalescing small batches exactly up to the threshold;
- creating a new batch when the threshold would be exceeded;
- preserving the correct batch_idx and row_idx for entries;
- sorting values across multiple coalesced batches;
- coalescing small partial-state payloads passed through merge_batch().
Added Criterion benchmarks for ordered ARRAY_AGG using random and
preordered input with 1, 8, 64, and 2,048 rows per update_batch().
The following commands have been executed and passed:
- `cargo test -p datafusion-functions-aggregate --lib array_agg::tests`
- ` cargo clippy -p datafusion-functions-aggregate --all-targets
--all-features -- -D warnings`
- `cargo bench -p datafusion-functions-aggregate --bench array_agg
--no-run`
- `cargo bench -p datafusion-functions-aggregate --bench array_agg --
ordered_array_agg`
- `cargo test --profile=ci --test sqllogictests`
- `cargo test -p datafusion`
- `cargo test -p datafusion-cli`
## Are there any user-facing changes?
No1 parent b73054a commit 431355f
2 files changed
Lines changed: 598 additions & 16 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
19 | 19 | | |
20 | 20 | | |
21 | 21 | | |
22 | | - | |
23 | | - | |
| 22 | + | |
| 23 | + | |
24 | 24 | | |
25 | | - | |
26 | | - | |
27 | | - | |
| 25 | + | |
| 26 | + | |
| 27 | + | |
| 28 | + | |
28 | 29 | | |
29 | | - | |
| 30 | + | |
30 | 31 | | |
| 32 | + | |
| 33 | + | |
31 | 34 | | |
32 | 35 | | |
33 | 36 | | |
34 | 37 | | |
35 | 38 | | |
36 | 39 | | |
| 40 | + | |
37 | 41 | | |
38 | 42 | | |
39 | 43 | | |
| |||
288 | 292 | | |
289 | 293 | | |
290 | 294 | | |
291 | | - | |
| 295 | + | |
| 296 | + | |
| 297 | + | |
| 298 | + | |
| 299 | + | |
| 300 | + | |
| 301 | + | |
| 302 | + | |
| 303 | + | |
| 304 | + | |
| 305 | + | |
| 306 | + | |
| 307 | + | |
| 308 | + | |
| 309 | + | |
| 310 | + | |
| 311 | + | |
| 312 | + | |
| 313 | + | |
| 314 | + | |
| 315 | + | |
| 316 | + | |
| 317 | + | |
| 318 | + | |
| 319 | + | |
| 320 | + | |
| 321 | + | |
| 322 | + | |
| 323 | + | |
| 324 | + | |
| 325 | + | |
| 326 | + | |
| 327 | + | |
| 328 | + | |
| 329 | + | |
| 330 | + | |
| 331 | + | |
| 332 | + | |
| 333 | + | |
| 334 | + | |
| 335 | + | |
| 336 | + | |
| 337 | + | |
| 338 | + | |
| 339 | + | |
| 340 | + | |
| 341 | + | |
| 342 | + | |
| 343 | + | |
| 344 | + | |
| 345 | + | |
| 346 | + | |
| 347 | + | |
| 348 | + | |
| 349 | + | |
| 350 | + | |
| 351 | + | |
| 352 | + | |
| 353 | + | |
| 354 | + | |
| 355 | + | |
| 356 | + | |
| 357 | + | |
| 358 | + | |
| 359 | + | |
| 360 | + | |
| 361 | + | |
| 362 | + | |
| 363 | + | |
| 364 | + | |
| 365 | + | |
| 366 | + | |
| 367 | + | |
| 368 | + | |
| 369 | + | |
| 370 | + | |
| 371 | + | |
| 372 | + | |
| 373 | + | |
| 374 | + | |
| 375 | + | |
| 376 | + | |
| 377 | + | |
| 378 | + | |
| 379 | + | |
| 380 | + | |
| 381 | + | |
| 382 | + | |
| 383 | + | |
| 384 | + | |
| 385 | + | |
| 386 | + | |
| 387 | + | |
| 388 | + | |
| 389 | + | |
| 390 | + | |
| 391 | + | |
| 392 | + | |
| 393 | + | |
| 394 | + | |
| 395 | + | |
| 396 | + | |
| 397 | + | |
| 398 | + | |
| 399 | + | |
| 400 | + | |
| 401 | + | |
| 402 | + | |
| 403 | + | |
| 404 | + | |
| 405 | + | |
| 406 | + | |
| 407 | + | |
| 408 | + | |
| 409 | + | |
| 410 | + | |
| 411 | + | |
| 412 | + | |
| 413 | + | |
| 414 | + | |
| 415 | + | |
| 416 | + | |
| 417 | + | |
| 418 | + | |
| 419 | + | |
| 420 | + | |
| 421 | + | |
| 422 | + | |
| 423 | + | |
| 424 | + | |
| 425 | + | |
| 426 | + | |
| 427 | + | |
| 428 | + | |
| 429 | + | |
| 430 | + | |
| 431 | + | |
| 432 | + | |
| 433 | + | |
| 434 | + | |
| 435 | + | |
| 436 | + | |
| 437 | + | |
| 438 | + | |
| 439 | + | |
| 440 | + | |
| 441 | + | |
| 442 | + | |
| 443 | + | |
| 444 | + | |
| 445 | + | |
| 446 | + | |
| 447 | + | |
| 448 | + | |
| 449 | + | |
| 450 | + | |
| 451 | + | |
| 452 | + | |
| 453 | + | |
| 454 | + | |
| 455 | + | |
| 456 | + | |
| 457 | + | |
| 458 | + | |
| 459 | + | |
| 460 | + | |
| 461 | + | |
| 462 | + | |
| 463 | + | |
| 464 | + | |
| 465 | + | |
| 466 | + | |
| 467 | + | |
| 468 | + | |
| 469 | + | |
| 470 | + | |
| 471 | + | |
| 472 | + | |
| 473 | + | |
| 474 | + | |
| 475 | + | |
| 476 | + | |
| 477 | + | |
| 478 | + | |
| 479 | + | |
| 480 | + | |
| 481 | + | |
| 482 | + | |
| 483 | + | |
| 484 | + | |
| 485 | + | |
| 486 | + | |
| 487 | + | |
| 488 | + | |
| 489 | + | |
| 490 | + | |
| 491 | + | |
| 492 | + | |
| 493 | + | |
| 494 | + | |
| 495 | + | |
| 496 | + | |
| 497 | + | |
| 498 | + | |
| 499 | + | |
| 500 | + | |
| 501 | + | |
| 502 | + | |
| 503 | + | |
| 504 | + | |
| 505 | + | |
| 506 | + | |
| 507 | + | |
| 508 | + | |
| 509 | + | |
| 510 | + | |
| 511 | + | |
| 512 | + | |
| 513 | + | |
| 514 | + | |
| 515 | + | |
| 516 | + | |
| 517 | + | |
| 518 | + | |
| 519 | + | |
292 | 520 | | |
0 commit comments