Skip to content

Commit 92ad99e

Browse files
viiryaclaude
andauthored
fix: keep the dictionary hash fast path off nested and reseeded buffers (#5757)
The dictionary fast path hashes each distinct dictionary value once and reuses that result for every key. It was selected by the column's position, `i == 0`, and it restarted from a hardcoded seed of 42. Both parts are wrong. `create_hashes_internal!` also runs on recursion, so a dictionary nested in a list, struct or map arrives as the only column of its call and looks like a first column even though the buffer already holds the hash accumulated for earlier elements of that row. That hash was discarded, and a dictionary-encoded list element hashed differently from the identical decoded value. Separately, the hardcoded 42 is wrong whenever the caller supplies its own seed, as `hash(col, seed)` and `xxhash64(col, seed)` allow, so even a genuine first column disagreed with its decoded form for a non-default seed. The reuse is valid exactly when every row carries the same incoming hash, so that is what is now checked, and the per-value hashes start from the seed the buffer actually holds rather than an assumed 42. A top-level dictionary keeps the optimisation. The uniformity check is a scan of the hash buffer, which is measurable: running it for every column cost 17% on an int column and 11% on a string column in a local criterion benchmark. It is therefore done inside the dictionary arm, so only dictionary columns pay it and other types are untouched. Both hash implementations share this structure and both are fixed, with regression tests that fail without the change: a dictionary as a list element hashes 3853467749 rather than the 1401423033 of the decoded data. The single-row cases above pin the hardcoded seed but not the uniformity check, since one row is uniform by definition. Each algorithm therefore also gets a multi-row case whose incoming seeds all differ, which forces the unpacking fallback, and which includes a null key and a key pointing at a null dictionary value. Dropping the uniformity check leaves the other twenty hash tests green and fails exactly those two. Co-authored-by: Claude Code <[email protected]>
1 parent 7f1e001 commit 92ad99e

3 files changed

Lines changed: 183 additions & 13 deletions

File tree

‎native/spark-expr/src/hash_funcs/murmur3.rs‎

Lines changed: 104 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -139,20 +139,23 @@ pub fn spark_compatible_murmur3_hash<T: AsRef<[u8]>>(data: T, seed: u32) -> u32
139139
fn create_hashes_dictionary<K: ArrowDictionaryKeyType>(
140140
array: &ArrayRef,
141141
hashes_buffer: &mut [u32],
142-
first_col: bool,
142+
seeds_are_pristine: bool,
143143
) -> datafusion::common::Result<()> {
144144
let dict_array = array.as_any().downcast_ref::<DictionaryArray<K>>().unwrap();
145-
if !first_col {
145+
if !seeds_are_pristine {
146146
// unpack the dictionary array as each row may have a different hash input
147147
let unpacked = take(dict_array.values().as_ref(), dict_array.keys(), None)?;
148148
create_murmur3_hashes(&[unpacked], hashes_buffer)?;
149149
} else {
150-
// For the first column, hash each dictionary value once, and then use
151-
// that computed hash for each key value to avoid a potentially
152-
// expensive redundant hashing for large dictionary elements (e.g. strings)
150+
// Every row still carries the untouched seed, so each distinct dictionary value hashes to
151+
// the same result no matter which row it appears in. Hash each value once and reuse it per
152+
// key, which avoids redundant hashing of large dictionary elements (e.g. strings).
153153
let dict_values = Arc::clone(dict_array.values());
154-
// same initial seed as Spark
155-
let mut dict_hashes = vec![42; dict_values.len()];
154+
// Seed from the buffer rather than assuming Spark's 42: `hash(col, seed)` lets the caller
155+
// choose, and the reuse is only sound if the per-value hashes start from the same seed the
156+
// rows carry. The caller guarantees the buffer is uniform, so any row's value will do.
157+
let seed = hashes_buffer.first().copied().unwrap_or(42);
158+
let mut dict_hashes = vec![seed; dict_values.len()];
156159
create_murmur3_hashes(&[dict_values], &mut dict_hashes)?;
157160
for (hash, key) in hashes_buffer.iter_mut().zip(dict_array.keys().iter()) {
158161
if let Some(key) = key {
@@ -205,6 +208,100 @@ mod tests {
205208
test_hashes_with_nulls!(create_murmur3_hashes, T, values, expected, u32);
206209
}
207210

211+
/// A dictionary array reached through a nested type arrives as the only column of its recursive
212+
/// call, so deciding the dictionary fast path from column position alone treated it as a first
213+
/// column and restarted from the seed, discarding the hash accumulated for earlier elements of
214+
/// the same row. The result differed from the identical decoded data.
215+
#[test]
216+
fn test_dictionary_element_in_list_matches_decoded() {
217+
use arrow::array::{DictionaryArray, Int32Array, ListArray};
218+
use arrow::buffer::OffsetBuffer;
219+
use arrow::datatypes::{Field, Int8Type};
220+
221+
let values: ArrayRef = Arc::new(Int32Array::from(vec![10, 20]));
222+
let keys = arrow::array::Int8Array::from(vec![0i8, 1]);
223+
let dict: ArrayRef = Arc::new(DictionaryArray::<Int8Type>::try_new(keys, values).unwrap());
224+
let decoded: ArrayRef = Arc::new(Int32Array::from(vec![10, 20]));
225+
226+
// One row holding both elements, so the second element's hash chains onto the first.
227+
let as_list = |elems: ArrayRef| -> ArrayRef {
228+
Arc::new(ListArray::new(
229+
Arc::new(Field::new("item", elems.data_type().clone(), true)),
230+
OffsetBuffer::new(vec![0i32, 2].into()),
231+
elems,
232+
None,
233+
))
234+
};
235+
236+
let mut from_dict = vec![42u32; 1];
237+
create_murmur3_hashes(&[as_list(dict)], &mut from_dict).unwrap();
238+
let mut from_decoded = vec![42u32; 1];
239+
create_murmur3_hashes(&[as_list(decoded)], &mut from_decoded).unwrap();
240+
241+
assert_eq!(
242+
from_dict, from_decoded,
243+
"a dictionary-encoded list element must hash like the decoded value"
244+
);
245+
}
246+
247+
/// The fast path must survive for a genuine first column, including one with a caller-supplied
248+
/// seed that is not Spark's 42, since the test for it is that every row is seeded alike.
249+
#[test]
250+
fn test_top_level_dictionary_matches_decoded() {
251+
use arrow::array::{DictionaryArray, Int32Array};
252+
use arrow::datatypes::Int8Type;
253+
254+
let values: ArrayRef = Arc::new(Int32Array::from(vec![10, 20]));
255+
let keys = arrow::array::Int8Array::from(vec![0i8, 1, 0]);
256+
let dict: ArrayRef = Arc::new(DictionaryArray::<Int8Type>::try_new(keys, values).unwrap());
257+
let decoded: ArrayRef = Arc::new(Int32Array::from(vec![10, 20, 10]));
258+
259+
for seed in [42u32, 7u32] {
260+
let mut a = vec![seed; 3];
261+
create_murmur3_hashes(&[Arc::clone(&dict)], &mut a).unwrap();
262+
let mut b = vec![seed; 3];
263+
create_murmur3_hashes(&[Arc::clone(&decoded)], &mut b).unwrap();
264+
assert_eq!(
265+
a, b,
266+
"top-level dictionary must match decoded for seed {seed}"
267+
);
268+
}
269+
}
270+
271+
/// The uniformity check is what makes the fast path safe, and a single-row case cannot pin it:
272+
/// one row is trivially uniform. This hashes several rows whose incoming seeds all differ, so a
273+
/// dictionary first column has to take the unpacking fallback. It also covers a null key and a
274+
/// key pointing at a null dictionary value, since both skip the hash update.
275+
#[test]
276+
fn test_dictionary_with_nonuniform_seeds_matches_decoded() {
277+
use arrow::array::{DictionaryArray, Int32Array};
278+
use arrow::datatypes::Int8Type;
279+
280+
// values[2] is null, and one key is itself null
281+
let values: ArrayRef = Arc::new(Int32Array::from(vec![Some(10), Some(20), None]));
282+
let keys = arrow::array::Int8Array::from(vec![Some(0), Some(1), Some(2), None, Some(0)]);
283+
let dict: ArrayRef = Arc::new(DictionaryArray::<Int8Type>::try_new(keys, values).unwrap());
284+
// The same logical data with the dictionary resolved.
285+
let decoded: ArrayRef = Arc::new(Int32Array::from(vec![
286+
Some(10),
287+
Some(20),
288+
None,
289+
None,
290+
Some(10),
291+
]));
292+
293+
let seeds: Vec<u32> = vec![7, 38, 69, 100, 131];
294+
let mut from_dict = seeds.clone();
295+
create_murmur3_hashes(&[dict], &mut from_dict).unwrap();
296+
let mut from_decoded = seeds;
297+
create_murmur3_hashes(&[decoded], &mut from_decoded).unwrap();
298+
299+
assert_eq!(
300+
from_dict, from_decoded,
301+
"with per-row seeds a dictionary must hash like the decoded array"
302+
);
303+
}
304+
208305
#[test]
209306
fn test_i8() {
210307
test_murmur3_hash::<i8, Int8Array>(

‎native/spark-expr/src/hash_funcs/utils.rs‎

Lines changed: 18 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -576,6 +576,15 @@ macro_rules! create_hashes_internal {
576576
use arrow::array::{types::*, *};
577577

578578
for (i, col) in $arrays.iter().enumerate() {
579+
// The dictionary fast path hashes each distinct dictionary value once and reuses that
580+
// result for every key, which is only valid while every row carries the same incoming
581+
// hash. Position in the column list is not a sufficient test: this macro also runs on
582+
// recursion, where a nested dictionary arrives as the only column of its call even
583+
// though the buffer already holds the hash accumulated for that row -- a
584+
// dictionary-encoded list element, for instance. So confirm the buffer is uniform,
585+
// which keeps the optimisation for a genuine first column (every row seeded alike,
586+
// whatever the seed) and unpacks otherwise. Only dictionaries need this, and the scan
587+
// is measurable on the hot path, so it is deferred into the dictionary arm below.
579588
let first_col = i == 0;
580589
match col.data_type() {
581590
DataType::Boolean => {
@@ -729,7 +738,13 @@ macro_rules! create_hashes_internal {
729738
DataType::Decimal128(_, _) => {
730739
$crate::hash_array_decimal!(Decimal128Array, col, $hashes_buffer, $hash_method);
731740
}
732-
DataType::Dictionary(index_type, _) => match **index_type {
741+
DataType::Dictionary(index_type, _) => {
742+
let first_col = first_col
743+
&& match $hashes_buffer.first() {
744+
None => true,
745+
Some(first) => $hashes_buffer.iter().all(|h| h == first),
746+
};
747+
match **index_type {
733748
DataType::Int8 => {
734749
$create_dictionary_hash_method::<Int8Type>(col, $hashes_buffer, first_col)?;
735750
}
@@ -788,7 +803,8 @@ macro_rules! create_hashes_internal {
788803
col.data_type(),
789804
)))
790805
}
791-
},
806+
}
807+
}
792808
DataType::List(field) => {
793809
let list_array = col.as_any().downcast_ref::<ListArray>().unwrap();
794810
let values = list_array.values();

‎native/spark-expr/src/hash_funcs/xxhash64.rs‎

Lines changed: 61 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -85,19 +85,22 @@ fn spark_compatible_xxhash64<T: AsRef<[u8]>>(data: T, seed: u64) -> u64 {
8585
fn create_xxhash64_hashes_dictionary<K: ArrowDictionaryKeyType>(
8686
array: &ArrayRef,
8787
hashes_buffer: &mut [u64],
88-
first_col: bool,
88+
seeds_are_pristine: bool,
8989
) -> Result<()> {
9090
let dict_array = array.as_any().downcast_ref::<DictionaryArray<K>>().unwrap();
91-
if !first_col {
91+
if !seeds_are_pristine {
9292
let unpacked = take(dict_array.values().as_ref(), dict_array.keys(), None)?;
9393
create_xxhash64_hashes(&[unpacked], hashes_buffer)?;
9494
} else {
9595
// Hash each dictionary value once, and then use that computed
9696
// hash for each key value to avoid a potentially expensive
9797
// redundant hashing for large dictionary elements (e.g. strings)
9898
let dict_values = Arc::clone(dict_array.values());
99-
// same initial seed as Spark
100-
let mut dict_hashes = vec![42u64; dict_values.len()];
99+
// Seed from the buffer rather than assuming Spark's 42: `xxhash64(col, seed)` lets the
100+
// caller choose, and the reuse is only sound if the per-value hashes start from the same
101+
// seed the rows carry. The caller guarantees the buffer is uniform.
102+
let seed = hashes_buffer.first().copied().unwrap_or(42u64);
103+
let mut dict_hashes = vec![seed; dict_values.len()];
101104
create_xxhash64_hashes(&[dict_values], &mut dict_hashes)?;
102105

103106
for (hash, key) in hashes_buffer.iter_mut().zip(dict_array.keys().iter()) {
@@ -151,6 +154,60 @@ mod tests {
151154
test_hashes_with_nulls!(create_xxhash64_hashes, T, values, expected, u64);
152155
}
153156

157+
/// The dictionary fast path is shared in shape with murmur3, so it has the same requirement:
158+
/// a dictionary reached through a nested type must not restart from the seed.
159+
#[test]
160+
fn test_dictionary_element_in_list_matches_decoded() {
161+
use arrow::array::{DictionaryArray, ListArray};
162+
use arrow::buffer::OffsetBuffer;
163+
use arrow::datatypes::{Field, Int8Type};
164+
165+
let values: ArrayRef = Arc::new(Int32Array::from(vec![10, 20]));
166+
let keys = arrow::array::Int8Array::from(vec![0i8, 1]);
167+
let dict: ArrayRef = Arc::new(DictionaryArray::<Int8Type>::try_new(keys, values).unwrap());
168+
let decoded: ArrayRef = Arc::new(Int32Array::from(vec![10, 20]));
169+
170+
let as_list = |elems: ArrayRef| -> ArrayRef {
171+
Arc::new(ListArray::new(
172+
Arc::new(Field::new("item", elems.data_type().clone(), true)),
173+
OffsetBuffer::new(vec![0i32, 2].into()),
174+
elems,
175+
None,
176+
))
177+
};
178+
179+
let mut from_dict = vec![42u64; 1];
180+
create_xxhash64_hashes(&[as_list(dict)], &mut from_dict).unwrap();
181+
let mut from_decoded = vec![42u64; 1];
182+
create_xxhash64_hashes(&[as_list(decoded)], &mut from_decoded).unwrap();
183+
assert_eq!(from_dict, from_decoded);
184+
}
185+
186+
/// Companion to the murmur3 test: per-row seeds force the unpacking fallback here too.
187+
#[test]
188+
fn test_dictionary_with_nonuniform_seeds_matches_decoded() {
189+
use arrow::array::DictionaryArray;
190+
use arrow::datatypes::Int8Type;
191+
192+
let values: ArrayRef = Arc::new(Int32Array::from(vec![Some(10), Some(20), None]));
193+
let keys = arrow::array::Int8Array::from(vec![Some(0), Some(1), Some(2), None, Some(0)]);
194+
let dict: ArrayRef = Arc::new(DictionaryArray::<Int8Type>::try_new(keys, values).unwrap());
195+
let decoded: ArrayRef = Arc::new(Int32Array::from(vec![
196+
Some(10),
197+
Some(20),
198+
None,
199+
None,
200+
Some(10),
201+
]));
202+
203+
let seeds: Vec<u64> = vec![7, 38, 69, 100, 131];
204+
let mut from_dict = seeds.clone();
205+
create_xxhash64_hashes(&[dict], &mut from_dict).unwrap();
206+
let mut from_decoded = seeds;
207+
create_xxhash64_hashes(&[decoded], &mut from_decoded).unwrap();
208+
assert_eq!(from_dict, from_decoded);
209+
}
210+
154211
#[test]
155212
fn test_i8() {
156213
test_xxhash64_hash::<i8, Int8Array>(

0 commit comments

Comments
 (0)