Is this faster and/or simpler than try_into from slice to array?

Why not Iterator::is_sorted_by?

let offsets_monotonically_increasing = offset_chunks
    .map(...)
    .is_sorted_by(...);

(again below)

Update: The code below uses the materialized offsets.

But for large objects, wouldn't it be cheaper (and simpler) to combine the checks instead of materializing the offset array? Most likely inside a helper method so the code can leverage ?:

    let mut offsets = offset_chunks.map(|chunk| match chunk {
        ...
    });
    let Some(mut prev_offset) = offset_chunks.next().transpose()? else {
        return Ok(());
    };
    for offset in offsets {
        let offset = offset?;
        if prev_offset >= offset {
            return Err(... not monotonic ...);
        }

        let value_bytes = slice_from_slice(value_buffer, prev_offset..offset)?;
        prev_offset = offset;
        let _ = Variant::try_new_with_metadata(self.metadata, value_bytes)?;
    };
    Ok(())
}

As above, no need to materialize the iterator if we combine the checks into a single loop?
(but also see comment below)

As above, I expect it will be straightforward to avoid materializing these iterators
(again below)

I agree -- it seems unecessary to allocate and copy all the values into a Vec here

Hm happy to change, but I think in this case the extra allocation isn’t hurting perf very much and it makes the code a lot simpler to reason about because we can split up the following checks better.

I could inline calls to map_bytes_to_offsets everywhere we loop over field_ids, but that doesn’t seem much better than doing a single allocation

I could inline calls to map_bytes_to_offsets everywhere we loop over field_ids, but that doesn’t seem much better than doing a single allocation

I only see one pass over field_ids? Two possible paths, but each is single-pass?
(the not-sorted-metadata case makes a second pass, but I'm pretty sure it's redundant and will never find a failure -- see other comment)

I think in this case the extra allocation isn’t hurting perf very much

Seems like something we could (should) quantify? For a not-small dictionary I would expect materialization cost to be quite noticeable. Anything big enough to fall out L1 cache would likely see a significant slowdown due to a wave of cache misses on every pass. And that includes not just the offset vec itself (easy enough to prefetch), but also the bytes of the strings and values we examine.

and it makes the code a lot simpler to reason about

I don't think that's necessarily true for the metadata and list cases above (see other comments).

For this case, it would look something like:

let field_ids = map_bytes_to_offsets(field_id_buffer, self.header.field_id_size);
if let Some(mut field_id) = field_ids.next() {
    if self.metadata.is_sorted() {
        // Since the metadata dictionary has unique and sorted field names...
        for next_field_id in field_ids {
            if next_field_id <= field_id {
                return Err(... field names not sorted ...);
            }
            field_id = next_field_id;
        }
    } else {
        // The metadata dictionary can't guarantee uniqueness... 
        ... very similar to the metadata sortedness check: scan + validate_fallible_iterator ...
        ... probably could even factor out a helper function that both sites can call ...
    }
    if field_id >= self.metadata.dictionary_size() {
        return Err(... field id is not valid ...);
    }
}

this comment seems incorrect

Oof, that is what I get from lifting this code from test cases

I ran these benchmarks locally

cargo bench --bench variant_validation

Here is some output:

Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 33.9s, or reduce sample count to 10.
Benchmarking bench_validate_large_object: Collecting 100 samples in estimated 33.859 s (100 iterations)

I think a non trivial amount of the time being measured by this benchmark is the creation of the JSON string...

See comment

Can we move the generation of large object out of benchmark? Only benchmarking validation?

Yeah, I think that would be useful. I did some profiling at more than half the time of this benchmark is spent parsing JSON

Arg -- that is embarassing. I will push up a fix soon

I found these benchmarks somewhat confusing -- they are mostly testing json --> Variant conversion I think.

While those are useful benchmarks, they probably shouldn't be called variant_validation

SO I suggest you split this benchmark up into two:

1. parquet-variant/benches/variant_validation -- creates the metadata and value progrmatically with VariantBuilder once and then benchmarks callingVariant::try_new on that (precreated) metadata/value
2. parquet-variant-json/benches/variant_json.rs -- creates a json string once and then benchmarks how fast calling json_to_variant is

I found these benchmarks somewhat confusing -- they are mostly testing json --> Variant conversion I think.

While those are useful benchmarks, they probably shouldn't be called variant_validation

Hi, the following benchmarks use iter_batched which doesn't include the startup time (in this case, building up the variant). The benchmark runs should only involve the validation code.

Reading this issue, it seems like iter_batched_ref is a better function to use.

As for the json_to_variant, I could've built up the variant manually via the builder, but found the json example quite convenient. Since we moved json_to_variant to a separate crate, I had no choice but to move the validation benchmarks here.

But I agree, we should move this back to parquet-variant. It is a bit unfortunate, but we can manually build up the objects.

I wonder how much improvement the new crate adds ?

One thing I thought was that if we create a Variant from JSON we already know all the values were utf8, so it makes sense to skip validating it again befor read

What is the difference between the currently used str::from_utf8 and this simdutf8::basic::from_utf8?

Yeah this isn't the bottleneck so I'm fine with using str::from_utf8. I am a big fan of simd and am a sucker for potential vectorized operations

Parquet already has simdutf8 as (optional) dependency, so I think it makes sense to use it if enabled.

I agree -- it seems unecessary to allocate and copy all the values into a Vec here

I don't understand why this is faster than simply checking that all the field_ids are less than self.metadata.dictionary_size -- finding the max requires looking at all the items anywyas

it seems like there is a lot of duplicated code that does about the same thing:
Check that a slice of offsets are all

1. sorted (potentially)--
2. Less than some max offset
3. Point into a valid sub variant

I wonder if it possible to factor it all out into a function like

fn validate_offsets(offset_buffer: &[u8], num_offsets: usize, offset_size: OffsetSize, max_valid_offset: usize) {
...
}

Or something 🤔

I plan on following up with a PR that removes this check since we can validate the monotonicity of offsets when accessing variants

Hmm, is this a new check? Seems exiting VariantMetadata's with_full_validation doesn't have this check?

Yeah, the current validation was written before we supported sorted dictionaries

nit:

We don't need this check -- the loop below does offsets[i-1]..offsets[i] for every i in 1..offsets.len(), and any non-monotonic offset would cause slice_from_slice to return an Err like:?

Tried to extract byte(s) 42..25 from 100-byte buffer

Is it worth making an extra pass over the offsets (which requires materializing them) just to have a slightly nicer error message?

The simplified version would be something like:

let offsets = map_bytes_to_offsets(offset_buffer, self.header.offset_size);
if let Some(mut start) = offsets.next() {
    for end in offsets {
          ... validate start..end ...
        start = end;
    }
}

Again, I'm not sure it's worth paying an extra pass for a monotonicity check, when the slicing operations that follow will naturally fail in the presence of non-monotonic offsets?

let offsets = map_bytes_to_offsets(offset_bytes, self.header.offset_size);
if let Some(first_offset) = offsets.next() {
    // Create an iterator over the strings. We must consume the iterator to validate it.
    let strings = offsets.scan(first_offset, |start, end| {
        let s = slice_from_slice(value_buffer, start..end);
        *start = end;
        Some(s)
    });
    if self.header.is_sorted {
        // verify the strings are sorted and unique, in addition to being individually valid
        if let Some(mut a) = strings.next().transpose()? {
            for b in strings {
                let b = b?;
                if a >= b {
                    return Err(... dictionary values are not unique and ordered ...);
                }
                a = b;
            }
        }
    } else {
        // Just verify the strings are all individually valid
        validate_fallible_iterator(strings)?;
    }
}

This time, an iterator scan works well because we naturally unpack the errors later.

Note: The above does require making slice_from_slice fully generic:

pub(crate) fn slice_from_slice<T, I: SliceIndex<[T]> + Clone + Debug>(
    bytes: &[T],
    index: I,
) -> Result<&I::Output, ArrowError> {

Needs a doc comment explaining what it does and the conditions under which it's panic-free?

Sounds good. I took a look at the codegen, the compiler optimizes out the bounds checks so it can not panic under any circumstance

The rustc optimizes and specializes super aggresively -- the specialization you show is for a single-element iterator -- it doesn't even have a loop. But agree that using chunks (rather than chunks_exact) means it shouldn't be able to panic.

Oof, the screenshot should've showed the codegen for chunks_exact.

chunks_exact would never panic. If the slice length that we want to chunk over is not evenly divided by the chunk size, it will omit the remainder elements and can be retrieved by calling remainder() from the iterator.

More formally, ChunksExact will return array.len() // chunk_length elements. ChunksExact::remainder will return a slice with array.len() % chunk_length elements.

chunks would risk a panic if the slice length is not evenly divided by the chunk size. Since, the remainder is directly appended as the last slice in the iterator.

clever!

We don't need this check. If any field id were out of bounds, the collectat L245 would have already failed.

Shallow validation already ensured the last offset is in bounds, correct?

does this not work for some reason?

(try_for_each does seem to have a pretty weird collect-like signature, but I would have hoped that the previous ? would have fixed the error type...)

I could inline calls to map_bytes_to_offsets everywhere we loop over field_ids, but that doesn’t seem much better than doing a single allocation

I only see one pass over field_ids? Two possible paths, but each is single-pass?
(the not-sorted-metadata case makes a second pass, but I'm pretty sure it's redundant and will never find a failure -- see other comment)

I think in this case the extra allocation isn’t hurting perf very much

Seems like something we could (should) quantify? For a not-small dictionary I would expect materialization cost to be quite noticeable. Anything big enough to fall out L1 cache would likely see a significant slowdown due to a wave of cache misses on every pass. And that includes not just the offset vec itself (easy enough to prefetch), but also the bytes of the strings and values we examine.

and it makes the code a lot simpler to reason about

I don't think that's necessarily true for the metadata and list cases above (see other comments).

For this case, it would look something like:

let field_ids = map_bytes_to_offsets(field_id_buffer, self.header.field_id_size);
if let Some(mut field_id) = field_ids.next() {
    if self.metadata.is_sorted() {
        // Since the metadata dictionary has unique and sorted field names...
        for next_field_id in field_ids {
            if next_field_id <= field_id {
                return Err(... field names not sorted ...);
            }
            field_id = next_field_id;
        }
    } else {
        // The metadata dictionary can't guarantee uniqueness... 
        ... very similar to the metadata sortedness check: scan + validate_fallible_iterator ...
        ... probably could even factor out a helper function that both sites can call ...
    }
    if field_id >= self.metadata.dictionary_size() {
        return Err(... field id is not valid ...);
    }
}

Hmm, if there are values like ..., None, Some(a), None, Some(b)..., is it possible that an unordered case like a >= b cannot be detected?

One question, if is_sorted is false, it means the dictionary cannot guarantee both sortedness and uniqueness? If so, is it still a "dictionary"?

And if so, the name is_sorted is also confusing as it doesn't carry only sortedness.

You're right, but all this naming comes from the variant spec 🤷

Hi @viirya, good question. From the specification:

If sorted_strings is set to 1, strings in the dictionary must be unique and sorted in lexicographic order. If the value is set to 0, readers may not make any assumptions about string order or uniqueness.

One question, is field id started from 0 and all field ids are continuous?

Yes, per the spec:

A field_id is an index into the dictionary in the metadata

Btw, existing full validation of VariantObject doesn't check if its field names are sorted, is it missing previously?

I think you're right. The old validation was only ensuring individual fields names were valid, without comparing them for sortedness.

Field names sortness is different to field id sortness, right? We still can check if field_ids is sorted or not. If it is sorted, we can still just check the last field id?