Skip to main content

arrow_buffer/buffer/
run.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::ArrowNativeType;
6use crate::buffer::ScalarBuffer;
7
8/// A buffer of monotonically increasing, positive integers used to store run-ends.
9///
10/// Used to compactly represent runs of the same value. Values being represented
11/// are stored in a separate buffer from this struct. See [`RunArray`] for an example
12/// of how this is used with a companion array to represent the values.
13///
14/// # Logical vs Physical
15///
16/// Physically, each value in the `run_ends` buffer is the cumulative length of
17/// all runs in the logical representation, up to that physical index. Consider
18/// the following example:
19///
20/// ```text
21///           physical                        logical
22///     ┌─────────┬─────────┐           ┌─────────┬─────────┐
23///     │    3    │    0    │ ◄──────┬─ │    A    │    0    │
24///     ├─────────┼─────────┤        │  ├─────────┼─────────┤
25///     │    4    │    1    │ ◄────┐ ├─ │    A    │    1    │
26///     ├─────────┼─────────┤      │ │  ├─────────┼─────────┤
27///     │    6    │    2    │ ◄──┐ │ └─ │    A    │    2    │
28///     └─────────┴─────────┘    │ │    ├─────────┼─────────┤
29///      run-ends    index       │ └─── │    B    │    3    │
30///                              │      ├─────────┼─────────┤
31///      logical_offset = 0      ├───── │    C    │    4    │
32///      logical_length = 6      │      ├─────────┼─────────┤
33///                              └───── │    C    │    5    │
34///                                     └─────────┴─────────┘
35///                                       values     index
36/// ```
37///
38/// A [`RunEndBuffer`] is physically the buffer and offset with length on the left.
39/// In this case, the offset and length represent the whole buffer, so it is essentially
40/// unsliced. See the section below on slicing for more details on how this buffer
41/// handles slicing.
42///
43/// This means that multiple logical values are represented in the same physical index,
44/// and multiple logical indices map to the same physical index. The [`RunEndBuffer`]
45/// containing `[3, 4, 6]` is essentially the physical indices `[0, 0, 0, 1, 2, 2]`,
46/// and having a separately stored buffer of values such as `[A, B, C]` can turn
47/// this into a representation of `[A, A, A, B, C, C]`.
48///
49/// # Slicing
50///
51/// In order to provide zero-copy slicing, this struct stores a separate **logical**
52/// offset and length. Consider the following example:
53///
54/// ```text
55///           physical                        logical
56///     ┌─────────┬─────────┐           ┌ ─ ─ ─ ─ ┬ ─ ─ ─ ─ ┐
57///     │    3    │    0    │ ◄──────┐       A         0
58///     ├─────────┼─────────┤        │  ├── ─ ─ ─ ┼ ─ ─ ─ ─ ┤
59///     │    4    │    1    │ ◄────┐ │       A         1
60///     ├─────────┼─────────┤      │ │  ├─────────┼─────────┤
61///     │    6    │    2    │ ◄──┐ │ └─ │    A    │    2    │◄─── logical_offset
62///     └─────────┴─────────┘    │ │    ├─────────┼─────────┤
63///      run-ends    index       │ └─── │    B    │    3    │
64///                              │      ├─────────┼─────────┤
65///      logical_offset = 2      └───── │    C    │    4    │
66///      logical_length = 3             ├─────────┼─────────┤
67///                                          C         5     ◄─── logical_offset + logical_length
68///                                     └ ─ ─ ─ ─ ┴ ─ ─ ─ ─ ┘
69///                                       values     index
70/// ```
71///
72/// The physical `run_ends` [`ScalarBuffer`] remains unchanged, in order to facilitate
73/// zero-copy. However, we now offset into the **logical** representation with an
74/// accompanying length. This allows us to represent values `[A, B, C]` using physical
75/// indices `0, 1, 2` with the same underlying physical buffer, at the cost of two
76/// extra `usize`s to represent the logical slice that was taken.
77///
78/// (A [`RunEndBuffer`] is considered unsliced when `logical_offset` is `0` and
79/// `logical_length` is equal to the last value in `run_ends`)
80///
81/// [`RunArray`]: https://docs.rs/arrow/latest/arrow/array/struct.RunArray.html
82/// [Run-End encoded layout]: https://arrow.apache.org/docs/format/Columnar.html#run-end-encoded-layout
83#[derive(Debug, Clone)]
84pub struct RunEndBuffer<E: ArrowNativeType> {
85    run_ends: ScalarBuffer<E>,
86    logical_length: usize,
87    logical_offset: usize,
88}
89
90impl<E> RunEndBuffer<E>
91where
92    E: ArrowNativeType,
93{
94    /// Create a new [`RunEndBuffer`] from a [`ScalarBuffer`], `logical_offset`
95    /// and `logical_length`.
96    ///
97    /// # Panics
98    ///
99    /// Panics if the [`RunArray` invariants] are not satisfied:
100    ///
101    /// - `run_ends` does not contain strictly increasing values greater than zero
102    /// - `logical_length` is not 0 and the last value of `run_ends` is less than
103    ///   `logical_offset + logical_length` (an empty slice is always accepted)
104    ///
105    /// [`RunArray` invariants]: https://docs.rs/arrow/latest/arrow/array/struct.RunArray.html#offset-and-len
106    pub fn new(run_ends: ScalarBuffer<E>, logical_offset: usize, logical_length: usize) -> Self {
107        assert!(
108            run_ends.windows(2).all(|w| w[0] < w[1]),
109            "run-ends not strictly increasing"
110        );
111
112        if logical_length != 0 {
113            assert!(!run_ends.is_empty(), "non-empty slice but empty run-ends");
114            let end = E::from_usize(logical_offset.saturating_add(logical_length)).unwrap();
115            assert!(
116                *run_ends.first().unwrap() > E::usize_as(0),
117                "run-ends not greater than 0"
118            );
119            assert!(
120                *run_ends.last().unwrap() >= end,
121                "slice beyond bounds of run-ends"
122            );
123        }
124
125        Self {
126            run_ends,
127            logical_length,
128            logical_offset,
129        }
130    }
131
132    /// Create a new [`RunEndBuffer`] from a [`ScalarBuffer`], `logical_offset`
133    /// and `logical_length`.
134    ///
135    /// # Safety
136    ///
137    /// `run_ends` must satisfy the [`RunArray` invariants]:
138    ///
139    /// - `run_ends` must contain strictly increasing values greater than zero
140    /// - If `logical_length` is not 0, the last value of `run_ends` must be
141    ///   greater than or equal to `logical_offset + logical_length`
142    ///
143    /// [`RunArray` invariants]: https://docs.rs/arrow/latest/arrow/array/struct.RunArray.html#offset-and-len
144    pub unsafe fn new_unchecked(
145        run_ends: ScalarBuffer<E>,
146        logical_offset: usize,
147        logical_length: usize,
148    ) -> Self {
149        Self {
150            run_ends,
151            logical_length,
152            logical_offset,
153        }
154    }
155
156    /// Returns the logical offset into the run-ends stored by this buffer.
157    #[inline]
158    pub fn offset(&self) -> usize {
159        self.logical_offset
160    }
161
162    /// Returns the logical length of the run-ends stored by this buffer.
163    #[inline]
164    pub fn len(&self) -> usize {
165        self.logical_length
166    }
167
168    /// Returns true if this buffer is logically empty.
169    #[inline]
170    pub fn is_empty(&self) -> bool {
171        self.logical_length == 0
172    }
173
174    /// Free up unused memory.
175    pub fn shrink_to_fit(&mut self) {
176        // TODO(emilk): we could shrink even more in the case where we are a small sub-slice of the full buffer
177        self.run_ends.shrink_to_fit();
178    }
179
180    /// Returns the physical (**unsliced**) run ends of this buffer.
181    ///
182    /// Take care when operating on these values as it doesn't take into account
183    /// any logical slicing that may have occurred.
184    #[inline]
185    pub fn values(&self) -> &[E] {
186        &self.run_ends
187    }
188
189    /// Returns an iterator yielding run ends adjusted for the logical slice.
190    ///
191    /// Each yielded value is subtracted by the [`logical_offset`] and capped
192    /// at the [`logical_length`].
193    ///
194    /// [`logical_offset`]: Self::offset
195    /// [`logical_length`]: Self::len
196    pub fn sliced_values(&self) -> impl Iterator<Item = E> + '_ {
197        let offset = self.logical_offset;
198        let len = self.logical_length;
199        // Doing this roundabout way since the iterator type we return must be
200        // the same (i.e. cannot use std::iter::empty())
201        let physical_slice = if self.is_empty() {
202            &self.run_ends[0..0]
203        } else {
204            let start = self.get_start_physical_index();
205            let end = self.get_end_physical_index();
206            &self.run_ends[start..=end]
207        };
208        physical_slice.iter().map(move |&val| {
209            // `len` is at most the largest run end, so it always fits in `E`
210            let val = val.as_usize().saturating_sub(offset).min(len);
211            E::usize_as(val)
212        })
213    }
214
215    /// Returns the maximum run-end encoded in the underlying buffer; that is, the
216    /// last physical run of the buffer. This does not take into account any logical
217    /// slicing that may have occurred.
218    #[inline]
219    pub fn max_value(&self) -> usize {
220        self.values().last().copied().unwrap_or_default().as_usize()
221    }
222
223    /// Performs a binary search to find the physical index for the given logical
224    /// index.
225    ///
226    /// Useful for extracting the corresponding physical `run_ends` when this buffer
227    /// is logically sliced.
228    ///
229    /// The result is arbitrary if `logical_index >= self.len()`.
230    pub fn get_physical_index(&self, logical_index: usize) -> usize {
231        let logical_index = self.logical_offset + logical_index;
232        let cmp = |p: &E| p.as_usize().cmp(&logical_index);
233
234        match self.run_ends.binary_search_by(cmp) {
235            Ok(idx) => idx + 1,
236            Err(idx) => idx,
237        }
238    }
239
240    /// Returns the physical index at which the logical array starts.
241    ///
242    /// The same as calling `get_physical_index(0)` but with a fast path if the
243    /// buffer is not logically sliced, in which case it always returns `0`.
244    pub fn get_start_physical_index(&self) -> usize {
245        if self.logical_offset == 0 || self.logical_length == 0 {
246            return 0;
247        }
248        // Fallback to binary search
249        self.get_physical_index(0)
250    }
251
252    /// Returns the physical index at which the logical array ends.
253    ///
254    /// The same as calling `get_physical_index(length - 1)` but with a fast path
255    /// if the buffer is not logically sliced, in which case it returns `length - 1`.
256    pub fn get_end_physical_index(&self) -> usize {
257        if self.logical_length == 0 {
258            return 0;
259        }
260        if self.max_value() == self.logical_offset + self.logical_length {
261            return self.values().len() - 1;
262        }
263        // Fallback to binary search
264        self.get_physical_index(self.logical_length - 1)
265    }
266
267    /// Slices this [`RunEndBuffer`] by the provided `logical_offset` and `logical_length`.
268    ///
269    /// # Panics
270    ///
271    /// - Specified slice (`logical_offset` + `logical_length`) exceeds existing
272    ///   logical length
273    pub fn slice(&self, logical_offset: usize, logical_length: usize) -> Self {
274        assert!(
275            logical_offset.saturating_add(logical_length) <= self.logical_length,
276            "the length + offset of the sliced RunEndBuffer cannot exceed the existing length"
277        );
278        Self {
279            run_ends: self.run_ends.clone(),
280            logical_offset: self.logical_offset + logical_offset,
281            logical_length,
282        }
283    }
284
285    /// Returns the inner [`ScalarBuffer`].
286    pub fn inner(&self) -> &ScalarBuffer<E> {
287        &self.run_ends
288    }
289
290    /// Returns the inner [`ScalarBuffer`], consuming self.
291    pub fn into_inner(self) -> ScalarBuffer<E> {
292        self.run_ends
293    }
294
295    /// Claim memory used by this buffer in the provided memory pool.
296    #[cfg(feature = "pool")]
297    pub fn claim(&self, pool: &dyn crate::MemoryPool) {
298        self.run_ends.claim(pool);
299    }
300
301    /// Returns the physical indices corresponding to the provided logical indices.
302    ///
303    /// Given a slice of logical indices, this method returns a `Vec` containing the
304    /// corresponding physical indices into the run-ends buffer.
305    ///
306    /// This method operates by iterating the logical indices in sorted order, instead of
307    /// finding the physical index for each logical index using binary search via
308    /// the function [`RunEndBuffer::get_physical_index`].
309    ///
310    /// Running benchmarks on both approaches showed that the approach used here
311    /// scaled well for larger inputs.
312    ///
313    /// See <https://github.com/apache/arrow-rs/pull/3622#issuecomment-1407753727> for more details.
314    ///
315    /// # Errors
316    ///
317    /// If any logical index is out of bounds (>= self.len()), returns an error containing the invalid index.
318    #[inline]
319    pub fn get_physical_indices<I>(&self, logical_indices: &[I]) -> Result<Vec<usize>, I>
320    where
321        I: ArrowNativeType,
322    {
323        let len = self.len();
324        let offset = self.offset();
325
326        let indices_len = logical_indices.len();
327
328        if indices_len == 0 {
329            return Ok(vec![]);
330        }
331
332        // `ordered_indices` store index into `logical_indices` and can be used
333        // to iterate `logical_indices` in sorted order.
334        let mut ordered_indices: Vec<usize> = (0..indices_len).collect();
335
336        // Instead of sorting `logical_indices` directly, sort the `ordered_indices`
337        // whose values are index of `logical_indices`
338        ordered_indices.sort_unstable_by_key(|&idx| logical_indices[idx].as_usize());
339
340        // Return early if all the logical indices cannot be converted to physical indices.
341        // `ordered_indices` has `indices_len` entries, and the empty case returned above.
342        let largest_logical_index = logical_indices[ordered_indices[indices_len - 1]];
343        if largest_logical_index.as_usize() >= len {
344            return Err(largest_logical_index);
345        }
346
347        // Skip some physical indices based on offset.
348        let skip_value = self.get_start_physical_index();
349
350        let mut physical_indices = vec![0; indices_len];
351
352        let mut ordered_index = 0_usize;
353        for (physical_index, run_end) in self.values().iter().enumerate().skip(skip_value) {
354            // Get the run end index (relative to offset) of current physical index
355            let run_end_value = run_end.as_usize() - offset;
356
357            // All the `logical_indices` that are less than current run end index
358            // belongs to current physical index.
359            while ordered_index < indices_len
360                && logical_indices[ordered_indices[ordered_index]].as_usize() < run_end_value
361            {
362                physical_indices[ordered_indices[ordered_index]] = physical_index;
363                ordered_index += 1;
364            }
365        }
366
367        // If there are input values >= run_ends.last_value then we'll not be able to convert
368        // all logical indices to physical indices.
369        if ordered_index < logical_indices.len() {
370            return Err(logical_indices[ordered_indices[ordered_index]]);
371        }
372        Ok(physical_indices)
373    }
374}
375
376#[cfg(test)]
377mod tests {
378    use crate::buffer::RunEndBuffer;
379
380    #[test]
381    fn test_zero_length_slice() {
382        let buffer = RunEndBuffer::new(vec![1_i32, 4_i32].into(), 0, 4);
383        assert_eq!(buffer.get_start_physical_index(), 0);
384        assert_eq!(buffer.get_end_physical_index(), 1);
385        assert_eq!(buffer.get_physical_index(3), 1);
386
387        for offset in 0..4 {
388            let sliced = buffer.slice(offset, 0);
389            assert_eq!(sliced.get_start_physical_index(), 0);
390            assert_eq!(sliced.get_end_physical_index(), 0);
391        }
392
393        let buffer = RunEndBuffer::new(Vec::<i32>::new().into(), 0, 0);
394        assert_eq!(buffer.get_start_physical_index(), 0);
395        assert_eq!(buffer.get_end_physical_index(), 0);
396    }
397
398    #[test]
399    fn test_sliced_values() {
400        // [0, 0, 1, 2, 2, 2]
401        let buffer = RunEndBuffer::new(vec![2i32, 3, 6].into(), 0, 6);
402
403        // Slice: [0, 1, 2, 2] start: 1, len: 4
404        // Logical indices: 1, 2, 3, 4
405        // Original run ends: [2, 3, 6]
406        // Adjusted: [2-1, 3-1, 6-1] capped at 4 -> [1, 2, 4]
407        let sliced = buffer.slice(1, 4);
408        let sliced_values: Vec<i32> = sliced.sliced_values().collect();
409        assert_eq!(sliced_values, &[1, 2, 4]);
410
411        // Slice: [2, 2] start: 4, len: 2
412        // Original run ends: [2, 3, 6]
413        // Slicing at 4 means we only have the last run (physical index 2, which ends at 6)
414        // Adjusted: [6-4] capped at 2 -> [2]
415        let sliced = buffer.slice(4, 2);
416        let sliced_values: Vec<i32> = sliced.sliced_values().collect();
417        assert_eq!(sliced_values, &[2]);
418    }
419}