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}