Vectorized hashing for hash aggregation code #26
Description
Activity
On arrow2, I took the following approach:
- Expose an
hashkernel - 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.- Expose an
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_hasherlooks cool too and is actually very similar to the one used in the hash join (hashbrown hashmap +IdHashBuilderwhich just uses the identity function) . Looking at the code ofhash_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) andhashbrownis 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_utilsPerfect, we have the same understanding of the problem, then :)
Yeah, I used
hash_hasherto generalize the Dictionary builder to arbitrary types, but as long as we have the concepts right, we can change it; I agree thathashbrown + IdHashBuilderis more performant. 👍The issue seems stale?
Reacted by Judah Rand- added a commit that references this issue
on Jan 12, 2023 - added a commit that references this issue
on Sep 3, 2024 This is solved
Reacted by Andrew Lamb- added a commit that references this issue
on Mar 23, 2025 - added a commit that references this issue
on Aug 9, 2025
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 causesThe 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.