[Variant] Support `variant_get` kernel for shredded variants

[alamb]

I just realized something -- when dealing with shredded variants, this value method will do a lot of work to unshred and encode the whole thing (see e.g. #7915 (comment)). And that work is not memoized anywhere unless the caller is able to do so. For efficiency reasons we should strongly consider some kind of direct pathing support in VariantArray itself. Otherwise, it would be far too easy for a caller to accidentally do quadratic work when repeatedly calling value+get_path pairs for different paths.

Originally posted by @scovich in #7919 (comment)

---

@Samyak2 in #7919 (comment)

Just to understand this -- is this what you're suggesting?

• We add a new get_path method in VariantArray that does this:
  • For each row, look up the type of the variant and perform the pathing without decoding. So, for example, if it's a VariantObject and there's a VariantPathElement::Field path, it would get the offset for the given field (not sure how yet) and advance the value slice by that much.
  • We would then create a new VariantArray with the metadata directly copied over and the value copied starting from the advanced slice.
  • For shredded variants, if the path ends up on a shredded value, what would be the expected behavior? I'm guessing that the shredded fields will be represented as an Array of the concrete type (an Int32Array for example) and not a VariantArray. Will we wrap these in a VariantArray and send it back? This is one case where having the path + cast in the same operation would help.
• This variant_get would then simply re-use VariantArray::get_path and perform the appropriate cast.

---

@alamb in #7919 (comment)

For efficiency reasons we should strongly consider some kind of direct pathing support in VariantArray itself. Otherwise, it would be far too easy for a caller to accidentally do quadratic work when repeatedly calling value+get_path pairs for different paths.

I think @scovich is saying that the variant_get kernel (on VariantArray should have a special case that knows how to look for a shredded sub field -- and if for example it is asking for a and the the typed_value.a column exists, variant_get could simply return that a column (already as an arrow array, no actual Variant manipulation required)

• I filed [Variant] Support variant_get kernel for shredded variants #7941 to track this

[scovich]

I think @scovich is saying that the variant_get kernel (on VariantArray should have a special case that knows how to look for a shredded sub field -- and if for example it is asking for a and the the typed_value.a column exists, variant_get could simply return that a column (already as an arrow array, no actual Variant manipulation required)

Consider the case where we want to project out just one leaf field of a very wide and deep variant value. I think two kinds of things can go wrong if pathing is a two-step process of calling VariantArray::value followed by Variant::get_path:

1. Uninteresting shredded fields -- then we had to pay the cost to create (many and deeply-nested) Variant::ShreddedVariantObject instances that the subsequent pathing call will just ignore. And if we end up calling VariantArray::value multiple times, we repeat the unnecessary work each time.
   • This is the case I originally worried about
   • NOTE: This shredded case is different from unshredded variant, where all the bytes are there regardless of whether we use them or not: We're stuck fetching all unshredded bytes from disk either way, because unshredded variant is a row-oriented encoding.
2. Interesting shredded fields -- Even if we magically/luckily don't pay to create other/unrelated variant fields, we still end up (re)creating the Variant::ShreddedVariantObject for the path of interest. Which is itself potentially quite wide and deep and thus a lot of work.
   • I believe this is the case @alamb refers to
   • NOTE: I think there are actually two sub-cases here:
     1. If the caller intends to cast the results to e.g. Int32Array (I think that's what @alamb was referring to), then it's definitely nice to avoid a round trip variant encoding at all.
     2. If the caller extracted the results as variant, then we could actually return a new VariantArray with the same metadata column, a missing value column, and an appropriately filtered typed_value. Again, this would not require any actual variant encoding work, just rearranging physical columns within the VariantArray itself.

[alamb]

Interesting shredded fields -- Even if we magically/luckily don't pay to create other/unrelated variant fields, we still end up (re)creating the Variant::ShreddedVariantObject for the path of interest. Which is itself potentially quite wide and deep and thus a lot of work.

That is an interesting point -- maybe we could somehow defer the construction of the shredded Variant (whatever form that takes) until actual access.

We would have to play around with it I think

[alamb]

Here is a practical suggestion on how to make progress on variant shredding -- we start working out how it would work for a simple example

I have written some tests here that manually construct a shredded VariantArray and then call variant_get on it.

• [Variant] WIP Tests for variant_get of shredded variants #7965

Perhaps someone can use that as inspiration as a first step to implement this feature

[alamb]

@scovich and I were discussing other options here #7915 (comment):

---

@scovich : #7915 (comment)

An unshredding operation requires two kinds of variant "building":

• Shredded fields need a full blown variant builder, because they're strongly typed and we need to encode them as variant. But the existing VariantMetadata already contains all their field names, so the builder only needs to look up their field ids. The spec requires the ability to unshred using a read-only metadata dictionary, so why go copying it?
• Unshredded fields can be copied as-is (I would honestly prefer copying raw bytes instead of parsing and then unparsing them the way [Variant] Support appending complex variants in VariantBuilder #7914 seems to favor). We need a builder to keep track of the updated offsets as we interleave existing variant value bytes with newly-unshredded value bytes.

Imagine a partially shredded variant column v:

• Fields a, m and x live in the typed_value column as a perfectly shredded struct
  • Furthermore, x is itself a shredded struct with its own fields i and j
    • Furthermore, i is a variant column (also using the same top-level metadata)
    • Furthermore, j is a partially shredded struct
• Fields b, n, and y live in the value column as a variant object

When unshredding, we need to turn a, b, and x from strongly typed values into variant objects -- the latter recursively so -- which requires a variant builder. The recursive unshredding of j also requires a builder of its own.

Once we have all the field values in variant form, we need to create a new variant object for v. We can copy the bytes of b, n and y as a contiguous block if we want -- relying on field id sorting to give the required ordering a, b, m, n, x, y -- but we do have to copy those bytes in order to inject the newly created variant value bytes for a, m, and x. Plus, it's entirely possible other newly-unshredded sibling values before and after v would have required copying its value bytes even if v were completely unshredded.

[alamb]

@alamb in #7915 (comment)

Shredded fields need a full blown variant builder, because they're strongly typed and we need to encode them as variant.

When unshredding, we need to turn a, b, and x from strongly typed values into variant objects -- the latter recursively so -- which requires a variant builder. The recursive unshredding of j also requires a builder of its own.

I see -- you are imagining unshredding the varaint phiscally (aka forming the bytes for a new unshredded variant value using a VariantBuilder) to access the shredded fields.

What if we made a view into the variant so we didn't have to copy anything to read the Variant? If we could get a Variant that accessed the shredded fields, physically unshredding becomes an exercise in creating a new builder and calling append_value:

Hypothetical unshred kernel

// Given a shredded variant that is itself a Variant and a view on the shredded columns 
fn unshred(shredded_variant: Varaint) -> (Vec<u8>, Vec<u8>) {
  // deep copy the shredded variant
  let mut variant_builder = VariantBuilder::new()
  variant_builder.append_value(shredded_variant)
}

Shredded Variants as "Views"

The question then is how to implement a view. Accessing primitive types as a Variant is straightforward

fn shredded_int_as_variant(value: i64) -> Variant {
  Varant::from(value)
}
// ... other primitive types here ..
fn shredded_str_as_variant(value: &str) -> Variant {
  Variant::from(value)
}

The tricky bit is accessing partially shredded objects. Maybe we could add the shredded fields to VariantObject, something like

struct VariantObject {
 // ... existing fields ..
 // fields that were shredded and live elsewhere
 shredded_fields: IndexMap<&str, Variant>
}

Then we can update all the accessor methods, etc.

An alternate mechanism that might be more explicit would a new explicit enumeration in Variant like

struct ShreddedObject {
  object: VariantObject,
  shredded_fields: IndexMap<&str, Variant>
}

enum Variant {
  ShreddedObject(..)
}

We could Box the shredded fields to keep the size of Variant down if needed

Hows does this handle the example?

Imagine a partially shredded variant column v:

• Fields a, m and x live in the typed_value column as a perfectly shredded struct

  • Furthermore, x is itself a shredded struct with its own fields i and j

    • Furthermore, i is a variant column (also using the same top-level metadata)
    • Furthermore, j is a partially shredded struct

• Fields b, n, and y live in the value column as a variant object

I think the view approach could handle this example. For example

• v is a Variant::Object(..) with shredded_fields
• v 's fields in the value_column contain b, n and y
• v::shredded_fields contains the Variants for a, m, and x

• `x` is a `VariantObject()` ...
  

[alamb]

@friendlymatthew in #7915 (comment)

Hi, how do we plan on storing typed_values? Do we plan on encoding it as a Variant and storing the binary representation of it? Or since it is supposed to be strongly typed, we want to map to specific DataTypes, which would require something like #7921

I've been playing around with the unshredding logic and the most naive version would look something like this. I don't mean this to be the actual implementation, but I am curious how we plan on representing typed_value.

naive reconstruct logic

pub fn reconstruct_variant(
    metadata: &[u8],
    value: Option<&[u8]>,
    typed_value: Option<(&[u8], &[u8])>, // this is itself a variant
) -> Result<(Vec<u8>, Vec<u8>), ArrowError> {
    match typed_value {
        Some((typed_metadata, typed_value)) => {
            let variant = Variant::try_new(typed_metadata, typed_value)?;

            match variant {
                Variant::Null
                | Variant::Int8(_)
                | Variant::Int16(_)
                | Variant::Int32(_)
                | Variant::Int64(_)
                | Variant::Date(_)
                | Variant::TimestampMicros(_)
                | Variant::TimestampNtzMicros(_)
                | Variant::Decimal4(_)
                | Variant::Decimal8(_)
                | Variant::Decimal16(_)
                | Variant::Float(_)
                | Variant::Double(_)
                | Variant::BooleanTrue
                | Variant::BooleanFalse
                | Variant::Binary(_)
                | Variant::String(_)
                | Variant::ShortString(_) => Ok((typed_metadata.to_vec(), typed_value.to_vec())),
                Variant::Object(shredded_object) => {
                    if let Some(value) = value {
                        let variant = Variant::try_new(metadata, value)?;

                        let partially_shredded_object =
                            variant.as_object().ok_or(ArrowError::InvalidArgumentError(
                                "partially shredded value must be an object".to_string(),
                            ))?;

                        let shredded_keys: HashSet<&str> =
                            HashSet::from_iter(shredded_object.iter().map(|(k, _)| k));

                        let partially_shredded_keys: HashSet<&str> =
                            HashSet::from_iter(partially_shredded_object.iter().map(|(k, _)| k));

                        if !shredded_keys.is_disjoint(&partially_shredded_keys) {
                            return Err(ArrowError::InvalidArgumentError(
                                "object keys must be disjoint".to_string(),
                            ));
                        }

                        // union the two objects together

                        let mut variant_builder = VariantBuilder::new();
                        let mut object_builder = variant_builder.new_object();

                        for (f, v) in shredded_object.iter() {
                            object_builder.insert(f, v);
                        }

                        for (f, v) in partially_shredded_object.iter() {
                            object_builder.insert(f, v);
                        }

                        object_builder.finish()?;

                        return Ok(variant_builder.finish());
                    }

                    Ok((typed_metadata.to_vec(), typed_value.to_vec()))
                }
                Variant::List(_) => {
                    if value.is_some() {
                        return Err(ArrowError::InvalidArgumentError(
                            "shredded array must not conflict with variant value".to_string(),
                        ));
                    }

                    return Ok((typed_metadata.to_vec(), typed_value.to_vec()));
                }
            }
        }
        None => match value {
            Some(value) => Ok((metadata.to_vec(), value.to_vec())),
            None => Err(ArrowError::InvalidArgumentError(
                "No value or typed value provided".to_string(),
            )),
        },
    }
}

If we strongly type typed_value to whatever the variant type is, the primitive variants work nicely, since we'd be storing a PrimitiveArray<T> and we can easily index into it.

For complex variants like objects/lists, I'm having a hard time figuring out how to strongly type these values. Maybe for these cases we should just store the binary encoded version of a Variant? (metadata, value).

[alamb]

There is a bunch more back and forth on the thread as well that might be interesting