16970635821

Committed 14 Aug 2025 04:13PM UTC coverage: 85.882% (-1.8%) from 87.693%

Build # 16970635821

Build Type

Pull #4215

github

Committed by

web-flow

Commit Message

Merge 5182504a6 into f547cbca5

Pull Request Pull Request #4215: Ji/vectors

Run Details

80 of 1729 new or added lines in 38 files covered. (4.63%)

117 existing lines in 25 files now uncovered.

56994 of 66363 relevant lines covered (85.88%)

609331.7 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 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>(&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;
                mask.iter_ones(|idx| {
                    unsafe {
                        // SAFETY: We assume that the elements are of type E and that the view is valid.
                        *self.as_slice_mut::<E>().get_unchecked_mut(offset) =
                            *self.as_slice::<E>().get_unchecked(idx);
                        offset += 1;
                    }
                });
            }
        }
    }
}

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

vortex-data / vortex / 16970635821

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