1use std::fmt::{Display, Formatter};
26use std::sync::Arc;
27
28use datafusion_common::arrow::array::{Array, ArrayRef, AsArray, Int32Array};
29use datafusion_common::arrow::compute::take;
30use datafusion_common::arrow::datatypes::{
31 DataType, Int8Type, Int16Type, Int32Type, Int64Type, UInt8Type, UInt16Type, UInt32Type,
32 UInt64Type,
33};
34use datafusion_common::{DataFusionError, ScalarValue};
35use datafusion_expr::{
36 ColumnarValue, Expr, ScalarFunctionArgs, ScalarUDF, ScalarUDFImpl, Signature, Volatility,
37};
38use datatypes::prelude::ConcreteDataType;
39use datatypes::value::Value;
40use serde::{Deserialize, Serialize};
41
42use crate::error::{self, Result};
43
44#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
51pub struct IcebergHash(String);
52
53impl IcebergHash {
54 pub const NAME: &str = "iceberg_hash";
55
56 pub fn new(column: impl Into<String>) -> Self {
57 Self(column.into())
58 }
59
60 pub fn column(&self) -> &str {
61 &self.0
62 }
63
64 pub fn accepts(data_type: &ConcreteDataType) -> bool {
65 data_type.is_string() || data_type.is_unsigned() || is_signed_integer(data_type)
66 }
67
68 pub fn output_type() -> ConcreteDataType {
70 ConcreteDataType::int32_datatype()
71 }
72
73 pub fn evaluate_value(value: &Value) -> Result<Value> {
74 let hash = match value {
75 Value::Null => return Ok(Value::Null),
76 Value::String(v) => murmur3_32(v.as_utf8().as_bytes()),
77 Value::Int8(v) => hash_long(*v as i64),
78 Value::Int16(v) => hash_long(*v as i64),
79 Value::Int32(v) => hash_long(*v as i64),
80 Value::Int64(v) => hash_long(*v),
81 Value::UInt8(v) => hash_long(*v as i64),
82 Value::UInt16(v) => hash_long(*v as i64),
83 Value::UInt32(v) => hash_long(*v as i64),
84 Value::UInt64(v) => hash_long(*v as i64),
85 other => {
86 return error::UnexpectedSnafu {
87 err_msg: format!("Unsupported value for {}: {other:?}", Self::NAME),
88 }
89 .fail();
90 }
91 };
92 Ok(Value::Int32(hash))
93 }
94
95 pub fn evaluate_array(array: &dyn Array) -> datafusion_common::Result<ArrayRef> {
96 iceberg_hash_array(array)
97 }
98
99 pub fn to_logical_expr(&self) -> Expr {
100 let column = Expr::Column(datafusion_common::Column::from_name(self.column()));
101 iceberg_hash_udf().call(vec![column])
102 }
103}
104
105impl Display for IcebergHash {
106 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
107 write!(f, "{}({})", Self::NAME, self.column())
108 }
109}
110
111pub fn iceberg_hash_udf() -> ScalarUDF {
117 ScalarUDF::new_from_impl(IcebergHashUdf::default())
118}
119
120fn is_signed_integer(data_type: &ConcreteDataType) -> bool {
121 matches!(
122 data_type,
123 ConcreteDataType::Int8(_)
124 | ConcreteDataType::Int16(_)
125 | ConcreteDataType::Int32(_)
126 | ConcreteDataType::Int64(_)
127 )
128}
129
130fn iceberg_hash_array(array: &dyn Array) -> datafusion_common::Result<ArrayRef> {
131 let hashes: Int32Array = match array.data_type() {
132 DataType::Null => Int32Array::from(vec![None; array.len()]),
134 DataType::Utf8 => array
135 .as_string::<i32>()
136 .iter()
137 .map(|v| v.map(|v| murmur3_32(v.as_bytes())))
138 .collect(),
139 DataType::LargeUtf8 => array
140 .as_string::<i64>()
141 .iter()
142 .map(|v| v.map(|v| murmur3_32(v.as_bytes())))
143 .collect(),
144 DataType::Utf8View => array
145 .as_string_view()
146 .iter()
147 .map(|v| v.map(|v| murmur3_32(v.as_bytes())))
148 .collect(),
149 DataType::Int8 => array
150 .as_primitive::<Int8Type>()
151 .unary(|v| hash_long(v as i64)),
152 DataType::Int16 => array
153 .as_primitive::<Int16Type>()
154 .unary(|v| hash_long(v as i64)),
155 DataType::Int32 => array
156 .as_primitive::<Int32Type>()
157 .unary(|v| hash_long(v as i64)),
158 DataType::Int64 => array.as_primitive::<Int64Type>().unary(hash_long),
159 DataType::UInt8 => array
160 .as_primitive::<UInt8Type>()
161 .unary(|v| hash_long(v as i64)),
162 DataType::UInt16 => array
163 .as_primitive::<UInt16Type>()
164 .unary(|v| hash_long(v as i64)),
165 DataType::UInt32 => array
166 .as_primitive::<UInt32Type>()
167 .unary(|v| hash_long(v as i64)),
168 DataType::UInt64 => array
169 .as_primitive::<UInt64Type>()
170 .unary(|v| hash_long(v as i64)),
171 DataType::Dictionary(_, _) => {
172 let dictionary = array.as_any_dictionary();
173 let values = iceberg_hash_array(dictionary.values().as_ref())?;
174 return Ok(take(values.as_ref(), dictionary.keys(), None)?);
175 }
176 other => {
177 return Err(DataFusionError::Execution(format!(
178 "{} does not support type {other}",
179 IcebergHash::NAME
180 )));
181 }
182 };
183 Ok(Arc::new(hashes))
184}
185
186fn hash_long(value: i64) -> i32 {
187 murmur3_32(&value.to_le_bytes())
188}
189
190fn murmur3_32(data: &[u8]) -> i32 {
192 const C1: u32 = 0xcc9e_2d51;
193 const C2: u32 = 0x1b87_3593;
194
195 fn mix_k(k: u32) -> u32 {
196 k.wrapping_mul(C1).rotate_left(15).wrapping_mul(C2)
197 }
198
199 let mut h = 0u32;
200 let (blocks, tail) = data.as_chunks::<4>();
201 for block in blocks {
202 h = (h ^ mix_k(u32::from_le_bytes(*block)))
203 .rotate_left(13)
204 .wrapping_mul(5)
205 .wrapping_add(0xe654_6b64);
206 }
207 if !tail.is_empty() {
208 let k = tail
209 .iter()
210 .rev()
211 .fold(0u32, |k, byte| (k << 8) | *byte as u32);
212 h ^= mix_k(k);
213 }
214
215 h ^= data.len() as u32;
217 h ^= h >> 16;
218 h = h.wrapping_mul(0x85eb_ca6b);
219 h ^= h >> 13;
220 h = h.wrapping_mul(0xc2b2_ae35);
221 h ^= h >> 16;
222 h as i32
223}
224
225#[derive(Debug, PartialEq, Eq, Hash)]
228struct IcebergHashUdf {
229 signature: Signature,
230}
231
232impl Default for IcebergHashUdf {
233 fn default() -> Self {
234 Self {
235 signature: Signature::any(1, Volatility::Immutable),
236 }
237 }
238}
239
240impl ScalarUDFImpl for IcebergHashUdf {
241 fn name(&self) -> &str {
242 IcebergHash::NAME
243 }
244
245 fn signature(&self) -> &Signature {
246 &self.signature
247 }
248
249 fn return_type(&self, _arg_types: &[DataType]) -> datafusion_common::Result<DataType> {
250 Ok(DataType::Int32)
251 }
252
253 fn invoke_with_args(
254 &self,
255 args: ScalarFunctionArgs,
256 ) -> datafusion_common::Result<ColumnarValue> {
257 let [arg] = args.args.as_slice() else {
258 return Err(DataFusionError::Internal(format!(
259 "{} expects one argument, got {}",
260 IcebergHash::NAME,
261 args.args.len()
262 )));
263 };
264 match arg {
265 ColumnarValue::Array(array) => {
266 Ok(ColumnarValue::Array(iceberg_hash_array(array.as_ref())?))
267 }
268 ColumnarValue::Scalar(scalar) => {
269 let hashes = iceberg_hash_array(scalar.to_array()?.as_ref())?;
270 Ok(ColumnarValue::Scalar(ScalarValue::try_from_array(
271 &hashes, 0,
272 )?))
273 }
274 }
275 }
276}
277
278#[cfg(test)]
279mod tests {
280 use datafusion_common::arrow::array::{
281 Int64Array, StringArray, StringDictionaryBuilder, StringViewArray, UInt64Array,
282 };
283 use datafusion_common::arrow::datatypes::UInt16Type;
284
285 use super::*;
286
287 #[test]
288 fn test_iceberg_spec_vectors() {
289 assert_eq!(hash_long(34), 2017239379);
291 assert_eq!(hash_long(17486), -653330422);
293 assert_eq!(hash_long(81068000000), -662762989);
295 assert_eq!(murmur3_32("iceberg".as_bytes()), 1210000089);
296 assert_eq!(murmur3_32(&[0, 1, 2, 3]), -188683207);
297 }
298
299 #[test]
300 fn test_unsigned_policy() {
301 assert_eq!(
302 IcebergHash::evaluate_value(&Value::UInt64(34)).unwrap(),
303 Value::Int32(2017239379)
304 );
305 assert_eq!(
306 IcebergHash::evaluate_value(&Value::UInt64(u64::MAX)).unwrap(),
307 Value::Int32(hash_long(-1))
308 );
309 }
310
311 #[test]
312 fn test_array_matches_value() {
313 let strings = [Some("iceberg"), None, Some(""), Some("中🙂")];
314 let mut dictionary = StringDictionaryBuilder::<UInt16Type>::new();
315 for v in strings {
316 dictionary.append_option(v);
317 }
318 let string_arrays: Vec<ArrayRef> = vec![
319 Arc::new(StringArray::from(strings.to_vec())),
320 Arc::new(StringViewArray::from(strings.to_vec())),
321 Arc::new(dictionary.finish()),
322 ];
323 let string_values = strings.map(|v| v.map_or(Value::Null, Value::from));
324
325 let ints = [Some(34), None, Some(i64::MIN), Some(-1)];
326 let unsigned = [Some(34), None, Some(u64::MAX), Some(0)];
327 let cases = string_arrays
328 .into_iter()
329 .map(|array| (array, string_values.to_vec()))
330 .chain([
331 (
332 Arc::new(Int64Array::from(ints.to_vec())) as ArrayRef,
333 ints.map(|v| v.map_or(Value::Null, Value::Int64)).to_vec(),
334 ),
335 (
336 Arc::new(UInt64Array::from(unsigned.to_vec())) as ArrayRef,
337 unsigned
338 .map(|v| v.map_or(Value::Null, Value::UInt64))
339 .to_vec(),
340 ),
341 ]);
342 for (array, values) in cases {
343 let hashes = IcebergHash::evaluate_array(array.as_ref()).unwrap();
344 let hashes = hashes.as_primitive::<Int32Type>();
345 for (row, value) in values.iter().enumerate() {
346 let expected = IcebergHash::evaluate_value(value).unwrap();
347 let actual = if hashes.is_null(row) {
348 Value::Null
349 } else {
350 Value::Int32(hashes.value(row))
351 };
352 assert_eq!(actual, expected, "{:?} row {row}", array.data_type());
353 }
354 }
355 }
356}