Repository navigation
Commit 4fc07e2
committed
perf(functions-aggregate): coalesce small ordered ARRAY_AGG batches
- Closes [apache#25199](apache#25199)
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.
- Coalesce consecutive small ordered ARRAY_AGG payload batches up to 64 rows.
- Add tests covering:
- coalescing exactly up to the threshold;
- creating a new batch after the threshold is reached;
- entry indices across coalesced and newly created batches;
- ordering across multiple coalesced batches;
- coalescing payloads received through partial-state merge_batch().
- Add ordered ARRAY_AGG benchmarks covering:
- 1, 8, 64, and 2,048 rows per update_batch();
- random input;
- preordered input.
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 and for this change.
| Rows/update | Batches | Total retained (with this change) | Bytes/row (with this change) | Total retained (baseline [apache#24392](apache#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.
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 bench -p datafusion-functions-aggregate --bench array_agg --no-run
- cargo bench -p datafusion-functions-aggregate --bench array_agg --ordered_array_agg1 parent d477a2b commit 4fc07e2
2 files changed
Lines changed: 285 additions & 9 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
18 | 18 | | |
19 | 19 | | |
20 | 20 | | |
| 21 | + | |
21 | 22 | | |
22 | 23 | | |
23 | 24 | | |
24 | 25 | | |
25 | | - | |
| 26 | + | |
26 | 27 | | |
27 | | - | |
| 28 | + | |
| 29 | + | |
28 | 30 | | |
29 | | - | |
| 31 | + | |
30 | 32 | | |
| 33 | + | |
| 34 | + | |
31 | 35 | | |
32 | 36 | | |
33 | 37 | | |
34 | 38 | | |
35 | 39 | | |
36 | 40 | | |
| 41 | + | |
37 | 42 | | |
38 | 43 | | |
39 | 44 | | |
| |||
288 | 293 | | |
289 | 294 | | |
290 | 295 | | |
291 | | - | |
| 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 | + | |
292 | 452 | | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
1250 | 1250 | | |
1251 | 1251 | | |
1252 | 1252 | | |
| 1253 | + | |
| 1254 | + | |
| 1255 | + | |
| 1256 | + | |
1253 | 1257 | | |
1254 | 1258 | | |
1255 | 1259 | | |
| |||
1535 | 1539 | | |
1536 | 1540 | | |
1537 | 1541 | | |
1538 | | - | |
1539 | | - | |
1540 | | - | |
1541 | | - | |
1542 | | - | |
| 1542 | + | |
| 1543 | + | |
| 1544 | + | |
| 1545 | + | |
| 1546 | + | |
| 1547 | + | |
| 1548 | + | |
| 1549 | + | |
| 1550 | + | |
| 1551 | + | |
| 1552 | + | |
| 1553 | + | |
| 1554 | + | |
| 1555 | + | |
| 1556 | + | |
| 1557 | + | |
| 1558 | + | |
| 1559 | + | |
| 1560 | + | |
| 1561 | + | |
| 1562 | + | |
| 1563 | + | |
| 1564 | + | |
| 1565 | + | |
| 1566 | + | |
| 1567 | + | |
| 1568 | + | |
| 1569 | + | |
1543 | 1570 | | |
1544 | 1571 | | |
1545 | 1572 | | |
| |||
2517 | 2544 | | |
2518 | 2545 | | |
2519 | 2546 | | |
| 2547 | + | |
| 2548 | + | |
| 2549 | + | |
| 2550 | + | |
2520 | 2551 | | |
2521 | 2552 | | |
2522 | 2553 | | |
| |||
2912 | 2943 | | |
2913 | 2944 | | |
2914 | 2945 | | |
| 2946 | + | |
| 2947 | + | |
| 2948 | + | |
| 2949 | + | |
| 2950 | + | |
| 2951 | + | |
| 2952 | + | |
| 2953 | + | |
| 2954 | + | |
| 2955 | + | |
| 2956 | + | |
| 2957 | + | |
| 2958 | + | |
| 2959 | + | |
| 2960 | + | |
| 2961 | + | |
| 2962 | + | |
| 2963 | + | |
| 2964 | + | |
| 2965 | + | |
| 2966 | + | |
| 2967 | + | |
| 2968 | + | |
| 2969 | + | |
| 2970 | + | |
| 2971 | + | |
| 2972 | + | |
| 2973 | + | |
| 2974 | + | |
| 2975 | + | |
| 2976 | + | |
| 2977 | + | |
| 2978 | + | |
| 2979 | + | |
| 2980 | + | |
| 2981 | + | |
| 2982 | + | |
| 2983 | + | |
| 2984 | + | |
| 2985 | + | |
| 2986 | + | |
| 2987 | + | |
| 2988 | + | |
| 2989 | + | |
| 2990 | + | |
| 2991 | + | |
| 2992 | + | |
| 2993 | + | |
| 2994 | + | |
| 2995 | + | |
| 2996 | + | |
| 2997 | + | |
| 2998 | + | |
| 2999 | + | |
| 3000 | + | |
| 3001 | + | |
| 3002 | + | |
| 3003 | + | |
| 3004 | + | |
| 3005 | + | |
| 3006 | + | |
| 3007 | + | |
| 3008 | + | |
| 3009 | + | |
| 3010 | + | |
| 3011 | + | |
| 3012 | + | |
| 3013 | + | |
| 3014 | + | |
| 3015 | + | |
| 3016 | + | |
| 3017 | + | |
| 3018 | + | |
| 3019 | + | |
| 3020 | + | |
| 3021 | + | |
| 3022 | + | |
| 3023 | + | |
| 3024 | + | |
| 3025 | + | |
| 3026 | + | |
| 3027 | + | |
| 3028 | + | |
| 3029 | + | |
| 3030 | + | |
2915 | 3031 | | |
2916 | 3032 | | |
2917 | 3033 | | |
| |||
0 commit comments