Tracking Issue: Fixed-Size List Arrays

This is a tracking issue for adding fixed-size list arrays to Vortex.

The main difference between lists and fixed-size lists is that fixed-size lists do not need to store an offsets buffer, since we are able to use the predictable stride pattern to jump to data. This allows us to more efficiently store data with known size (like matrices or tensors) as well as compute more efficiently with SIMD.

Public API

pub enum DType {
    /// A logical fixed-size list type.
    ///
    /// This is parameterized by a `DType` that represents the element type of the inner lists, as
    /// well as a `u32` size that determines the fixed length of each `FixedSizeList` scalar.
    FixedSizeList(Arc<DType>, u32, Nullability),
}

#[cfg(not(target_arch = "wasm32"))]
const_assert_eq!(size_of::<DType>(), 16);

#[cfg(target_arch = "wasm32")]
const_assert_eq!(size_of::<DType>(), 12); // Increase size to 12 bytes because of the `u32` field.

Prior Art

• Apache Arrow Fixed-Size List Overview: https://arrow.apache.org/docs/format/Intro.html#fixed-size-list
• Apache Arrow Fixed-Size List Layout: https://arrow.apache.org/docs/format/Columnar.html#fixed-size-list-layout
• Apache Arrow Variable-Size List Layout: https://arrow.apache.org/docs/format/Columnar.html#variable-size-list-layout
• Apache Arrow Fixed-shape Tensor: https://arrow.apache.org/docs/format/CanonicalExtensions.html#fixed-shape-tensor
• Arrow Rust FixedSizeListArray: https://docs.rs/arrow/latest/arrow/array/struct.FixedSizeListArray.html
• pyarrow.FixedSizeListType: https://arrow.apache.org/docs/python/generated/pyarrow.FixedSizeListType.html
• DuckDB Array Type (the same as fixed-size list): https://duckdb.org/docs/stable/sql/data_types/array.html
• Adding a new variant (DType::Decimal) to Vortex: feat: Decimal types #3058
• Conversion to numpy array potential optimizations: https://github.com/apache/arrow/issues/ 35622 (so we don't ping that issue)

Steps / History

• Feature: Add DType::FixedSizeList variant #4371
• Feature: Add FixedSizeList support in vortex-scalar #4380
• Feature: FixedSizeList infrastructure #4385
• Feature: Add FixedSizeListArray and FixedSizeListVTable #4405
• Feature: Add FixedSizeListBuilder #4428
• Feature: Implement Compute Functions for FixedSizeListArray #4495
• Feature: Add FixedSizeList fuzzing support #4541
• Feature: Implementation of ConstantArray and SparseArray canonicalize for FixedSizeList #4545
• Feature: Add DuckDB conversion for fixed-size lists / ARRAY type #4590
• Chore: Add missing FixedSizeListEncoding #4592
• Chore: Add no-op IsSorted and MinMax compute kernels for FixedSizeListVTable #4601
• Fix: FixedSizeList DuckDB exporter bug #4610
• Feature: Implement FixedSizeList in PyVortex bindings #4618

Unresolved Questions

• Is it okay to increase the size of DType to 12 bytes on WASM (instead of the previous size of 8)? Or instead have an FixedListElementType that Arcs both the DType and the u32 size? If we do that then List should also be changed
• Is u32 the correct type to use here (Arrow uses i32 for Java)