adriangb opened a new issue, #25116: URL: https://github.com/apache/datafusion/issues/25116
### Is your feature request related to a problem or challenge? `GroupsAccumulatorAdapter` (in `datafusion/functions-aggregate-common/src/aggregate/groups_accumulator.rs`) runs any aggregate that has no native `GroupsAccumulator`, for example `covar_samp`. It routes each input batch to the per-group `Accumulator`s through one scratch `Vec<u32>` of row indices per group: 1. the push loop appends each row's index to its group's scratch vector, 2. the offsets loop walks **every** group, skips the empty ones, and concatenates the rest into `batch_indices`, 3. the values are `take`n once by `batch_indices` and sliced per group, 4. every scratch vector is `clear()`ed, retaining its capacity. This came up in review of https://github.com/apache/datafusion/pull/24858, which fixes the memory accounting for the retained capacity in step 4. @2010YOUY01 noted there that the design only pays off at low cardinality. Reading the loop, I think the memory side is secondary and the CPU side is the real problem. **Memory.** The retained capacity per group is the largest number of rows that group ever received from a single batch. At high cardinality that is one or two rows, so each vector sits at its minimum allocation: a 24-byte header plus a 16-byte heap block, next to a boxed accumulator that is usually larger. Roughly a third of the per-group overhead, not a multiplier. **CPU.** Step 2 costs one iteration per *existing* group on *every* batch, independent of how many groups the batch touches. Per input row: | groups | rows per batch | offsets-loop iterations per input row | | --- | --- | --- | | 128 | 8192 | 0.02 | | 100,000 | 8192 | 12 | | 1,000,000 | 8192 | 122 | At a million groups the adapter spends two orders of magnitude more work scanning idle groups than it spends routing the rows themselves. This is from reading the loop, not from a measurement; `datafusion/functions-aggregate/benches/approx_distinct.rs` already drives the adapter and would confirm it with a high-cardinality case. ### Describe the solution you'd like Make the per-batch work and the scratch memory proportional to the batch, not to the number of groups. One design should handle both ends of the cardinality range, rather than switching between two implementations on a threshold. **Minimal version.** Record the groups touched while pushing, and iterate only those when building `batch_indices` and offsets. The order in which groups are visited does not affect correctness (each group's accumulator only sees its own rows). This removes the O(groups) scan and keeps the current memory profile. The accounting from https://github.com/apache/datafusion/pull/24858 would move into the push loop, where capacity growth is visible per push. **Full version.** Drop the per-group scratch vectors entirely. Sort the batch's `(group_index, row_index)` pairs, or bucket them through a map of touched groups, and emit `batch_indices` and offsets directly from the result. Scratch memory becomes O(batch size) with nothing retained per group, which would supersede the accounting mechanism in https://github.com/apache/datafusion/pull/24858 rather than extend it. The cost is a sort of a few thousand keys per batch, which should be small next to the per-group dynamic dispatch and array slicing that already dominate the adapter. ### Describe alternatives you've considered - Switching to a different adapter implementation above a group-count threshold, either from statistics at planning time or dynamically at runtime. This adds a second code path and a tuning knob for a problem that a batch-proportional design solves at both ends. - Leaving the adapter as is and giving more aggregates a native `GroupsAccumulator`. Worth doing on its own, but the adapter remains the fallback for user-defined aggregates and will keep hitting this cliff. ### Additional context https://github.com/apache/datafusion/pull/24858 is a correct interim fix for the accounting and is not blocked on this redesign. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
