Skip to main content

partition/
function.rs

1// Copyright 2023 Greptime Team
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! `iceberg_hash`, the hash allowed on the column side of a partition rule.
16//!
17//! The hash decides which region a row is written to and is persisted in
18//! partition metadata, so its result for a given input must never change across
19//! versions. A different algorithm needs a new type.
20//!
21//! Rule simplification and coverage checks treat the hash as an independent
22//! dimension, which holds because it is defined for every value of the accepted
23//! column types.
24
25use 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/// `iceberg_hash(column)`: the 32-bit Murmur3 hash defined by the Iceberg table
45/// spec (appendix B) over a string or integer column, as an `INT`.
46///
47/// Integers of every width hash as Iceberg longs. `UINT64` values hash their bits
48/// as a long, so values up to `i64::MAX` match Iceberg. `NULL` hashes to `NULL`.
49/// The field is the hashed column.
50#[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    /// The type of the result, which is also the type of the literals it is compared with.
69    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
111/// Returns the DataFusion form of [`IcebergHash`].
112///
113/// Partition rules plan this UDF directly, and the SQL function `iceberg_hash`
114/// is registered from the same constructor, so a persisted rule and a user query
115/// always hash through one implementation.
116pub 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        // `iceberg_hash(NULL)` reaches here as an untyped null.
133        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
190/// MurmurHash3 x86 32-bit with seed 0, returned as a signed integer like Iceberg.
191fn 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    // Murmur3 mixes in the length modulo 2^32.
216    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/// DataFusion form of [`IcebergHash`], so storage engines
226/// can evaluate a region's partition expression as a filter.
227#[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        // Iceberg table spec, appendix B.
290        assert_eq!(hash_long(34), 2017239379);
291        // date 2017-11-16 hashes as int 17486.
292        assert_eq!(hash_long(17486), -653330422);
293        // time 22:31:08 hashes as long 81068000000 micros.
294        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}