Skip to main content

vortex_array/arrays/listview/compute/
zip.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use std::mem::MaybeUninit;
5use std::ops::BitAnd;
6use std::ops::BitOr;
7use std::ops::Not;
8
9use itertools::Either;
10use vortex_buffer::Buffer;
11use vortex_buffer::BufferMut;
12use vortex_error::VortexExpect;
13use vortex_error::VortexResult;
14use vortex_mask::Mask;
15
16use crate::ArrayRef;
17use crate::ExecutionCtx;
18use crate::IntoArray;
19use crate::array::ArrayView;
20use crate::arrays::Chunked;
21use crate::arrays::ChunkedArray;
22use crate::arrays::ListView;
23use crate::arrays::ListViewArray;
24use crate::arrays::chunked::ChunkedArrayExt;
25use crate::arrays::listview::ListViewArraySlotsExt;
26use crate::builtins::ArrayBuiltins;
27use crate::dtype::DType;
28use crate::dtype::Nullability;
29use crate::dtype::PType;
30use crate::scalar_fn::fns::zip::ZipKernel;
31use crate::validity::Validity;
32
33/// Zip two [`ListViewArray`]s by selecting whole list views per row.
34///
35/// A [`ListViewArray`] addresses each list by an `(offset, size)` pair into a shared `elements`
36/// array, and unlike [`ListArray`](crate::arrays::ListArray) it does not require lists to be stored
37/// contiguously or in order. Zipping two list views is therefore a metadata-only operation over the
38/// `offsets`, `sizes` and `validity` child arrays: we concatenate the two `elements` arrays
39/// (without rewriting them) and, for each row, select the `(offset, size)` pair from `if_true` or
40/// `if_false` per the mask. `if_false` views are shifted past the end of `if_true`'s elements so
41/// they continue to address the correct half of the concatenated elements array.
42impl ZipKernel for ListView {
43    fn zip(
44        if_true: ArrayView<'_, ListView>,
45        if_false: &ArrayRef,
46        mask: &ArrayRef,
47        ctx: &mut ExecutionCtx,
48    ) -> VortexResult<Option<ArrayRef>> {
49        let Some(if_false) = if_false.as_opt::<ListView>() else {
50            return Ok(None);
51        };
52
53        // Null mask entries select `if_false`, matching `Zip`'s SQL ELSE semantics.
54        let mask = mask.clone().fill_null(false)?.execute::<Mask>(ctx)?;
55        match &mask {
56            // Defer the trivial masks to the generic zip, which just casts one side.
57            Mask::AllTrue(_) | Mask::AllFalse(_) => return Ok(None),
58            Mask::Values(_) => {}
59        }
60
61        let len = if_true.len();
62
63        let result_elements_dtype = if_true
64            .elements()
65            .dtype()
66            .union_nullability(if_false.elements().dtype().nullability());
67
68        // `if_false`'s elements share the element dtype up to nullability; normalize so both chunks
69        // of the concatenated elements array have an identical dtype.
70        let true_elements = if_true.elements().cast(result_elements_dtype.clone())?;
71        let false_elements = if_false.elements().cast(result_elements_dtype.clone())?;
72
73        // `if_false` views index into the second half of the concatenated elements.
74        let false_shift = true_elements.len() as u64;
75
76        // Concatenate the two `elements` arrays without copying. If either side is already a
77        // `ChunkedArray` (e.g. the result of a previous list-view zip), splice its chunks in
78        // directly rather than nesting chunked arrays.
79        let chunks = element_chunks(&true_elements).chain(element_chunks(&false_elements));
80        let elements = ChunkedArray::try_new(chunks, result_elements_dtype)?.into_array();
81
82        let true_offsets = to_u64(if_true.offsets(), ctx)?;
83        let true_sizes = to_u64(if_true.sizes(), ctx)?;
84        let false_offsets = to_u64(if_false.offsets(), ctx)?;
85        let false_sizes = to_u64(if_false.sizes(), ctx)?;
86
87        let mut offsets = BufferMut::<u64>::with_capacity(len);
88        let mut sizes = BufferMut::<u64>::with_capacity(len);
89        {
90            let true_offsets = true_offsets.as_slice();
91            let true_sizes = true_sizes.as_slice();
92            let false_offsets = false_offsets.as_slice();
93            let false_sizes = false_sizes.as_slice();
94
95            let offsets_out = offsets.spare_capacity_mut();
96            let sizes_out = sizes.spare_capacity_mut();
97
98            // We matched `Mask::Values` above, so the bit buffer is materialized. `unaligned_chunks`
99            // iterates faster than `chunks`: it exposes the byte-aligned body as a plain `&[u64]`
100            // with no per-word reshifting, isolating any bit misalignment into a leading `prefix`
101            // and trailing `suffix` word. We blend both sides branchlessly per row so the compiler
102            // vectorizes the inner select instead of mispredicting a data-dependent branch.
103            let mask_bits = mask
104                .values()
105                .vortex_expect("mask is Mask::Values")
106                .bit_buffer();
107            let unaligned = mask_bits.unaligned_chunks();
108            // The prefix word's low `lead` bits are padding; shifting them out aligns row 0 to bit 0,
109            // after which every chunk and the suffix start cleanly on a row boundary.
110            let lead = unaligned.lead_padding();
111
112            let mut select_block = |word: u64, base: usize, n: usize| {
113                let end = base + n;
114                // `if_false` views address the second half of the concatenated elements, so shift
115                // their offsets by `false_shift`; sizes are taken verbatim from the chosen side.
116                select_column(
117                    word,
118                    &true_offsets[base..end],
119                    &false_offsets[base..end],
120                    false_shift,
121                    &mut offsets_out[base..end],
122                );
123                select_column(
124                    word,
125                    &true_sizes[base..end],
126                    &false_sizes[base..end],
127                    0,
128                    &mut sizes_out[base..end],
129                );
130            };
131
132            let mut base = 0;
133            if let Some(prefix) = unaligned.prefix() {
134                let n = (64 - lead).min(len);
135                select_block(prefix >> lead, base, n);
136                base += n;
137            }
138            for &word in unaligned.chunks() {
139                select_block(word, base, 64);
140                base += 64;
141            }
142            if let Some(suffix) = unaligned.suffix() {
143                select_block(suffix, base, len - base);
144            }
145        }
146
147        // SAFETY: `select_column` initialized exactly `len` slots in both buffers.
148        unsafe {
149            offsets.set_len(len);
150            sizes.set_len(len);
151        }
152
153        let validity = zip_validity(if_true.validity()?, if_false.validity()?, &mask, ctx)?;
154
155        Ok(Some(
156            ListViewArray::try_new(
157                elements,
158                offsets.freeze().into_array(),
159                sizes.freeze().into_array(),
160                validity,
161                ctx,
162            )?
163            .into_array(),
164        ))
165    }
166}
167
168/// Branchlessly select one `u64` column per row from `if_true` or `if_false`.
169///
170/// `word` holds the mask bits for this block, bit `j` (LSB-first) selecting row `j`: a set bit keeps
171/// `true_vals[j]`, an unset bit keeps `false_vals[j] + false_add`. The bit is expanded to a
172/// full-width lane mask and blended, so the inner loop is branch-free and auto-vectorizable. Inputs
173/// are sliced to the output length up front so the compiler can elide bounds checks across the block.
174#[inline]
175fn select_column(
176    word: u64,
177    true_vals: &[u64],
178    false_vals: &[u64],
179    false_add: u64,
180    out: &mut [MaybeUninit<u64>],
181) {
182    let n = out.len();
183    let true_vals = &true_vals[..n];
184    let false_vals = &false_vals[..n];
185    for j in 0..n {
186        // 0 for an unset bit, `u64::MAX` for a set bit.
187        let lane = 0u64.wrapping_sub((word >> j) & 1);
188        out[j].write((true_vals[j] & lane) | ((false_vals[j] + false_add) & !lane));
189    }
190}
191
192/// Iterates over `array`'s element chunks, flattening a top-level [`ChunkedArray`] so the
193/// concatenated elements never nest chunked arrays.
194fn element_chunks(array: &ArrayRef) -> impl Iterator<Item = ArrayRef> + '_ {
195    match array.as_opt::<Chunked>() {
196        Some(chunked) => {
197            Either::Left((0..chunked.nchunks()).map(move |i| chunked.chunk(i).clone()))
198        }
199        None => Either::Right(std::iter::once(array.clone())),
200    }
201}
202
203/// Read a non-nullable integer array into a `u64` buffer.
204fn to_u64(array: &ArrayRef, ctx: &mut ExecutionCtx) -> VortexResult<Buffer<u64>> {
205    array
206        .clone()
207        .cast(DType::Primitive(PType::U64, Nullability::NonNullable))?
208        .execute::<Buffer<u64>>(ctx)
209}
210
211/// Combine the two list-level validities, taking `if_true`'s validity where `mask` is set and
212/// `if_false`'s where it is not.
213fn zip_validity(
214    if_true: Validity,
215    if_false: Validity,
216    mask: &Mask,
217    ctx: &mut ExecutionCtx,
218) -> VortexResult<Validity> {
219    Ok(match (&if_true, &if_false) {
220        (Validity::NonNullable, Validity::NonNullable) => Validity::NonNullable,
221        (Validity::AllValid, Validity::AllValid) => Validity::AllValid,
222        (Validity::AllInvalid, Validity::AllInvalid) => Validity::AllInvalid,
223        _ => {
224            let true_mask = if_true.execute_mask(mask.len(), ctx)?;
225            let false_mask = if_false.execute_mask(mask.len(), ctx)?;
226            let combined = true_mask
227                .bitand(mask)
228                .bitor(&false_mask.bitand(&mask.not()));
229            Validity::from_mask(combined, if_true.nullability() | if_false.nullability())
230        }
231    })
232}
233
234#[cfg(test)]
235mod tests {
236    #![allow(
237        clippy::cast_possible_truncation,
238        reason = "test fixtures use small indices that fit the target widths"
239    )]
240
241    use std::sync::LazyLock;
242
243    use vortex_buffer::Buffer;
244    use vortex_buffer::buffer;
245    use vortex_error::VortexResult;
246    use vortex_mask::Mask;
247    use vortex_session::VortexSession;
248
249    use crate::ArrayRef;
250    use crate::IntoArray;
251    use crate::VortexSessionExecute;
252    use crate::arrays::BoolArray;
253    use crate::arrays::Chunked;
254    use crate::arrays::ChunkedArray;
255    use crate::arrays::ListView;
256    use crate::arrays::ListViewArray;
257    use crate::arrays::chunked::ChunkedArrayExt;
258    use crate::arrays::listview::ListViewArraySlotsExt;
259    use crate::assert_arrays_eq;
260    use crate::builtins::ArrayBuiltins;
261    use crate::dtype::DType;
262    use crate::dtype::Nullability;
263    use crate::dtype::PType;
264    use crate::validity::Validity;
265
266    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
267
268    fn list_view(
269        elements: ArrayRef,
270        offsets: ArrayRef,
271        sizes: ArrayRef,
272        validity: Validity,
273    ) -> ArrayRef {
274        let mut ctx = SESSION.create_execution_ctx();
275        ListViewArray::try_new(elements, offsets, sizes, validity, &mut ctx)
276            .unwrap()
277            .into_array()
278    }
279
280    /// `zip` of two list views selects whole lists per the mask and keeps the list encoding.
281    #[test]
282    fn zip_selects_lists() -> VortexResult<()> {
283        let mut ctx = SESSION.create_execution_ctx();
284        // [[1, 2], [3], [4, 5, 6]]
285        let if_true = list_view(
286            buffer![1i32, 2, 3, 4, 5, 6].into_array(),
287            buffer![0u32, 2, 3].into_array(),
288            buffer![2u32, 1, 3].into_array(),
289            Validity::NonNullable,
290        );
291        // [[10], [20, 21], [30]]
292        let if_false = list_view(
293            buffer![10i32, 20, 21, 30].into_array(),
294            buffer![0u32, 1, 3].into_array(),
295            buffer![1u32, 2, 1].into_array(),
296            Validity::NonNullable,
297        );
298        let mask = Mask::from_iter([true, false, true]);
299
300        let result = mask
301            .into_array()
302            .zip(if_true, if_false)?
303            .execute::<ArrayRef>(&mut ctx)?;
304
305        // The kernel should keep the list-view encoding rather than canonicalizing.
306        assert!(result.is::<ListView>());
307
308        // Expected: [[1, 2], [20, 21], [4, 5, 6]]
309        let expected = list_view(
310            buffer![1i32, 2, 20, 21, 4, 5, 6].into_array(),
311            buffer![0u32, 2, 4].into_array(),
312            buffer![2u32, 2, 3].into_array(),
313            Validity::NonNullable,
314        );
315        assert_arrays_eq!(result, expected, &mut ctx);
316        Ok(())
317    }
318
319    /// `zip` selects list-level validity from the chosen side and widens nullability.
320    #[test]
321    fn zip_selects_validity() -> VortexResult<()> {
322        let mut ctx = SESSION.create_execution_ctx();
323        // [[1], null, [2]] (list-level nulls)
324        let if_true = list_view(
325            buffer![1i32, 2].into_array(),
326            buffer![0u32, 1, 1].into_array(),
327            buffer![1u32, 0, 1].into_array(),
328            Validity::Array(BoolArray::from_iter([true, false, true]).into_array()),
329        );
330        // [[10], [20], null]
331        let if_false = list_view(
332            buffer![10i32, 20].into_array(),
333            buffer![0u32, 1, 2].into_array(),
334            buffer![1u32, 1, 0].into_array(),
335            Validity::Array(BoolArray::from_iter([true, true, false]).into_array()),
336        );
337        // true -> if_true, false -> if_false
338        let mask = Mask::from_iter([false, true, true]);
339
340        let result = mask.into_array().zip(if_true, if_false)?;
341
342        // Row 0 -> if_false[0] = [10]; row 1 -> if_true[1] = null; row 2 -> if_true[2] = [2]
343        let expected = list_view(
344            buffer![10i32, 2].into_array(),
345            buffer![0u32, 1, 1].into_array(),
346            buffer![1u32, 0, 1].into_array(),
347            Validity::Array(BoolArray::from_iter([true, false, true]).into_array()),
348        );
349        assert_arrays_eq!(result, expected, &mut ctx);
350        Ok(())
351    }
352
353    /// `zip` handles out-of-order/non-contiguous offsets and widens nullability when only one side
354    /// is nullable.
355    #[test]
356    fn zip_out_of_order_offsets_and_widening() -> VortexResult<()> {
357        let mut ctx = SESSION.create_execution_ctx();
358        // [[5, 6], [7], [8, 9]] expressed with out-of-order offsets.
359        let if_true = list_view(
360            buffer![7i32, 8, 9, 5, 6].into_array(),
361            buffer![3u32, 0, 1].into_array(),
362            buffer![2u32, 1, 2].into_array(),
363            Validity::NonNullable,
364        );
365        // [[100], null, [200, 201]]
366        let if_false = list_view(
367            buffer![100i32, 200, 201].into_array(),
368            buffer![0u32, 1, 1].into_array(),
369            buffer![1u32, 0, 2].into_array(),
370            Validity::Array(BoolArray::from_iter([true, false, true]).into_array()),
371        );
372        let mask = Mask::from_iter([true, true, false]);
373
374        let result = mask
375            .into_array()
376            .zip(if_true, if_false)?
377            .execute::<ArrayRef>(&mut ctx)?;
378        assert!(result.is::<ListView>());
379
380        // [[5, 6], [7], [200, 201]], all valid but nullable (widened by if_false).
381        let expected = list_view(
382            buffer![5i32, 6, 7, 200, 201].into_array(),
383            buffer![0u32, 2, 3].into_array(),
384            buffer![2u32, 1, 2].into_array(),
385            Validity::AllValid,
386        );
387        assert_arrays_eq!(result, expected, &mut ctx);
388        Ok(())
389    }
390
391    /// Zipping more rows than fit in a single 64-bit mask chunk exercises both the chunked select
392    /// loop and the trailing remainder, including the `false_shift` applied to `if_false` views.
393    #[test]
394    fn zip_spans_multiple_mask_chunks() -> VortexResult<()> {
395        let mut ctx = SESSION.create_execution_ctx();
396        // 130 single-element lists per side: `if_true[i] = [i]`, `if_false[i] = [1000 + i]`.
397        let len = 130usize;
398        let true_elements: Vec<i32> = (0..len as i32).collect();
399        let false_elements: Vec<i32> = (0..len as i32).map(|i| 1000 + i).collect();
400        let offsets: Vec<u64> = (0..len as u64).collect();
401        let sizes: Vec<u64> = vec![1; len];
402
403        let if_true = list_view(
404            true_elements
405                .iter()
406                .copied()
407                .collect::<Buffer<i32>>()
408                .into_array(),
409            offsets
410                .iter()
411                .copied()
412                .collect::<Buffer<u64>>()
413                .into_array(),
414            sizes.iter().copied().collect::<Buffer<u64>>().into_array(),
415            Validity::NonNullable,
416        );
417        let if_false = list_view(
418            false_elements
419                .iter()
420                .copied()
421                .collect::<Buffer<i32>>()
422                .into_array(),
423            offsets
424                .iter()
425                .copied()
426                .collect::<Buffer<u64>>()
427                .into_array(),
428            sizes.iter().copied().collect::<Buffer<u64>>().into_array(),
429            Validity::NonNullable,
430        );
431
432        // A non-trivial pattern that straddles the chunk boundary (index 63/64) and the remainder.
433        let mask_bits: Vec<bool> = (0..len).map(|i| i.is_multiple_of(3) || i == 64).collect();
434        let mask = Mask::from_iter(mask_bits.iter().copied());
435
436        let result = mask
437            .into_array()
438            .zip(if_true, if_false)?
439            .execute::<ArrayRef>(&mut ctx)?;
440        assert!(result.is::<ListView>());
441
442        // Each row collapses to a single element: `i` when the mask is set, else `1000 + i`.
443        let expected_elements: Vec<i32> = (0..len)
444            .map(|i| {
445                if mask_bits[i] {
446                    i as i32
447                } else {
448                    1000 + i as i32
449                }
450            })
451            .collect();
452        let expected = list_view(
453            expected_elements
454                .iter()
455                .copied()
456                .collect::<Buffer<i32>>()
457                .into_array(),
458            offsets
459                .iter()
460                .copied()
461                .collect::<Buffer<u64>>()
462                .into_array(),
463            sizes.iter().copied().collect::<Buffer<u64>>().into_array(),
464            Validity::NonNullable,
465        );
466        assert_arrays_eq!(result, expected, &mut ctx);
467        Ok(())
468    }
469
470    /// A mask whose bit buffer starts at a non-byte-aligned offset (here from slicing a bool array)
471    /// has non-zero `unaligned_chunks` lead padding, exercising the prefix word alongside the
472    /// aligned chunk body and the suffix.
473    #[test]
474    fn zip_handles_offset_mask() -> VortexResult<()> {
475        let mut ctx = SESSION.create_execution_ctx();
476        // 200 single-element lists per side: `if_true[i] = [i]`, `if_false[i] = [1000 + i]`. With a
477        // 3-bit lead offset the mask spans more than 16 bytes, so `unaligned_chunks` exposes a
478        // non-empty aligned `chunks` body between the prefix and suffix words.
479        let len = 200usize;
480        let true_elements: Vec<i32> = (0..len as i32).collect();
481        let false_elements: Vec<i32> = (0..len as i32).map(|i| 1000 + i).collect();
482        let offsets: Vec<u64> = (0..len as u64).collect();
483        let sizes: Vec<u64> = vec![1; len];
484
485        let single_element_view = |elements: &[i32]| {
486            list_view(
487                elements
488                    .iter()
489                    .copied()
490                    .collect::<Buffer<i32>>()
491                    .into_array(),
492                offsets
493                    .iter()
494                    .copied()
495                    .collect::<Buffer<u64>>()
496                    .into_array(),
497                sizes.iter().copied().collect::<Buffer<u64>>().into_array(),
498                Validity::NonNullable,
499            )
500        };
501        let if_true = single_element_view(&true_elements);
502        let if_false = single_element_view(&false_elements);
503
504        // Slice off the first `offset` bits so the mask's bit buffer keeps a sub-byte offset while
505        // remaining `len` rows long. A non-trivial pattern straddles the prefix/body and chunk
506        // boundaries within the sliced window.
507        let offset = 3usize;
508        let mask_bits: Vec<bool> = (0..offset + len)
509            .map(|i| i.is_multiple_of(3) || i == offset + 64)
510            .collect();
511        let mask = BoolArray::from_iter(mask_bits.iter().copied())
512            .into_array()
513            .slice(offset..offset + len)?;
514
515        let result = mask.zip(if_true, if_false)?.execute::<ArrayRef>(&mut ctx)?;
516        assert!(result.is::<ListView>());
517
518        // Each row collapses to a single element: `i` when the sliced mask is set, else `1000 + i`.
519        let expected_elements: Vec<i32> = (0..len)
520            .map(|i| {
521                if mask_bits[offset + i] {
522                    i as i32
523                } else {
524                    1000 + i as i32
525                }
526            })
527            .collect();
528        let expected = single_element_view(&expected_elements);
529        assert_arrays_eq!(result, expected, &mut ctx);
530        Ok(())
531    }
532
533    /// When an input's `elements` is already a [`ChunkedArray`], its chunks are spliced in rather
534    /// than nesting a chunked array inside the concatenated elements.
535    #[test]
536    fn zip_flattens_chunked_elements() -> VortexResult<()> {
537        let mut ctx = SESSION.create_execution_ctx();
538        // elements [1, 2, 3] stored as two chunks; lists [[1, 2], [3]].
539        let chunked_elements = ChunkedArray::try_new(
540            vec![buffer![1i32, 2].into_array(), buffer![3i32].into_array()],
541            DType::Primitive(PType::I32, Nullability::NonNullable),
542        )?
543        .into_array();
544        let if_true = list_view(
545            chunked_elements,
546            buffer![0u32, 2].into_array(),
547            buffer![2u32, 1].into_array(),
548            Validity::NonNullable,
549        );
550        // [[10], [20]]
551        let if_false = list_view(
552            buffer![10i32, 20].into_array(),
553            buffer![0u32, 1].into_array(),
554            buffer![1u32, 1].into_array(),
555            Validity::NonNullable,
556        );
557        let mask = Mask::from_iter([true, false]);
558
559        let result = mask
560            .into_array()
561            .zip(if_true, if_false)?
562            .execute::<ArrayRef>(&mut ctx)?;
563
564        // The concatenated elements are chunked, but no chunk is itself a `ChunkedArray`.
565        let result_lv = result
566            .as_opt::<ListView>()
567            .expect("zip keeps the list-view encoding");
568        let chunked = result_lv
569            .elements()
570            .as_opt::<Chunked>()
571            .expect("zip concatenates elements into a chunked array");
572        assert!(
573            chunked.iter_chunks().all(|chunk| !chunk.is::<Chunked>()),
574            "chunked elements must be flattened, not nested",
575        );
576
577        // [[1, 2], [20]]
578        let expected = list_view(
579            buffer![1i32, 2, 20].into_array(),
580            buffer![0u32, 2].into_array(),
581            buffer![2u32, 1].into_array(),
582            Validity::NonNullable,
583        );
584        assert_arrays_eq!(result, expected, &mut ctx);
585        Ok(())
586    }
587}