Repository navigation
Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators #7065
Description
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 #6800 (comment) 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 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.
Activity
my-vegetable-has-exploded commentedon Nov 27, 2023
It seems like deque in cpp ？
But what does adaptive mean in
with adaptive sizing?thanks, @alamb
alamb commentedon Nov 28, 2023
I think @yjshen meant something like storing the values in
Vec<Vec<T>>rather thanVec<T>And when more space was needed, create a new
Vec::with_capacityrather than push to the existingVec(which might reallocate and copy)avantgardnerio commentedon Aug 1, 2024
We (Coralogix) may want to tackle this but combine with
ColumnStatistics::distinct_countto only allocate once.alamb commentedon Aug 1, 2024
Using statistics to improve the allocation performance certainly seems like a good idea -- though I am not sure the default distinct statistics are very reliable
Rachelint commentedon Aug 6, 2024
take
Rachelint commentedon Aug 6, 2024
Working on an poc for performance improvement which is related to this.
[-]Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators[/-][+][EPIC] Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators[/+]Rachelint commentedon Apr 5, 2025
Restart pushing this improvement forward in #15591.
Plan to impl a simple sketch for it firstly, and then file related issues to impl rests of it (support in many many
accmulatorsandgroup values...)alamb commentedon Apr 5, 2025
Welcome back @Rachelint -- I predict it is going to be a great few months in DataFusion for performance
BTW if you are interested in other low level things, I would love some help sorting out parquet filter pushdown (would involve figuring out how to evaluate predicates on string columns in two passes without slowing things down)
The eventual goal is
Enable parquet filter pushdown (
filter_pushdown) by default #3463more details on Parquet decoder / decoded predicate / page / results Cache arrow-rs#7363
Rachelint commentedon Apr 5, 2025
Thanks, it seems interesting!
Rachelint commentedon Apr 28, 2025
The formal sketch pr #15591 is ready for review now.
alamb commentedon Apr 28, 2025
I will try and find time for a review over the next few days
[-][EPIC] Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators[/-][+] Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators[/+]alamb commentedon Aug 12, 2025
I don't think this is an epic in the sense that it is a project being actively worked on, so updating title
avantgardnerio commentedon Aug 13, 2025
Have we considered using the
fallible_collectionscrate to avoid OOMs in general?alamb commentedon Aug 13, 2025
Not that I know of
alamb commentedon Aug 27, 2026
I have captured as much as I can about the overall issue in a new ticket that explains this issue better including the symptoms and what we have tried so far