vortex_array/arrays/struct_/array.rs
1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use std::borrow::Borrow;
5use std::iter::once;
6
7use itertools::Itertools;
8use vortex_array_macros::array_slots;
9use vortex_error::VortexExpect;
10use vortex_error::VortexResult;
11use vortex_error::vortex_bail;
12use vortex_error::vortex_err;
13
14use crate::ArrayRef;
15use crate::ArraySlots;
16use crate::IntoArray;
17use crate::array::Array;
18use crate::array::ArrayParts;
19use crate::array::EmptyArrayData;
20use crate::array::TypedArrayRef;
21use crate::array::child_to_validity;
22use crate::array::validity_to_child;
23use crate::arrays::ChunkedArray;
24use crate::arrays::Struct;
25use crate::builtins::ArrayBuiltins;
26use crate::dtype::DType;
27use crate::dtype::FieldName;
28use crate::dtype::FieldNames;
29use crate::dtype::StructFields;
30use crate::validity::Validity;
31
32// StructArray has a variable number of slots: [validity?, field_0, ..., field_N]
33/// Slot layout of a [`Struct`] array: `[validity?, fields...]`.
34#[array_slots(Struct)]
35pub struct StructSlots {
36 /// The optional row-level validity child.
37 #[slot(0)]
38 pub validity: Option<ArrayRef>,
39 /// The field arrays, one per struct field, all sharing the outer length.
40 #[slot(1..)]
41 pub fields: Vec<ArrayRef>,
42}
43
44/// A struct array that stores multiple named fields as columns, similar to a database row.
45///
46/// This mirrors the Apache Arrow Struct array encoding and provides a columnar representation
47/// of structured data where each row contains multiple named fields of potentially different types.
48///
49/// ## Data Layout
50///
51/// The struct array uses a columnar layout where:
52/// - Each field is stored as a separate child array
53/// - All fields must have the same length (number of rows)
54/// - Field names and types are defined in the struct's dtype
55/// - An optional validity mask indicates which entire rows are null
56///
57/// ## Row-level nulls
58///
59/// The StructArray contains its own top-level nulls, which are superimposed on top of the
60/// field-level validity values. This can be the case even if the fields themselves are non-nullable,
61/// accessing a particular row can yield nulls even if all children are valid at that position.
62///
63/// ```
64/// use vortex_array::arrays::{StructArray, BoolArray};
65/// use vortex_array::validity::Validity;
66/// use vortex_array::dtype::FieldNames;
67/// use vortex_array::{IntoArray, VortexSessionExecute};
68/// use vortex_session::VortexSession;
69/// use vortex_buffer::buffer;
70///
71/// // Create struct with all non-null fields but struct-level nulls
72/// let struct_array = StructArray::try_new(
73/// FieldNames::from(["a", "b", "c"]),
74/// vec![
75/// buffer![1i32, 2i32].into_array(), // non-null field a
76/// buffer![10i32, 20i32].into_array(), // non-null field b
77/// buffer![100i32, 200i32].into_array(), // non-null field c
78/// ],
79/// 2,
80/// Validity::Array(BoolArray::from_iter([true, false]).into_array()), // row 1 is null
81/// ).unwrap();
82/// let mut ctx = VortexSession::empty().create_execution_ctx();
83///
84/// // Row 0 is valid - returns a struct scalar with field values
85/// let row0 = struct_array.execute_scalar(0, &mut ctx).unwrap();
86/// assert!(!row0.is_null());
87///
88/// // Row 1 is null at struct level - returns null even though fields have values
89/// let row1 = struct_array.execute_scalar(1, &mut ctx).unwrap();
90/// assert!(row1.is_null());
91/// ```
92///
93/// ## Name uniqueness
94///
95/// It is valid for a StructArray to have multiple child columns that have the same name. In this
96/// case, any accessors that use column names will find the first column in sequence with the name.
97///
98/// ```
99/// use vortex_array::arrays::StructArray;
100/// use vortex_array::arrays::struct_::StructArrayExt;
101/// use vortex_array::validity::Validity;
102/// use vortex_array::dtype::FieldNames;
103/// use vortex_array::{IntoArray, VortexSessionExecute};
104/// use vortex_session::VortexSession;
105/// use vortex_buffer::buffer;
106///
107/// // Create struct with duplicate "data" field names
108/// let struct_array = StructArray::try_new(
109/// FieldNames::from(["data", "data"]),
110/// vec![
111/// buffer![1i32, 2i32].into_array(), // first "data"
112/// buffer![3i32, 4i32].into_array(), // second "data"
113/// ],
114/// 2,
115/// Validity::NonNullable,
116/// ).unwrap();
117///
118/// // field_by_name returns the FIRST "data" field
119/// let first_data = struct_array.unmasked_field_by_name("data").unwrap();
120/// let mut ctx = VortexSession::empty().create_execution_ctx();
121/// assert_eq!(first_data.execute_scalar(0, &mut ctx).unwrap(), 1i32.into());
122/// ```
123///
124/// ## Field Operations
125///
126/// Struct arrays support efficient column operations:
127/// - **Projection**: Select/reorder fields without copying data
128/// - **Field access**: Get columns by name or index
129/// - **Column addition**: Add new fields to create extended structs
130/// - **Column removal**: Remove fields to create narrower structs
131///
132/// ## Validity Semantics
133///
134/// - Row-level nulls are tracked in the struct's validity child
135/// - Individual field nulls are tracked in each field's own validity
136/// - A null struct row means all fields in that row are conceptually null
137/// - Field-level nulls can exist independently of struct-level nulls
138///
139/// # Examples
140///
141/// ```
142/// use vortex_array::arrays::{StructArray, PrimitiveArray};
143/// use vortex_array::arrays::struct_::StructArrayExt;
144/// use vortex_array::validity::Validity;
145/// use vortex_array::dtype::FieldNames;
146/// use vortex_array::IntoArray;
147/// use vortex_buffer::buffer;
148///
149/// // Create arrays for each field
150/// let ids = PrimitiveArray::new(buffer![1i32, 2, 3], Validity::NonNullable);
151/// let names = PrimitiveArray::new(buffer![100u64, 200, 300], Validity::NonNullable);
152///
153/// // Create struct array with named fields
154/// let struct_array = StructArray::try_new(
155/// FieldNames::from(["id", "score"]),
156/// vec![ids.into_array(), names.into_array()],
157/// 3,
158/// Validity::NonNullable,
159/// ).unwrap();
160///
161/// assert_eq!(struct_array.len(), 3);
162/// assert_eq!(struct_array.names().len(), 2);
163///
164/// // Access field by name
165/// let id_field = struct_array.unmasked_field_by_name("id").unwrap();
166/// assert_eq!(id_field.len(), 3);
167/// ```
168pub struct StructDataParts {
169 pub struct_fields: StructFields,
170 pub fields: Vec<ArrayRef>,
171 pub validity: Validity,
172}
173
174/// Allocate the slots of a [`Struct`] array holding only its validity, with room for `nfields`
175/// field slots to be pushed.
176///
177/// Callers that build their field arrays fallibly use this directly, so they don't have to stage
178/// them in a `Vec` just to hand them over as an infallible iterator.
179pub(super) fn struct_slots_with_capacity(
180 validity: &Validity,
181 length: usize,
182 nfields: usize,
183) -> ArraySlots {
184 let mut slots = ArraySlots::with_capacity(StructSlots::FIELDS_OFFSET + nfields);
185 slots.push(validity_to_child(validity, length));
186 slots
187}
188
189pub(super) fn make_struct_slots(
190 fields: impl IntoIterator<Item = ArrayRef>,
191 validity: &Validity,
192 length: usize,
193) -> ArraySlots {
194 // Take the fields by value so callers that already own them move their `ArrayRef`s straight
195 // into the `SmallVec` instead of paying a refcount bump per field.
196 let fields = fields.into_iter();
197 let mut slots = struct_slots_with_capacity(validity, length, fields.size_hint().0);
198 slots.extend(fields.map(Some));
199 slots
200}
201
202/// Struct-specific accessors.
203///
204/// Slot accessors (`validity`, `fields`, `slots_view`) live on the generated
205/// [`StructArraySlotsExt`] supertrait; this trait layers struct-specific lookups on top.
206pub trait StructArrayExt: StructArraySlotsExt {
207 fn nullability(&self) -> crate::dtype::Nullability {
208 match self.dtype() {
209 DType::Struct(_, nullability) => *nullability,
210 _ => unreachable!("StructArrayExt requires a struct dtype"),
211 }
212 }
213
214 fn names(&self) -> &FieldNames {
215 self.dtype().as_struct_fields().names()
216 }
217
218 fn struct_validity(&self) -> Validity {
219 child_to_validity(self.validity(), self.nullability())
220 }
221
222 /// Iterate over the field arrays in declaration order.
223 fn iter_unmasked_fields(&self) -> impl ExactSizeIterator<Item = &ArrayRef> + '_ {
224 self.fields().iter()
225 }
226
227 /// The field array at `idx`, or `None` if `idx` is out of bounds.
228 ///
229 /// Use this over [`unmasked_field`](Self::unmasked_field) when the index comes from outside
230 /// the library and an out-of-bounds value is an error to report rather than a bug to panic on.
231 fn unmasked_field_opt(&self, idx: usize) -> Option<&ArrayRef> {
232 self.fields().get(idx)
233 }
234
235 /// The field array at `idx`.
236 ///
237 /// # Panics
238 ///
239 /// If `idx` is out of bounds.
240 fn unmasked_field(&self, idx: usize) -> &ArrayRef {
241 self.unmasked_field_opt(idx)
242 .vortex_expect("StructArray field slot")
243 }
244
245 fn unmasked_field_by_name_opt(&self, name: impl AsRef<str>) -> Option<&ArrayRef> {
246 let name = name.as_ref();
247 self.struct_fields()
248 .find(name)
249 .map(|idx| self.unmasked_field(idx))
250 }
251
252 fn unmasked_field_by_name(&self, name: impl AsRef<str>) -> VortexResult<&ArrayRef> {
253 let name = name.as_ref();
254 self.unmasked_field_by_name_opt(name).ok_or_else(|| {
255 vortex_err!(
256 "Field {name} not found in struct array with names {:?}",
257 self.names()
258 )
259 })
260 }
261
262 fn struct_fields(&self) -> &StructFields {
263 self.dtype().as_struct_fields()
264 }
265}
266impl<T: TypedArrayRef<Struct>> StructArrayExt for T {}
267
268impl Array<Struct> {
269 /// Creates a new `StructArray`.
270 pub fn new(
271 names: FieldNames,
272 fields: impl IntoIterator<Item = ArrayRef>,
273 length: usize,
274 validity: Validity,
275 ) -> Self {
276 Self::try_new(names, fields, length, validity)
277 .vortex_expect("StructArray construction failed")
278 }
279
280 /// Constructs a new `StructArray`.
281 pub fn try_new(
282 names: FieldNames,
283 fields: impl IntoIterator<Item = ArrayRef>,
284 length: usize,
285 validity: Validity,
286 ) -> VortexResult<Self> {
287 let fields = fields.into_iter();
288 let (lower, _) = fields.size_hint();
289 let mut field_dtypes = Vec::with_capacity(lower);
290 let mut slots = ArraySlots::with_capacity(StructSlots::FIELDS_OFFSET + lower);
291 slots.push(validity_to_child(&validity, length));
292 for field in fields {
293 field_dtypes.push(field.dtype().clone());
294 slots.push(Some(field));
295 }
296 let dtype = StructFields::new(names, field_dtypes);
297 Self::try_from_struct_parts(ArrayParts::new(
298 Struct,
299 DType::Struct(dtype, validity.nullability()),
300 length,
301 EmptyArrayData,
302 slots,
303 ))
304 }
305
306 /// Creates a new `StructArray` without validation.
307 ///
308 /// # Safety
309 ///
310 /// Caller must ensure the field arrays match the supplied dtype, length, and validity.
311 pub unsafe fn new_unchecked(
312 fields: impl IntoIterator<Item = ArrayRef>,
313 dtype: StructFields,
314 length: usize,
315 validity: Validity,
316 ) -> Self {
317 let outer_dtype = DType::Struct(dtype, validity.nullability());
318 let slots = make_struct_slots(fields, &validity, length);
319 unsafe {
320 Self::from_struct_parts_unchecked(ArrayParts::new(
321 Struct,
322 outer_dtype,
323 length,
324 EmptyArrayData,
325 slots,
326 ))
327 }
328 }
329
330 /// Constructs a new `StructArray` with an explicit dtype.
331 pub fn try_new_with_dtype(
332 fields: impl IntoIterator<Item = ArrayRef>,
333 dtype: StructFields,
334 length: usize,
335 validity: Validity,
336 ) -> VortexResult<Self> {
337 let outer_dtype = DType::Struct(dtype, validity.nullability());
338 let slots = make_struct_slots(fields, &validity, length);
339 Self::try_from_struct_parts(ArrayParts::new(
340 Struct,
341 outer_dtype,
342 length,
343 EmptyArrayData,
344 slots,
345 ))
346 }
347
348 /// Creates the array from parts after validation.
349 ///
350 /// The generic constructors call this function. It is not generic, so crates that call those
351 /// constructors do not each compile the `Struct` array vtable.
352 fn try_from_struct_parts(parts: ArrayParts<Struct>) -> VortexResult<Self> {
353 Array::try_from_parts(parts)
354 }
355
356 /// Creates the array from parts without validation.
357 ///
358 /// The generic constructors call this function. It is not generic, so crates that call those
359 /// constructors do not each compile the `Struct` array vtable.
360 ///
361 /// # Safety
362 ///
363 /// The parts must be logically consistent.
364 unsafe fn from_struct_parts_unchecked(parts: ArrayParts<Struct>) -> Self {
365 unsafe { Array::from_parts_unchecked(parts) }
366 }
367
368 /// Construct a `StructArray` from named fields.
369 pub fn from_fields<N: AsRef<str>>(items: &[(N, ArrayRef)]) -> VortexResult<Self> {
370 Self::try_from_iter(items.iter().map(|(a, b)| (a, b.clone())))
371 }
372
373 /// Create a `StructArray` from an iterator of (name, array) pairs with validity.
374 pub fn try_from_iter_with_validity<
375 N: AsRef<str>,
376 A: IntoArray,
377 T: IntoIterator<Item = (N, A)>,
378 >(
379 iter: T,
380 validity: Validity,
381 ) -> VortexResult<Self> {
382 let (names, fields): (Vec<FieldName>, Vec<ArrayRef>) = iter
383 .into_iter()
384 .map(|(name, fields)| (FieldName::from(name.as_ref()), fields.into_array()))
385 .unzip();
386 let len = fields
387 .first()
388 .map(|f| f.len())
389 .ok_or_else(|| vortex_err!("StructArray cannot be constructed from an empty slice of arrays because the length is unspecified"))?;
390
391 Self::try_new(FieldNames::from_iter(names), fields, len, validity)
392 }
393
394 /// Create a `StructArray` from an iterator of (name, array) pairs.
395 pub fn try_from_iter<N: AsRef<str>, A: IntoArray, T: IntoIterator<Item = (N, A)>>(
396 iter: T,
397 ) -> VortexResult<Self> {
398 let (names, fields): (Vec<FieldName>, Vec<ArrayRef>) = iter
399 .into_iter()
400 .map(|(name, field)| (FieldName::from(name.as_ref()), field.into_array()))
401 .unzip();
402 let len = fields
403 .first()
404 .map(ArrayRef::len)
405 .ok_or_else(|| vortex_err!("StructArray cannot be constructed from an empty slice of arrays because the length is unspecified"))?;
406
407 Self::try_new(
408 FieldNames::from_iter(names),
409 fields,
410 len,
411 Validity::NonNullable,
412 )
413 }
414
415 // TODO(aduffy): Add equivalent function to support field masks for nested column access.
416 /// Return a new StructArray with the given projection applied.
417 ///
418 /// Projection does not copy data arrays. Projection is defined by an ordinal array slice
419 /// which specifies the new ordering of columns in the struct. The projection can be used to
420 /// perform column re-ordering, deletion, or duplication at a logical level, without any data
421 /// copying.
422 pub fn project(&self, projection: &[FieldName]) -> VortexResult<Self> {
423 let mut children = Vec::with_capacity(projection.len());
424 let mut names = Vec::with_capacity(projection.len());
425
426 for f_name in projection {
427 let idx = self
428 .struct_fields()
429 .find(f_name.as_ref())
430 .ok_or_else(|| vortex_err!("Unknown field {f_name}"))?;
431
432 names.push(self.names()[idx].clone());
433 children.push(self.unmasked_field(idx).clone());
434 }
435
436 Self::try_new(
437 FieldNames::from(names.as_slice()),
438 children,
439 self.len(),
440 self.validity()?,
441 )
442 }
443
444 /// Create a fieldless `StructArray` with the given length.
445 pub fn new_fieldless_with_len(len: usize) -> Self {
446 let dtype = DType::Struct(
447 StructFields::new(FieldNames::default(), Vec::new()),
448 crate::dtype::Nullability::NonNullable,
449 );
450 let slots = make_struct_slots([], &Validity::NonNullable, len);
451 unsafe {
452 Array::from_parts_unchecked(ArrayParts::new(Struct, dtype, len, EmptyArrayData, slots))
453 }
454 }
455
456 // TODO(ngates): remove this... it doesn't help to consume self.
457 pub fn into_data_parts(self) -> StructDataParts {
458 let fields = self.fields().to_vec();
459 let validity = self.validity().vortex_expect("StructArray validity");
460 StructDataParts {
461 struct_fields: self.struct_fields().clone(),
462 fields,
463 validity,
464 }
465 }
466
467 pub fn remove_column(&self, name: impl Into<FieldName>) -> Option<(Self, ArrayRef)> {
468 let name = name.into();
469 let struct_dtype = self.struct_fields();
470 let len = self.len();
471
472 let position = struct_dtype.find(name.as_ref())?;
473
474 let slot_position = StructSlots::FIELDS_OFFSET + position;
475 let field = self.unmasked_field(position).clone();
476 // `Filter` has a zero lower bound, so build the slots with an exact capacity instead of
477 // letting `collect` grow them.
478 let slots = self.slots();
479 let mut new_slots = ArraySlots::with_capacity(slots.len() - 1);
480 new_slots.extend(slots[..slot_position].iter().cloned());
481 new_slots.extend(slots[slot_position + 1..].iter().cloned());
482
483 let new_dtype = struct_dtype.without_field(position).ok()?;
484 let new_array = unsafe {
485 Self::from_struct_parts_unchecked(ArrayParts::new(
486 Struct,
487 DType::Struct(new_dtype, self.dtype().nullability()),
488 len,
489 EmptyArrayData,
490 new_slots,
491 ))
492 };
493 Some((new_array, field))
494 }
495
496 pub fn with_column(&self, name: impl Into<FieldName>, array: ArrayRef) -> VortexResult<Self> {
497 let name = name.into();
498 let struct_dtype = self.struct_fields();
499
500 let names = struct_dtype.names().iter().cloned().chain(once(name));
501 let types = struct_dtype.fields().chain(once(array.dtype().clone()));
502 let new_fields = StructFields::new(names.collect(), types.collect());
503
504 let children = self.iter_unmasked_fields().cloned().chain(once(array));
505
506 Self::try_new_with_dtype(children, new_fields, self.len(), self.validity()?)
507 }
508
509 pub fn remove_column_owned(&self, name: impl Into<FieldName>) -> Option<(Self, ArrayRef)> {
510 self.remove_column(name)
511 }
512
513 pub fn try_concat<T>(chunks: impl IntoIterator<Item = T>) -> VortexResult<Self>
514 where
515 T: Borrow<Array<Struct>>,
516 {
517 let mut it = chunks.into_iter();
518 let Some(first) = it.next() else {
519 vortex_bail!("cannot concat empty iterator of arrays");
520 };
521 let first_dtype = first.borrow().dtype().clone();
522 let struct_fields = first_dtype.as_struct_fields().clone();
523 let names = struct_fields.names();
524
525 let it = [first].into_iter().chain(it);
526 let (field_arrays_per_chunk, validities) = it
527 .map(|chunk| {
528 let chunk = chunk.borrow();
529 if &first_dtype != chunk.dtype() {
530 vortex_bail!(
531 "cannot concatenate struct arrays with differing dtypes: {}, {}",
532 first_dtype,
533 chunk.dtype(),
534 );
535 }
536
537 let fields = names
538 .iter()
539 .map(|name| {
540 chunk
541 .unmasked_field_by_name(name)
542 .vortex_expect("field exists because it is in dtype")
543 .clone()
544 })
545 .collect::<Vec<_>>();
546 let validity = chunk.validity()?;
547
548 Ok((fields, (validity, chunk.len())))
549 })
550 .process_results(|iter| iter.unzip::<_, _, Vec<_>, Vec<_>>())?;
551
552 let field_arrays = struct_fields
553 .fields()
554 .enumerate()
555 .map(|(i, dtype)| {
556 // SAFETY: We establish above that every array has the same type.
557 let chunks = field_arrays_per_chunk.iter().map(|x| x[i].clone());
558 unsafe { ChunkedArray::new_unchecked(chunks, dtype) }.into_array()
559 })
560 .collect::<Vec<_>>();
561 let len = validities.iter().map(|(_v, len)| len).sum();
562 let validity = Validity::concat(validities).vortex_expect("verified non-empty above");
563
564 // SAFETY:
565 //
566 // 1. The field arrays, by construction, have the type specified in fields.
567 //
568 // 2. Each Array<Struct> has a valid len, therefore the sum of those lens should be valid
569 // for the concatenation of each field.
570 //
571 // 3. Each Array<Struct> has a valid validity, so the concatenation of those validities has
572 // the correct length and dtype harmony.
573 Ok(unsafe { Array::<Struct>::new_unchecked(field_arrays, struct_fields, len, validity) })
574 }
575
576 /// Push the struct's top-level validity into each field, so a row null at the struct level
577 /// becomes null in every field.
578 ///
579 /// If `remove_struct_validity` is set the result is non-nullable; otherwise it keeps its
580 /// top-level validity.
581 pub fn push_validity_into_children(&self, remove_struct_validity: bool) -> VortexResult<Self> {
582 let struct_validity = self.struct_validity();
583
584 let new_validity = if remove_struct_validity {
585 Validity::NonNullable
586 } else {
587 struct_validity.clone()
588 };
589
590 // Nothing to push down. The fields are unchanged, so reuse the existing `StructFields`
591 // rather than re-deriving it field by field.
592 if struct_validity.definitely_no_nulls() {
593 return Self::try_new_with_dtype(
594 self.iter_unmasked_fields().cloned(),
595 self.struct_fields().clone(),
596 self.len(),
597 new_validity,
598 );
599 }
600
601 // Null each field where the struct row is null.
602 let mask = struct_validity.to_array(self.len());
603 let fields = self
604 .iter_unmasked_fields()
605 .map(|field| field.clone().mask(mask.clone()))
606 .collect::<VortexResult<Vec<_>>>()?;
607
608 Self::try_new(self.names().clone(), fields, self.len(), new_validity)
609 }
610}