[
https://issues.apache.org/jira/browse/SPARK-58677?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Nathan Holland updated SPARK-58677:
-----------------------------------
Description:
This ticket expands on SPARK-45900, to explicitly mention the desire for a
BINARY return type for xxhash3_128 as well as additional functionality that a
modern hashing algorithm on Spark could implement. (such as deterministic
support for complex types)
The original intent of that ticket was to capture a new hashing model through
XXH3 that allowed for high performance hashing using XXH3 with the API of the
earlier XXHash64 hash family, rather than some of the cryptographic hash
functions (SHA/MD5 etc)
h2. Return Type
One difference in this model I am proposing - SPARK-45900 has been resolved by
returning a string, which is more consistent with the older hashing models.
When writing SPARK-45900 I mentioned that this was a downside of the existing
SHA models, to clarifify - returning a STRING type has heavier overhead and
prevents future optimisations that occur by allowing HotSpot (and C
interpreters like Photon) to take advantage of SIMD instructions. Furthermore
I've been experimenting with expanding the BINARY type to have fixed byte types
and have seen some promising performance increases that may be useful at a
later date.
As XXH3 was built specifically around SIMD instructions to provide speed ups
over XXHash64 and Spark 4.4 is not out yet, I believe now would be the time to
discuss what this API should return - and either choose with a seperate API
that returns the BINARY 128 bytes or make the change to the solution of
SPARK-45900 to return a BINARY type by default and let users use the "hex"
function if they want the result as a Binary String. I'd propose that if we
preserve the hex functionality we suffix it as _hex, which allows us to split
up the raw bytes and the friendlier strings if required.
You can see a few instances that return bytes[]/unsigned 128 ints or hex
specific variants below, so I believe there is presidence
* [https://duckdb.org/community_extensions/extensions/hashfuncs] (duckdb
communit hashfuncs sporting *xxh3_128* and {*}xxh3_128_hex{*}) *- I think this
is the best method to allow for a hex code when needed, while still allowing a
byte[] for performance and compact storage when needed.*
*
[https://clickhouse.com/docs/reference/functions/regular-functions/hash-functions#xxh3_128]
(Clickhouse definition 128 unsigned int which without native support is
approximately equivalent to a byte[128])
*
[https://learn.microsoft.com/en-us/dotnet/api/system.io.hashing.xxhash128.hash?view=net-11.0-pp#system-io-hashing-xxhash128-hash(system-byte())]
(C# implementation returning byte[128])
* [https://github.com/Cyan4973/xxHash/blob/dev/xxhash.h#L1378] (the reference
using two long's within a struct, technically we could return a struct with a
high and a low long like this, but I would worry about allocations until
Valhalla drops and I feel like byte[128] is probably a better fit anyway)
To summarise this would create a simplified function base like the below,
allowing for some good performance uplift with xxh3_128 in future through
Vectorisation, while xxh3_128_hex is still there for people who prefer human
readable values / want a drop in replacement for the likes of MD5 without
wrapping it in a hex() string.
* xxh3_64(...) -> BIGINT
* xxh3_128(...) -> 16-byte BINARY
* xxh3_128_hex(...) -> 32-character lowercase STRING{{{{}}{}}}
h2. XXHash64 Style Hash API
One of the benefits that made me open the original ticket is the feedback from
customers that one of xxhash64's benefits from an API perspective is the simple
API to support multiple columns which conceptually allow the hashing of columns
by passing them in natively without having to implement brittle solutions
(often something like concat_ws or to_json) to hash data that spans columns. I
believe an expansion to the functionality to SPARK-45900 to support columns
would allow XXH3 to be seen successor to the XXHash64 function with this user
friendly API - while keeping all the semantics that a unitary function would
support - including byte compatibility with the original C reference code.
One of the downsides to the XXHash64 API is that it doesn't natively support
types of datatypes like Variant Types (common in Bronze Zone) and Maps
(occasionally used when importing from JSON, requiring hash algorithms to
handle their unordered nature) - and don't handle null values well at all. I've
come up with a heavily tested way to deterministically provide this XXHash64
style API across a multitude of types to really minimise the amount of
boilerplate that would need to be run (often with various types of performance
overheads or bugs). I've seperated this hashing method out slightly because I
feel like breaking the existing hashing logic to "fix" it, would be too much of
a breaking change, but XXH3 as a new interface can take on these improved fixes
- leaving any changes to xxhash64 logic to a major version change if it comes
to it.
h2. Proposal Codebase
My current codebase can be found here for a proposed implementation of the
above two key changes (better support for hashing data types and multiple
columns, and the return of a binary type which better captures the hash results
rather than a string). Note that I am currently working on supporting the
*_hex* function, once that is done i'll update the hash below.
*
[https://github.com/NathanNZ/spark/commit/d4317b9853a9b1f775c1ab11534dc8ea5a048040]
* I've also got a work in progress solution with pre-built containers to test
the functionality.
** [https://github.com/NathanNZ/spark-nathan-containers]
Links:
- https://issues.apache.org/jira/browse/SPARK-45900 (Original SPARK-45900
ticket)
was:
This ticket expands on SPARK-45900, to explicitly mention the desire for a
BINARY return type for xxhash3_128 as well as additional functionality that a
modern hashing algorithm on Spark could implement. (such as deterministic
support for complex types)
The original intent of that ticket was to capture a new hashing model through
XXH3 that allowed for high performance hashing using XXH3 with the API of the
earlier XXHash64 hash family, rather than some of the cryptographic hash
functions (SHA/MD5 etc)
h2. Return Type
One difference in this model I am proposing - SPARK-45900 has been resolved by
returning a string, which is more consistent with the older hashing models.
When writing SPARK-45900 I mentioned that this was a downside of the existing
SHA models, to clarifify - returning a STRING type has heavier overhead and
prevents future optimisations that occur by allowing HotSpot (and C
interpreters like Photon) to take advantage of SIMD instructions. Furthermore
I've been experimenting with expanding the BINARY type to have fixed byte types
and have seen some promising performance increases that may be useful at a
later date.
As XXH3 was built specifically around SIMD instructions to provide speed ups
over XXHash64 and Spark 4.4 is not out yet, I believe now would be the time to
discuss what this API should return - and either choose with a seperate API
that returns the BINARY 128 bytes or make the change to the solution of
SPARK-45900 to return a BINARY type by default and let users use the "hex"
function if they want the result as a Binary String. I'd propose that if we
preserve the hex functionality we suffix it as _hex, which allows us to split
up the raw bytes and the friendlier strings if required.
You can see a few instances that return bytes[]/unsigned 128 ints or hex
specific variants below, so I believe there is presidence
* [https://duckdb.org/community_extensions/extensions/hashfuncs] (duckdb
communit hashfuncs sporting *xxh3_128* and {*}xxh3_128_hex{*}) *- I think this
is the best method to allow for a hex code when needed, while still allowing a
byte[] for performance and compact storage when needed.*
*
[https://clickhouse.com/docs/reference/functions/regular-functions/hash-functions#xxh3_128]
(Clickhouse definition 128 unsigned int which without native support is
approximately equivalent to a byte[128])
*
[https://learn.microsoft.com/en-us/dotnet/api/system.io.hashing.xxhash128.hash?view=net-11.0-pp#system-io-hashing-xxhash128-hash(system-byte())]
(C# implementation returning byte[128])
* [https://github.com/Cyan4973/xxHash/blob/dev/xxhash.h#L1378] (the reference
using two long's within a struct, technically we could return a struct with a
high and a low long like this, but I would worry about allocations until
Valhalla drops and I feel like byte[128] is probably a better fit anyway)
To summarise this would create a simplified function base like the below,
allowing for some good performance uplift with xxh3_128 in future through
Vectorisation, while xxh3_128_hex is still there for people who prefer human
readable values / want a drop in replacement for the likes of MD5 without
wrapping it in a hex() string.
* xxh3_64(...) -> BIGINT
* xxh3_128(...) -> 16-byte BINARY
* xxh3_128_hex(...) -> 32-character lowercase STRING{{{}{}}}
h2. XXHash64 Style Hash API
I have heard from customers that one of xxhash64's benefits is the simple API
to support multiple columns which conceptually allow the hashing of columns by
passing them in natively without having to implement brittle solutions (often
something like concat_ws) to hash data. I believe an expansion to the
functionality to SPARK-45900 to support columns would allow XXH3 to be seen
successor to the XXHash64 function with this user friendly API - while keeping
all the semantics that a unitary function would support - including byte
compatability with the original C reference code.
h2. Proposal Codebase
My current codebase can be found here for a proposed implementation of the
above two key changes (better support for hashing data types and multiple
columns, and the return of a binary type which better captures the hash results
rather than a string). Note that I am currently working on supporting the
*_hex* function, once that is done i'll update the hash below.
*
[https://github.com/NathanNZ/spark/commit/d4317b9853a9b1f775c1ab11534dc8ea5a048040]
* I've also got a work in progress solution with pre-built containers to test
the functionality.
** [https://github.com/NathanNZ/spark-nathan-containers]
Links:
- https://issues.apache.org/jira/browse/SPARK-45900 (Original SPARK-45900
ticket)
> Expand hash functionalities of XXH3 to better match XXHash64
> ------------------------------------------------------------
>
> Key: SPARK-58677
> URL: https://issues.apache.org/jira/browse/SPARK-58677
> Project: Spark
> Issue Type: Improvement
> Components: PySpark, SQL
> Affects Versions: 4.4.0
> Reporter: Nathan Holland
> Priority: Major
>
> This ticket expands on SPARK-45900, to explicitly mention the desire for a
> BINARY return type for xxhash3_128 as well as additional functionality that a
> modern hashing algorithm on Spark could implement. (such as deterministic
> support for complex types)
> The original intent of that ticket was to capture a new hashing model through
> XXH3 that allowed for high performance hashing using XXH3 with the API of the
> earlier XXHash64 hash family, rather than some of the cryptographic hash
> functions (SHA/MD5 etc)
> h2. Return Type
> One difference in this model I am proposing - SPARK-45900 has been resolved
> by returning a string, which is more consistent with the older hashing
> models. When writing SPARK-45900 I mentioned that this was a downside of the
> existing SHA models, to clarifify - returning a STRING type has heavier
> overhead and prevents future optimisations that occur by allowing HotSpot
> (and C interpreters like Photon) to take advantage of SIMD instructions.
> Furthermore I've been experimenting with expanding the BINARY type to have
> fixed byte types and have seen some promising performance increases that may
> be useful at a later date.
> As XXH3 was built specifically around SIMD instructions to provide speed ups
> over XXHash64 and Spark 4.4 is not out yet, I believe now would be the time
> to discuss what this API should return - and either choose with a seperate
> API that returns the BINARY 128 bytes or make the change to the solution of
> SPARK-45900 to return a BINARY type by default and let users use the "hex"
> function if they want the result as a Binary String. I'd propose that if we
> preserve the hex functionality we suffix it as _hex, which allows us to split
> up the raw bytes and the friendlier strings if required.
> You can see a few instances that return bytes[]/unsigned 128 ints or hex
> specific variants below, so I believe there is presidence
> * [https://duckdb.org/community_extensions/extensions/hashfuncs] (duckdb
> communit hashfuncs sporting *xxh3_128* and {*}xxh3_128_hex{*}) *- I think
> this is the best method to allow for a hex code when needed, while still
> allowing a byte[] for performance and compact storage when needed.*
> *
> [https://clickhouse.com/docs/reference/functions/regular-functions/hash-functions#xxh3_128]
> (Clickhouse definition 128 unsigned int which without native support is
> approximately equivalent to a byte[128])
> *
> [https://learn.microsoft.com/en-us/dotnet/api/system.io.hashing.xxhash128.hash?view=net-11.0-pp#system-io-hashing-xxhash128-hash(system-byte())]
> (C# implementation returning byte[128])
> * [https://github.com/Cyan4973/xxHash/blob/dev/xxhash.h#L1378] (the
> reference using two long's within a struct, technically we could return a
> struct with a high and a low long like this, but I would worry about
> allocations until Valhalla drops and I feel like byte[128] is probably a
> better fit anyway)
> To summarise this would create a simplified function base like the below,
> allowing for some good performance uplift with xxh3_128 in future through
> Vectorisation, while xxh3_128_hex is still there for people who prefer human
> readable values / want a drop in replacement for the likes of MD5 without
> wrapping it in a hex() string.
> * xxh3_64(...) -> BIGINT
> * xxh3_128(...) -> 16-byte BINARY
> * xxh3_128_hex(...) -> 32-character lowercase STRING{{{{}}{}}}
> h2. XXHash64 Style Hash API
> One of the benefits that made me open the original ticket is the feedback
> from customers that one of xxhash64's benefits from an API perspective is the
> simple API to support multiple columns which conceptually allow the hashing
> of columns by passing them in natively without having to implement brittle
> solutions (often something like concat_ws or to_json) to hash data that spans
> columns. I believe an expansion to the functionality to SPARK-45900 to
> support columns would allow XXH3 to be seen successor to the XXHash64
> function with this user friendly API - while keeping all the semantics that a
> unitary function would support - including byte compatibility with the
> original C reference code.
> One of the downsides to the XXHash64 API is that it doesn't natively support
> types of datatypes like Variant Types (common in Bronze Zone) and Maps
> (occasionally used when importing from JSON, requiring hash algorithms to
> handle their unordered nature) - and don't handle null values well at all.
> I've come up with a heavily tested way to deterministically provide this
> XXHash64 style API across a multitude of types to really minimise the amount
> of boilerplate that would need to be run (often with various types of
> performance overheads or bugs). I've seperated this hashing method out
> slightly because I feel like breaking the existing hashing logic to "fix" it,
> would be too much of a breaking change, but XXH3 as a new interface can take
> on these improved fixes - leaving any changes to xxhash64 logic to a major
> version change if it comes to it.
> h2. Proposal Codebase
> My current codebase can be found here for a proposed implementation of the
> above two key changes (better support for hashing data types and multiple
> columns, and the return of a binary type which better captures the hash
> results rather than a string). Note that I am currently working on supporting
> the *_hex* function, once that is done i'll update the hash below.
> *
> [https://github.com/NathanNZ/spark/commit/d4317b9853a9b1f775c1ab11534dc8ea5a048040]
> * I've also got a work in progress solution with pre-built containers to
> test the functionality.
> ** [https://github.com/NathanNZ/spark-nathan-containers]
>
> Links:
> - https://issues.apache.org/jira/browse/SPARK-45900 (Original SPARK-45900
> ticket)
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
