You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "alamb (via GitHub)" <gi...@apache.org> on 2023/07/24 10:48:48 UTC
[GitHub] [arrow-datafusion] alamb opened a new issue, #7065: Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators
alamb opened a new issue, #7065:
URL: https://github.com/apache/arrow-datafusion/issues/7065
### 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 (TODO link) 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.
### Describe alternatives you've considered
_No response_
### Additional context
_No response_
--
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: github-unsubscribe@arrow.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] [EPIC] Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators [datafusion]
Posted by "Rachelint (via GitHub)" <gi...@apache.org>.
Rachelint commented on issue #7065:
URL: https://github.com/apache/datafusion/issues/7065#issuecomment-2835855497
The formal sketch pr #15591 is ready for review now.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb closed issue #7065: Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators
URL: https://github.com/apache/datafusion/issues/7065
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators [datafusion]
Posted by "Rachelint (via GitHub)" <gi...@apache.org>.
Rachelint commented on issue #7065:
URL: https://github.com/apache/datafusion/issues/7065#issuecomment-2271693196
take
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #7065:
URL: https://github.com/apache/datafusion/issues/7065#issuecomment-5432613501
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
- https://github.com/apache/datafusion/issues/24704
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators [arrow-datafusion]
Posted by "my-vegetable-has-exploded (via GitHub)" <gi...@apache.org>.
my-vegetable-has-exploded commented on issue #7065:
URL: https://github.com/apache/arrow-datafusion/issues/7065#issuecomment-1827953667
It seems like deque in cpp ？
But what does adaptive mean in ```with adaptive sizing```?
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #7065:
URL: https://github.com/apache/arrow-datafusion/issues/7065#issuecomment-1830067924
> 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)
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] [EPIC] Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #7065:
URL: https://github.com/apache/datafusion/issues/7065#issuecomment-2780656655
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)
- more details on https://github.com/apache/arrow-rs/issues/7363
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #7065:
URL: https://github.com/apache/datafusion/issues/7065#issuecomment-3183787623
> Have we considered using the `fallible_collections` crate to avoid OOMs in general?
Not that I know of
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] [EPIC] Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators [datafusion]
Posted by "Rachelint (via GitHub)" <gi...@apache.org>.
Rachelint commented on issue #7065:
URL: https://github.com/apache/datafusion/issues/7065#issuecomment-2780814988
> Welcome back [@Rachelint](https://github.com/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!
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb closed issue #7065: Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators
URL: https://github.com/apache/datafusion/issues/7065
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators [datafusion]
Posted by "Rachelint (via GitHub)" <gi...@apache.org>.
Rachelint commented on issue #7065:
URL: https://github.com/apache/datafusion/issues/7065#issuecomment-2271691810
take
Working on an poc, which is related to this.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators [datafusion]
Posted by "Rachelint (via GitHub)" <gi...@apache.org>.
Rachelint commented on issue #7065:
URL: https://github.com/apache/datafusion/issues/7065#issuecomment-2271695044
Working on an poc for performance improvemetn which is related to this.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] [EPIC] Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #7065:
URL: https://github.com/apache/datafusion/issues/7065#issuecomment-2835913384
I will try and find time for a review over the next few days
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #7065:
URL: https://github.com/apache/datafusion/issues/7065#issuecomment-3180753896
I don't think this is an epic in the sense that it is a project being actively worked on, so updating title
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators [datafusion]
Posted by "avantgardnerio (via GitHub)" <gi...@apache.org>.
avantgardnerio commented on issue #7065:
URL: https://github.com/apache/datafusion/issues/7065#issuecomment-3182347912
Have we considered using the `fallible_collections` crate to avoid OOMs in general?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators [datafusion]
Posted by "avantgardnerio (via GitHub)" <gi...@apache.org>.
avantgardnerio commented on issue #7065:
URL: https://github.com/apache/datafusion/issues/7065#issuecomment-2263878251
We (Coralogix) may want to tackle this but combine with `ColumnStatistics::distinct_count` to only allocate once.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #7065:
URL: https://github.com/apache/datafusion/issues/7065#issuecomment-2263882420
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
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] [EPIC] Improve aggregate performance with adaptive sizing in accumulators / avoiding reallocations in accumulators [datafusion]
Posted by "Rachelint (via GitHub)" <gi...@apache.org>.
Rachelint commented on issue #7065:
URL: https://github.com/apache/datafusion/issues/7065#issuecomment-2780541825
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`...)
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org