Skip to main content

parquet/column/writer/
min_max.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4
5use crate::basic::SortOrder;
6use crate::column::writer::{compare_greater, is_nan};
7use crate::data_type::private::ParquetValueType;
8use crate::schema::types::BasicTypeInfo;
9
10/// Accumulators for 64 bytes of values, i.e. a cache line and one AVX-512
11/// register, or four NEON / two AVX2 registers.
12const LANES_32: usize = 16;
13const LANES_64: usize = 8;
14
15/// Returns the minimum and maximum of `values` after mapping them with `key`,
16/// or `None` if `values` is empty.
17#[inline(always)]
18fn min_max_by_key<T: Copy, K: Copy + Ord, const LANES: usize>(
19    values: &[T],
20    key: impl Fn(T) -> K,
21    key_min: K,
22    key_max: K,
23) -> Option<(K, K)> {
24    if values.is_empty() {
25        return None;
26    }
27
28    let mut mins = [key_max; LANES];
29    let mut maxs = [key_min; LANES];
30
31    let (chunks, remainder) = values.as_chunks::<LANES>();
32    for chunk in chunks {
33        for i in 0..LANES {
34            let k = key(chunk[i]);
35            mins[i] = mins[i].min(k);
36            maxs[i] = maxs[i].max(k);
37        }
38    }
39    for (i, v) in remainder.iter().enumerate() {
40        let k = key(*v);
41        mins[i] = mins[i].min(k);
42        maxs[i] = maxs[i].max(k);
43    }
44
45    let min = mins.into_iter().min().unwrap();
46    let max = maxs.into_iter().max().unwrap();
47    Some((min, max))
48}
49
50#[inline]
51fn is_unsigned(basic_type_info: &BasicTypeInfo) -> bool {
52    matches!(basic_type_info.sort_order(), SortOrder::UNSIGNED)
53}
54
55/// Returns the min and max of an `INT32` column, or `None` if `values` is empty.
56pub(crate) fn min_max_i32(basic_type_info: &BasicTypeInfo, values: &[i32]) -> Option<(i32, i32)> {
57    if is_unsigned(basic_type_info) {
58        min_max_by_key::<_, _, LANES_32>(values, |v| v as u32, u32::MIN, u32::MAX)
59            .map(|(min, max)| (min as i32, max as i32))
60    } else {
61        min_max_by_key::<_, _, LANES_32>(values, |v| v, i32::MIN, i32::MAX)
62    }
63}
64
65/// Returns the min and max of an `INT64` column, or `None` if `values` is empty.
66pub(crate) fn min_max_i64(basic_type_info: &BasicTypeInfo, values: &[i64]) -> Option<(i64, i64)> {
67    if is_unsigned(basic_type_info) {
68        min_max_by_key::<_, _, LANES_64>(values, |v| v as u64, u64::MIN, u64::MAX)
69            .map(|(min, max)| (min as i64, max as i64))
70    } else {
71        min_max_by_key::<_, _, LANES_64>(values, |v| v, i64::MIN, i64::MAX)
72    }
73}
74
75macro_rules! float_min_max {
76    ($name:ident, $float:ty, $int:ty, $uint:ty, $lanes:expr) => {
77        /// Returns the min, max and NaN count of a floating point column,
78        /// comparing by IEEE 754 total order and skipping NaN.
79        ///
80        /// Returns `None` if `values` is empty or contains only NaN, in which
81        /// case the min and max are NaN themselves and the caller falls back
82        /// to the scalar implementation.
83        pub(crate) fn $name(values: &[$float]) -> Option<($float, $float, u64)> {
84            const SIGN_SHIFT: u32 = <$int>::BITS - 1;
85
86            // Maps the bits of a float to an integer with the same ordering as
87            // `total_cmp`: negative values have their magnitude bits flipped
88            // so that they order in reverse. The mapping is its own inverse.
89            //
90            // To avoid calling `{f32,f64}::total_cmp` for both min and max values and every other comparison
91            // we transform the input once (like what rust is doing internally before comparing) and reuse it, this avoids the overhead of calling `total_cmp` twice for each value.
92            // and doing the same calculation.
93            //
94            // This is the same transformation used in Rust `f32::total_cmp` and `f64::total_cmp`
95            // but we avoid calling
96            // f32: https://github.com/rust-lang/rust/blob/b5427502dab50cb27d9327d2893ddf2337dd4388/library/core/src/num/f32.rs#L1626
97            // f64: https://github.com/rust-lang/rust/blob/b5427502dab50cb27d9327d2893ddf2337dd4388/library/core/src/num/f64.rs#L1604
98            #[inline(always)]
99            fn total_order_key(bits: $int) -> $int {
100                bits ^ ((((bits >> SIGN_SHIFT) as $uint) >> 1) as $int)
101            }
102
103            // Bounds the per lane NaN counters well below overflow on every
104            // platform, including 32-bit.
105            const BLOCK: usize = 1 << 30;
106
107            let mut min = <$int>::MAX;
108            let mut max = <$int>::MIN;
109            let mut nan_count = 0u64;
110
111            for block in values.chunks(BLOCK) {
112                let mut mins = [<$int>::MAX; $lanes];
113                let mut maxs = [<$int>::MIN; $lanes];
114                let mut nans = [<$uint>::MIN; $lanes];
115
116                // NaN lanes are replaced by the identity of each accumulator, so
117                // they never win, without a branch.
118                let mut accumulate = |i: usize, v: $float| {
119                    let bits = v.to_bits();
120                    let is_nan = v.is_nan();
121                    let key = total_order_key(bits as $int);
122                    mins[i] = mins[i].min(if is_nan { <$int>::MAX } else { key });
123                    maxs[i] = maxs[i].max(if is_nan { <$int>::MIN } else { key });
124                    nans[i] += is_nan as $uint;
125                };
126
127                let (chunks, remainder) = block.as_chunks::<$lanes>();
128                for chunk in chunks {
129                    for i in 0..$lanes {
130                        accumulate(i, chunk[i]);
131                    }
132                }
133                for (i, v) in remainder.iter().enumerate() {
134                    accumulate(i, *v);
135                }
136
137                min = min.min(mins.into_iter().min().unwrap());
138                max = max.max(maxs.into_iter().max().unwrap());
139                nan_count += nans.into_iter().map(u64::from).sum::<u64>();
140            }
141
142            if nan_count as usize == values.len() {
143                return None;
144            }
145
146            let min = <$float>::from_bits(total_order_key(min) as $uint);
147            let max = <$float>::from_bits(total_order_key(max) as $uint);
148            Some((min, max, nan_count))
149        }
150    };
151}
152
153float_min_max!(min_max_f32, f32, i32, u32, LANES_32);
154float_min_max!(min_max_f64, f64, i64, u64, LANES_64);
155
156// Get min and max values for all values in `iter`.
157//
158// For floating point we need to compare NaN values until we encounter a non-NaN
159// value which then becomes the new min/max. After this, only non-NaN values are
160// evaluated. If all values are NaN, then the min/max NaNs as determined by
161// IEEE 754 total order are returned.
162pub(crate) fn fallback_min_max<'a, T, I>(
163    basic_type_info: &BasicTypeInfo,
164    mut iter: I,
165) -> Option<(T, T, u64)>
166where
167    T: ParquetValueType + 'a,
168    I: Iterator<Item = &'a T>,
169{
170    let first = iter.next()?;
171    let mut min_max_nan = is_nan(basic_type_info, first);
172    let mut nan_count = min_max_nan as u64;
173
174    let mut min = first;
175    let mut max = first;
176    for val in iter {
177        match (min_max_nan, is_nan(basic_type_info, val)) {
178            // skip NaNs if we've encounter non-NaN
179            (false, true) => {
180                nan_count += 1;
181            }
182            // if min/max are NaN, check for non-NaN and reset
183            (true, false) => {
184                min = val;
185                max = val;
186                min_max_nan = false;
187            }
188            // both are NaN or non-NaN, so do the comparison
189            (_, val_is_nan) => {
190                nan_count += val_is_nan as u64;
191                // we've already initialized min and max, so a single value can't be both
192                // extremes
193                if compare_greater(basic_type_info, min, val) {
194                    min = val;
195                } else if compare_greater(basic_type_info, val, max) {
196                    max = val;
197                }
198            }
199        }
200    }
201
202    Some((min.clone(), max.clone(), nan_count))
203}
204
205#[cfg(test)]
206mod tests {
207    use super::*;
208    use crate::basic::{ConvertedType, IntType, LogicalType, Type as PhysicalType};
209    use crate::schema::types::Type;
210    use rand::prelude::*;
211
212    fn type_info(physical: PhysicalType, logical: Option<LogicalType>) -> BasicTypeInfo {
213        Type::primitive_type_builder("col", physical)
214            .with_logical_type(logical)
215            .build()
216            .unwrap()
217            .get_basic_info()
218            .clone()
219    }
220
221    fn signed_int(bits: u8) -> Option<LogicalType> {
222        Some(LogicalType::Integer(IntType {
223            bit_width: bits as i8,
224            is_signed: true,
225        }))
226    }
227
228    fn unsigned_int(bits: u8) -> Option<LogicalType> {
229        Some(LogicalType::Integer(IntType {
230            bit_width: bits as i8,
231            is_signed: false,
232        }))
233    }
234
235    /// Lengths around every lane count and remainder boundary
236    fn lengths() -> impl Iterator<Item = usize> {
237        (0..=70).chain([127, 128, 129, 1000, 4097])
238    }
239
240    fn check_ints<T, F>(
241        rng: &mut StdRng,
242        info: &BasicTypeInfo,
243        kernel: F,
244        gen_value: impl Fn(&mut StdRng) -> T,
245    ) where
246        T: crate::data_type::private::ParquetValueType + Copy,
247        F: Fn(&BasicTypeInfo, &[T]) -> Option<(T, T)>,
248    {
249        for len in lengths() {
250            let values: Vec<T> = (0..len).map(|_| gen_value(rng)).collect();
251            let expected = fallback_min_max(info, values.iter());
252            let actual = kernel(info, &values).map(|(min, max)| (min, max, 0));
253            assert_eq!(actual, expected, "len {len}: {values:?}");
254        }
255    }
256
257    #[test]
258    fn test_min_max_i32() {
259        let mut rng = StdRng::seed_from_u64(42);
260        let edges = [i32::MIN, i32::MIN + 1, -1, 0, 1, i32::MAX - 1, i32::MAX];
261        for info in [
262            type_info(PhysicalType::INT32, None),
263            type_info(PhysicalType::INT32, signed_int(32)),
264            type_info(PhysicalType::INT32, unsigned_int(32)),
265            type_info(PhysicalType::INT32, unsigned_int(8)),
266        ] {
267            check_ints(&mut rng, &info, min_max_i32, |r| r.random());
268            check_ints(&mut rng, &info, min_max_i32, |r| *edges.choose(r).unwrap());
269            check_ints(&mut rng, &info, min_max_i32, |r| r.random_range(-3..3));
270        }
271    }
272
273    #[test]
274    fn test_min_max_i64() {
275        let mut rng = StdRng::seed_from_u64(42);
276        let edges = [i64::MIN, i64::MIN + 1, -1, 0, 1, i64::MAX - 1, i64::MAX];
277        for info in [
278            type_info(PhysicalType::INT64, None),
279            type_info(PhysicalType::INT64, signed_int(64)),
280            type_info(PhysicalType::INT64, unsigned_int(64)),
281        ] {
282            check_ints(&mut rng, &info, min_max_i64, |r| r.random());
283            check_ints(&mut rng, &info, min_max_i64, |r| *edges.choose(r).unwrap());
284            check_ints(&mut rng, &info, min_max_i64, |r| r.random_range(-3..3));
285        }
286    }
287
288    #[test]
289    fn test_unsigned_int32_converted_type() {
290        let info = Type::primitive_type_builder("col", PhysicalType::INT32)
291            .with_converted_type(ConvertedType::UINT_32)
292            .build()
293            .unwrap()
294            .get_basic_info()
295            .clone();
296        assert_eq!(min_max_i32(&info, &[-1, 0, 5]), Some((0, -1)));
297    }
298
299    macro_rules! float_tests {
300        ($test:ident, $float:ty, $uint:ty, $kernel:ident, $physical:expr) => {
301            #[test]
302            fn $test() {
303                let info = type_info($physical, None);
304                let mut rng = StdRng::seed_from_u64(42);
305
306                let quiet_nan = <$float>::NAN;
307                let neg_nan = -<$float>::NAN;
308                let payload_nan = <$float>::from_bits(<$float>::NAN.to_bits() | 1);
309                let max_nan = <$float>::from_bits(<$uint>::MAX >> 1);
310                let edges = [
311                    <$float>::NEG_INFINITY,
312                    <$float>::MIN,
313                    -1.0,
314                    -<$float>::MIN_POSITIVE,
315                    -0.0,
316                    0.0,
317                    <$float>::MIN_POSITIVE,
318                    <$float>::from_bits(1),
319                    1.0,
320                    <$float>::MAX,
321                    <$float>::INFINITY,
322                    quiet_nan,
323                    neg_nan,
324                    payload_nan,
325                    max_nan,
326                ];
327                let nans = [quiet_nan, neg_nan, payload_nan, max_nan];
328
329                let generators: [&dyn Fn(&mut StdRng) -> $float; 5] = [
330                    &|r| r.random::<$float>() * 2.0 - 1.0,
331                    &|r| <$float>::from_bits(r.random()),
332                    &|r| *edges.choose(r).unwrap(),
333                    &|r| *nans.choose(r).unwrap(),
334                    &|r| {
335                        if r.random_bool(0.95) {
336                            quiet_nan
337                        } else {
338                            r.random()
339                        }
340                    },
341                ];
342
343                for generator in generators {
344                    for len in lengths() {
345                        let values: Vec<$float> = (0..len).map(|_| generator(&mut rng)).collect();
346                        let expected = fallback_min_max(&info, values.iter());
347                        match $kernel(&values) {
348                            Some(actual) => {
349                                // Compare bits to tell apart -0.0 / 0.0
350                                let to_bits = |(min, max, nans): ($float, $float, u64)| {
351                                    (min.to_bits(), max.to_bits(), nans)
352                                };
353                                assert_eq!(
354                                    to_bits(actual),
355                                    to_bits(expected.unwrap()),
356                                    "len {len}: {values:?}"
357                                );
358                            }
359                            // Only all NaN (or empty) input defers to the scalar path
360                            None => assert!(values.iter().all(|v| v.is_nan()), "{values:?}"),
361                        }
362                    }
363                }
364            }
365        };
366    }
367
368    float_tests!(test_min_max_f32, f32, u32, min_max_f32, PhysicalType::FLOAT);
369    float_tests!(
370        test_min_max_f64,
371        f64,
372        u64,
373        min_max_f64,
374        PhysicalType::DOUBLE
375    );
376}