Skip to main content

arrow_row/
variable.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::null_sentinel;
6use arrow_array::types::ByteArrayType;
7use arrow_array::*;
8use arrow_buffer::bit_util::ceil;
9use arrow_buffer::{
10    ArrowNativeType, BooleanBuffer, MutableBuffer, NullBuffer, OffsetBuffer, ScalarBuffer,
11};
12use arrow_data::MAX_INLINE_VIEW_LEN;
13use arrow_schema::{ArrowError, SortOptions};
14use builder::make_view;
15
16/// The block size of the variable length encoding
17pub const BLOCK_SIZE: usize = 32;
18
19/// The first block is split into `MINI_BLOCK_COUNT` mini-blocks
20///
21/// This helps to reduce the space amplification for small strings
22pub const MINI_BLOCK_COUNT: usize = 4;
23
24/// The mini block size
25pub const MINI_BLOCK_SIZE: usize = BLOCK_SIZE / MINI_BLOCK_COUNT;
26
27/// The continuation token
28pub const BLOCK_CONTINUATION: u8 = 0xFF;
29
30/// Indicates an empty string
31pub const EMPTY_SENTINEL: u8 = 1;
32
33/// Indicates a non-empty string
34pub const NON_EMPTY_SENTINEL: u8 = 2;
35
36/// Indicates a Null value (for DataType::Null)
37pub const NULL_VALUE_SENTINEL: u8 = 3;
38
39/// Returns the padded length of the encoded length of the given length
40#[inline]
41pub fn padded_length(a: Option<usize>) -> usize {
42    match a {
43        Some(a) => non_null_padded_length(a),
44        None => 1,
45    }
46}
47
48/// Returns the padded length of the encoded length of the given length
49#[inline]
50pub(crate) fn non_null_padded_length(len: usize) -> usize {
51    if len <= BLOCK_SIZE {
52        1 + ceil(len, MINI_BLOCK_SIZE) * (MINI_BLOCK_SIZE + 1)
53    } else {
54        // Each miniblock ends with a 1 byte continuation, therefore add
55        // `(MINI_BLOCK_COUNT - 1)` additional bytes over non-miniblock size
56        MINI_BLOCK_COUNT + ceil(len, BLOCK_SIZE) * (BLOCK_SIZE + 1)
57    }
58}
59
60/// Decodes a single byte from each row, where a valid value is determined via
61/// a configurable sentinel. Optionally returns `None` if there are no null values.
62pub(crate) fn decode_nulls_sentinel(
63    rows: &[&[u8]],
64    options: SortOptions,
65) -> Result<Option<NullBuffer>, ArrowError> {
66    let null_sentinel = null_sentinel(options);
67    let nulls = MutableBuffer::try_collect_bool(rows.len(), |x| rows[x][0] != null_sentinel)
68        .map_err(|e| ArrowError::MemoryError(e.to_string()))?;
69    let nulls = BooleanBuffer::new(nulls.into(), 0, rows.len());
70    let nulls = NullBuffer::new(nulls);
71    Ok((nulls.null_count() > 0).then_some(nulls))
72}
73
74/// Variable length values are encoded as
75///
76/// - single `0_u8` if null
77/// - single `1_u8` if empty array
78/// - `2_u8` if not empty, followed by one or more blocks
79///
80/// where a block is encoded as
81///
82/// - [`BLOCK_SIZE`] bytes of string data, padded with 0s
83/// - `0xFF_u8` if this is not the last block for this string
84/// - otherwise the length of the block as a `u8`
85pub fn encode<'a, I: Iterator<Item = Option<&'a [u8]>>>(
86    data: &mut [u8],
87    offsets: &mut [usize],
88    i: I,
89    opts: SortOptions,
90) {
91    for (offset, maybe_val) in offsets.iter_mut().skip(1).zip(i) {
92        *offset += encode_one(&mut data[*offset..], maybe_val, opts);
93    }
94}
95
96/// Calls [`encode`] with optimized iterator for generic byte arrays
97pub(crate) fn encode_generic_byte_array<T: ByteArrayType>(
98    data: &mut [u8],
99    offsets: &mut [usize],
100    input_array: &GenericByteArray<T>,
101    opts: SortOptions,
102) {
103    let input_offsets = input_array.value_offsets();
104    let bytes = input_array.values().as_slice();
105
106    if let Some(null_buffer) = input_array.nulls().filter(|x| x.null_count() > 0) {
107        let input_iter =
108            input_offsets
109                .windows(2)
110                .zip(null_buffer.iter())
111                .map(|(start_end, is_valid)| {
112                    if is_valid {
113                        let item_range = start_end[0].as_usize()..start_end[1].as_usize();
114                        // SAFETY: the offsets of the input are valid by construction
115                        // so it is ok to use unsafe here
116                        let item = unsafe { bytes.get_unchecked(item_range) };
117                        Some(item)
118                    } else {
119                        None
120                    }
121                });
122
123        encode(data, offsets, input_iter, opts);
124    } else {
125        // Skip null checks
126        let input_iter = input_offsets.windows(2).map(|start_end| {
127            let item_range = start_end[0].as_usize()..start_end[1].as_usize();
128            // SAFETY: the offsets of the input are valid by construction
129            // so it is ok to use unsafe here
130            let item = unsafe { bytes.get_unchecked(item_range) };
131            Some(item)
132        });
133
134        encode(data, offsets, input_iter, opts);
135    }
136}
137
138pub fn encode_null(out: &mut [u8], opts: SortOptions) -> usize {
139    out[0] = null_sentinel(opts);
140    1
141}
142
143pub fn encode_empty(out: &mut [u8], opts: SortOptions) -> usize {
144    out[0] = match opts.descending {
145        true => !EMPTY_SENTINEL,
146        false => EMPTY_SENTINEL,
147    };
148    1
149}
150
151/// Ensure `NullArray`s don't get encoded as empty lists which can lose their length
152pub fn encode_null_value(out: &mut [u8], opts: SortOptions) -> usize {
153    out[0] = match opts.descending {
154        true => !NON_EMPTY_SENTINEL,
155        false => NON_EMPTY_SENTINEL,
156    };
157    out[1] = match opts.descending {
158        true => !NULL_VALUE_SENTINEL,
159        false => NULL_VALUE_SENTINEL,
160    };
161    2
162}
163
164#[inline]
165pub fn encode_one(out: &mut [u8], val: Option<&[u8]>, opts: SortOptions) -> usize {
166    match val {
167        None => encode_null(out, opts),
168        Some([]) => encode_empty(out, opts),
169        Some(val) => {
170            // Write `2_u8` to demarcate as non-empty, non-null string
171            out[0] = NON_EMPTY_SENTINEL;
172
173            let len = if val.len() <= BLOCK_SIZE {
174                1 + encode_blocks::<MINI_BLOCK_SIZE>(&mut out[1..], val)
175            } else {
176                let (initial, rem) = val.split_at(BLOCK_SIZE);
177                let offset = encode_blocks::<MINI_BLOCK_SIZE>(&mut out[1..], initial);
178                out[offset] = BLOCK_CONTINUATION;
179                1 + offset + encode_blocks::<BLOCK_SIZE>(&mut out[1 + offset..], rem)
180            };
181
182            if opts.descending {
183                // Invert bits
184                out[..len].iter_mut().for_each(|v| *v = !*v)
185            }
186            len
187        }
188    }
189}
190
191/// Writes `val` in `SIZE` blocks with the appropriate continuation tokens
192#[inline]
193fn encode_blocks<const SIZE: usize>(out: &mut [u8], val: &[u8]) -> usize {
194    let block_count = ceil(val.len(), SIZE);
195    let end_offset = block_count * (SIZE + 1);
196    let to_write = &mut out[..end_offset];
197
198    let (chunks, remainder) = val.as_chunks::<SIZE>();
199    let to_write_chunks = to_write.chunks_exact_mut(SIZE + 1);
200    for (input, output) in chunks.iter().zip(to_write_chunks) {
201        let out_block: &mut [u8; SIZE] = (&mut output[..SIZE]).try_into().unwrap();
202
203        *out_block = *input;
204
205        // Indicate that there are further blocks to follow
206        output[SIZE] = BLOCK_CONTINUATION;
207    }
208
209    if !remainder.is_empty() {
210        let start_offset = (block_count - 1) * (SIZE + 1);
211        to_write[start_offset..start_offset + remainder.len()].copy_from_slice(remainder);
212        *to_write.last_mut().unwrap() = remainder.len() as u8;
213    } else {
214        // We must overwrite the continuation marker written by the loop above
215        *to_write.last_mut().unwrap() = SIZE as u8;
216    }
217    end_offset
218}
219
220/// Decodes a single block of data
221/// The `f` function accepts a slice of the decoded data, it may be called multiple times
222pub fn decode_blocks(row: &[u8], options: SortOptions, mut f: impl FnMut(&[u8])) -> usize {
223    let (non_empty_sentinel, continuation) = match options.descending {
224        true => (!NON_EMPTY_SENTINEL, !BLOCK_CONTINUATION),
225        false => (NON_EMPTY_SENTINEL, BLOCK_CONTINUATION),
226    };
227
228    if row[0] != non_empty_sentinel {
229        // Empty or null string
230        return 1;
231    }
232
233    // Extracts the block length from the sentinel
234    let block_len = |sentinel: u8| match options.descending {
235        true => !sentinel as usize,
236        false => sentinel as usize,
237    };
238
239    let mut idx = 1;
240    for _ in 0..MINI_BLOCK_COUNT {
241        let sentinel = row[idx + MINI_BLOCK_SIZE];
242        if sentinel != continuation {
243            f(&row[idx..idx + block_len(sentinel)]);
244            return idx + MINI_BLOCK_SIZE + 1;
245        }
246        f(&row[idx..idx + MINI_BLOCK_SIZE]);
247        idx += MINI_BLOCK_SIZE + 1;
248    }
249
250    loop {
251        let sentinel = row[idx + BLOCK_SIZE];
252        if sentinel != continuation {
253            f(&row[idx..idx + block_len(sentinel)]);
254            return idx + BLOCK_SIZE + 1;
255        }
256        f(&row[idx..idx + BLOCK_SIZE]);
257        idx += BLOCK_SIZE + 1;
258    }
259}
260
261/// Returns the number of bytes of encoded data
262fn decoded_len(row: &[u8], options: SortOptions) -> usize {
263    let mut len = 0;
264    decode_blocks(row, options, |block| len += block.len());
265    len
266}
267
268/// Decodes a binary array from `rows` with the provided `options`
269pub fn decode_binary<I: OffsetSizeTrait>(
270    rows: &mut [&[u8]],
271    options: SortOptions,
272) -> Result<GenericBinaryArray<I>, ArrowError> {
273    let len = rows.len();
274    let nulls = decode_nulls_sentinel(rows, options)?;
275
276    let values_capacity = rows.iter().map(|row| decoded_len(row, options)).sum();
277    I::from_usize(values_capacity).ok_or(ArrowError::OffsetOverflowError(values_capacity))?;
278    let mut offsets = Vec::<I>::with_capacity(len + 1);
279    offsets.push(I::zero());
280    let mut values = MutableBuffer::try_with_capacity(values_capacity)
281        .map_err(|e| ArrowError::MemoryError(e.to_string()))?;
282
283    for row in rows {
284        let offset = decode_blocks(row, options, |b| values.extend_from_slice(b));
285        *row = &row[offset..];
286        offsets.push(I::usize_as(values.len()))
287    }
288
289    if options.descending {
290        values.as_slice_mut().iter_mut().for_each(|o| *o = !*o)
291    }
292
293    // SAFETY:
294    // Valid by construction above
295    Ok(unsafe {
296        GenericBinaryArray::new_unchecked(
297            OffsetBuffer::new(ScalarBuffer::from(offsets)),
298            values.into(),
299            nulls,
300        )
301    })
302}
303
304fn decode_binary_view_inner<const VALIDATE_UTF8: bool>(
305    rows: &mut [&[u8]],
306    options: SortOptions,
307) -> Result<BinaryViewArray, ArrowError> {
308    let len = rows.len();
309    let inline_str_max_len = MAX_INLINE_VIEW_LEN as usize;
310
311    let nulls = decode_nulls_sentinel(rows, options)?;
312
313    // Capacity for all long strings plus room for one short string
314    let mut values_capacity = inline_str_max_len;
315    let mut inline_capacity = 0;
316    for row in rows.iter() {
317        let len = decoded_len(row, options);
318        if len > inline_str_max_len {
319            values_capacity += len;
320        } else if VALIDATE_UTF8 {
321            inline_capacity += len;
322        }
323    }
324    // Every view offset is at most the total length of the non-inlined values,
325    // so checking it once here keeps the offsets below within the `i32` range
326    // the Arrow spec requires
327    let long_values_len = values_capacity - inline_str_max_len;
328    if long_values_len > i32::MAX as usize {
329        return Err(ArrowError::InvalidArgumentError(format!(
330            "{long_values_len} bytes of non-inlined values too long to decode into a view array with a single data buffer"
331        )));
332    }
333    let mut values = MutableBuffer::try_with_capacity(values_capacity)
334        .map_err(|e| ArrowError::MemoryError(e.to_string()))?;
335    let mut view_utf8_validation_buffer = if VALIDATE_UTF8 {
336        Vec::with_capacity(inline_capacity)
337    } else {
338        Vec::new()
339    };
340
341    let null_sentinel = null_sentinel(options);
342    let mut views = vec![0_u128; len];
343    for (i, row) in rows.iter_mut().enumerate() {
344        let start_offset = values.len();
345        let offset = decode_blocks(row, options, |b| values.extend_from_slice(b));
346        // Measure string length via change in values buffer. This way we can
347        // overwrite short strings in the values buffer as we inline those to
348        // views.
349        let decoded_len = values.len() - start_offset;
350        if row[0] == null_sentinel {
351            debug_assert_eq!(offset, 1);
352            debug_assert_eq!(start_offset, values.len());
353        } else {
354            // Safety: we just appended the data to the end of the buffer
355            let val = unsafe { values.get_unchecked_mut(start_offset..) };
356
357            if options.descending {
358                val.iter_mut().for_each(|o| *o = !*o);
359            }
360
361            views[i] = make_view(val, 0, start_offset as u32);
362
363            if decoded_len <= inline_str_max_len {
364                if VALIDATE_UTF8 {
365                    view_utf8_validation_buffer.extend_from_slice(val);
366                }
367                values.truncate(start_offset);
368            }
369        }
370        *row = &row[offset..];
371    }
372
373    if VALIDATE_UTF8 {
374        std::str::from_utf8(&values).unwrap();
375        std::str::from_utf8(&view_utf8_validation_buffer).unwrap();
376    }
377
378    // SAFETY:
379    // Valid by construction above
380    Ok(unsafe { BinaryViewArray::new_unchecked(views.into(), [values.into()].into(), nulls) })
381}
382
383/// Decodes a binary view array from `rows` with the provided `options`
384///
385/// Returns an error if the non-inlined values are longer than `i32::MAX` bytes,
386/// the most a single data buffer can address
387pub fn decode_binary_view(
388    rows: &mut [&[u8]],
389    options: SortOptions,
390) -> Result<BinaryViewArray, ArrowError> {
391    decode_binary_view_inner::<false>(rows, options)
392}
393
394/// Decodes a string array from `rows` with the provided `options`
395///
396/// # Safety
397///
398/// The row must contain valid UTF-8 data
399pub unsafe fn decode_string<I: OffsetSizeTrait>(
400    rows: &mut [&[u8]],
401    options: SortOptions,
402    validate_utf8: bool,
403) -> Result<GenericStringArray<I>, ArrowError> {
404    let decoded = decode_binary::<I>(rows, options)?;
405
406    if validate_utf8 {
407        return Ok(GenericStringArray::from(decoded));
408    }
409
410    let (offsets, values, nulls) = decoded.into_parts();
411
412    // SAFETY:
413    // Row data must have come from a valid UTF-8 array
414    Ok(unsafe { GenericStringArray::new_unchecked(offsets, values, nulls) })
415}
416
417/// Decodes a string view array from `rows` with the provided `options`
418///
419/// # Safety
420///
421/// The row must contain valid UTF-8 data
422///
423/// Returns an error if the non-inlined values are longer than `i32::MAX` bytes,
424/// the most a single data buffer can address
425pub unsafe fn decode_string_view(
426    rows: &mut [&[u8]],
427    options: SortOptions,
428    validate_utf8: bool,
429) -> Result<StringViewArray, ArrowError> {
430    let view = if validate_utf8 {
431        decode_binary_view_inner::<true>(rows, options)?
432    } else {
433        decode_binary_view_inner::<false>(rows, options)?
434    };
435    Ok(unsafe { view.to_string_view_unchecked() })
436}
437
438pub fn decode_null_value(rows: &mut [&[u8]], options: SortOptions) {
439    for row in rows.iter_mut() {
440        let (sentinel1, sentinel2) = match options.descending {
441            true => (!NON_EMPTY_SENTINEL, !NULL_VALUE_SENTINEL),
442            false => (NON_EMPTY_SENTINEL, NULL_VALUE_SENTINEL),
443        };
444        debug_assert_eq!(row[0], sentinel1, "Expected NULL_VALUE_SENTINEL at byte 0");
445        debug_assert_eq!(row[1], sentinel2, "Expected NULL_VALUE_SENTINEL at byte 1");
446        *row = &row[2..];
447    }
448}