Vectorized hashing for hash aggregation code

[Dandandan]

Updating the hash aggregate implementation to use vectorized hashing should give a decent speed up to queries that are dependant on fast hash aggregate implementations.

Currently keys are generated of type Vec<u8> and are hashed row-by-row which causes

• more memory usage
• slow re-hashing of the backing hashmap
• type un-aware hashing for simple primitive values

The implementation should also solve hash collisions, so the original should be able to be compared with the values.

There is some WIP code here apache/arrow#9213 which can be used as a starting point / to continue from.

[jorgecarleitao]

On arrow2, I took the following approach:

1. Expose an hash kernel
2. use hash_hasher

My hypothesis is that if we move hashing to arrow instead of doing item by item, we likely gain a lot. However, to do that, we need to tell our hasher to not re-hash the keys that it receives, thus the hash_hasher.

[Dandandan]

Thanks @jorgecarleitao !

Yeah I would agree, would be great to have a hashing kernel or maybe some basic primitives to build one easily using arrow. Something like hash_hasher looks cool too and is actually very similar to the one used in the hash join (hashbrown hashmap + IdHashBuilder which just uses the identity function) . Looking at the code of hash_hasher, it's something similar done as in the hash join (IdHashBuilder), but seems that it should be doing a bit more work (e.g. the "hash combiner" works over bytes) and hashbrown is also slightly faster. I believe because of more inlining as the standard library one uses / exports the same crate..

For this PR I was thinking to move the code to hash_utils

[jorgecarleitao]

Perfect, we have the same understanding of the problem, then :)

Yeah, I used hash_hasher to generalize the Dictionary builder to arbitrary types, but as long as we have the concepts right, we can change it; I agree that hashbrown + IdHashBuilder is more performant. 👍

[xudong963]

The issue seems stale?

[Dandandan]

This is solved