Rich-T-kid opened a new issue, #11518: URL: https://github.com/apache/arrow-rs/issues/11518
DataFusion currently owns the code that computes row hashes for Arrow arrays (`create_hashes`). It lives in two files in `datafusion-common`: - https://github.com/apache/datafusion/blob/main/datafusion/common/src/hash_utils.rs - https://github.com/apache/datafusion/blob/main/datafusion/common/src/hash_utils/build_hasher.rs While working on speeding up `RepartitionExec`, I found several ways to make hash creation faster using bit manipulation and architecture-specific code paths. However, some of these optimizations need aligned Arrow buffers, which means access to `MutableBuffer`. DataFusion does not expose `MutableBuffer`, and I don't think it should. The code is also array/Arrow-focused rather than query-execution-specific, so it seems like a better fit for arrow-rs. This also came up while working on #10614 (optimizing PLAIN Parquet string columns into dictionary arrays), and when computing NDV (number of distinct values) with `std` hash maps. Hashing utilities in arrow-rs would let the Parquet reader and other arrow-rs crates reuse them. ## Describe the solution you'd like Move the array-hashing functionality into arrow-rs, probably in an existing crate (`arrow-arith` or `arrow-data`) rather than a new one, since it is only two files. I'd start with the pieces that DataFusion already has, then build on them. The areas this could cover, roughly in order of how much they motivate the move: 1. **Reusable hashing utilities** for Arrow arrays (`create_hashes` and friends). 2. **Architecture-specific hashing** (aligned buffers, SIMD, bit tricks). 3. **NDV / cardinality estimation** (bloom filters, theta sketches), as an alternative to a costly hash per row. This relates to the discussion in https://lists.apache.org/thread/l8om71xjcv94x0z3hdvnbswk9ssyn2ks 4. **Hash-based data structures/operations.** Some of this already exists, so it's lower priority. 5. **Hash functions with different distribution properties** (e.g. avoiding hot partitions). This is probably not needed initially. Nothing in the two DataFusion files looks specific to query execution. **Open questions** - **Where should this live?** `arrow-arith`, `arrow-data`, or somewhere else? Is a new crate warranted? - **What public API should be exposed**, and how much of it should be committed to as stable? - **Hash stability:** should the hash output be stable across versions and platforms? DataFusion relies on consistent hashing for repartitioning, so this matters for any shared implementation. - **DataFusion migration:** once this exists in arrow-rs, DataFusion would depend on it instead of its own copy. What is the preferred migration path? - **Scope:** is there appetite for items 3 and 4 above (NDV estimation, hash-based structures), or should this stay limited to hash computation? **Describe alternatives you've considered** - Keep the code in DataFusion and expose the needed buffer APIs. I'd rather not, since that would mean making `MutableBuffer` part of DataFusion's public surface. **Additional context** - Prior discussion in arrow-rs: - https://github.com/apache/arrow-rs/issues/4802 (Hash for Array) - https://github.com/apache/arrow-rs/issues/6996 (Expose vectorized hash table that work with `Array`s) - Related PR where the idea came up: https://github.com/apache/arrow-rs/pull/10614 - initial discord thread https://discord.com/channels/885562378132000778/1314936346653102080/1555242391911530599 -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
