datafusion: Implement fast min/max accumulator for binary / strings (now it uses the slower path)
Is your feature request related to a problem or challenge?
https://github.com/apache/arrow-datafusion/pull/6904 introduces some fancy new hashing and ways to implement aggregates
See related blog post: https://datafusion.apache.org/blog/2023/08/05/datafusion_fast_grouping/
min/max for strings (StringArray / LargeStringArray, etc) now uses the slower Accumulator implementation which could be made much faster
Describe the solution youβd like
I would like to implement a fast GroupsAccumulator for Min/Max
Describe alternatives youβve considered
here is one potential way to implement it:
We could store the current minimum for all groups in the same Rows π€ and track an index into that Rows for the current minimum for each group.
This would require an extra copy of the input values, but it could probably be vectorized pretty well, as shown in the following diagram.
Sorry what I meant was something like the following where the accumulator only stored the current minimum values.
This approach would potentially end up with min_storage being full of βgarbageβ if many batches had new minumums, but I think we could heuristically βcompactβ min_storage (if it had 2*num_groups, for example) if it got too large
β β β β β β β β β β β β β β β β β β β
β Accumulator β
state
βββββββββββ βββββββββββ β βββββββββββ βββββββββββ β
β βββββββ β β βββββββ β β βββββββ β β βββββββ β
β β A β β β β A βββΌβββββ β β β D β β βββββββΌββ 1 β β β
β βββββββ€ β β βββββββ€ β β β βββββββ€ β β β βββββββ€ β
β β B β β β β B β β ββββΌββΌβΆβ A βββΌβββββ β β 0 β β β
β βββββββ€ β β βββββββ€ β β βββββββ β β βββββββ β
β β A β β β β A β β β β β β β β
β βββββββ€ β β βββββββ€ β β β β β
β β A β β β β A β β β β β β β β
β βββββββ€ β β βββββββ€ β β β β β
β β C β β β β C β β β β β β β β
β βββββββ β β βββββββ β β β β β
βββββββββββ βββββββββββ β βββββββββββ βββββββββββ β
input input β min_storage: min_values β
values values Rows
(Array) (Rows) β β β β β β β β β β β β β β β β β β β
step 1: step 2: for
convert any value step 3: min value
arguments to that is a new (per group) is
Row format group tracked as an
minimum, copy index into
it to a min_storage `Rows`
second `Rows`
See https://github.com/apache/arrow-datafusion/pull/6800#issuecomment-1622290981 for more details
Additional context
No response
About this issue
- Original URL
- State: closed
- Created 3 years ago
- Comments: 42 (42 by maintainers)
In terms of implementation, what I suggest is:
For the POC here is the reproducer I recommend:
Step 1. Get
hits_partitionedusingbench.sh:Step 2: Prepare a script with reproducer query:
Step 3: Run script (with release build of
datafusion-cli):set datafusion.execution.parquet.schema_force_view_types = true;-->Elapsed 18.431 seconds.set datafusion.execution.parquet.schema_force_view_types = false;-->Elapsed 6.427 seconds.The goal is to get
set datafusion.execution.parquet.schema_force_view_types = true;to be the same (or better) than when it is falseIf you look at the flamegraph-string-view.svg, you can see most of the time is spent doing GroupsAccumulator
I think what @alamb means is that just simply using
Vec<String>to store the states will be at least not worse thanStringArray + GroupsAccumulatorAdapter, and it is easy to start from.And after improving it to be not worse than
StringArray + GroupsAccumulatorAdapter, we can continue to push forward enabling string view by default.Fixed in #12575, now min/max on
StringViewArrayshould be slightly faster thanStringArrayOk, I think https://github.com/apache/datafusion/pull/12792 is ready to review. It has a nice 10% improvement on Q28 and avoids the slowdown when string view is enabled
this makes a lot of sense (and is similar to what the current non groups accumulator does β finds the min per batch and then updates the current overall min from that, rather than updating the min for each input row).
I will check out https://github.com/apache/datafusion/pull/12677 β I hoped to do it today but I appear to be almost out of time
Finally got around to trying out a little POC locally. Iβm getting much better results by just storing the state as
Vec<String>itβs very much not polished at this moment in time but I will have some more time on Sunday + early next week to continue working on this. It is currently only implemented forMINwill need to work onMAXnext but I foresee the implementation being almost identical.Without view types:
With view types:
A 1.29% performance improvement π
Awesome thank you @Rachelint.
Iβve begun working on a small POC locally with this information. It took me a bit of reading up on context to get going for sure. After reading through https://docs.rs/datafusion/latest/datafusion/physical_plan/trait.Accumulator.html and https://docs.rs/datafusion/latest/datafusion/logical_expr/trait.GroupsAccumulator.html, tracing through the code locally, and reading through the discussion a few times I now have a better understanding of where to start, the expected outcome and a path to get there.
Yes indeed. Thank you
π―
I guess the current goal is to remove the calling of slice, and get an at least not worse performance than
StringArray + GroupsAccumulatorAdapteras mentioned above.Cool, Iβm assuming this change didnβt impact the
GroupsAccumulatorAdaptercall in anyway since Iβm still seeing a similar performance + flamegraph with the following query:Seems like a reasonable place to start in my opinion. If we want to get more sophisticated at a later time we can try something more exotic. I suspect there will be times when individual allocations will be faster and times when a buffer will be faster and there will be memory consumption tradeoffs as well.
TLDR we should implement something and as long as it is better than what is currently going on that will be good.
Yes⦠At least it will be better than now, even we just use
Vec<String>to impl a specificGroupsAccumulatorforStringtypeβ¦Seems really interesting, I am reading the related disscusions.
Great! Iβll get started on this later in the week/over the weekend π Will likely bug folks as I require help haha π
@devanbenz I think this would be a fun and interesting project as well as valuable to DataFusion. However, I also think it is pretty advanced β I would enjoy helping with it, but also maybe @Rachelint or @jayzhan211 are interested in helping out π€
I dont know of anyone working on this @devanbenz β but I also donβt know of any benchmarks or actual queries that use
min/maxon string columns. The place it shows up is when computing statistics when writing parquet, but I think parquet is already pretty good at this (and has its own code to compute min/max)