viirya opened a new issue, #5756:
URL: https://github.com/apache/datafusion-comet/issues/5756
### Describe the bug
A dictionary-encoded value hashes differently from the identical decoded
value when it is
reached through a nested type, so two rows holding the same logical data get
different
hashes.
`create_hashes_internal!` decides the dictionary fast path from the column's
position:
```rust
for (i, col) in $arrays.iter().enumerate() {
let first_col = i == 0;
```
and `create_hashes_dictionary` uses that to hash each distinct dictionary
value once and
reuse it per key, starting from the seed:
```rust
if !first_col {
let unpacked = take(dict_array.values().as_ref(), dict_array.keys(),
None)?;
create_murmur3_hashes(&[unpacked], hashes_buffer)?;
} else {
let mut dict_hashes = vec![42; dict_values.len()]; // restarts from
the seed
```
That reuse is only sound when every row still carries the same incoming
hash. But this
macro also runs on recursion: a dictionary nested in a list, struct or map
arrives as the
*only* column of its recursive call, so `i == 0` is true even though the
buffer already
holds the hash accumulated for earlier elements of that row. The accumulated
hash is then
discarded and the element is hashed from the seed.
Two separate problems, both in the `else` branch:
1. **Nested dictionaries lose the running hash** (the bug above).
2. **The seed is hardcoded to 42**, so even a genuine first column is wrong
when the caller
supplies a different seed, as `hash(col, seed)` and `xxhash64(col, seed)`
allow.
Both apply to murmur3 and xxhash64, which share this structure.
For a shuffle partitioning key this means equal keys can land in different
partitions,
breaking grouping and joins. It also affects the `hash()` and `xxhash64()`
SQL functions.
### Steps to reproduce
A dictionary as a list element, against the decoded equivalent:
```rust
let values: ArrayRef = Arc::new(Int32Array::from(vec![10, 20]));
let keys = Int8Array::from(vec![0i8, 1]);
let dict: ArrayRef = Arc::new(DictionaryArray::<Int8Type>::try_new(keys,
values).unwrap());
let decoded: ArrayRef = Arc::new(Int32Array::from(vec![10, 20]));
// one row holding both elements, so the second chains onto the first
let as_list = |elems: ArrayRef| -> ArrayRef { /* ListArray with offsets [0,
2] */ };
let mut a = vec![42u32; 1];
create_murmur3_hashes(&[as_list(dict)], &mut a).unwrap(); // 3853467749
let mut b = vec![42u32; 1];
create_murmur3_hashes(&[as_list(decoded)], &mut b).unwrap(); // 1401423033
```
For the hardcoded seed, a plain top-level dictionary column with seed 7 also
disagrees with
its decoded form.
Note what is *not* affected: a top-level dictionary as the first column with
seed 42 is
correct (the seed really is 42), and a dictionary as a later column is
correct (it takes the
`!first_col` branch, which unpacks and recurses properly). Nesting is what
triggers it.
### Expected behavior
Hashing dictionary-encoded data should give the same result as hashing the
decoded data, at
any nesting depth and for any seed.
### Additional context
Found while reviewing nested hash partitioning keys (#5567), which makes
this reachable from
shuffle partitioning, but the defect predates that change and reproduces on
`main` with no
configuration changes -- the `hash()` path over a nested dictionary column
hits it too.
Credit to Codex for spotting it, via an independent leaf-by-leaf chaining
oracle rather than
a batch-versus-per-row comparison, which cannot catch a bug both sides share.
--
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]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
