alamb opened a new issue, #7065: URL: https://github.com/apache/datafusion/issues/7065
UPDATE: Now that @Rachelint has begun work on #11931 I turned this ticket into an "epic" (aka I'll link related tasks here) ### Is your feature request related to a problem or challenge? Making aggregations fast in datafusion helps its adoption and makes it even cooler As part of the new #6904 work, @yjshen had an idea https://github.com/apache/arrow-datafusion/pull/6800#discussion_r1251142165 that could avoid a copy in the accumulator implementations: ### Describe the solution you'd like ```Adaptive sizing(perhaps?): How would the hash table header and states in each accumulator initialize and grow their sizes afterward?``` Here is the structure of the current group operator ``` ┌──────────────┐ ┌──────────────┐ ┌──────────────┐ │┌────────────┐│ │┌────────────┐│ │┌────────────┐│ ┌─────┐ ││accumulator ││ ││accumulator ││ ││accumulator ││ │ 5 │ ││ 0 ││ ││ 0 ││ ││ 0 ││ ├─────┤ ││ ┌────────┐ ││ ││ ┌────────┐ ││ ││ ┌────────┐ ││ │ 9 │ ││ │ state │ ││ ││ │ state │ ││ ││ │ state │ ││ ├─────┤ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ │ │ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ ├─────┤ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ │ 1 │ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ ├─────┤ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ │ │ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ └─────┘ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ ││ └────────┘ ││ ││ └────────┘ ││ ││ └────────┘ ││ │└────────────┘│ │└────────────┘│ │└────────────┘│ Hash Table └──────────────┘ └──────────────┘ └──────────────┘ New NewAccumulator stores "group indexes" There is one GroupsAccumulator per aggregate which are indexes into (NOT PER GROUP). Internally, each Vec<GroupState> GroupsAccumulator manages the state for multiple groups ``` The implementation of this, such as [Average](https://github.com/apache/arrow-datafusion/blob/b135a96a9647d0b7df6099bbd222e5280e75d0a8/datafusion/physical-expr/src/aggregate/average.rs#L322-L326) is to use a `Vec<T>`. While this approach is simple to implement, it also means that as the Vec grows, the accumulated vales may be copied (up to 2 times on average, given a doubling strategy) An alternate, suggested by @yjshen is to segment the state into **fixed-sized vectors, allocate a new vector at a time**, fill it until full, then create a new vector for upcoming new states. ``` ┌──────────────┐ ┌──────────────┐ ┌──────────────┐ │┌────────────┐│ │┌────────────┐│ │┌────────────┐│ ┌─────┐ ││accumulator ││ ││accumulator ││ ││accumulator ││ │ 5 │ ││ AGG ││ ││ SUM ││ ││ 0 ││ ├─────┤ ││ ┌────────┐ ││ ││ ┌────────┐ ││ ││ ┌────────┐ ││ │ 9 │ ││ │ state- │ ││ ││ │ state- │ ││ ││ │ state │ ││ ├─────┤ ││ │segment-│ ││ ││ │segment-│ ││ ││ │ │ ││ │ │ ││ │ 1 │ ││ ││ │ 1 │ ││ ││ │ │ ││ ├─────┤ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ │ 1 │ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ ├─────┤ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ │ │ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ └─────┘ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ ││ └────────┘ ││ ││ └────────┘ ││ ││ └────────┘ ││ ││ ││ ││ ││ │└────────────┘│ Hash Table ││ ┌────────┐ ││ ││ ┌────────┐ ││ └──────────────┘ ││ │ state- │ ││ ││ │ state- │ ││ ││ │segment-│ ││ ││ │segment-│ ││ ││ │ 2 │ ││ ││ │ 2 │ ││ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ ││ │ │ ││ ││ └────────┘ ││ ││ └────────┘ ││ │└────────────┘│ │└────────────┘│ └──────────────┘ └──────────────┘ ``` Thru this segmented approach, we could avoid memory copy for each resize, which the number of resizing would be great for high cardinality aggs, and grows the size more predictably. But admittedly, this approach would also bring complexity for both header pointer management and update span multiple vectors. ### Implementation Steps: - [ ] https://github.com/apache/datafusion/issues/11931 (base implementation) - [x] https://github.com/apache/datafusion/issues/12114 -- 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]
