Skip to content

Tracking Issue: Canonicalize ListView over List #4699

Closed
1 of 2 issues completed
Closed

Description

@connortsui20

Tracking Issue: Canonicalize ListView over List

This is a tracking issue for 1) adding a ListView encoding to Vortex and 2) making the new ListView encoding the canonical encoding for the DType::List logical type.

One of the limitations / tradeoffs that the current List encoding has is that it does not store a sizes buffer alongside the offsets buffer, where the size of each list scalar is implicitly calculated via the equation offsets[i + 1] - offsets[i].

The issue with this is that we cannot effectively vectorize execution over the current List encoding because of the inherent sequential dependencies of the list offsets (next value depends on the previous value). This makes the List encoding both less random-access/slice friendly as well as less SIMD friendly, on top of independent data generally providing better branch/loop prediction.

Public API

struct ListViewArray { ... }

struct ListViewBuilder<OffsetType, SizeType> 
where
    OffsetType: OffsetPType,
    SizeType: OffsetPType,
{ ... }

#[derive(Debug, Clone)]
pub enum Canonical {
<-- snip -->
    // List(ListArray),
    List(ListViewArray),
<-- snip -->
}

Child Arrays

There are two possible ways to store the offsets and sizes data. The first way is to store 2 separate child arrays, and the second is to store a single array where each "scalar" is the pair of the offset and the size for a list scalar next to each other.

We have chosen the first layout. The main reason is that it allows better compressibility. It also enables the next section.

Generic offsets and sizes

There is technically no reason that the offsets array and the sizes array cannot be different integer types. As long as the sizes integer type is smaller than the offsets type (since a size bigger than the largest offset would cause overflow), we can have any combination of offsets and sizes child arrays.

This is notably different from the Rust Arrow implementation, in which the GenericListViewBuilder is only generic over a single OffsetSize parameter.

Binary Compatability

ListViewArray will be compatible with Arrow's ListViewArray when both the offsets and sizes are i32, and compatible with LargeListViewArray when both child arrays are i64.

Prior Art

Steps / History

Discarded PRs

Unresolved Questions

  • Is allowing distinct offsets and sizes types a good idea? (Yes)

Activity

  1. self-assigned this
    on Sep 18, 2025
  2. added
    epicPublic roadmap umbrella for a major initiative, with work tracked in sub-issues.
    on Sep 18, 2025
  3. added a commit that references this issue on Sep 22, 2025
  4. added a commit that references this issue on Sep 25, 2025
  5. robert3005 commented on Nov 28, 2025

    @robert3005
    Contributor

    I think this can be closed, we have change the canonical. The only outstanding bug that's filed separately is supporting ListViews as native arrow type that's blocked on Datafusion supporting it properly (hopefully DF 51 has enough support)

  6. removed theissue type on Jan 22, 2026
  7. added
    featureA feature request
    and removed on Jan 22, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

epicPublic roadmap umbrella for a major initiative, with work tracked in sub-issues.featureA feature request

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions