Add low level support for shredding and unshredding

[scovich]

Is your feature request related to a problem or challenge? Please describe what you are trying to do.

The variant shredding specification allows for variant values to be "shredded" where part of the overall variant is strongly-typed and part is normal binary variant. Working with shredded variant values requires writers to pull out specific subsets of a variant object that match a target schema ("shredding"). It also requires readers to potentially "unshred" by injecting strongly typed values back into the binary variant they came from.

Partial shredding of object values increases the complexity significantly -- some fields of an object could be shredded out as a struct, while others are not. And so on, recursively.

NOTE: The specification mandates that the variant metadata dictionary must contain all path parts, regardless of whether a given path is shredded or not. So (un)shredding operations do not need to modify the variant metadata dictionary.

Describe the solution you'd like

Ultimately, shredding and unshredding will be a problem for arrow-array and/or arrow-compute to solve (see below). But those higher level operations will need low-level support from Variant and its decoders/builders in order to do their work.

We should start figuring out what that low-level support looks like. A likely starting point would be the ability to insert and remove specific variant values from an existing variant object. These should be cheap byte-shuffling operations that don't waste time introspecting unrelated parts of the variant value buffer. And it needs to be efficient even when doing recursive inserts and removes as part of a partial (un)shredding operation.

At the higher level:

The parquet reader and writer will just use whatever shredding schema they receive from the parquet footer or user, respectively. No special low-level variant support needed there. But a user wishing to write shredded parquet will need a way to convert an Array of binary variant values into an Array of shredded variant values, or a strongly typed Array (e.g. StructArray) into an Array of shredded variant values. And a user wishing to read shredded parquet will will need a way to convert an Array of shredded variant values (with a specific shredding schema) to an Array of binary variant values, or an Array of shredded variant values having a different shredding schema, or a strongly typed Array (e.g. StructArray).

Describe alternatives you've considered

Just starting to think about this, and realizing we should probably start figuring out the low-level building blocks that arrow-array will eventually rely on. Now that we actually have variant builders and decoders, we can probably make progress here.

Additional context

https://github.com/apache/parquet-format/blob/master/VariantShredding.md

[tustvold]

Just a small point, we probably want to avoid fundamental crates like arrow-array, etc... from needing to depend on variants. These crates are used in contexts that are size sensitive, e.g. WASM, and so keeping them lightweight is important.

I'm not sure what kernel support for variants should look like, but my ideal would be to find a way to minimise the need for explicit support in kernels outside of those specifically for variants. I had envisaged that variants would need to be materialized/coerced to a concrete arrow array before being processed by arrow kernels such as take, cast, eq, etc...

Forcing people to depend on variant functionality, when it isn't actually part of arrow but instead parquet, feels unfortunate

[scovich]

I'm not sure what kernel support for variants should look like, but my ideal would be to find a way to minimise the need for explicit support in kernels outside of those specifically for variants.

This issue is specifically about the low-level (byte slice) support for manipulating individual variant values -- a building block for future higher level columnar operations -- and that logic should almost certainly live in the parquet-variant crate?

Meanwhile -- One way or another, people will need a way to manipulate columns of variant values in and out of more strongly-typed forms. Otherwise I'm not sure how useful variant would be in practice? Where that higher level logic lives seems like a secondary question. Probably some arrow-variant crate that depends on arrow-schema, arrow-array, and parquet-variant?

I had envisaged that variants would need to be materialized/coerced to a concrete arrow array before being processed by arrow kernels such as take, cast, eq, etc...

Not sure how the type system should handle it -- I'm not really familiar arrow's logical type system -- but both binary and shredded variant columns physically take the form of structs. So I'd expect the parquet reader to produce a StructArray with the appropriate columns (metadata, value, and/or typed_value). The problem is what to do with it at that point.

One could imagine defining kernels like variant_extract (that fetch a sub-variant by path, possibly with some form of casting), a variant "reader builder" (similar to JSON builder) that can convert variant values to strongly-typed (**), a "writer builder" that can convert strongly-typed values to variant, etc. All of those would likely need the kinds of byte-level manipulation this issue describes.

(**) Problem is, the JSON reader builder has a lot of semantics challenges that people have kind of been expecting variant to solve... so we have some work to do there if we don't want to just lift and shift the problem from json to variant.

[alamb]

Here is how I was imagining Variant support looks like:

1. To arrow-rs , arrays that hold variant will be StructArrays with at least two field: metadata, and value of binary (or maybe binary dictionary / RLE) type. This mirrrors the parquet physical representation
2. The fact that the column is a Variant is represented using the Metadata on a field (as an extension type)
3. Arrays that hold "shredded" variant values will be StructArrays with the two metadata and value columns and the additional shredded columns
4. Higher level engines (like DataFusion) will need to translate requests to extract a field from a variant object to the appropriate APIs on those StructArrays
5. We will need some new kernels (probably living in parquet-variant)

SOme potential new kernels

1. Extract a field of a Variant column (annotated StructArray) into a new array (variant_extract as proposed by @scovich perhaps)
2. (maybe) add a new field/fields to a Variant column
3. json value -->variant (annotated StructArray)
4. variant --> json
5. variant_to_struct (an extension of variant_extract perhaps to cast to/from variant and a (real) StructArray

I'll try and work up an example / diagram of how this would work over the next few days