You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by gi...@apache.org on 2026/07/27 04:29:08 UTC
(datafusion) 01/01: feat: add BuildHasher variants for hash_utils (#21820)
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-21820-77b172e1505283f9ac6af050ee8547f910c28262
in repository https://gitbox.apache.org/repos/asf/datafusion.git
commit e8a65f2d6f24afa75192fc63aca38011ede88800
Author: xudong.w <wx...@gmail.com>
AuthorDate: Mon Jul 27 12:28:42 2026 +0800
feat: add BuildHasher variants for hash_utils (#21820)
## Which issue does this PR close?
- Closes https://github.com/apache/datafusion/issues/21428.
## Rationale for this change
This PR adds `BuildHasher`-based variants for `hash_utils` so callers
can compute row hashes with a caller-provided hash builder instead of
always using DataFusion's default `RandomState`.
The main constraint is performance: `with_hashes` is a hot path,
especially for string, dictionary, and nested array hashing. A previous
version in #21429 caused measurable regressions in the default
`RandomState` path, for example `large_utf8: single, no nulls` regressed
from roughly `26.7us` to `36.3us`, and `large_utf8: multiple, no nulls`
from roughly `112us` to `127us`.
This version keeps the default path performance-oriented by avoiding a
fully generic `BuildHasher` rewrite of the existing hot loops.
## What changes are included in this PR?
This PR adds:
- `with_hashes_with_hasher`
- `create_hashes_with_hasher`
- custom-hasher implementations for primitive, string, binary,
byte-view, dictionary, and nested arrays
- tests covering custom hashers, multi-column hashing, and dictionary
equivalence
The implementation intentionally uses a hybrid design:
- Default `RandomState` leaf hot paths remain specialized.
- Custom `BuildHasher` leaf paths live separately in
`hash_utils/build_hasher.rs`.
- Nested/structural logic is shared through an internal child-hashing
adapter, so struct/list/map/union/run/dictionary behavior does not need
to be broadly duplicated.
The trade-off is that there is still some duplication for
primitive/string/binary leaf loops. That duplication is intentional:
those are the hottest loops, and keeping them separate prevents the
existing `RandomState` path from becoming generic over `BuildHasher` or
being perturbed by the custom-hasher implementation.
## Are these changes tested?
Yes.
---------
Co-authored-by: Dmitrii Blaginin <dm...@blaginin.me>
Co-authored-by: Andrew Lamb <an...@nerdnetworks.org>
---
datafusion/common/src/hash_utils.rs | 494 +++++++++++++++++++----
datafusion/common/src/hash_utils/build_hasher.rs | 494 +++++++++++++++++++++++
2 files changed, 911 insertions(+), 77 deletions(-)
diff --git a/datafusion/common/src/hash_utils.rs b/datafusion/common/src/hash_utils.rs
index 1443b6152b..cfe5799968 100644
--- a/datafusion/common/src/hash_utils.rs
+++ b/datafusion/common/src/hash_utils.rs
@@ -91,6 +91,8 @@ use crate::error::Result;
use crate::error::{_internal_datafusion_err, _internal_err};
use std::cell::RefCell;
+mod build_hasher;
+
// Combines two hashes into one hash
#[inline]
pub fn combine_hashes(l: u64, r: u64) -> u64 {
@@ -186,13 +188,32 @@ where
}).map_err(|_| _internal_datafusion_err!("with_hashes cannot access thread-local storage during or after thread destruction"))?
}
+/// Creates hashes for the given arrays using a thread-local buffer and a custom
+/// hash builder, then calls the provided callback with the computed hashes.
+///
+/// Hash compatibility with [`with_hashes`] follows the rules documented on
+/// [`create_hashes_with_hasher`].
+pub fn with_hashes_with_hasher<I, T, F, R, S>(
+ arrays: I,
+ hash_builder: &S,
+ callback: F,
+) -> Result<R>
+where
+ I: IntoIterator<Item = T>,
+ T: AsDynArray,
+ F: FnOnce(&[u64]) -> Result<R>,
+ S: BuildHasher,
+{
+ build_hasher::with_hashes_with_hasher(arrays, hash_builder, callback)
+}
+
#[cfg(not(feature = "force_hash_collisions"))]
fn hash_null<S: HashState>(
random_state: &S,
hashes_buffer: &'_ mut [u64],
- mul_col: bool,
+ multi_col: bool,
) {
- if mul_col {
+ if multi_col {
hashes_buffer.iter_mut().for_each(|hash| {
// stable hash for null value
*hash = combine_hashes(random_state.hash_one(1), *hash);
@@ -254,6 +275,30 @@ macro_rules! hash_float_value {
}
hash_float_value!((half::f16, u16), (f32, u32), (f64, u64));
+#[cfg(not(feature = "force_hash_collisions"))]
+trait ChildHashing {
+ fn create_hashes<I, T>(&self, arrays: I, hashes_buffer: &mut [u64]) -> Result<()>
+ where
+ I: IntoIterator<Item = T>,
+ T: AsDynArray;
+}
+
+#[cfg(not(feature = "force_hash_collisions"))]
+struct HashStateChildHashing<'a, S> {
+ hash_state: &'a S,
+}
+
+#[cfg(not(feature = "force_hash_collisions"))]
+impl<S: HashState> ChildHashing for HashStateChildHashing<'_, S> {
+ fn create_hashes<I, T>(&self, arrays: I, hashes_buffer: &mut [u64]) -> Result<()>
+ where
+ I: IntoIterator<Item = T>,
+ T: AsDynArray,
+ {
+ create_hashes(arrays, self.hash_state, hashes_buffer).map(|_| ())
+ }
+}
+
/// Builds hash values of PrimitiveArray and writes them into `hashes_buffer`
/// If `rehash==true` this folds the existing hash into the hasher state
/// and hashes only the new value (avoiding a separate combine step).
@@ -472,31 +517,25 @@ fn hash_generic_byte_view_array<T: ByteViewType>(
}
}
-/// Hash dictionary array with compile-time specialization for null handling.
+/// Scatter precomputed dictionary value hashes to key positions.
///
-/// Uses const generics to eliminate runtim branching in the hot loop:
+/// Uses const generics to eliminate runtime branching in the hot loop:
/// - `HAS_NULL_KEYS`: Whether to check for null dictionary keys
/// - `HAS_NULL_VALUES`: Whether to check for null dictionary values
/// - `MULTI_COL`: Whether to combine with existing hash (true) or initialize (false)
#[cfg(not(feature = "force_hash_collisions"))]
#[inline(never)]
-fn hash_dictionary_inner<
+fn hash_dictionary_scatter<
K: ArrowDictionaryKeyType,
const HAS_NULL_KEYS: bool,
const HAS_NULL_VALUES: bool,
const MULTI_COL: bool,
>(
array: &DictionaryArray<K>,
- random_state: &impl HashState,
+ dict_hashes: &[u64],
hashes_buffer: &mut [u64],
-) -> Result<()> {
- // Hash each dictionary value once, and then use that computed
- // hash for each key value to avoid a potentially expensive
- // redundant hashing for large dictionary elements (e.g. strings)
+) {
let dict_values = array.values();
- let mut dict_hashes = vec![0; dict_values.len()];
- create_hashes([dict_values], random_state, &mut dict_hashes)?;
-
if HAS_NULL_KEYS {
for (hash, key) in hashes_buffer.iter_mut().zip(array.keys().iter()) {
if let Some(key) = key {
@@ -522,70 +561,98 @@ fn hash_dictionary_inner<
}
}
}
- Ok(())
}
-/// Hash the values in a dictionary array
#[cfg(not(feature = "force_hash_collisions"))]
-fn hash_dictionary<K: ArrowDictionaryKeyType>(
+fn dispatch_dictionary_scatter<K: ArrowDictionaryKeyType>(
array: &DictionaryArray<K>,
- random_state: &impl HashState,
+ dict_hashes: &[u64],
hashes_buffer: &mut [u64],
multi_col: bool,
-) -> Result<()> {
+) {
let has_null_keys = array.keys().null_count() != 0;
let has_null_values = array.values().null_count() != 0;
- // Dispatcher based on null presence and multi-column mode
- // Should reduce branching within hot loops
match (has_null_keys, has_null_values, multi_col) {
- (false, false, false) => hash_dictionary_inner::<K, false, false, false>(
+ (false, false, false) => hash_dictionary_scatter::<K, false, false, false>(
array,
- random_state,
+ dict_hashes,
hashes_buffer,
),
- (false, false, true) => hash_dictionary_inner::<K, false, false, true>(
+ (false, false, true) => hash_dictionary_scatter::<K, false, false, true>(
array,
- random_state,
+ dict_hashes,
hashes_buffer,
),
- (false, true, false) => hash_dictionary_inner::<K, false, true, false>(
+ (false, true, false) => hash_dictionary_scatter::<K, false, true, false>(
array,
- random_state,
+ dict_hashes,
hashes_buffer,
),
- (false, true, true) => hash_dictionary_inner::<K, false, true, true>(
+ (false, true, true) => hash_dictionary_scatter::<K, false, true, true>(
array,
- random_state,
+ dict_hashes,
hashes_buffer,
),
- (true, false, false) => hash_dictionary_inner::<K, true, false, false>(
+ (true, false, false) => hash_dictionary_scatter::<K, true, false, false>(
array,
- random_state,
+ dict_hashes,
hashes_buffer,
),
- (true, false, true) => hash_dictionary_inner::<K, true, false, true>(
+ (true, false, true) => hash_dictionary_scatter::<K, true, false, true>(
array,
- random_state,
+ dict_hashes,
hashes_buffer,
),
- (true, true, false) => hash_dictionary_inner::<K, true, true, false>(
+ (true, true, false) => hash_dictionary_scatter::<K, true, true, false>(
array,
- random_state,
+ dict_hashes,
hashes_buffer,
),
- (true, true, true) => hash_dictionary_inner::<K, true, true, true>(
+ (true, true, true) => hash_dictionary_scatter::<K, true, true, true>(
array,
- random_state,
+ dict_hashes,
hashes_buffer,
),
}
}
+/// Hash the values in a dictionary array.
+#[cfg(not(feature = "force_hash_collisions"))]
+fn hash_dictionary<K: ArrowDictionaryKeyType>(
+ array: &DictionaryArray<K>,
+ random_state: &impl HashState,
+ hashes_buffer: &mut [u64],
+ multi_col: bool,
+) -> Result<()> {
+ // Hash each dictionary value once, and then use that computed
+ // hash for each key value to avoid a potentially expensive
+ // redundant hashing for large dictionary elements (e.g. strings)
+ let dict_values = array.values();
+ let mut dict_hashes = vec![0; dict_values.len()];
+ create_hashes([dict_values], random_state, &mut dict_hashes)?;
+ dispatch_dictionary_scatter(array, &dict_hashes, hashes_buffer, multi_col);
+ Ok(())
+}
+
+#[cfg(not(feature = "force_hash_collisions"))]
+fn hash_dictionary_with_child_hashing<K: ArrowDictionaryKeyType>(
+ array: &DictionaryArray<K>,
+ child_hashing: &impl ChildHashing,
+ hashes_buffer: &mut [u64],
+ multi_col: bool,
+) -> Result<()> {
+ let dict_values = array.values();
+ let mut dict_hashes = vec![0; dict_values.len()];
+ child_hashing.create_hashes([dict_values], &mut dict_hashes)?;
+ dispatch_dictionary_scatter(array, &dict_hashes, hashes_buffer, multi_col);
+ Ok(())
+}
+
#[cfg(not(feature = "force_hash_collisions"))]
fn hash_struct_array(
array: &StructArray,
- random_state: &impl HashState,
+ child_hashing: &impl ChildHashing,
hashes_buffer: &mut [u64],
) -> Result<()> {
let nulls = array.nulls();
@@ -593,7 +660,7 @@ fn hash_struct_array(
// Create hashes for each row that combines the hashes over all the column at that row.
let mut values_hashes = vec![0u64; row_len];
- create_hashes(array.columns(), random_state, &mut values_hashes)?;
+ child_hashing.create_hashes(array.columns(), &mut values_hashes)?;
// Separate paths to avoid allocating Vec when there are no nulls
if let Some(nulls) = nulls {
@@ -615,7 +682,7 @@ fn hash_struct_array(
#[cfg(not(feature = "force_hash_collisions"))]
fn hash_map_array(
array: &MapArray,
- random_state: &impl HashState,
+ child_hashing: &impl ChildHashing,
hashes_buffer: &mut [u64],
) -> Result<()> {
let nulls = array.nulls();
@@ -634,7 +701,7 @@ fn hash_map_array(
.iter()
.map(|col| col.slice(first_offset, entries_len))
.collect();
- create_hashes(&sliced_columns, random_state, &mut values_hashes)?;
+ child_hashing.create_hashes(&sliced_columns, &mut values_hashes)?;
// Combine the hashes for entries on each row with each other and previous hash for that row
// Adjust indices by first_offset since values_hashes is sliced starting from first_offset
@@ -666,7 +733,7 @@ fn hash_map_array(
#[cfg(not(feature = "force_hash_collisions"))]
fn hash_list_array<OffsetSize>(
array: &GenericListArray<OffsetSize>,
- random_state: &impl HashState,
+ child_hashing: &impl ChildHashing,
hashes_buffer: &mut [u64],
) -> Result<()>
where
@@ -677,11 +744,10 @@ where
let last_offset = array.value_offsets().last().cloned().unwrap_or_default();
let value_bytes_len = (last_offset - first_offset).as_usize();
let mut values_hashes = vec![0u64; value_bytes_len];
- create_hashes(
+ child_hashing.create_hashes(
[array
.values()
.slice(first_offset.as_usize(), value_bytes_len)],
- random_state,
&mut values_hashes,
)?;
@@ -717,7 +783,7 @@ where
#[cfg(not(feature = "force_hash_collisions"))]
fn hash_list_view_array<OffsetSize>(
array: &GenericListViewArray<OffsetSize>,
- random_state: &impl HashState,
+ child_hashing: &impl ChildHashing,
hashes_buffer: &mut [u64],
) -> Result<()>
where
@@ -728,7 +794,7 @@ where
let sizes = array.value_sizes();
let nulls = array.nulls();
let mut values_hashes = vec![0u64; values.len()];
- create_hashes([values], random_state, &mut values_hashes)?;
+ child_hashing.create_hashes([values], &mut values_hashes)?;
if let Some(nulls) = nulls {
for (i, (offset, size)) in offsets.iter().zip(sizes.iter()).enumerate() {
if nulls.is_valid(i) {
@@ -756,7 +822,7 @@ where
#[cfg(not(feature = "force_hash_collisions"))]
fn hash_union_array(
array: &UnionArray,
- random_state: &impl HashState,
+ child_hashing: &impl ChildHashing,
hashes_buffer: &mut [u64],
) -> Result<()> {
let DataType::Union(union_fields, _mode) = array.data_type() else {
@@ -766,12 +832,12 @@ fn hash_union_array(
if array.is_dense() {
// Dense union: children only contain values of their type, so they're already compact.
// Use the default hashing approach which is efficient for dense unions.
- hash_union_array_default(array, union_fields, random_state, hashes_buffer)
+ hash_union_array_default(array, union_fields, child_hashing, hashes_buffer)
} else {
// Sparse union: each child has the same length as the union array.
// Optimization: only hash the elements that are actually referenced by type_ids,
// instead of hashing all K*N elements (where K = num types, N = array length).
- hash_sparse_union_array(array, union_fields, random_state, hashes_buffer)
+ hash_sparse_union_array(array, union_fields, child_hashing, hashes_buffer)
}
}
@@ -788,7 +854,7 @@ fn hash_union_array(
fn hash_union_array_default(
array: &UnionArray,
union_fields: &UnionFields,
- random_state: &impl HashState,
+ child_hashing: &impl ChildHashing,
hashes_buffer: &mut [u64],
) -> Result<()> {
let mut child_hashes: HashMap<i8, Vec<u64>> =
@@ -798,7 +864,7 @@ fn hash_union_array_default(
for (type_id, _field) in union_fields.iter() {
let child = array.child(type_id);
let mut child_hash_buffer = vec![0; child.len()];
- create_hashes([child], random_state, &mut child_hash_buffer)?;
+ child_hashing.create_hashes([child], &mut child_hash_buffer)?;
child_hashes.insert(type_id, child_hash_buffer);
}
@@ -829,7 +895,7 @@ fn hash_union_array_default(
fn hash_sparse_union_array(
array: &UnionArray,
union_fields: &UnionFields,
- random_state: &impl HashState,
+ child_hashing: &impl ChildHashing,
hashes_buffer: &mut [u64],
) -> Result<()> {
use std::collections::HashMap;
@@ -840,7 +906,7 @@ fn hash_sparse_union_array(
return hash_union_array_default(
array,
union_fields,
- random_state,
+ child_hashing,
hashes_buffer,
);
}
@@ -868,7 +934,7 @@ fn hash_sparse_union_array(
// Hash the filtered array
let mut filtered_hashes = vec![0u64; filtered.len()];
- create_hashes([&filtered], random_state, &mut filtered_hashes)?;
+ child_hashing.create_hashes([&filtered], &mut filtered_hashes)?;
// Scatter hashes back to correct positions
for (hash, &idx) in filtered_hashes.iter().zip(indices.iter()) {
@@ -884,14 +950,14 @@ fn hash_sparse_union_array(
#[cfg(not(feature = "force_hash_collisions"))]
fn hash_fixed_list_array(
array: &FixedSizeListArray,
- random_state: &impl HashState,
+ child_hashing: &impl ChildHashing,
hashes_buffer: &mut [u64],
) -> Result<()> {
let values = array.values();
let value_length = array.value_length() as usize;
let nulls = array.nulls();
let mut values_hashes = vec![0u64; values.len()];
- create_hashes([values], random_state, &mut values_hashes)?;
+ child_hashing.create_hashes([values], &mut values_hashes)?;
if let Some(nulls) = nulls {
for i in 0..array.len() {
if nulls.is_valid(i) {
@@ -919,11 +985,12 @@ fn hash_fixed_list_array(
#[cfg(not(feature = "force_hash_collisions"))]
fn hash_run_array_inner<
R: RunEndIndexType,
+ C: ChildHashing + ?Sized,
const HAS_NULL_VALUES: bool,
const REHASH: bool,
>(
array: &RunArray<R>,
- random_state: &impl HashState,
+ child_hashing: &C,
hashes_buffer: &mut [u64],
) -> Result<()> {
// We find the relevant runs that cover potentially sliced arrays, so we can only hash those
@@ -950,11 +1017,8 @@ fn hash_run_array_inner<
end_physical_index - start_physical_index,
);
let mut values_hashes = vec![0u64; sliced_values.len()];
- create_hashes(
- std::slice::from_ref(&sliced_values),
- random_state,
- &mut values_hashes,
- )?;
+ child_hashing
+ .create_hashes(std::slice::from_ref(&sliced_values), &mut values_hashes)?;
let mut start_in_slice = 0;
for (adjusted_physical_index, &absolute_run_end) in run_ends_values
@@ -990,24 +1054,26 @@ fn hash_run_array_inner<
#[cfg(not(feature = "force_hash_collisions"))]
fn hash_run_array<R: RunEndIndexType>(
array: &RunArray<R>,
- random_state: &impl HashState,
+ child_hashing: &impl ChildHashing,
hashes_buffer: &mut [u64],
rehash: bool,
) -> Result<()> {
let has_null_values = array.values().null_count() != 0;
match (has_null_values, rehash) {
- (false, false) => {
- hash_run_array_inner::<R, false, false>(array, random_state, hashes_buffer)
- }
+ (false, false) => hash_run_array_inner::<R, _, false, false>(
+ array,
+ child_hashing,
+ hashes_buffer,
+ ),
(false, true) => {
- hash_run_array_inner::<R, false, true>(array, random_state, hashes_buffer)
+ hash_run_array_inner::<R, _, false, true>(array, child_hashing, hashes_buffer)
}
(true, false) => {
- hash_run_array_inner::<R, true, false>(array, random_state, hashes_buffer)
+ hash_run_array_inner::<R, _, true, false>(array, child_hashing, hashes_buffer)
}
(true, true) => {
- hash_run_array_inner::<R, true, true>(array, random_state, hashes_buffer)
+ hash_run_array_inner::<R, _, true, true>(array, child_hashing, hashes_buffer)
}
}
}
@@ -1041,38 +1107,67 @@ fn hash_single_array(
}
DataType::Struct(_) => {
let array = as_struct_array(array)?;
- hash_struct_array(array, random_state, hashes_buffer)?;
+ let child_hashing = HashStateChildHashing {
+ hash_state: random_state,
+ };
+ hash_struct_array(array, &child_hashing, hashes_buffer)?;
}
DataType::List(_) => {
let array = as_list_array(array)?;
- hash_list_array(array, random_state, hashes_buffer)?;
+ let child_hashing = HashStateChildHashing {
+ hash_state: random_state,
+ };
+ hash_list_array(array, &child_hashing, hashes_buffer)?;
}
DataType::LargeList(_) => {
let array = as_large_list_array(array)?;
- hash_list_array(array, random_state, hashes_buffer)?;
+ let child_hashing = HashStateChildHashing {
+ hash_state: random_state,
+ };
+ hash_list_array(array, &child_hashing, hashes_buffer)?;
}
DataType::ListView(_) => {
let array = as_list_view_array(array)?;
- hash_list_view_array(array, random_state, hashes_buffer)?;
+ let child_hashing = HashStateChildHashing {
+ hash_state: random_state,
+ };
+ hash_list_view_array(array, &child_hashing, hashes_buffer)?;
}
DataType::LargeListView(_) => {
let array = as_large_list_view_array(array)?;
- hash_list_view_array(array, random_state, hashes_buffer)?;
+ let child_hashing = HashStateChildHashing {
+ hash_state: random_state,
+ };
+ hash_list_view_array(array, &child_hashing, hashes_buffer)?;
}
DataType::Map(_, _) => {
let array = as_map_array(array)?;
- hash_map_array(array, random_state, hashes_buffer)?;
+ let child_hashing = HashStateChildHashing {
+ hash_state: random_state,
+ };
+ hash_map_array(array, &child_hashing, hashes_buffer)?;
}
DataType::FixedSizeList(_,_) => {
let array = as_fixed_size_list_array(array)?;
- hash_fixed_list_array(array, random_state, hashes_buffer)?;
+ let child_hashing = HashStateChildHashing {
+ hash_state: random_state,
+ };
+ hash_fixed_list_array(array, &child_hashing, hashes_buffer)?;
}
DataType::Union(_, _) => {
let array = as_union_array(array)?;
- hash_union_array(array, random_state, hashes_buffer)?;
+ let child_hashing = HashStateChildHashing {
+ hash_state: random_state,
+ };
+ hash_union_array(array, &child_hashing, hashes_buffer)?;
}
DataType::RunEndEncoded(_, _) => downcast_run_array! {
- array => hash_run_array(array, random_state, hashes_buffer, rehash)?,
+ array => {
+ let child_hashing = HashStateChildHashing {
+ hash_state: random_state,
+ };
+ hash_run_array(array, &child_hashing, hashes_buffer, rehash)?
+ },
_ => unreachable!()
}
_ => {
@@ -1158,8 +1253,36 @@ where
Ok(hashes_buffer)
}
+/// Creates hash values for every row using a caller-provided hash builder.
+///
+/// The number of rows to hash is determined by `hashes_buffer.len()`.
+/// `hashes_buffer` should be pre-sized appropriately.
+///
+/// # Hash compatibility
+///
+/// Hash values are not guaranteed to be bit-for-bit identical to those from
+/// [`create_hashes`], even when `hash_builder` also implements [`HashState`].
+/// The optimized [`HashState`] path seeds the hasher from the previous hash
+/// when rehashing some primitive and byte-view values, whereas this function
+/// combines independently computed hashes. Use one API consistently if hashes
+/// are persisted or exchanged.
+pub fn create_hashes_with_hasher<'a, I, T, S>(
+ arrays: I,
+ hash_builder: &S,
+ hashes_buffer: &'a mut [u64],
+) -> Result<&'a mut [u64]>
+where
+ I: IntoIterator<Item = T>,
+ T: AsDynArray,
+ S: BuildHasher,
+{
+ build_hasher::create_hashes_with_hasher(arrays, hash_builder, hashes_buffer)
+}
+
#[cfg(test)]
mod tests {
+ #[cfg(not(feature = "force_hash_collisions"))]
+ use std::hash::{BuildHasherDefault, Hasher};
use std::sync::Arc;
use arrow::array::*;
@@ -1168,6 +1291,23 @@ mod tests {
use super::*;
+ #[cfg(not(feature = "force_hash_collisions"))]
+ #[derive(Default)]
+ struct TestHasher(u64);
+
+ #[cfg(not(feature = "force_hash_collisions"))]
+ impl Hasher for TestHasher {
+ fn finish(&self) -> u64 {
+ self.0
+ }
+
+ fn write(&mut self, bytes: &[u8]) {
+ for byte in bytes {
+ self.0 = self.0.wrapping_mul(37).wrapping_add(u64::from(*byte));
+ }
+ }
+ }
+
#[test]
fn create_hashes_for_decimal_array() -> Result<()> {
let array = vec![1, 2, 3, 4]
@@ -1404,6 +1544,206 @@ mod tests {
Ok(())
}
+ #[test]
+ #[cfg(not(feature = "force_hash_collisions"))]
+ fn test_create_hashes_with_custom_hasher() {
+ let array: ArrayRef = Arc::new(Int32Array::from(vec![1, 2, 1, 4]));
+ let hash_builder = BuildHasherDefault::<TestHasher>::default();
+
+ let mut custom_hashes = vec![0; array.len()];
+ create_hashes_with_hasher([&array], &hash_builder, &mut custom_hashes).unwrap();
+
+ let random_state = RandomState::with_seed(0);
+ let mut default_hashes = vec![0; array.len()];
+ create_hashes([&array], &random_state, &mut default_hashes).unwrap();
+
+ assert_eq!(custom_hashes[0], custom_hashes[2]);
+ assert_ne!(custom_hashes[0], custom_hashes[1]);
+ assert_ne!(custom_hashes, default_hashes);
+ }
+
+ #[test]
+ #[cfg(not(feature = "force_hash_collisions"))]
+ fn test_create_hashes_with_custom_hasher_normalizes_negative_zero() {
+ let array: ArrayRef = Arc::new(Float64Array::from(vec![0.0, -0.0]));
+ let hash_builder = BuildHasherDefault::<TestHasher>::default();
+ let mut hashes = vec![0; array.len()];
+
+ create_hashes_with_hasher([&array], &hash_builder, &mut hashes).unwrap();
+
+ assert_eq!(hashes[0], hashes[1]);
+ }
+
+ #[test]
+ #[cfg(not(feature = "force_hash_collisions"))]
+ fn test_create_hashes_dictionary_with_custom_hasher() {
+ let strings = [Some("foo"), None, Some("bar"), Some("foo"), None];
+ let string_array: ArrayRef =
+ Arc::new(strings.iter().cloned().collect::<StringArray>());
+ let dict_array: ArrayRef = Arc::new(
+ strings
+ .iter()
+ .cloned()
+ .collect::<DictionaryArray<Int8Type>>(),
+ );
+ let hash_builder = BuildHasherDefault::<TestHasher>::default();
+
+ let mut string_hashes = vec![0; strings.len()];
+ create_hashes_with_hasher([&string_array], &hash_builder, &mut string_hashes)
+ .unwrap();
+
+ let mut dict_hashes = vec![0; strings.len()];
+ create_hashes_with_hasher([&dict_array], &hash_builder, &mut dict_hashes)
+ .unwrap();
+
+ assert_eq!(string_hashes, dict_hashes);
+ }
+
+ #[test]
+ #[cfg(not(feature = "force_hash_collisions"))]
+ fn test_create_hashes_struct_with_custom_hasher() {
+ let struct_array = StructArray::from(vec![
+ (
+ Arc::new(Field::new("int", DataType::Int32, false)),
+ Arc::new(Int32Array::from(vec![1, 2, 1, 3])) as ArrayRef,
+ ),
+ (
+ Arc::new(Field::new("string", DataType::Utf8, false)),
+ Arc::new(StringArray::from(vec!["alpha", "beta", "alpha", "alpha"]))
+ as ArrayRef,
+ ),
+ ]);
+ let hash_builder = BuildHasherDefault::<TestHasher>::default();
+
+ let mut child_hashes = vec![0; struct_array.len()];
+ create_hashes_with_hasher(
+ struct_array.columns(),
+ &hash_builder,
+ &mut child_hashes,
+ )
+ .unwrap();
+ let expected_hashes = child_hashes
+ .into_iter()
+ .map(|hash| combine_hashes(0, hash))
+ .collect::<Vec<_>>();
+
+ let array: ArrayRef = Arc::new(struct_array);
+ let mut actual_hashes = vec![0; array.len()];
+ create_hashes_with_hasher([&array], &hash_builder, &mut actual_hashes).unwrap();
+
+ assert_eq!(actual_hashes, expected_hashes);
+ assert_eq!(actual_hashes[0], actual_hashes[2]);
+ assert_ne!(actual_hashes[0], actual_hashes[3]);
+ }
+
+ #[test]
+ #[cfg(not(feature = "force_hash_collisions"))]
+ fn test_create_hashes_long_utf8_view_with_custom_hasher() {
+ let values = vec![
+ Some("this string is longer than twelve bytes"),
+ None,
+ Some("another string longer than twelve bytes"),
+ Some("this string is longer than twelve bytes"),
+ ];
+ let view_array = StringViewArray::from(values.clone());
+ assert!(!view_array.data_buffers().is_empty());
+ let view_array: ArrayRef = Arc::new(view_array);
+ let hash_builder = BuildHasherDefault::<TestHasher>::default();
+
+ let mut view_hashes = vec![0; view_array.len()];
+ create_hashes_with_hasher([&view_array], &hash_builder, &mut view_hashes)
+ .unwrap();
+ let expected_hashes = values
+ .iter()
+ .map(|value| {
+ value
+ .map(|value| hash_builder.hash_one(value.as_bytes()))
+ .unwrap_or_default()
+ })
+ .collect::<Vec<_>>();
+ assert_eq!(view_hashes, expected_hashes);
+
+ let prefix_array: ArrayRef = Arc::new(Int32Array::from(vec![1, 2, 3, 1]));
+ let mut expected_hashes = vec![0; prefix_array.len()];
+ create_hashes_with_hasher([&prefix_array], &hash_builder, &mut expected_hashes)
+ .unwrap();
+ for (hash, value) in expected_hashes.iter_mut().zip(&values) {
+ if let Some(value) = value {
+ *hash = combine_hashes(hash_builder.hash_one(value.as_bytes()), *hash);
+ }
+ }
+
+ let mut view_hashes = vec![0; view_array.len()];
+ create_hashes_with_hasher(
+ [&prefix_array, &view_array],
+ &hash_builder,
+ &mut view_hashes,
+ )
+ .unwrap();
+ assert_eq!(view_hashes, expected_hashes);
+ }
+
+ #[test]
+ #[cfg(not(feature = "force_hash_collisions"))]
+ fn test_single_column_leaf_hashes_match_with_same_hasher() {
+ let arrays: Vec<ArrayRef> = vec![
+ Arc::new(Int32Array::from(vec![Some(1), None, Some(-1)])),
+ Arc::new(Float64Array::from(vec![Some(0.0), Some(-0.0), None])),
+ Arc::new(StringArray::from(vec![Some("foo"), None, Some("bar")])),
+ Arc::new(BinaryArray::from(vec![
+ Some(&b"short"[..]),
+ None,
+ Some(&b"longer than twelve bytes"[..]),
+ ])),
+ Arc::new(StringViewArray::from(vec![
+ Some("short"),
+ None,
+ Some("longer than twelve bytes"),
+ ])),
+ ];
+ let random_state = RandomState::with_seed(0);
+
+ for array in arrays {
+ let mut default_hashes = vec![0; array.len()];
+ create_hashes([&array], &random_state, &mut default_hashes).unwrap();
+
+ let mut custom_hashes = vec![0; array.len()];
+ create_hashes_with_hasher([&array], &random_state, &mut custom_hashes)
+ .unwrap();
+
+ assert_eq!(
+ custom_hashes,
+ default_hashes,
+ "single-column parity failed for {}",
+ array.data_type()
+ );
+ }
+ }
+
+ #[test]
+ #[cfg(not(feature = "force_hash_collisions"))]
+ fn test_with_hashes_with_custom_hasher() {
+ let int_array: ArrayRef = Arc::new(Int32Array::from(vec![1, 2, 3]));
+ let str_array: ArrayRef = Arc::new(StringArray::from(vec!["a", "b", "c"]));
+ let hash_builder = BuildHasherDefault::<TestHasher>::default();
+
+ let mut expected_hashes = vec![0; int_array.len()];
+ create_hashes_with_hasher(
+ [&int_array, &str_array],
+ &hash_builder,
+ &mut expected_hashes,
+ )
+ .unwrap();
+
+ let actual_hashes =
+ with_hashes_with_hasher([&int_array, &str_array], &hash_builder, |hashes| {
+ Ok(hashes.to_vec())
+ })
+ .unwrap();
+
+ assert_eq!(actual_hashes, expected_hashes);
+ }
+
#[test]
// Tests actual values of hashes, which are different if forcing collisions
#[cfg(not(feature = "force_hash_collisions"))]
diff --git a/datafusion/common/src/hash_utils/build_hasher.rs b/datafusion/common/src/hash_utils/build_hasher.rs
new file mode 100644
index 0000000000..12258beb11
--- /dev/null
+++ b/datafusion/common/src/hash_utils/build_hasher.rs
@@ -0,0 +1,494 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use super::{AsDynArray, HASH_BUFFER, MAX_BUFFER_SIZE};
+#[cfg(not(feature = "force_hash_collisions"))]
+use super::{
+ ChildHashing, combine_hashes, hash_dictionary_with_child_hashing,
+ hash_fixed_list_array, hash_list_array, hash_list_view_array, hash_map_array,
+ hash_run_array, hash_struct_array, hash_union_array,
+};
+#[cfg(not(feature = "force_hash_collisions"))]
+use crate::cast::{
+ as_binary_view_array, as_boolean_array, as_fixed_size_list_array,
+ as_generic_binary_array, as_large_list_array, as_large_list_view_array,
+ as_list_array, as_list_view_array, as_map_array, as_string_array,
+ as_string_view_array, as_struct_array, as_union_array,
+};
+use crate::error::Result;
+use crate::error::{_internal_datafusion_err, _internal_err};
+#[cfg(feature = "force_hash_collisions")]
+use arrow::array::Array;
+#[cfg(not(feature = "force_hash_collisions"))]
+use arrow::array::types::{IntervalDayTime, IntervalMonthDayNano};
+#[cfg(not(feature = "force_hash_collisions"))]
+use arrow::array::*;
+#[cfg(not(feature = "force_hash_collisions"))]
+use arrow::datatypes::*;
+#[cfg(not(feature = "force_hash_collisions"))]
+use arrow::{downcast_dictionary_array, downcast_primitive_array};
+use std::hash::BuildHasher;
+
+pub(super) fn with_hashes_with_hasher<I, T, F, R, S>(
+ arrays: I,
+ hash_builder: &S,
+ callback: F,
+) -> Result<R>
+where
+ I: IntoIterator<Item = T>,
+ T: AsDynArray,
+ F: FnOnce(&[u64]) -> Result<R>,
+ S: BuildHasher,
+{
+ let mut iter = arrays.into_iter().peekable();
+
+ let required_size = match iter.peek() {
+ Some(arr) => arr.as_dyn_array().len(),
+ None => {
+ return _internal_err!("with_hashes_with_hasher requires at least one array");
+ }
+ };
+
+ HASH_BUFFER.try_with(|cell| {
+ let mut buffer = cell.try_borrow_mut().map_err(|_| {
+ _internal_datafusion_err!(
+ "with_hashes_with_hasher cannot be called reentrantly on the same thread"
+ )
+ })?;
+
+ buffer.clear();
+ buffer.resize(required_size, 0);
+
+ create_hashes_with_hasher_impl(iter, hash_builder, &mut buffer[..required_size])?;
+
+ let result = callback(&buffer[..required_size])?;
+
+ if buffer.capacity() > MAX_BUFFER_SIZE {
+ buffer.truncate(MAX_BUFFER_SIZE);
+ buffer.shrink_to_fit();
+ }
+
+ Ok(result)
+ }).map_err(|_| {
+ _internal_datafusion_err!(
+ "with_hashes_with_hasher cannot access thread-local storage during or after thread destruction"
+ )
+ })?
+}
+
+pub(super) fn create_hashes_with_hasher<'a, I, T, S>(
+ arrays: I,
+ hash_builder: &S,
+ hashes_buffer: &'a mut [u64],
+) -> Result<&'a mut [u64]>
+where
+ I: IntoIterator<Item = T>,
+ T: AsDynArray,
+ S: BuildHasher,
+{
+ create_hashes_with_hasher_impl(arrays, hash_builder, hashes_buffer)
+}
+
+fn create_hashes_with_hasher_impl<'a, I, T, S>(
+ arrays: I,
+ hash_builder: &S,
+ hashes_buffer: &'a mut [u64],
+) -> Result<&'a mut [u64]>
+where
+ I: IntoIterator<Item = T>,
+ T: AsDynArray,
+ S: BuildHasher,
+{
+ for (i, array) in arrays.into_iter().enumerate() {
+ let rehash = i >= 1;
+ hash_single_array_with_hasher(
+ array.as_dyn_array(),
+ hash_builder,
+ hashes_buffer,
+ rehash,
+ )?;
+ }
+ Ok(hashes_buffer)
+}
+
+#[cfg(not(feature = "force_hash_collisions"))]
+struct BuildHasherChildHashing<'a, S> {
+ hash_builder: &'a S,
+}
+
+#[cfg(not(feature = "force_hash_collisions"))]
+impl<S: BuildHasher> ChildHashing for BuildHasherChildHashing<'_, S> {
+ fn create_hashes<I, T>(&self, arrays: I, hashes_buffer: &mut [u64]) -> Result<()>
+ where
+ I: IntoIterator<Item = T>,
+ T: AsDynArray,
+ {
+ create_hashes_with_hasher_impl(arrays, self.hash_builder, hashes_buffer)
+ .map(|_| ())
+ }
+}
+
+#[cfg(not(feature = "force_hash_collisions"))]
+trait BuildHasherHashValue {
+ fn hash_one_with_hasher<S: BuildHasher>(&self, state: &S) -> u64;
+}
+
+#[cfg(not(feature = "force_hash_collisions"))]
+impl<T: BuildHasherHashValue + ?Sized> BuildHasherHashValue for &T {
+ fn hash_one_with_hasher<S: BuildHasher>(&self, state: &S) -> u64 {
+ T::hash_one_with_hasher(self, state)
+ }
+}
+
+macro_rules! build_hasher_hash_value {
+ ($($t:ty),+) => {
+ $(#[cfg(not(feature = "force_hash_collisions"))]
+ impl BuildHasherHashValue for $t {
+ fn hash_one_with_hasher<S: BuildHasher>(&self, state: &S) -> u64 {
+ state.hash_one(self)
+ }
+ })+
+ };
+}
+build_hasher_hash_value!(i8, i16, i32, i64, i128, i256, u8, u16, u32, u64, u128);
+build_hasher_hash_value!(bool, str, [u8], IntervalDayTime, IntervalMonthDayNano);
+
+macro_rules! build_hasher_hash_float_value {
+ ($(($t:ty, $i:ty)),+) => {
+ $(#[cfg(not(feature = "force_hash_collisions"))]
+ impl BuildHasherHashValue for $t {
+ fn hash_one_with_hasher<S: BuildHasher>(&self, state: &S) -> u64 {
+ let bits = <$i>::from_ne_bytes(self.to_ne_bytes());
+ let bits = if bits << 1 == 0 { 0 } else { bits };
+ state.hash_one(bits)
+ }
+ })+
+ };
+}
+build_hasher_hash_float_value!((half::f16, u16), (f32, u32), (f64, u64));
+
+#[cfg(not(feature = "force_hash_collisions"))]
+fn hash_null_with_hasher<S: BuildHasher>(
+ hash_builder: &S,
+ hashes_buffer: &mut [u64],
+ multi_col: bool,
+) {
+ if hashes_buffer.is_empty() {
+ return;
+ }
+
+ let null_hash = hash_builder.hash_one(1);
+ if multi_col {
+ hashes_buffer.iter_mut().for_each(|hash| {
+ *hash = combine_hashes(null_hash, *hash);
+ })
+ } else {
+ hashes_buffer.fill(null_hash);
+ }
+}
+
+#[cfg(not(feature = "force_hash_collisions"))]
+fn hash_array_primitive_with_hasher<T, S>(
+ array: &PrimitiveArray<T>,
+ hash_builder: &S,
+ hashes_buffer: &mut [u64],
+ rehash: bool,
+) where
+ T: ArrowPrimitiveType<Native: BuildHasherHashValue>,
+ S: BuildHasher,
+{
+ assert_eq!(
+ hashes_buffer.len(),
+ array.len(),
+ "hashes_buffer and array should be of equal length"
+ );
+
+ if array.null_count() == 0 {
+ if rehash {
+ for (hash, &value) in hashes_buffer.iter_mut().zip(array.values().iter()) {
+ *hash = combine_hashes(value.hash_one_with_hasher(hash_builder), *hash);
+ }
+ } else {
+ for (hash, &value) in hashes_buffer.iter_mut().zip(array.values().iter()) {
+ *hash = value.hash_one_with_hasher(hash_builder);
+ }
+ }
+ } else if rehash {
+ for i in array.nulls().unwrap().valid_indices() {
+ let value = unsafe { array.value_unchecked(i) };
+ hashes_buffer[i] = combine_hashes(
+ value.hash_one_with_hasher(hash_builder),
+ hashes_buffer[i],
+ );
+ }
+ } else {
+ for i in array.nulls().unwrap().valid_indices() {
+ let value = unsafe { array.value_unchecked(i) };
+ hashes_buffer[i] = value.hash_one_with_hasher(hash_builder);
+ }
+ }
+}
+
+#[cfg(not(feature = "force_hash_collisions"))]
+fn hash_array_with_hasher<T, S>(
+ array: &T,
+ hash_builder: &S,
+ hashes_buffer: &mut [u64],
+ rehash: bool,
+) where
+ T: ArrayAccessor,
+ T::Item: BuildHasherHashValue,
+ S: BuildHasher,
+{
+ assert_eq!(
+ hashes_buffer.len(),
+ array.len(),
+ "hashes_buffer and array should be of equal length"
+ );
+
+ if array.null_count() == 0 {
+ if rehash {
+ for (i, hash) in hashes_buffer.iter_mut().enumerate() {
+ let value = unsafe { array.value_unchecked(i) };
+ *hash = combine_hashes(value.hash_one_with_hasher(hash_builder), *hash);
+ }
+ } else {
+ for (i, hash) in hashes_buffer.iter_mut().enumerate() {
+ let value = unsafe { array.value_unchecked(i) };
+ *hash = value.hash_one_with_hasher(hash_builder);
+ }
+ }
+ } else if rehash {
+ for i in array.nulls().unwrap().valid_indices() {
+ let value = unsafe { array.value_unchecked(i) };
+ hashes_buffer[i] = combine_hashes(
+ value.hash_one_with_hasher(hash_builder),
+ hashes_buffer[i],
+ );
+ }
+ } else {
+ for i in array.nulls().unwrap().valid_indices() {
+ let value = unsafe { array.value_unchecked(i) };
+ hashes_buffer[i] = value.hash_one_with_hasher(hash_builder);
+ }
+ }
+}
+
+#[cfg(not(feature = "force_hash_collisions"))]
+#[inline(never)]
+fn hash_string_view_array_inner_with_hasher<
+ T: ByteViewType,
+ S: BuildHasher,
+ const HAS_NULLS: bool,
+ const HAS_BUFFERS: bool,
+ const REHASH: bool,
+>(
+ array: &GenericByteViewArray<T>,
+ hash_builder: &S,
+ hashes_buffer: &mut [u64],
+) {
+ assert_eq!(
+ hashes_buffer.len(),
+ array.len(),
+ "hashes_buffer and array should be of equal length"
+ );
+
+ let buffers = array.data_buffers();
+ let view_bytes = |view_len: u32, view: u128| {
+ let view = ByteView::from(view);
+ let offset = view.offset as usize;
+ unsafe {
+ let data = buffers.get_unchecked(view.buffer_index as usize);
+ data.get_unchecked(offset..offset + view_len as usize)
+ }
+ };
+
+ let hashes_and_views = hashes_buffer.iter_mut().zip(array.views().iter());
+ for (i, (hash, &v)) in hashes_and_views.enumerate() {
+ if HAS_NULLS && array.is_null(i) {
+ continue;
+ }
+ let view_len = v as u32;
+ if !HAS_BUFFERS || view_len <= 12 {
+ if REHASH {
+ *hash = combine_hashes(v.hash_one_with_hasher(hash_builder), *hash);
+ } else {
+ *hash = v.hash_one_with_hasher(hash_builder);
+ }
+ continue;
+ }
+ let value = view_bytes(view_len, v);
+ if REHASH {
+ *hash = combine_hashes(value.hash_one_with_hasher(hash_builder), *hash);
+ } else {
+ *hash = value.hash_one_with_hasher(hash_builder);
+ }
+ }
+}
+
+#[cfg(not(feature = "force_hash_collisions"))]
+fn hash_generic_byte_view_array_with_hasher<T: ByteViewType, S: BuildHasher>(
+ array: &GenericByteViewArray<T>,
+ hash_builder: &S,
+ hashes_buffer: &mut [u64],
+ rehash: bool,
+) {
+ match (
+ array.null_count() != 0,
+ !array.data_buffers().is_empty(),
+ rehash,
+ ) {
+ (false, false, false) => {
+ for (hash, &view) in hashes_buffer.iter_mut().zip(array.views().iter()) {
+ *hash = view.hash_one_with_hasher(hash_builder);
+ }
+ }
+ (false, false, true) => {
+ for (hash, &view) in hashes_buffer.iter_mut().zip(array.views().iter()) {
+ *hash = combine_hashes(view.hash_one_with_hasher(hash_builder), *hash);
+ }
+ }
+ (false, true, false) => {
+ hash_string_view_array_inner_with_hasher::<T, S, false, true, false>(
+ array,
+ hash_builder,
+ hashes_buffer,
+ )
+ }
+ (false, true, true) => {
+ hash_string_view_array_inner_with_hasher::<T, S, false, true, true>(
+ array,
+ hash_builder,
+ hashes_buffer,
+ )
+ }
+ (true, false, false) => {
+ hash_string_view_array_inner_with_hasher::<T, S, true, false, false>(
+ array,
+ hash_builder,
+ hashes_buffer,
+ )
+ }
+ (true, false, true) => {
+ hash_string_view_array_inner_with_hasher::<T, S, true, false, true>(
+ array,
+ hash_builder,
+ hashes_buffer,
+ )
+ }
+ (true, true, false) => {
+ hash_string_view_array_inner_with_hasher::<T, S, true, true, false>(
+ array,
+ hash_builder,
+ hashes_buffer,
+ )
+ }
+ (true, true, true) => {
+ hash_string_view_array_inner_with_hasher::<T, S, true, true, true>(
+ array,
+ hash_builder,
+ hashes_buffer,
+ )
+ }
+ }
+}
+
+#[cfg(not(feature = "force_hash_collisions"))]
+fn hash_single_array_with_hasher<S: BuildHasher>(
+ array: &dyn Array,
+ hash_builder: &S,
+ hashes_buffer: &mut [u64],
+ rehash: bool,
+) -> Result<()> {
+ let child_hashing = BuildHasherChildHashing { hash_builder };
+
+ downcast_primitive_array! {
+ array => hash_array_primitive_with_hasher(array, hash_builder, hashes_buffer, rehash),
+ DataType::Null => hash_null_with_hasher(hash_builder, hashes_buffer, rehash),
+ DataType::Boolean => hash_array_with_hasher(&as_boolean_array(array)?, hash_builder, hashes_buffer, rehash),
+ DataType::Utf8 => hash_array_with_hasher(&as_string_array(array)?, hash_builder, hashes_buffer, rehash),
+ DataType::Utf8View => hash_generic_byte_view_array_with_hasher(as_string_view_array(array)?, hash_builder, hashes_buffer, rehash),
+ DataType::LargeUtf8 => hash_array_with_hasher(&as_largestring_array(array), hash_builder, hashes_buffer, rehash),
+ DataType::Binary => hash_array_with_hasher(&as_generic_binary_array::<i32>(array)?, hash_builder, hashes_buffer, rehash),
+ DataType::BinaryView => hash_generic_byte_view_array_with_hasher(as_binary_view_array(array)?, hash_builder, hashes_buffer, rehash),
+ DataType::LargeBinary => hash_array_with_hasher(&as_generic_binary_array::<i64>(array)?, hash_builder, hashes_buffer, rehash),
+ DataType::FixedSizeBinary(_) => {
+ let array: &FixedSizeBinaryArray = array.as_any().downcast_ref().unwrap();
+ hash_array_with_hasher(&array, hash_builder, hashes_buffer, rehash)
+ }
+ DataType::Dictionary(_, _) => downcast_dictionary_array! {
+ array => hash_dictionary_with_child_hashing(array, &child_hashing, hashes_buffer, rehash)?,
+ _ => unreachable!()
+ }
+ DataType::Struct(_) => {
+ let array = as_struct_array(array)?;
+ hash_struct_array(array, &child_hashing, hashes_buffer)?;
+ }
+ DataType::List(_) => {
+ let array = as_list_array(array)?;
+ hash_list_array(array, &child_hashing, hashes_buffer)?;
+ }
+ DataType::LargeList(_) => {
+ let array = as_large_list_array(array)?;
+ hash_list_array(array, &child_hashing, hashes_buffer)?;
+ }
+ DataType::ListView(_) => {
+ let array = as_list_view_array(array)?;
+ hash_list_view_array(array, &child_hashing, hashes_buffer)?;
+ }
+ DataType::LargeListView(_) => {
+ let array = as_large_list_view_array(array)?;
+ hash_list_view_array(array, &child_hashing, hashes_buffer)?;
+ }
+ DataType::Map(_, _) => {
+ let array = as_map_array(array)?;
+ hash_map_array(array, &child_hashing, hashes_buffer)?;
+ }
+ DataType::FixedSizeList(_,_) => {
+ let array = as_fixed_size_list_array(array)?;
+ hash_fixed_list_array(array, &child_hashing, hashes_buffer)?;
+ }
+ DataType::Union(_, _) => {
+ let array = as_union_array(array)?;
+ hash_union_array(array, &child_hashing, hashes_buffer)?;
+ }
+ DataType::RunEndEncoded(_, _) => downcast_run_array! {
+ array => hash_run_array(array, &child_hashing, hashes_buffer, rehash)?,
+ _ => unreachable!()
+ }
+ _ => {
+ return _internal_err!(
+ "Unsupported data type in hasher: {}",
+ array.data_type()
+ );
+ }
+ }
+ Ok(())
+}
+
+#[cfg(feature = "force_hash_collisions")]
+fn hash_single_array_with_hasher<S: BuildHasher>(
+ _array: &dyn Array,
+ _hash_builder: &S,
+ hashes_buffer: &mut [u64],
+ _rehash: bool,
+) -> Result<()> {
+ for hash in hashes_buffer.iter_mut() {
+ *hash = 0;
+ }
+ Ok(())
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org