16991469020

Committed 15 Aug 2025 01:54PM UTC coverage: 86.018% (-1.8%) from 87.855%

Build # 16991469020

Build Type

Pull #4215

github

Committed by

web-flow

Commit Message

Merge 58201b202 into 62e231a41

Pull Request Pull Request #4215: Ji/vectors

Run Details

90 of 1746 new or added lines in 40 files covered. (5.15%)

117 existing lines in 25 files now uncovered.

56661 of 65871 relevant lines covered (86.02%)

614266.74 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

0.0

/vortex-array/src/pipeline/view.rs

// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright the Vortex contributors

use std::fmt::Debug;

use vortex_buffer::ByteBuffer;
use vortex_error::VortexExpect;

use crate::pipeline::N;
use crate::pipeline::bits::{BitView, BitViewMut};
use crate::pipeline::types::{Element, VType};

pub struct View<'a> {
    /// The physical type of the vector, which defines how the elements are stored.
    pub(super) vtype: VType,
    /// A pointer to the allocated elements buffer.
    /// Alignment is at least the size of the element type.
    /// The capacity of the elements buffer is N * size_of::<T>() where T is the element type.
    pub(super) elements: *const u8,
    /// The validity mask for the vector, indicating which elements in the buffer are valid.
    /// This value can be `None` if the expected DType is `NonNullable`.
    pub(super) validity: Option<BitView<'a>>,
    // A selection mask over the elements and validity of the vector.
    pub(super) len: usize,

    /// Additional buffers of data used by the vector, such as string data.
    #[allow(dead_code)]
    pub(super) data: Vec<ByteBuffer>,

    /// Marker defining the lifetime of the contents of the vector.
    pub(super) _marker: std::marker::PhantomData<&'a ()>,
}

impl<'a> View<'a> {
    #[inline(always)]
    pub fn len(&self) -> usize {
        self.len
    }

    pub fn as_slice<T>(&self) -> &'a [T]
    where
        T: Element,
    {
        debug_assert_eq!(self.vtype, T::vtype(), "Invalid type for canonical view");
        // SAFETY: We assume that the elements are of type T and that the view is valid.
        unsafe { std::slice::from_raw_parts(self.elements.cast(), N) }
    }

    /// Re-interpret cast the vector into a new type where the element has the same width.
    #[inline(always)]
    pub fn reinterpret_as<E: Element>(&mut self) {
        assert_eq!(
            self.vtype.byte_width(),
            size_of::<E>(),
            "Cannot reinterpret {} as {}",
            self.vtype,
            E::vtype()
        );
        self.vtype = E::vtype();
    }
}

/// A vector is the atomic unit of canonical data in Vortex.
///
/// Like with our canonical arrays, it is physically typed, not logically typed. So each DType
/// has a well-defined physical representation in vector form.
///
/// I'm not quite sure on sizing yet. We could follow DuckDB and make vectors 2k elements. We
/// could follow FastLanes and make them 1k elements. Or we could do something interesting where
/// we pick the largest power of two that lets us fit ~3-4 vectors into the L1 cache. For example,
/// strings may be 1k elements, but u8 integers may be 8k elements. Many compute functions operate
/// over two inputs of the same type, so this could be interesting.
///
/// Interestingly, Vectors don't own their own data. In fact, I'm considering calling them 'views'.
/// This also solves our problem of zero-copy export by allowing us to pass down an output buffer
/// from an external source. This tends to work well since these external sources typically agree
/// with us on the physical representation of data, e.g. DuckDB, Arrow, Numpy, etc.
///
/// ## Why is this a single type-erased struct?
///
/// If we used generics at this level, we would taint all functions that use this type with a
/// generic type. To remove the generic, we'd need to introduce a trait, at which point we're
/// forced into both dynamic dispatch, and boxed return types. We also cannot down-cast a dynamic
/// trait that holds borrowed data since `Any` requires a static lifetime.
///
/// ## How do we handle custom encodings, e.g. FSST, RoaringBitMap, ZStd, etc.?
///
/// I could imagine a VarBinView vector (i.e. it has 16-byte views in its elements buffer), but
/// is able to delay decompression of the data buffers. These could be stored as child arrays and
/// decompressed on-demand, since this is now an opaque operation (and then call export on the
/// child data arrays using a slices mask? We'd be masking binary data... that sounds slow).
/// In conclusion... I'm not really sure yet.
///
/// What about dictionary arrays? Are they even important at this level?
/// I have done a "medium amount" of thinking on this, and I think we can actually get away with
/// not supporting dictionary encoding at the vector level. Vortex arrays actually define the
/// encoding tree, and therefore can decide how to implement a compute function. So where it's
/// possible to return a dictionary encoded thing, e.g. to DuckDB, we would have some sort of
/// Vortex Array -> DuckDB function that would check for top-level dictionaries and handle the
/// conversion at that layer.

/// ## Can we re-use parts of the pipeline to avoid common-subexpression elimination?
///
/// This gets tricky... Suppose we start with a Vortex expression. We can then pass that naively
/// through pipeline construction. This now represents a physical execution plan. At this point,
/// we could in theory optimize the pipeline by removing common sub-expressions, such as
/// canonicalizing the same field multiple times to pass into two comparison operators.
///
/// We'd then need some way to buffer the intermediate results as both expressions are driven.
/// Maybe this works? Not sure yet.
pub struct ViewMut<'a> {
    /// The physical type of the vector, which defines how the elements are stored.
    pub(super) vtype: VType,
    /// A pointer to the allocated elements buffer.
    /// Alignment is at least the size of the element type.
    /// The capacity of the elements buffer is N * size_of::<T>() where T is the element type.
    // TODO(ngates): it would be nice to guarantee _wider_ alignment, ideally 128 bytes, so that
    //  we can use aligned load/store instructions for wide SIMD lanes.
    pub(super) elements: *mut u8,
    /// The validity mask for the vector, indicating which elements in the buffer are valid.
    /// This value can be `None` if the expected DType is `NonNullable`.
    pub(super) validity: Option<BitViewMut<'a>>,

    /// Additional buffers of data used by the vector, such as string data.
    // TODO(ngates): ideally these buffers are compressed somehow? E.g. using FSST?
    #[allow(dead_code)]
    pub(super) data: Vec<ByteBuffer>,

    /// Marker defining the lifetime of the contents of the vector.
    pub(super) _marker: std::marker::PhantomData<&'a mut ()>,
}

impl<'a> ViewMut<'a> {
    pub fn new<E: Element>(elements: &'a mut [E], validity: Option<BitViewMut<'a>>) -> Self {
        assert_eq!(elements.len(), N);
        Self {
            vtype: E::vtype(),
            elements: elements.as_mut_ptr().cast(),
            validity,
            data: vec![],
            _marker: Default::default(),
        }
    }

    /// Re-interpret cast the vector into a new type where the element has the same width.
    #[inline(always)]
    pub fn reinterpret_as<E: Element>(&mut self) -> ViewMut<'a> {
        assert_eq!(
            self.vtype.byte_width(),
            size_of::<E>(),
            "Cannot reinterpret {} as {}",
            self.vtype,
            E::vtype()
        );
        Self {
            vtype: E::vtype(),
            elements: self.elements,
            validity: self.validity.take(),
            data: self.data.clone(),
            _marker: Default::default(),
        }
    }

    /// Returns an immutable slice of the elements in the vector.
    #[inline(always)]
    pub fn as_slice<E: Element>(&self) -> &'a [E] {
        debug_assert_eq!(self.vtype, E::vtype(), "Invalid type for canonical view");
        unsafe { std::slice::from_raw_parts(self.elements.cast::<E>(), N) }
    }

    /// Returns a mutable slice of the elements in the vector, allowing for modification.
    /// FIXME(ngates): test the performance if we return &mut [E; N] instead of &[E].
    #[inline(always)]
    pub fn as_slice_mut<E: Element>(&mut self) -> &'a mut [E] {
        debug_assert_eq!(self.vtype, E::vtype(), "Invalid type for canonical view");
        unsafe { std::slice::from_raw_parts_mut(self.elements.cast::<E>(), N) }
    }

    /// Access the validity mask of the vector.
    ///
    /// ## Panics
    ///
    /// Panics if the vector does not support validity, i.e. if the DType was non-nullable when
    /// it was created.
    pub fn validity(&mut self) -> &mut BitViewMut<'a> {
        self.validity
            .as_mut()
            .vortex_expect("Vector does not support validity")
    }

    pub fn add_buffer(&mut self, buffer: ByteBuffer) {
        self.data.push(buffer);
    }

    /// Flatten the view by bringing the selected elements of the mask to the beginning of
    /// the elements buffer.
    ///
    /// FIXME(ngates): also need to select validity bits.
    pub fn select_mask<E: Element + Debug>(&mut self, mask: &BitView) {
        assert_eq!(
            self.vtype,
            E::vtype(),
            "ViewMut::flatten_mask: type mismatch"
        );

        match mask.true_count() {
            0 => {
                // If the mask has no true bits, we set the length to 0.
            }
            N => {
                // If the mask has N true bits, we copy all elements.
            }
            n if n > 3 * N / 4 => {
                // High density: use iter_zeros to compact by removing gaps
                let slice = self.as_slice_mut::<E>();
                let mut write_idx = 0;
                let mut read_idx = 0;

                mask.iter_zeros(|zero_idx| {
                    // Copy elements from read_idx to zero_idx (exclusive) to write_idx
                    let count = zero_idx - read_idx;
                    unsafe {
                        // SAFETY: We assume that the elements are of type E and that the view is valid.
                        // Using memmove for potentially overlapping regions
                        std::ptr::copy(
                            slice.as_ptr().add(read_idx),
                            slice.as_mut_ptr().add(write_idx),
                            count,
                        );
                        write_idx += count;
                    }
                    read_idx = zero_idx + 1;
                });

                // Copy any remaining elements after the last zero
                unsafe {
                    std::ptr::copy(
                        slice.as_ptr().add(read_idx),
                        slice.as_mut_ptr().add(write_idx),
                        N - read_idx,
                    );
                }
            }
            _ => {
                let mut offset = 0;
                let slice = self.as_slice_mut::<E>();
                mask.iter_ones(|idx| {
                    unsafe {
                        // SAFETY: We assume that the elements are of type E and that the view is valid.
                        let value = *slice.get_unchecked(idx);
                        // TODO(joe): use ptr increment (not offset).
                        *slice.get_unchecked_mut(offset) = value;

                        offset += 1;
                    }
                });
            }
        }
    }
}

1	// SPDX-License-Identifier: Apache-2.0
2	// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4	use std::fmt::Debug;
5
6	use vortex_buffer::ByteBuffer;
7	use vortex_error::VortexExpect;
8
9	use crate::pipeline::N;
10	use crate::pipeline::bits::{BitView, BitViewMut};
11	use crate::pipeline::types::{Element, VType};
12
13	pub struct View<'a> {
14	/// The physical type of the vector, which defines how the elements are stored.
15	pub(super) vtype: VType,
16	/// A pointer to the allocated elements buffer.
17	/// Alignment is at least the size of the element type.
18	/// The capacity of the elements buffer is N * size_of::<T>() where T is the element type.
19	pub(super) elements: *const u8,
20	/// The validity mask for the vector, indicating which elements in the buffer are valid.
21	/// This value can be `None` if the expected DType is `NonNullable`.
22	pub(super) validity: Option<BitView<'a>>,
23	// A selection mask over the elements and validity of the vector.
24	pub(super) len: usize,
25
26	/// Additional buffers of data used by the vector, such as string data.
27	#[allow(dead_code)]
28	pub(super) data: Vec<ByteBuffer>,
29
30	/// Marker defining the lifetime of the contents of the vector.
31	pub(super) _marker: std::marker::PhantomData<&'a ()>,
32	}
33
34	impl<'a> View<'a> {
35	#[inline(always)]
NEW 36	pub fn len(&self) -> usize {	×
NEW 37	self.len	×
NEW 38	}	×
39
NEW 40	pub fn as_slice<T>(&self) -> &'a [T]	×
NEW 41	where	×
NEW 42	T: Element,	×
43	{
NEW 44	debug_assert_eq!(self.vtype, T::vtype(), "Invalid type for canonical view");	×
45	// SAFETY: We assume that the elements are of type T and that the view is valid.
NEW 46	unsafe { std::slice::from_raw_parts(self.elements.cast(), N) }	×
NEW 47	}	×
48
49	/// Re-interpret cast the vector into a new type where the element has the same width.
50	#[inline(always)]
NEW 51	pub fn reinterpret_as<E: Element>(&mut self) {	×
NEW 52	assert_eq!(	×
NEW 53	self.vtype.byte_width(),	×
54	size_of::<E>(),
NEW 55	"Cannot reinterpret {} as {}",	×
56	self.vtype,
NEW 57	E::vtype()	×
58	);
NEW 59	self.vtype = E::vtype();	×
NEW 60	}	×
61	}
62
63	/// A vector is the atomic unit of canonical data in Vortex.
64	///
65	/// Like with our canonical arrays, it is physically typed, not logically typed. So each DType
66	/// has a well-defined physical representation in vector form.
67	///
68	/// I'm not quite sure on sizing yet. We could follow DuckDB and make vectors 2k elements. We
69	/// could follow FastLanes and make them 1k elements. Or we could do something interesting where
70	/// we pick the largest power of two that lets us fit ~3-4 vectors into the L1 cache. For example,
71	/// strings may be 1k elements, but u8 integers may be 8k elements. Many compute functions operate
72	/// over two inputs of the same type, so this could be interesting.
73	///
74	/// Interestingly, Vectors don't own their own data. In fact, I'm considering calling them 'views'.
75	/// This also solves our problem of zero-copy export by allowing us to pass down an output buffer
76	/// from an external source. This tends to work well since these external sources typically agree
77	/// with us on the physical representation of data, e.g. DuckDB, Arrow, Numpy, etc.
78	///
79	/// ## Why is this a single type-erased struct?
80	///
81	/// If we used generics at this level, we would taint all functions that use this type with a
82	/// generic type. To remove the generic, we'd need to introduce a trait, at which point we're
83	/// forced into both dynamic dispatch, and boxed return types. We also cannot down-cast a dynamic
84	/// trait that holds borrowed data since `Any` requires a static lifetime.
85	///
86	/// ## How do we handle custom encodings, e.g. FSST, RoaringBitMap, ZStd, etc.?
87	///
88	/// I could imagine a VarBinView vector (i.e. it has 16-byte views in its elements buffer), but
89	/// is able to delay decompression of the data buffers. These could be stored as child arrays and
90	/// decompressed on-demand, since this is now an opaque operation (and then call export on the
91	/// child data arrays using a slices mask? We'd be masking binary data... that sounds slow).
92	/// In conclusion... I'm not really sure yet.
93	///
94	/// What about dictionary arrays? Are they even important at this level?
95	/// I have done a "medium amount" of thinking on this, and I think we can actually get away with
96	/// not supporting dictionary encoding at the vector level. Vortex arrays actually define the
97	/// encoding tree, and therefore can decide how to implement a compute function. So where it's
98	/// possible to return a dictionary encoded thing, e.g. to DuckDB, we would have some sort of
99	/// Vortex Array -> DuckDB function that would check for top-level dictionaries and handle the
100	/// conversion at that layer.
101
102	/// ## Can we re-use parts of the pipeline to avoid common-subexpression elimination?
103	///
104	/// This gets tricky... Suppose we start with a Vortex expression. We can then pass that naively
105	/// through pipeline construction. This now represents a physical execution plan. At this point,
106	/// we could in theory optimize the pipeline by removing common sub-expressions, such as
107	/// canonicalizing the same field multiple times to pass into two comparison operators.
108	///
109	/// We'd then need some way to buffer the intermediate results as both expressions are driven.
110	/// Maybe this works? Not sure yet.
111	pub struct ViewMut<'a> {
112	/// The physical type of the vector, which defines how the elements are stored.
113	pub(super) vtype: VType,
114	/// A pointer to the allocated elements buffer.
115	/// Alignment is at least the size of the element type.
116	/// The capacity of the elements buffer is N * size_of::<T>() where T is the element type.
117	// TODO(ngates): it would be nice to guarantee _wider_ alignment, ideally 128 bytes, so that
118	// we can use aligned load/store instructions for wide SIMD lanes.
119	pub(super) elements: *mut u8,
120	/// The validity mask for the vector, indicating which elements in the buffer are valid.
121	/// This value can be `None` if the expected DType is `NonNullable`.
122	pub(super) validity: Option<BitViewMut<'a>>,
123
124	/// Additional buffers of data used by the vector, such as string data.
125	// TODO(ngates): ideally these buffers are compressed somehow? E.g. using FSST?
126	#[allow(dead_code)]
127	pub(super) data: Vec<ByteBuffer>,
128
129	/// Marker defining the lifetime of the contents of the vector.
130	pub(super) _marker: std::marker::PhantomData<&'a mut ()>,
131	}
132
133	impl<'a> ViewMut<'a> {
NEW 134	pub fn new<E: Element>(elements: &'a mut [E], validity: Option<BitViewMut<'a>>) -> Self {	×
NEW 135	assert_eq!(elements.len(), N);	×
NEW 136	Self {	×
NEW 137	vtype: E::vtype(),	×
NEW 138	elements: elements.as_mut_ptr().cast(),	×
NEW 139	validity,	×
NEW 140	data: vec![],	×
NEW 141	_marker: Default::default(),	×
NEW 142	}	×
NEW 143	}	×
144
145	/// Re-interpret cast the vector into a new type where the element has the same width.
146	#[inline(always)]
NEW 147	pub fn reinterpret_as<E: Element>(&mut self) -> ViewMut<'a> {	×
NEW 148	assert_eq!(	×
NEW 149	self.vtype.byte_width(),	×
150	size_of::<E>(),
NEW 151	"Cannot reinterpret {} as {}",	×
152	self.vtype,
NEW 153	E::vtype()	×
154	);
NEW 155	Self {	×
NEW 156	vtype: E::vtype(),	×
NEW 157	elements: self.elements,	×
NEW 158	validity: self.validity.take(),	×
NEW 159	data: self.data.clone(),	×
NEW 160	_marker: Default::default(),	×
NEW 161	}	×
NEW 162	}	×
163
164	/// Returns an immutable slice of the elements in the vector.
165	#[inline(always)]
NEW 166	pub fn as_slice<E: Element>(&self) -> &'a [E] {	×
NEW 167	debug_assert_eq!(self.vtype, E::vtype(), "Invalid type for canonical view");	×
NEW 168	unsafe { std::slice::from_raw_parts(self.elements.cast::<E>(), N) }	×
NEW 169	}	×
170
171	/// Returns a mutable slice of the elements in the vector, allowing for modification.
172	/// FIXME(ngates): test the performance if we return &mut [E; N] instead of &[E].
173	#[inline(always)]
NEW 174	pub fn as_slice_mut<E: Element>(&mut self) -> &'a mut [E] {	×
NEW 175	debug_assert_eq!(self.vtype, E::vtype(), "Invalid type for canonical view");	×
NEW 176	unsafe { std::slice::from_raw_parts_mut(self.elements.cast::<E>(), N) }	×
NEW 177	}	×
178
179	/// Access the validity mask of the vector.
180	///
181	/// ## Panics
182	///
183	/// Panics if the vector does not support validity, i.e. if the DType was non-nullable when
184	/// it was created.
NEW 185	pub fn validity(&mut self) -> &mut BitViewMut<'a> {	×
NEW 186	self.validity	×
NEW 187	.as_mut()	×
NEW 188	.vortex_expect("Vector does not support validity")	×
NEW 189	}	×
190
NEW 191	pub fn add_buffer(&mut self, buffer: ByteBuffer) {	×
NEW 192	self.data.push(buffer);	×
NEW 193	}	×
194
195	/// Flatten the view by bringing the selected elements of the mask to the beginning of
196	/// the elements buffer.
197	///
198	/// FIXME(ngates): also need to select validity bits.
NEW 199	pub fn select_mask<E: Element + Debug>(&mut self, mask: &BitView) {	×
NEW 200	assert_eq!(	×
201	self.vtype,
NEW 202	E::vtype(),	×
NEW 203	"ViewMut::flatten_mask: type mismatch"	×
204	);
205
NEW 206	match mask.true_count() {	×
NEW 207	0 => {	×
NEW 208	// If the mask has no true bits, we set the length to 0.	×
NEW 209	}	×
NEW 210	N => {	×
NEW 211	// If the mask has N true bits, we copy all elements.	×
NEW 212	}	×
NEW 213	n if n > 3 * N / 4 => {	×
214	// High density: use iter_zeros to compact by removing gaps
NEW 215	let slice = self.as_slice_mut::<E>();	×
NEW 216	let mut write_idx = 0;	×
NEW 217	let mut read_idx = 0;	×
218
NEW 219	mask.iter_zeros(\|zero_idx\| {	×
220	// Copy elements from read_idx to zero_idx (exclusive) to write_idx
NEW 221	let count = zero_idx - read_idx;	×
NEW 222	unsafe {	×
NEW 223	// SAFETY: We assume that the elements are of type E and that the view is valid.	×
NEW 224	// Using memmove for potentially overlapping regions	×
NEW 225	std::ptr::copy(	×
NEW 226	slice.as_ptr().add(read_idx),	×
NEW 227	slice.as_mut_ptr().add(write_idx),	×
NEW 228	count,	×
NEW 229	);	×
NEW 230	write_idx += count;	×
NEW 231	}	×
NEW 232	read_idx = zero_idx + 1;	×
NEW 233	});	×
234
235	// Copy any remaining elements after the last zero
NEW 236	unsafe {	×
NEW 237	std::ptr::copy(	×
NEW 238	slice.as_ptr().add(read_idx),	×
NEW 239	slice.as_mut_ptr().add(write_idx),	×
NEW 240	N - read_idx,	×
NEW 241	);	×
NEW 242	}	×
243	}
244	_ => {
NEW 245	let mut offset = 0;	×
NEW 246	let slice = self.as_slice_mut::<E>();	×
NEW 247	mask.iter_ones(\|idx\| {	×
NEW 248	unsafe {	×
NEW 249	// SAFETY: We assume that the elements are of type E and that the view is valid.	×
NEW 250	let value = *slice.get_unchecked(idx);	×
NEW 251	// TODO(joe): use ptr increment (not offset).	×
NEW 252	*slice.get_unchecked_mut(offset) = value;	×
NEW 253		×
NEW 254	offset += 1;	×
NEW 255	}	×
NEW 256	});	×
257	}
258	}
NEW 259	}	×
260	}

vortex-data / vortex / 16991469020

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous