Improve aggregate performance with specialized groups accumulator for single string group by

[alamb]

Is your feature request related to a problem or challenge?

DataFusion could be made faster for queries that have a GROUP BY <string> column

For example, in ClickBench Q34

Q34: SELECT "URL", COUNT(*) AS c FROM hits GROUP BY "URL" ORDER BY c DESC LIMIT 10;

You can run this query from a datafusion checkout like this (using the code in #7060, which hopefully will be merged shortly):

# get data
./benchmarks/bench.sh data clickbench_1
# run benchmark
cargo run --release  --bin dfbench -- clickbench --query 34

Here is the profile from running 16 cores:

cargo run --release  --bin dfbench -- clickbench --query 34 --iterations 10 --partitions 16

Describe the solution you'd like

I would like a special cased GroupsValue for this case of a single string (hopefully Utf8, LargeUTf8, Binary, and LargeBinary) column that:

1. Does no allocations per group (aka stores all strings in some single contiguous location)
2. Avoids the Row format / copy of values

Other ideas that could make this faster:

1. Small String optimization
2. special case ASCII (to avoid UTF8 checks for data, like TPCH, that does not contain UTF8 data)

"Small String optimization" refers to the format described in the umbra paper,

This would have to be adapted for Rust / safetly but the same general idea applies (inlining the first few bytes of the string into the hash table for quick "is it equal" comparisons, and then having an offset to an external area for larger strings)

Describe alternatives you've considered

No response

Additional context

@tustvold's changes in #6969 and #7043 should make it very easy to code this up as a different GroupValues implementation

[Dandandan]

I think for single column group, we could "just"

• use the arrow string / binary builder and store the strings data outside of the hashtable -> makes it also cheap to produce the final column
• make sure to memoize hashes (repeatedly hashing is likely slow)

anything I missed here?

[alamb]

anything I missed here?

I think that would get most of the benefit.

Another potential optimization would be to potentially use the 'small string optimization' so the hash table comparison could be done inline and have one level of indirection

So in the hash table store not only the group_index but also another 12 bytes:

0-3: length of the string group key value (u32)
4-7: first four bytes of the string value itself (u32)
8-11: offset into string buffer (u32)

That way group key comparisons are faster because:

1. If the first 8 bytes are different you know the group value is different
2. We can check the actual values in the string builder without an extra level of computation on the offset buffer

Perhaps we could learn from the `View` implementation @tustvold was working on here

https://github.com/apache/arrow-rs/pull/4585/files#diff-694565dedb86d29ae2474ae09d51867a98a534543a45d79fcc3506b2958b73baR26

[alamb]

Here is a suggestion for a specific data structure for a similar idea from @Dandandan 👍
https://github.com/apache/arrow-datafusion/pull/8721/files#r1441586235

/// Contains hashes and offsets for given hash (+ potential collisions), use `RawTable` for extra speed
uniques: HashMap<u64, SmallVec<u64; 1>>,
/// actual string/byte data, can be emitted cheaply / free
values: BufferBuilder<u8>,

[tustvold]

If you use the raw_entry API on HashMap, or RawTable, you should be able to avoid needing the SmallVec to handle hash collisions - as they will be handled for you more efficiently by the hash probing setup.

[Dandandan]

If you use the raw_entry API on HashMap, or RawTable, you should be able to avoid needing the SmallVec to handle hash collisions - as they will be handled for you more efficiently by the hash probing setup.

Yes, good addition 👍

[jayzhan211]

This task seems interesting, if no one take on this, I would like to give it a try.

Probably work on the follow up on #8721 first. Distinct Accumulator for Bytes