viirya opened a new issue, #5777:
URL: https://github.com/apache/datafusion-comet/issues/5777
## Is your feature request related to a problem or challenge?
Hashing `array<struct<..>>` is far slower than the amount of data justifies.
With the `hash`
benchmark on main, 8192 rows of ten struct elements each takes about 10.2
ms, while the same
element count as `array<int32>` takes 146 µs.
The cause is in `hash_list_array!`, the fallback for a list whose elements
are not primitives.
For every element it slices a one-element Arrow array and re-enters the hash
dispatch for it:
```rust
for elem_idx in 0..len {
let elem_array = values.slice(start + elem_idx, 1);
let mut single_hash = [*hash];
$recursive_hash_method(&[elem_array], &mut single_hash)?;
*hash = single_hash[0];
}
```
So each element costs an Arrow array allocation plus a full type match, and
a list of primitives
avoids both by going through a vectorized path instead.
This is the shape behind
`spark.comet.shuffle.native.partitioning.hash.nested.enabled`
defaulting to off in #5567: with the config on, `array<struct<int, string>>`
as a shuffle
partitioning key measured 561 ms against 164 ms for letting Spark do the
whole shuffle, so
using it was a loss.
## Describe the solution you'd like
Spark chains the element hashes in order, so the elements of one row have to
be hashed in
sequence, but the allocation and dispatch do not have to happen per element.
Hashing one element
per row at a time, seeded with each row's running hash, gives the same
values while dropping the
number of dispatches from the total element count to the length of the
longest list.
Two details that matter for that to be a win everywhere rather than a trade:
- Carrying the surviving rows forward instead of rescanning the batch each
pass, since otherwise
the scheduling cost is rows x longest-list, which is almost entirely
wasted when one list is
much longer than the rest.
- Taking a simpler walk when every row is non-null with the same length,
since no row drops out
early there and the bookkeeping would be pure overhead.
## Describe alternatives you've considered
Leaving the config off, which is the status quo. That keeps a supported
nested type unusable as
a partitioning key for the shape most likely to appear in practice.
Special-casing the string child, or hashing fields directly at gathered
indices without
materializing, would go further but means making the whole hash dispatch
index-aware; that macro
is shared by murmur3 and xxhash64 and its correctness decides partition
assignment, so it is a
much wider change.
## Additional context
The hash values must not change, since they decide which partition a row
lands in.
--
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]
