Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators

@Rachelint

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.

Implementation Steps:

Manage group values and states by blocks in aggregation #11931 (base implementation)
Aggregation fuzz testing #12114

@alamb

It seems like deque in cpp ？

But what does adaptive mean in with adaptive sizing?
thanks, @alamb

@yjshen

But what does adaptive mean in with adaptive sizing?

I think @yjshen meant something like storing the values in Vec<Vec<T>> rather than Vec<T>

And when more space was needed, create a new Vec::with_capacity rather than push to the existing Vec (which might reallocate and copy)

We (Coralogix) may want to tackle this but combine with ColumnStatistics::distinct_count to only allocate once.

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

take

Working on an poc for performance improvement which is related to this.

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 accmulators and group values...)

@Rachelint

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

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 by default #3463](https://github.com/apache/datafusion/issues/3463)

* more details on [Parquet decoder / decoded page Cache arrow-rs#7363](https://github.com/apache/arrow-rs/issues/7363)

Thanks, it seems interesting!

The formal sketch pr #15591 is ready for review now.

I will try and find time for a review over the next few days

I don't think this is an epic in the sense that it is a project being actively worked on, so updating title

Have we considered using the fallible_collections crate to avoid OOMs in general?

Have we considered using the fallible_collections crate to avoid OOMs in general?

Not that I know of

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

[EPIC] Use blocked / chunked memory management in hash aggregation #24704

Navigation Menu

Repository navigation

Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators #7065

Is your feature request related to a problem or challenge?

Describe the solution you'd like

Implementation Steps:

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators #7065

Description

Is your feature request related to a problem or challenge?

Describe the solution you'd like

Implementation Steps:

Activity

my-vegetable-has-exploded commented on Nov 27, 2023

alamb commented on Nov 28, 2023

avantgardnerio commented on Aug 1, 2024

alamb commented on Aug 1, 2024

Rachelint commented on Aug 6, 2024

Rachelint commented on Aug 6, 2024

Rachelint commented on Apr 5, 2025

alamb commented on Apr 5, 2025

Rachelint commented on Apr 5, 2025

Rachelint commented on Apr 28, 2025

alamb commented on Apr 28, 2025

alamb commented on Aug 12, 2025

avantgardnerio commented on Aug 13, 2025

alamb commented on Aug 13, 2025

alamb commented on Aug 27, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions