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)

Most upvoted comments

In terms of implementation, what I suggest is:

  1. Do a POC implementaiton: wire up just enough `StringView, don’t worry about GC, basic unit tests
  2. Verify it makes the clickbench query faster
  3. Flesh out testing, documentation, add support for StringArrary, etc
  4. Merge and profit (bonus points for blogging about it)

For the POC here is the reproducer I recommend:

Step 1. Get hits_partitioned using bench.sh:

cd benchmarks
./bench.sh data clickbench_partitioned

Step 2: Prepare a script with reproducer query:

set datafusion.execution.parquet.schema_force_view_types = true;


SELECT REGEXP_REPLACE("Referer", '^https?://(?:www\\.)?([^/]+)/.*$', '\\1') AS k, AVG(length("Referer")) AS l, COUNT(*) AS c, MIN("Referer")
FROM hits_partitioned
WHERE "Referer" <> '' GROUP BY k HAVING COUNT(*) > 100000 ORDER BY l DESC LIMIT 25;
andrewlamb@Andrews-MacBook-Pro-2:~/Software/datafusion2/benchmarks/data$ cat q28.sql
set datafusion.execution.parquet.schema_force_view_types = true;

SELECT REGEXP_REPLACE("Referer", '^https?://(?:www\\.)?([^/]+)/.*$', '\\1') AS k, AVG(length("Referer")) AS l, COUNT(*) AS c, MIN("Referer")
FROM hits_partitioned
WHERE "Referer" <> '' GROUP BY k HAVING COUNT(*) > 100000 ORDER BY l DESC LIMIT 25;

Step 3: Run script (with release build of datafusion-cli):

datafusion-cli -f q28.sql
  • 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 false

If you look at the flamegraph-string-view.svg, you can see most of the time is spent doing GroupsAccumulator

Screenshot 2024-09-16 at 4 44 50 PM

@Rachelint your implicit idea of using Vec<String> to store the state I think is actually quite interesting and maybe we should try that one first: It would at least avoid calling Array::slice and likely be better than using GroupsAccumulatorAdapter, even if we could improve it later with more explciit memory management πŸ€”

So this would effectively be using a Vec<String> for state instead of your proposal of using something akin to StringView notated here #6906 (comment) @alamb?

I think what @alamb means is that just simply using Vec<String> to store the states will be at least not worse than StringArray + 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.

while working on https://github.com/apache/datafusion/pull/12092 it turns out that Min / Max on BinaryView and StringView are suuuuper slow.

Fixed in #12575, now min/max on StringViewArray should be slightly faster than StringArray

Ok, 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

The more values are in the same group within the batch, the less β€œgarbage” we created compare to the original proposed design.

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 for MIN will need to work on MAX next but I foresee the implementation being almost identical.

Screenshot 2024-09-26 at 4 56 25 PM

Without view types:

25 row(s) fetched.
Elapsed 12.293 seconds.

With view types:

25 row(s) fetched.
Elapsed 12.135 seconds.

A 1.29% performance improvement 😎

I have had more time to take a look at this and sort of just wrap my head around how GroupsAccumulatorAdapter works a bit. I’m seeing that the performance impact is happening here https://github.com/apache/datafusion/blob/a35d0075744a058f81bd9ebed747e2e597434019/datafusion/functions-aggregate-common/src/aggregate/groups_accumulator.rs#L475

in slice_and_maybe_filter I’m under the assumption that this is happening due to the difference between the BinaryView and the Binary Scalar values. Taking a look at influxdata.com/blog/faster-queries-with-stringview-part-one-influxdb I understand that BinaryView is effectively a non-contiguous structure where as Binary is contiguous so it is easily sliced. So the idea here is to effectively change the underlying state in which the accumulator structure receives that data thus making it either easier to call slice or remove the calling of slice entirely?

I guess the current goal is to remove the calling of slice, and get an at least not worse performance than StringArray + GroupsAccumulatorAdapter as mentioned above.

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.

I think what @alamb means is that just simply using Vec<String> to store the states will be at least not worse than StringArray + GroupsAccumulatorAdapter, and it is easy to start from.

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 + GroupsAccumulatorAdapter as mentioned above.

πŸ’―

I have had more time to take a look at this and sort of just wrap my head around how GroupsAccumulatorAdapter works a bit. I’m seeing that the performance impact is happening here

https://github.com/apache/datafusion/blob/a35d0075744a058f81bd9ebed747e2e597434019/datafusion/functions-aggregate-common/src/aggregate/groups_accumulator.rs#L475 in slice_and_maybe_filter I’m under the assumption that this is happening due to the difference between the BinaryView and the Binary Scalar values. Taking a look at https://www.influxdata.com/blog/faster-queries-with-stringview-part-one-influxdb/ I understand that BinaryView is effectively a non-contiguous structure where as Binary is contiguous so it is easily sliced. So the idea here is to effectively change the underlying state in which the accumulator structure receives that data thus making it either easier to call slice or remove the calling of slice entirely?

I guess the current goal is to remove the calling of slice, and get an at least not worse performance than StringArray + GroupsAccumulatorAdapter as mentioned above.

while working on #12092 it turns out that Min / Max on BinaryView and StringView are suuuuper slow.

Fixed in #12575, now min/max on StringViewArray should be slightly faster than StringArray

I mean, fixed for that particular clickbench query which does not leverage stats to prune parquet access.

Cool, I’m assuming this change didn’t impact the GroupsAccumulatorAdapter call in anyway since I’m still seeing a similar performance + flamegraph with the following query:

set datafusion.execution.parquet.schema_force_view_types = true;


SELECT REGEXP_REPLACE("Referer", '^https?://(?:www\\.)?([^/]+)/.*$', '\\1') AS k, AVG(length("Referer")) AS l, COUNT(*) AS c, MIN("Referer")
FROM hits_partitioned
WHERE "Referer" <> '' GROUP BY k HAVING COUNT(*) > 100000 ORDER BY l DESC LIMIT 25;

with_changes_sv

I am not familiar enough with StringViewArray, is it ok to do that? And will it lead to a extremely bad performance?

I think using a single Buffer for each string will be bad for performance (likely worse than storing as String and copying them at the end. StringViewArray is really optimized for a small number of buffers (even though in theory it could have 2B of them as it is indexed on i32)

Ok, for StringView min/max, seems we can just start with using Vec<u128>(views) to store the inlined state(<= 12), use Vec<String> to store the unlined.

And when converting it to StringViewArray, we just copy the Vec<String> to create the buffer (GroupsAccumulatorAdapter copy the states too).

For the short strings(<=12), it can avoid allocating String, and for the long ones, it just do the same thing as GroupsAccumulatorAdapter. Seems it can have a better performance(due optimization for shorts)?

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.

@Rachelint your implicit idea of using Vec<String> to store the state I think is actually quite interesting and maybe we should try that one first:

It would at least avoid calling Array::slice and likely be better than using GroupsAccumulatorAdapter, even if we could improve it later with more explciit memory management πŸ€”

Yes… At least it will be better than now, even we just use Vec<String> to impl a specific GroupsAccumulator for String type…

@alamb is there anyone working on this + is this issue still relevant? I would love to tackle it as it seems like an interesting feature/optimization.

@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 πŸ€”

Seems really interesting, I am reading the related disscusions.

@alamb is there anyone working on this + is this issue still relevant? I would love to tackle it as it seems like an interesting feature/optimization.

@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 πŸ€”

Great! I’ll get started on this later in the week/over the weekend πŸ˜ƒ Will likely bug folks as I require help haha πŸ˜†

@alamb is there anyone working on this + is this issue still relevant? I would love to tackle it as it seems like an interesting feature/optimization.

@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 πŸ€”

@alamb is there anyone working on this + is this issue still relevant? I would love to tackle it as it seems like an interesting feature/optimization.

I dont know of anyone working on this @devanbenz – but I also don’t know of any benchmarks or actual queries that use min / max on 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)