17045413678

Committed 18 Aug 2025 03:43PM UTC coverage: 86.065% (-1.8%) from 87.913%

Build # 17045413678

Build Type

Pull #4215

github

Committed by

web-flow

Commit Message

Merge 2657b4c8e into cb2220961

Pull Request Pull Request #4215: Ji/vectors

Run Details

136 of 1803 new or added lines in 42 files covered. (7.54%)

127 existing lines in 26 files now uncovered.

56918 of 66134 relevant lines covered (86.06%)

612050.14 hits per line

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

0.0

/vortex-vector/src/view.rs

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

use std::fmt::Display;

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

use crate::SC;
use crate::bits::{BitView, BitViewMut};
use crate::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`.
    // TODO: support validity
    #[allow(dead_code)]
    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 is_empty(&self) -> bool {
        self.len == 0
    }

    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(), SC) }
    }

    /// 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(), SC);
        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>(), SC) }
    }

    /// 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>(), SC) }
    }

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

vortex-data / vortex / 17045413678

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