Tracking Issue: Add `DType::Union`

[connortsui20]

This is a tracking issue for adding the DType::Union variant and canonical encoding for Union.

Motivation

See the parent epic issue: #7705

Design

We will be following the Arrow specification of Union, though we have an important decision to make here. Arrow specifies both a dense and a sparse union layout. Both layouts (encodings in Vortex) would have child arrays for each type that a value could be, as well as a types child array that specifies which type in the Union array a given row is (and thus, which child array to look at to fetch the correct value).

Note that we cannot reuse the StructFields type for Union as we need to also track the i8 tags for each of the possible variants of the union.

Dense vs Sparse

Dense encoding: each child array contains only the values that actually belong to that type, packed contiguously. An additional offsets buffer tells us which slot of the chosen child holds the value for that row.

Slicing and filtering requires walking type_ids to recompute per-child offsets.

type_ids: [0, 1, 0, 1, 0]
offsets:  [0, 0, 1, 1, 2]
child 0 (int):    [10, 20, 30]
child 1 (string): ["a", "b"]

Sparse encoding: every child array has the same length as the union itself, so the value at row i is simply found at position i of child type_ids[i].

The "inactive" slots of each child are unused but must still be addressable. There is no offsets buffer.

type_ids: [0, 1, 0, 1, 0]
child 0 (int):    [10, _, 20, _, 30]   // _ slots are inactive
child 1 (string): [_, "a", _, "b", _]

Why Sparse should be Canonical (and not Dense)

We want to support quick execution of things like slice and filter on our canonical arrays, and sparse is clearly superior to dense in this case (since dense would have to perform compute just to figure out how to slice child arrays).

Additionally, the space loss of sparse in Arrow does not necessarily translate to Vortex because our canonical types do not require the children to also be canonical. This means that actually sparse children under a sparse Union (for example, if I have 99000 integers and 1000 strings all separated) can be encoded with a SparseArray, so we would not lose much space compared to the dense union encoding.

It then follows that DenseUnionArray can just be a different physical encoding of Union. I think the compressor might have to be smarter about compressing into Dense though, since SparseUnion is basically always more performant for the compute we want to do.

Type IDs

Per Arrow's Schema.fbs: "By default ids in the type vector refer to the offsets in the children. Optionally typeIds provides an indirection between the child offset and the type id for each child."

So the per-row type tag defaults to consecutive 0..N matching child offsets, but an optional typeIds: [i8] array can provide indirection. For example, children [a, b, c] with typeIds = [0, 5, 7] means the data buffer uses tags 0, 5, 7 to select them (This matters for schema evolution because it means removing a child doesn't renumber the others).

UnionVariants will have to carry this information.

Also note that UnionVariants will enforce that variant names cannot be duplicated, and must be unique. The arrow specification says nothing about this, but we can enforce this behavior as the alternative of having duplicate variant names is insane.

Nullability semantics

• Follow Arrow's row-level semantics: a union has no independent parent validity. A row is null when its selected child is null, and inactive sparse-child nulls do not matter.
• Derive the union DType's nullability from its variants rather than storing a second outer Nullability. Implemented by Remove stored Union Nullability #8714.
• Decide how an operation that introduces new nulls changes UnionVariants. This affects mask, take with null indices, null-producing casts, and appending a null in UnionBuilder. Until that policy is defined, these cases should return an explicit unsupported error.

Steps

• Add DType::Union + UnionVariants, including flatbuffer/protobuf schemas and round-trip tests: Add UnionVariants type and embed it in DType::Union #8703
• Remove stored Union Nullability and derive it from the variants: Remove stored Union Nullability #8714
• Add UnionScalar: Add UnionScalar #8739
• Add canonical sparse UnionArray
• Implement compute over UnionArray
• Figure out null semantics with mask, take with null indices, union casts
• Arrow roundtrip
• UnionBuilder?
• Add dense union encoding

Implementation history

• Add DType::Union and UnionVariants #7890
• Add DType::Union variant carrying just Nullability #7901
• Add UnionVariants type and embed it in DType::Union #7902
• Add UnionVariants type and embed it in DType::Union #8703
• Remove stored Union Nullability #8714
• Reject negative Union type IDs #8738
• Add UnionScalar #8739

[connortsui20]

(generated comment from Codex)

The nullability question does not need to block the canonical sparse UnionArray.

The Arrow implementations agree on the behavior that matters for the array:

• arrow-rs has no parent null buffer and gathers logical validity from the selected child.
• Arrow C++ follows the selected child for IsNull(i).
• Arrow Java reports no physical nulls on the union itself, while value access still follows the selected child.

A union therefore has no validity mask of its own. A row is null when the selected child is null. Nulls in inactive sparse children do not matter.

The outer Arrow Field::nullable flag is less consistent. arrow-rs creates union fields as non-nullable, while the Java dense and sparse helpers use different defaults. That flag should not define the Vortex semantics.

The contract currently on develop is sufficient: a nullable union needs at least one nullable or Null variant, a non-nullable union cannot have either, and the array computes validity from the selected child.

The remaining question is what with_nullability, mask, or another null-producing operation should do when it needs to make an existing union nullable. The operation could make an existing variant nullable, require a Null variant, or require an explicit output type.

This can be deferred. The initial canonical array can require an already-consistent union DType and return unsupported from operations that would need to change it, including mask, nullable-index take, null-producing casts, and appending a null.

This does not affect the physical layout, so UnionArray can be implemented and used now. The concrete documentation for this boundary is in #8714.

[connortsui20]

Ok, we are going to try and remove Nullability from the DType completely and see what happens as we implement things. See #8714