[Variant] Support Shredded Lists/Array in `variant_get`

[alamb]

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

• part of [EPIC] [Parquet] Implement Variant type support in Parquet #6736

We introduced the basic variant_get kernel in and now we need to expand its feature set

• [Variant] Add variant_get and Shredded VariantArray #8021

In particular, Shredded Arrays (VariantList) are described here:

• Representing Variant In Arrow Proposal: "Shredding an Array"
• Variant Shredding::Arrays

Describe the solution you'd like
I would like variant_get to support shredded arrays, along with being able to extract elements from them.

So roughly that means

// get the variant as a ListArray
variant_get(array, Field::new(List...)))
// get the shredded variant as a non shredded variant (convert to Variant::List)
variant_get(array)

Describe alternatives you've considered

1. Add a test that manually constructs a shredded variant array (follow the example in the arrow proposal)
2. Add a test that tries to get that array as a variant and as a ListArray
3. Implement the code

Additional context
Reference

• Variant Spec
• Variant Shredding Spec
• Representing Variant In Arrow Proposal

[sdf-jkl]

take

[sdf-jkl]

Hey @alamb, welcome back! I’d like to give a more substantial issue like this a try to practice and learn more. I’d really appreciate your feedback and guidance on how to approach tackling it. Also, would love any help or insights from @carpecodeum, @klion26, and @scovich.

(I did my homework reading the Variant and Variant Shredding spec)

Thanks in advance!

[scovich]

Hi @sdf-jkl -- this is definitely a challenging one, so I would strongly recommend some "whiteboard designing" and pathfinding efforts before actually trying to code up a full solution.

Pathing through shredded variant objects is pretty straightforward because it's just projection. For example,

SELECT variant_get(v, 'a.b.c', INT)` AS c FROM t

ideally just translates to

SELECT v.typed_value.a.typed_value.b.typed_value.c.typed_value AS c FROM t

(if everything shredded perfectly)

In contrast, pathing through a shredded variant array requires slicing. For example,

SELECT variant_get(v, 'a[0].b[1].c[2]', INT)` AS c FROM t

... would, if perfectly shredded, require to first project out the the following path:

v.typed_value.a.typed_value.list.element.typed_value.b.typed_value.list.element.typed_value.c.typed_value.list.element

... and then slice the result down to the single requested row (because the projected column contains every a[i].b[j].c[k] for ALL i, j, and k).

If the path selects an array instead of an array element, e.g. a[0].b[1].c, then the slicing has to return just the contiguous subset of rows that belong to that sub-sub-list.

And that's just for the perfect shredding case. If it's imperfectly shredded, then at least some of the slicing has to happen inside binary variant values instead, which will involve a different kind of slicing and dicing.

NOTE: None of this is impossible... it's just complex. And a lot of the infrastructure you'll need, like slicing and dicing of binary variant values, is still at least partly work in progress.

[sdf-jkl]

Hey @scovich, I’ve put together some initial tests based on your shredded object tests here #8354. I also created a helper function to generate a shredded lists variant array.
Before I move forward, I just wanted to check in to make sure the tests and the generated array look good.
Thanks for your help with this.

[sdf-jkl]

Hey @liamzwbao, now that #8830 got merged, do you want to take this issue over?

[liamzwbao]

Sure, thanks for tagging me! I will take a look