feat: add dense union encoding in vortex-spatial

[HarukiMoriarty]

Rationale for this change

GeoArrow mixed-geometry arrays use dense unions, while the Vortex canonical union representation is sparse. This PR adds a generic external dense physical encoding without moving encoding policy into vortex-array.

What changes are included in this PR?

• Add the external vortex-dense-union encoding for logical DType::Union values.
• Store row-aligned type IDs and offsets with compact variant children.
• Preserve DenseUnion through slice, filter, take, and mask operations.
• Canonicalize unsupported operations to sparse UnionArray using dictionary-backed children without copying payload values.
• Register DenseUnion for Vortex file serialization and deserialization.
• Add behavior, validation, serde, and benchmark coverage.

What APIs are changed? Are there any user-facing changes?

• Adds the vortex-dense-union crate and its DenseUnion construction/accessor APIs.
• DType::Union and canonical sparse UnionArray remain in vortex-array.
• This does not yet add a GeoUnion extension or GeoArrow dense-union conversion.

Performance

Representation	Median executed take	Relative time
Sparse UnionArray	42.29–42.56 µs	1.00×
DenseUnion	88.91–90.35 µs	2.10–2.12×

[connortsui20]

It seems like this actually has a similar issue to ListView, where we can filter, take, slice the type IDs and offsets, but then we have no way of garbage collecting the unused data (which kind of defeats the purpose of the Dense encoding)?

And if someone inevitably wants that behavior, they actually have no way to express it? I guess technically we can express it by canonicalizing into a sparse encoding by literally rebuilding the whole thing from scratch, but that is very inefficient.

Maybe its time we add that garbage collection array that we've talked about for almost a year?

[connortsui20]

I think this does not actually work? If we look at https://arrow.apache.org/docs/format/Columnar.html#dense-union it says this:

The respective offsets for each child value array must be in order / increasing.

So if we take on the offsets we can reorder these which breaks sortedness per child.

So "not correct" here just means not zero-copyable to Arrow for this encoding. But maybe we don't care? It seems generally useful to have things out of order for more efficient take?

@robert3005 do you have any thoughts?

[robert3005]

Maybe in vortex you don't need a dense union and you only ever produce it on export to arrow? Is there a particular case where you find DenseUnion to be necessary?

[HarukiMoriarty]

Yes, Vortex can represent this using canonical sparse unions, but DenseUnion is intended as a performance encoding for GeoArrow Geometry.

[connortsui20]

• see Tracking Issue: Garbage Collection #9397

[connortsui20]

the AI review comments were verbose so I deleted them (claude cant edit review comments seemingly).

I will ask it to post again, but with more concise explanations

[connortsui20]

Reviewed 568bf2a. Differential tests against the sparse UnionArray across slice, filter, take, mask, and canonicalize agreed on every case, including nullable variants, null take indices, empty children, and zero-length results, so no correctness bug turned up in the data paths.

Two findings worth blocking on. The canonicalize hot loop does a per-row linear tag scan and allocates len * variants zeroed codes, which is where the 2.1x goes. DenseUnion also cannot be written to a file, because no edition declares vortex.dense_union. The benchmark behind the performance table never runs in CI either.

The Arrow offset-ordering question on take is still open. The differential tests would not have caught it, because they compare against Vortex sparse unions rather than Arrow.

---

Generated by Claude Code

[codspeed-hq]

Merging this PR will not alter performance

⚠️ Unknown Walltime execution environment detected

Using the Walltime instrument on standard Hosted Runners will lead to inconsistent data.

For the most accurate results, we recommend using CodSpeed Macro Runners: bare-metal machines fine-tuned for performance measurement consistency.

✅ 2000 untouched benchmarks
🆕 2 new benchmarks
⏩ 89 skipped benchmarks¹

Performance Changes

	Mode	Benchmark	BASE	HEAD	Efficiency
🆕	Simulation	dense_take	N/A	3.5 ms	N/A
🆕	Simulation	sparse_take	N/A	2 ms	N/A

---

_{Comparing nemo/dense-union (7459934) with develop (b363fb7)}

Footnotes

1. 89 benchmarks were skipped, so the baseline results were used instead. If they were deleted from the codebase, click here and archive them to remove them from the performance reports. ↩