mbutrovich commented on code in PR #68: URL: https://github.com/apache/datafusion-spark/pull/68#discussion_r4602344540
########## crates/sqllogictest/test_files/hash/hash.slt: ########## @@ -0,0 +1,586 @@ +# SPDX-License-Identifier: Apache-2.0 +# SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership +# SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements + +# Tests for Spark-compatible hash (32-bit Murmur3, seed 42) +# Reference: https://spark.apache.org/docs/latest/api/sql/index.html#hash +# Expected values were checked against Spark 4.2.0 (PySpark). + +# Int32 + +query I +SELECT hash(arrow_cast(1, 'Int32')); +---- +-559580957 + +query I +SELECT hash(arrow_cast(0, 'Int32')); +---- +933211791 + +query I +SELECT hash(arrow_cast(-1, 'Int32')); +---- +-1604776387 + +query I +SELECT hash(arrow_cast(2147483647, 'Int32')); +---- +133916647 + +query I +SELECT hash(arrow_cast(-2147483648, 'Int32')); +---- +723455942 + +# Int64 + +query I +SELECT hash(arrow_cast(1, 'Int64')); +---- +-1712319331 + +query I +SELECT hash(arrow_cast(0, 'Int64')); +---- +-1670924195 + +query I +SELECT hash(arrow_cast(-1, 'Int64')); +---- +-939490007 + +query I +SELECT hash(arrow_cast(9223372036854775807, 'Int64')); +---- +-1604625029 + +query I +SELECT hash(arrow_cast(-9223372036854775808, 'Int64')); +---- +-853646085 + +# Float64: -0.0 hashes like 0.0 + +query I +SELECT hash(arrow_cast(1.0, 'Float64')); +---- +-460888942 + +query I +SELECT hash(arrow_cast(0.0, 'Float64')); +---- +-1670924195 + +query I +SELECT hash(arrow_cast(-0.0, 'Float64')); +---- +-1670924195 + +query I +SELECT hash(arrow_cast(-1.0, 'Float64')); +---- +332927831 + +# Float32: -0.0 hashes like 0.0 + +query I +SELECT hash(arrow_cast(1.0, 'Float32')); +---- +-466301895 + +query I +SELECT hash(arrow_cast(0.0, 'Float32')); +---- +933211791 + +query I +SELECT hash(arrow_cast(-0.0, 'Float32')); +---- +933211791 + +query I +SELECT hash(arrow_cast(-1.0, 'Float32')); +---- +-603084565 + +# Strings: every tail length, multi-byte UTF-8 + +query I +SELECT hash('hello'); +---- +-1008564952 + +query I +SELECT hash('bar'); +---- +-1808790533 + +query I +SELECT hash(''); +---- +142593372 + +query I +SELECT hash('a'); +---- +1485273170 + +query I +SELECT hash('ab'); +---- +-97053317 + +query I +SELECT hash('abc'); +---- +1322437556 + +query I +SELECT hash('abcd'); +---- +-396302900 + +query I +SELECT hash('abcde'); +---- +814637928 + +query I +SELECT hash('😁'); +---- +885025535 + +query I +SELECT hash('天地'); +---- +-1899966402 + +# NULL leaves the seed (42) unchanged; the result is never NULL +query I +SELECT hash(NULL); +---- +42 + +query I +SELECT hash(arrow_cast(NULL, 'Int32')); +---- +42 + +# NULL arguments are skipped when hashing several columns +query B +SELECT hash(1, NULL) = hash(1); +---- +true + +query B +SELECT hash(NULL, 1) = hash(1); +---- +true + +# Arguments chain: the hash of the previous argument seeds the next +query B +SELECT hash(1, 2) = hash(2, 1); +---- +false + +# Spark's documented example; DataFusion types 123 and 2 as BIGINT, Spark as INT +query I +SELECT hash('Spark', [CAST(123 AS INT)], CAST(2 AS INT)); +---- +-1321691492 + +query I +SELECT hash('Spark', [CAST(123 AS INT)]); +---- +1262264271 + +# Hashing several arguments equals hashing a struct of them +query I +SELECT hash(CAST(1 AS INT), 'x'); +---- +-1305545736 + +# Decimals with precision <= 18 hash as the unscaled long + +query I +SELECT hash(CAST(123.45 AS DECIMAL(10, 2))); +---- +1416086240 + +query I +SELECT hash(CAST(-123.45 AS DECIMAL(10, 2))); +---- +-1959512858 + +# Decimals with precision > 18 hash the minimal big-endian two's complement +# bytes of the unscaled value (Java's BigInteger.toByteArray) + +query I +SELECT hash(CAST(1 AS DECIMAL(20, 0))); +---- +-386724586 + +query I +SELECT hash(CAST(0 AS DECIMAL(20, 0))); +---- +-783713497 + +query I +SELECT hash(CAST(-1 AS DECIMAL(20, 0))); +---- +1398487324 + +# 127 and -128 fit in one byte; 128 and -129 need a leading sign byte +query I +SELECT hash(CAST(127 AS DECIMAL(20, 0))); +---- +1185089389 + +query I +SELECT hash(CAST(128 AS DECIMAL(20, 0))); +---- +-544401882 + +query I +SELECT hash(CAST(-128 AS DECIMAL(20, 0))); +---- +775851899 + +query I +SELECT hash(CAST(-129 AS DECIMAL(20, 0))); +---- +-771458971 + +query I +SELECT hash(CAST(1.5 AS DECIMAL(20, 1))); +---- +-357711666 + +query I +SELECT hash(CAST('12345678901234567890.1234567890' AS DECIMAL(38, 10))); +---- +269448356 + +query I +SELECT hash(CAST('-12345678901234567890.1234567890' AS DECIMAL(38, 10))); +---- +694017569 + +query I +SELECT hash(CAST('99999999999999999999999999999999999999' AS DECIMAL(38, 0))); +---- +-817514053 + +query I +SELECT hash(CAST('-99999999999999999999999999999999999999' AS DECIMAL(38, 0))); +---- +1400911110 + +query I +SELECT hash(CAST(NULL AS DECIMAL(20, 0))); +---- +42 + +# Lists hash each element in order, chaining the running hash; NULL elements +# are skipped and an empty or NULL list leaves the seed unchanged + +query I +SELECT hash([CAST(1 AS INT), CAST(2 AS INT), CAST(3 AS INT)]); +---- +-912918097 + +query I +SELECT hash([1, 2, 3]); +---- +1045631400 + +query I +SELECT hash(['a', 'b']); +---- +190734147 + +query I +SELECT hash([CAST(1 AS INT), NULL, CAST(3 AS INT)]); +---- +1066699649 + +query I +SELECT hash(arrow_cast([], 'List(Int32)')); +---- +42 + +query I +SELECT hash(arrow_cast(NULL, 'List(Int32)')); +---- +42 + +query I +SELECT hash([CAST(1 AS DECIMAL(20, 0)), CAST(-129 AS DECIMAL(20, 0))]); +---- +-265473650 + +query I +SELECT hash([CAST(123.45 AS DECIMAL(10, 2))]); +---- +1416086240 + +# Nested lists flatten into the same chain as a flat list +query I +SELECT hash([[CAST(1 AS INT)], [CAST(2 AS INT), CAST(3 AS INT)]]); +---- +-912918097 + +# Structs hash each field in order; NULL fields are skipped + +query I +SELECT hash(named_struct('a', CAST(1 AS INT), 'b', 'x')); +---- +-1305545736 + +query I +SELECT hash(named_struct('a', CAST(1 AS INT), 'b', CAST(NULL AS VARCHAR))); +---- +-559580957 + +query I +SELECT hash(named_struct('a', CAST(1 AS DECIMAL(20, 0)))); +---- +-386724586 + +# Maps hash each key then its value, entry by entry. Spark 4.2.0 rejects hash on +# maps by default (DATATYPE_MISMATCH.HASH_MAP_TYPE); these values are from Spark +# with spark.sql.legacy.allowHashOnMapType=true. + +query I +SELECT hash(map([CAST(1 AS INT), CAST(2 AS INT)], ['a', 'b'])); +---- +-1706464220 + +query I +SELECT hash(map(['a'], [CAST(1 AS INT)])); +---- +532252686 + +# Dictionary-encoded values hash like their decoded values + +query I +SELECT hash(arrow_cast('hello', 'Dictionary(Int32, Utf8)')); +---- +-1008564952 + +query I +SELECT hash(arrow_cast(CAST(1 AS INT), 'Dictionary(Int8, Int32)')); +---- +-559580957 + +query I +SELECT hash(arrow_cast(column1, 'Dictionary(Int32, Utf8)')) +FROM VALUES ('hello'), ('bar'), (NULL), ('hello'); +---- +-1008564952 +-1808790533 +42 +-1008564952 + +# A dictionary after another argument is seeded per row by the running hash +query I +SELECT hash(CAST(1 AS INT), arrow_cast(column1, 'Dictionary(Int32, Utf8)')) +FROM VALUES ('x'), ('x'); +---- +-1305545736 +-1305545736 + +# Booleans hash as INT 1 or 0 + +query I +SELECT hash(true); +---- +-559580957 + +query I +SELECT hash(false); +---- +933211791 + +# TINYINT and SMALLINT widen to INT before hashing + +query I +SELECT hash(CAST(1 AS TINYINT)); +---- +-559580957 + +query I +SELECT hash(CAST(0 AS TINYINT)); +---- +933211791 + +query I +SELECT hash(CAST(-1 AS TINYINT)); +---- +-1604776387 + +query I +SELECT hash(CAST(127 AS TINYINT)); +---- +1135925485 + +query I +SELECT hash(CAST(-128 AS TINYINT)); +---- +1110053733 + +query I +SELECT hash(CAST(1 AS SMALLINT)); +---- +-559580957 + +query I +SELECT hash(CAST(-1 AS SMALLINT)); +---- +-1604776387 + +query I +SELECT hash(CAST(32767 AS SMALLINT)); +---- +1249274084 + +query I +SELECT hash(CAST(-32768 AS SMALLINT)); +---- +-1871935946 + +# LargeUtf8 and Utf8View hash like Utf8 + +query I +SELECT hash(arrow_cast('hello', 'LargeUtf8')); +---- +-1008564952 + +query I +SELECT hash(arrow_cast('hello', 'Utf8View')); +---- +-1008564952 + +# Binary hashes its bytes + +query I +SELECT hash(X'0102'); +---- +1964783052 + +# Dates hash as INT days since the epoch; Date64 (milliseconds) is floored to days + +query I +SELECT hash(DATE '2020-01-01'); +---- +-725858435 + +query I +SELECT hash(arrow_cast(DATE '2020-01-01', 'Date64')); +---- +-725858435 + +query I +SELECT hash(arrow_cast(-1, 'Date64')); +---- +-1604776387 + +# Timestamps hash as BIGINT microseconds since the epoch, whatever the Arrow unit. +# DataFusion's TIMESTAMP literals are nanoseconds. Spark values are with +# spark.sql.session.timeZone=UTC. + +query I +SELECT hash(TIMESTAMP '2020-01-01 00:00:00'); +---- +-1486022740 + +query I +SELECT hash(arrow_cast(TIMESTAMP '2020-01-01 00:00:00', 'Timestamp(Second, None)')); +---- +-1486022740 + +query I +SELECT hash(arrow_cast(TIMESTAMP '2020-01-01 00:00:00', 'Timestamp(Millisecond, None)')); +---- +-1486022740 + +query I +SELECT hash(arrow_cast(TIMESTAMP '2020-01-01 00:00:00', 'Timestamp(Microsecond, None)')); +---- +-1486022740 + +query I +SELECT hash(arrow_cast(TIMESTAMP '2020-01-01 00:00:00', 'Timestamp(Nanosecond, Some("UTC"))')); +---- +-1486022740 + +query I +SELECT hash([TIMESTAMP '2020-01-01 00:00:00']); +---- +-1486022740 + +# -1 ns floors to -1 us (Spark: timestamp_micros(-1)); -1 s is -1000000 us +query I +SELECT hash(arrow_cast(-1, 'Timestamp(Nanosecond, None)')); +---- +-939490007 + +query I +SELECT hash(arrow_cast(-1, 'Timestamp(Second, None)')); +---- +346627249 + +# Every NaN hashes like the canonical NaN; negating NaN flips its sign bit + +query I +SELECT hash(CAST('NaN' AS DOUBLE)); +---- +-1281358385 + +query I +SELECT hash(-CAST('NaN' AS DOUBLE)); +---- +-1281358385 + +query I +SELECT hash(CAST('NaN' AS FLOAT)); +---- +-349261430 + +query I +SELECT hash(-CAST('NaN' AS FLOAT)); +---- +-349261430 + +query I +SELECT hash([CAST('NaN' AS DOUBLE), -CAST('NaN' AS DOUBLE)]); +---- +1050078426 + +query I +SELECT hash([-CAST('NaN' AS FLOAT)]); +---- +-349261430 + +# Table data (VALUES integers are Int64, which hash as 8 bytes) +statement ok +CREATE TABLE hash_t AS VALUES (1, 'hello'), (NULL, 'bar'), (0, NULL); + +query I +SELECT hash(column1) FROM hash_t; +---- +-1712319331 +42 +-1670924195 + +query I +SELECT hash(column2) FROM hash_t; +---- +-1008564952 +-1808790533 +42 Review Comment: The only column inputs here are integers, strings, and dictionaries. Lists, structs, and maps are only tested as literals, so the `.slt` file never takes their null-aware loops (a NULL list, struct, or map row next to non-NULL rows). Could we add cases like these? The values come from Spark 4.2.0 with INT columns, and they pass on this branch: ``` # Column inputs with NULL rows, which take the null-aware loops query I SELECT hash(column1) FROM (VALUES ([CAST(1 AS INT), CAST(2 AS INT)]), (NULL), ([NULL, CAST(3 AS INT)]), (arrow_cast([], 'List(Int32)'))); ---- -222940379 42 -1823081949 42 query I SELECT hash(column1) FROM (VALUES ([[CAST(1 AS INT), CAST(2 AS INT)], [CAST(3 AS INT)]]), ([arrow_cast(NULL, 'List(Int32)')]), (NULL)); ---- -912918097 42 42 query I SELECT hash(CASE WHEN i = 2 THEN NULL ELSE named_struct('a', i, 'b', CAST(i AS VARCHAR)) END) FROM (SELECT CAST(column1 AS INT) AS i FROM (VALUES (1), (2), (3))); ---- -1161632238 42 2015795020 query I SELECT hash(CASE WHEN i = 2 THEN NULL ELSE map([i], [CAST(i AS VARCHAR)]) END) FROM (SELECT CAST(column1 AS INT) AS i FROM (VALUES (1), (2), (3))); ---- -1161632238 42 2015795020 ``` ########## crates/spark/src/function/hash/murmur3.rs: ########## @@ -0,0 +1,359 @@ +// SPDX-License-Identifier: Apache-2.0 +// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership +// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements + +use std::sync::Arc; + +use arrow::array::{ArrayRef, Int32Array, types::ArrowDictionaryKeyType}; +use arrow::buffer::{Buffer, ScalarBuffer}; +use arrow::datatypes::{DataType, Field, FieldRef}; +use datafusion_common::{Result, ScalarValue, internal_err}; +use datafusion_expr::{ + ColumnarValue, Documentation, ReturnFieldArgs, ScalarFunctionArgs, ScalarUDFImpl, + Signature, Volatility, +}; +use datafusion_macros::user_doc; + +use super::utils::hash_dictionary_values; +use crate::create_hashes_internal; + +const DEFAULT_SEED: u32 = 42; + +/// Spark-compatible `hash` expression. +/// +/// <https://spark.apache.org/docs/latest/api/sql/index.html#hash> +#[user_doc( + doc_section(label = "Hashing Functions"), + description = "Returns the 32-bit Murmur3 hash (seed 42) of the arguments as an INT, matching Spark's `hash`. \ + DataFusion has no built-in equivalent. Arguments are hashed in order, and each argument's hash seeds the next, \ + so `hash(a, b)` equals `hash(named_struct('a', a, 'b', b))` and argument order matters. \ + NULL arguments, NULL list elements and NULL struct fields are skipped, so the result is never NULL: \ + `hash(NULL)` returns 42. The result depends on the input type, as in Spark: INT hashes 4 bytes and BIGINT 8, \ + and integer literals are BIGINT in DataFusion but INT in Spark, so cast them to INT to match Spark's results. \ + `-0.0` hashes like `0.0`, and every NaN hashes like the canonical NaN. Dates hash as INT days and \ + timestamps as BIGINT microseconds, whatever the Arrow unit (DataFusion's TIMESTAMP literals are \ + nanoseconds, floored to microseconds). Decimals with precision up to 18 hash as their unscaled long, and wider decimals hash \ + the minimal big-endian two's complement bytes of the unscaled value. Lists hash each element in order \ + (nested lists flatten into the same chain, and an empty list leaves the seed unchanged), structs hash each field, \ + and maps hash each key then its value. This crate hashes maps as if Spark's `spark.sql.legacy.allowHashOnMapType` \ + were set, where Spark 4 rejects them by default (see https://github.com/apache/datafusion-spark/issues/69). \ + Dictionary-encoded values hash like their decoded values. At least one argument is required.", + syntax_example = "hash(expr1[, ..., exprN])", + sql_example = r#"```sql +> SELECT hash('Spark', [CAST(123 AS INT)], CAST(2 AS INT)); +-1321691492 +> SELECT hash(CAST(1 AS INT)); +-559580957 +> SELECT hash(1); +-1712319331 +> SELECT hash(NULL); +42 +```"#, + argument( + name = "expr1", + description = "Expression of any type to hash. NULL is skipped." + ), + argument( + name = "exprN", + description = "Further expressions, hashed in order with the previous hash as the seed." + ) +)] +#[derive(Debug, PartialEq, Eq, Hash)] +pub struct SparkHash { + signature: Signature, +} + +impl Default for SparkHash { + fn default() -> Self { + Self::new() + } +} + +impl SparkHash { + pub fn new() -> Self { + Self { + signature: Signature::variadic_any(Volatility::Immutable), + } + } +} + +impl ScalarUDFImpl for SparkHash { + fn name(&self) -> &str { + "hash" + } + + fn signature(&self) -> &Signature { + &self.signature + } + + fn return_type(&self, _arg_types: &[DataType]) -> Result<DataType> { + internal_err!("return_field_from_args should be used instead") + } + + fn return_field_from_args(&self, _args: ReturnFieldArgs) -> Result<FieldRef> { + // Spark's HashExpression overrides nullable to false: NULL inputs are + // skipped and the seed is used, so the result is never null. + Ok(Arc::new(Field::new(self.name(), DataType::Int32, false))) + } + + fn documentation(&self) -> Option<&Documentation> { + self.doc() + } + + fn invoke_with_args(&self, args: ScalarFunctionArgs) -> Result<ColumnarValue> { + // When every argument is a scalar the result is the same for every row, + // so hash a single row and return a scalar. Otherwise expand scalars to + // the batch length so every array has `number_rows` entries. + let all_scalars = args + .args + .iter() + .all(|arg| matches!(arg, ColumnarValue::Scalar(_))); + let num_rows = if all_scalars { 1 } else { args.number_rows }; + let arrays = args + .args + .iter() + .map(|arg| arg.to_array(num_rows)) + .collect::<Result<Vec<_>>>()?; + + let mut hashes: Vec<u32> = vec![DEFAULT_SEED; num_rows]; + create_murmur3_hashes(&arrays, &mut hashes)?; + + if all_scalars { + Ok(ColumnarValue::Scalar(ScalarValue::Int32(Some( + hashes[0] as i32, + )))) + } else { + // Reinterpret Vec<u32> as ScalarBuffer<i32> without copying. + let buffer = ScalarBuffer::<i32>::from(Buffer::from_vec(hashes)); + Ok(ColumnarValue::Array(Arc::new(Int32Array::new( + buffer, None, + )))) + } + } +} + +#[inline] +fn mix_k1(k1: u32) -> u32 { + k1.wrapping_mul(0xcc9e2d51) + .rotate_left(15) + .wrapping_mul(0x1b873593) +} + +#[inline] +fn mix_h1(h1: u32, k1: u32) -> u32 { + (h1 ^ k1) + .rotate_left(13) + .wrapping_mul(5) + .wrapping_add(0xe6546b64) +} + +#[inline] +fn fmix(mut h1: u32, len: u32) -> u32 { + h1 ^= len; + h1 ^= h1 >> 16; + h1 = h1.wrapping_mul(0x85ebca6b); + h1 ^= h1 >> 13; + h1 = h1.wrapping_mul(0xc2b2ae35); + h1 ^= h1 >> 16; + h1 +} + +/// Spark's `Murmur3_x86_32.hashUnsafeBytes`: whole 4-byte little-endian words +/// first, then each remaining tail byte is mixed separately as a sign-extended +/// word (this differs from the canonical MurmurHash3 tail handling). +#[inline] +fn spark_compatible_murmur3_hash<T: AsRef<[u8]>>(data: T, seed: u32) -> u32 { + let data = data.as_ref(); + let (words, tail) = data.as_chunks::<4>(); + let mut h1 = seed; + for word in words { + h1 = mix_h1(h1, mix_k1(u32::from_le_bytes(*word))); + } + for &byte in tail { + h1 = mix_h1(h1, mix_k1(byte as i8 as i32 as u32)); + } + fmix(h1, data.len() as u32) +} + +/// Hash the values in a dictionary array using murmur3. +fn create_murmur3_hashes_dictionary<K: ArrowDictionaryKeyType>( + array: &ArrayRef, + hashes_buffer: &mut [u32], + seeds_are_pristine: bool, +) -> Result<()> { + hash_dictionary_values::<K, u32>( + array, + hashes_buffer, + seeds_are_pristine, + create_murmur3_hashes, + ) +} + +/// Create murmur3 hash values for every row, based on the values in the columns. +/// +/// The number of rows to hash is determined by `hashes_buffer.len()`. +/// `hashes_buffer` should be pre-sized appropriately and seeded with the +/// initial hash value (Spark uses `42`). +fn create_murmur3_hashes(arrays: &[ArrayRef], hashes_buffer: &mut [u32]) -> Result<()> { + create_hashes_internal!( + arrays, + hashes_buffer, + spark_compatible_murmur3_hash, + create_murmur3_hashes_dictionary, + create_murmur3_hashes + ); + Ok(()) +} + +#[cfg(test)] Review Comment: `CONTRIBUTING.md` asks for a port to bring the source's tests with it. Comet's `murmur3.rs` has 29 unit tests ([test module](https://github.com/apache/datafusion-comet/blob/ba16e1a53127c90ba00fdc7058703945a8bb9f34/native/spark-expr/src/hash_funcs/murmur3.rs#L196-L1317)), and this PR has six. Many of Comet's build arrays that SQL can't produce but Comet passes to `invoke_with_args`. Examples are a NULL struct whose children still hold values, a NULL list or map row that owns a populated offset range, and sliced lists of structs. I copied 27 of them into this branch: everything except the two that test Comet's gather-eligibility internals. 25 pass. The two that fail are `test_ansi_intervals_hash_like_int_and_long` and `test_lists_of_null_type_and_intervals`, which is the interval gap above. Could we port them so these paths keep the coverage they have in Comet? ########## crates/spark/src/function/hash/murmur3.rs: ########## @@ -0,0 +1,359 @@ +// SPDX-License-Identifier: Apache-2.0 +// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership +// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements + +use std::sync::Arc; + +use arrow::array::{ArrayRef, Int32Array, types::ArrowDictionaryKeyType}; +use arrow::buffer::{Buffer, ScalarBuffer}; +use arrow::datatypes::{DataType, Field, FieldRef}; +use datafusion_common::{Result, ScalarValue, internal_err}; +use datafusion_expr::{ + ColumnarValue, Documentation, ReturnFieldArgs, ScalarFunctionArgs, ScalarUDFImpl, + Signature, Volatility, +}; +use datafusion_macros::user_doc; + +use super::utils::hash_dictionary_values; +use crate::create_hashes_internal; + +const DEFAULT_SEED: u32 = 42; + +/// Spark-compatible `hash` expression. +/// +/// <https://spark.apache.org/docs/latest/api/sql/index.html#hash> +#[user_doc( + doc_section(label = "Hashing Functions"), + description = "Returns the 32-bit Murmur3 hash (seed 42) of the arguments as an INT, matching Spark's `hash`. \ + DataFusion has no built-in equivalent. Arguments are hashed in order, and each argument's hash seeds the next, \ + so `hash(a, b)` equals `hash(named_struct('a', a, 'b', b))` and argument order matters. \ + NULL arguments, NULL list elements and NULL struct fields are skipped, so the result is never NULL: \ + `hash(NULL)` returns 42. The result depends on the input type, as in Spark: INT hashes 4 bytes and BIGINT 8, \ + and integer literals are BIGINT in DataFusion but INT in Spark, so cast them to INT to match Spark's results. \ + `-0.0` hashes like `0.0`, and every NaN hashes like the canonical NaN. Dates hash as INT days and \ + timestamps as BIGINT microseconds, whatever the Arrow unit (DataFusion's TIMESTAMP literals are \ + nanoseconds, floored to microseconds). Decimals with precision up to 18 hash as their unscaled long, and wider decimals hash \ + the minimal big-endian two's complement bytes of the unscaled value. Lists hash each element in order \ + (nested lists flatten into the same chain, and an empty list leaves the seed unchanged), structs hash each field, \ + and maps hash each key then its value. This crate hashes maps as if Spark's `spark.sql.legacy.allowHashOnMapType` \ + were set, where Spark 4 rejects them by default (see https://github.com/apache/datafusion-spark/issues/69). \ + Dictionary-encoded values hash like their decoded values. At least one argument is required.", + syntax_example = "hash(expr1[, ..., exprN])", + sql_example = r#"```sql +> SELECT hash('Spark', [CAST(123 AS INT)], CAST(2 AS INT)); +-1321691492 +> SELECT hash(CAST(1 AS INT)); +-559580957 +> SELECT hash(1); +-1712319331 +> SELECT hash(NULL); +42 +```"#, + argument( + name = "expr1", + description = "Expression of any type to hash. NULL is skipped." + ), + argument( + name = "exprN", + description = "Further expressions, hashed in order with the previous hash as the seed." + ) +)] +#[derive(Debug, PartialEq, Eq, Hash)] +pub struct SparkHash { + signature: Signature, +} + +impl Default for SparkHash { + fn default() -> Self { + Self::new() + } +} + +impl SparkHash { + pub fn new() -> Self { + Self { + signature: Signature::variadic_any(Volatility::Immutable), + } + } +} + +impl ScalarUDFImpl for SparkHash { + fn name(&self) -> &str { + "hash" + } + + fn signature(&self) -> &Signature { + &self.signature + } + + fn return_type(&self, _arg_types: &[DataType]) -> Result<DataType> { + internal_err!("return_field_from_args should be used instead") + } + + fn return_field_from_args(&self, _args: ReturnFieldArgs) -> Result<FieldRef> { + // Spark's HashExpression overrides nullable to false: NULL inputs are + // skipped and the seed is used, so the result is never null. + Ok(Arc::new(Field::new(self.name(), DataType::Int32, false))) + } + + fn documentation(&self) -> Option<&Documentation> { + self.doc() + } + + fn invoke_with_args(&self, args: ScalarFunctionArgs) -> Result<ColumnarValue> { + // When every argument is a scalar the result is the same for every row, + // so hash a single row and return a scalar. Otherwise expand scalars to + // the batch length so every array has `number_rows` entries. + let all_scalars = args + .args + .iter() + .all(|arg| matches!(arg, ColumnarValue::Scalar(_))); + let num_rows = if all_scalars { 1 } else { args.number_rows }; + let arrays = args + .args + .iter() + .map(|arg| arg.to_array(num_rows)) + .collect::<Result<Vec<_>>>()?; + + let mut hashes: Vec<u32> = vec![DEFAULT_SEED; num_rows]; + create_murmur3_hashes(&arrays, &mut hashes)?; + + if all_scalars { + Ok(ColumnarValue::Scalar(ScalarValue::Int32(Some( + hashes[0] as i32, + )))) + } else { + // Reinterpret Vec<u32> as ScalarBuffer<i32> without copying. + let buffer = ScalarBuffer::<i32>::from(Buffer::from_vec(hashes)); + Ok(ColumnarValue::Array(Arc::new(Int32Array::new( + buffer, None, + )))) + } + } +} + +#[inline] +fn mix_k1(k1: u32) -> u32 { + k1.wrapping_mul(0xcc9e2d51) + .rotate_left(15) + .wrapping_mul(0x1b873593) +} + +#[inline] +fn mix_h1(h1: u32, k1: u32) -> u32 { + (h1 ^ k1) + .rotate_left(13) + .wrapping_mul(5) + .wrapping_add(0xe6546b64) +} + +#[inline] +fn fmix(mut h1: u32, len: u32) -> u32 { + h1 ^= len; + h1 ^= h1 >> 16; + h1 = h1.wrapping_mul(0x85ebca6b); + h1 ^= h1 >> 13; + h1 = h1.wrapping_mul(0xc2b2ae35); + h1 ^= h1 >> 16; + h1 +} + +/// Spark's `Murmur3_x86_32.hashUnsafeBytes`: whole 4-byte little-endian words +/// first, then each remaining tail byte is mixed separately as a sign-extended +/// word (this differs from the canonical MurmurHash3 tail handling). +#[inline] +fn spark_compatible_murmur3_hash<T: AsRef<[u8]>>(data: T, seed: u32) -> u32 { + let data = data.as_ref(); + let (words, tail) = data.as_chunks::<4>(); + let mut h1 = seed; + for word in words { + h1 = mix_h1(h1, mix_k1(u32::from_le_bytes(*word))); + } + for &byte in tail { + h1 = mix_h1(h1, mix_k1(byte as i8 as i32 as u32)); + } + fmix(h1, data.len() as u32) +} + +/// Hash the values in a dictionary array using murmur3. +fn create_murmur3_hashes_dictionary<K: ArrowDictionaryKeyType>( + array: &ArrayRef, + hashes_buffer: &mut [u32], + seeds_are_pristine: bool, +) -> Result<()> { + hash_dictionary_values::<K, u32>( + array, + hashes_buffer, + seeds_are_pristine, + create_murmur3_hashes, + ) +} + +/// Create murmur3 hash values for every row, based on the values in the columns. +/// +/// The number of rows to hash is determined by `hashes_buffer.len()`. +/// `hashes_buffer` should be pre-sized appropriately and seeded with the +/// initial hash value (Spark uses `42`). +fn create_murmur3_hashes(arrays: &[ArrayRef], hashes_buffer: &mut [u32]) -> Result<()> { + create_hashes_internal!( + arrays, + hashes_buffer, + spark_compatible_murmur3_hash, + create_murmur3_hashes_dictionary, + create_murmur3_hashes + ); + Ok(()) +} Review Comment: `hash` accepts Spark's interval and `TIME` types at planning, but hashing them fails at execution with an internal error: ``` > SELECT hash(INTERVAL '1' DAY); Internal error: Unsupported data type in hasher: Interval(MonthDayNano). > SELECT hash(TIME '12:00:00'); Internal error: Unsupported data type in hasher: Time64(ns). > SELECT hash(arrow_cast(86400000000, 'Duration(Microsecond)')); Internal error: Unsupported data type in hasher: Duration(µs). ``` Spark hashes all of them ([`hash.scala`](https://github.com/apache/spark/blob/32f7299601108917fb01920a54e084595b7b3bf8/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/hash.scala#L547-L557)). In Spark 4.2.0, `hash(INTERVAL '1' DAY)` is `892267096` and `hash(TIME '12:00:00')` is `-1984942870`. Comet's `create_hashes_internal!` already has arms for `Time64(Nanosecond)`, `Interval(MonthDayNano)`, `Interval(YearMonth)`, and `Duration(Microsecond)` ([`utils.rs`](https://github.com/apache/datafusion-comet/blob/ba16e1a53127c90ba00fdc7058703945a8bb9f34/native/spark-expr/src/hash_funcs/utils.rs#L1004-L1040)). They came from apache/datafusion-comet#4398, apache/datafusion-comet#5135, and apache/datafusion-comet#7084, after the snapshot `hash/utils.rs` was ported from. Without them, Comet would lose interval and `TIME` hashing when it switches to this `hash`. Could we port those arms and their tests? Comet's `Interval(MonthDayNano)` arm matches Spark 4.2.0's generated code, which leaves out the days field, and its comment explains why. Once that's in, the `expr1` argument doc ("Expression of any type") holds. Otherwise it should name the types that fail. -- 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]
