You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "friendlymatthew (via GitHub)" <gi...@apache.org> on 2025/07/07 15:55:59 UTC
[PR] [Variant] Speedup validation [arrow-rs]
friendlymatthew opened a new pull request, #7878:
URL: https://github.com/apache/arrow-rs/pull/7878
This PR is based off of this commit https://github.com/apache/arrow-rs/pull/7871. Please review from the second commit.
# Rationale for this change
This PR contains algorithmic modifications to the validation logic and the associated benchmarks, specifically targeting complex object and list validation.
Previously, the approach involved iterating over each element and repeatedly fetching the same slice of the backing buffer, then slicing _into_ that buffer again for each individual element. This led to redundant buffer access.
This validation approach is done in multiple passes that take advantage of the variant's memory layout. For example, dictionary field names are stored contiguously; instead of validating each field name slice is a UTF8 separately, we now validate the entire field name buffer in a single pass.
The benchmark cases were adapted from `test_json_to_variant_object_very_large`, `test_json_to_variant_object_complex`, and `test_json_to_variant_array_nested_large` test cases.
Compared to #7871, we observe a significant improvement in performance:
<img width="576" alt="Screenshot 2025-07-07 at 10 25 07 AM" src="https://github.com/user-attachments/assets/b8644466-8259-4081-892b-c18f9f64b9f3" />
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "scovich (via GitHub)" <gi...@apache.org>.
scovich commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2192432185
##########
parquet-variant/src/variant/list.rs:
##########
@@ -205,13 +204,62 @@ impl<'m, 'v> VariantList<'m, 'v> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
+ /*
+ (1) the associated variant metadata is [valid] (*)
+ (2) all other offsets are in-bounds (*)
+ (3) all offsets are monotonically increasing (*)
+ (4) all values are (recursively) valid variant objects (*)
+ */
+
+ // (1)
// Validate the metadata dictionary first, if not already validated, because we pass it
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ // (2), (4)
+ // if we check all values are valid by using offset lookups,
+ // we know all offsets are in bounds if correct
+
+ // note how we do this once!
+ let byte_range = self.header.first_offset_byte()..self.first_value_byte;
+ let offset_bytes = slice_from_slice(self.value, byte_range)?;
+
+ let offset_chunks = offset_bytes.chunks_exact(self.header.offset_size());
+ assert!(offset_chunks.remainder().is_empty()); // guaranteed by shallow validation
+
+ let offsets = offset_chunks
+ .map(|chunk| match self.header.offset_size {
+ OffsetSizeBytes::One => chunk[0] as usize,
+ OffsetSizeBytes::Two => u16::from_le_bytes([chunk[0], chunk[1]]) as usize,
+ OffsetSizeBytes::Three => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], 0]) as usize
+ }
+ OffsetSizeBytes::Four => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]) as usize
+ }
+ })
+ .collect::<Vec<_>>();
+
+ // (3)
+ let monotonic_offsets = offsets.is_sorted_by(|a, b| a < b);
+ if !monotonic_offsets {
+ return Err(ArrowError::InvalidArgumentError(
+ "offsets are not monotonically increasing".to_string(),
+ ));
+ }
+
+ // (4)
+
+ let value_buffer = &self.value[self.first_value_byte..];
+
+ for i in 0..offsets.len() - 1 {
+ let start_offset = offsets[i];
+ let end_offset = offsets[i + 1];
+
+ let value_bytes = slice_from_slice(value_buffer, start_offset..end_offset)?;
+ Variant::try_new_with_metadata(self.metadata, value_bytes)?;
Review Comment:
I _think_ we wouldn't repeatedly validate the metadata, because invoking its `with_full_validation` method annotates the object accordingly, and the list/object `with_full_validation` validates the metadata before recursing into their children?
I was more referring to the repeated copying of 80-ish bytes that comprise the `VariantMetadata` struct, see e.g.
* https://github.com/apache/arrow-rs/issues/7831
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2198202500
##########
parquet-variant/src/variant/object.rs:
##########
@@ -210,9 +209,80 @@ impl<'m, 'v> VariantObject<'m, 'v> {
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let field_id_buffer = slice_from_slice(
+ self.value,
+ self.header.field_ids_start_byte()..self.first_field_offset_byte,
+ )?;
+
+ let field_ids = map_bytes_to_offsets(field_id_buffer, self.header.field_id_size)
+ .collect::<Vec<_>>();
+
+ // Validate all field ids exist in the metadata dictionary and the corresponding field names are lexicographically sorted
+ if self.metadata.is_sorted() {
+ // Since the metadata dictionary has unique and sorted field names, we can also guarantee this object's field names
+ // are lexicographically sorted by their field id ordering
+ if !field_ids.is_sorted() {
+ return Err(ArrowError::InvalidArgumentError(
+ "field names not sorted".to_string(),
+ ));
+ }
+
+ // Since field ids are sorted, if the last field is smaller than the dictionary size,
+ // we also know all field ids are smaller than the dictionary size and in-bounds.
+ if let Some(&last_field_id) = field_ids.last() {
+ if last_field_id >= self.metadata.dictionary_size() {
+ return Err(ArrowError::InvalidArgumentError(
+ "field id is not valid".to_string(),
+ ));
+ }
+ }
+ } else {
+ // The metadata dictionary can't guarantee uniqueness or sortedness, so we have to parse out the corresponding field names
+ // to check lexicographical order
+ let are_field_names_sorted = field_ids
+ .iter()
+ .map(|&i| self.metadata.get(i))
+ .collect::<Result<Vec<_>, _>>()?
+ .is_sorted();
+
+ if !are_field_names_sorted {
+ return Err(ArrowError::InvalidArgumentError(
+ "field names not sorted".to_string(),
+ ));
+ }
+
+ // Since field ids are not guaranteed to be sorted, scan over all field ids
Review Comment:
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?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#issuecomment-3058296506
I have sort of lost track of the current state of this PR. Is it something we want to merge and then do follow ons? If so, can we file some tickets to track those follow ons? Or do we want to keep working on this PR?
I would like to improve the benchmarks to more cleanly separate the validation benchmarks from JSON parsing benchmarks.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2196386599
##########
parquet-variant-json/benches/variant_validation.rs:
##########
@@ -0,0 +1,137 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+extern crate parquet_variant;
Review Comment:
> 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](https://docs.rs/criterion/latest/criterion/struct.Bencher.html#method.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](https://github.com/bheisler/criterion.rs/issues/475), 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.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2196386781
##########
parquet-variant-json/benches/variant_validation.rs:
##########
@@ -0,0 +1,137 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+extern crate parquet_variant;
+extern crate parquet_variant_json;
+
+use criterion::*;
+
+use parquet_variant::{Variant, VariantBuilder};
+use parquet_variant_json::json_to_variant;
+
+fn generate_large_object() -> (Vec<u8>, Vec<u8>) {
+ // 256 elements (keys: 000-255) - each element is an object of 256 elements (240-495) - each
+ // element a list of numbers from 0-127
+ let keys: Vec<String> = (0..=255).map(|n| format!("{n:03}")).collect();
Review Comment:
See https://github.com/apache/arrow-rs/pull/7878/files#r2196386599
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#issuecomment-3045733774
Note: this is still a POC. There's some code movement to do, but I figured it would be best to leave the diff like this to make it more readable.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2191367294
##########
parquet-variant/src/variant/list.rs:
##########
@@ -205,13 +204,62 @@ impl<'m, 'v> VariantList<'m, 'v> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
+ /*
+ (1) the associated variant metadata is [valid] (*)
+ (2) all other offsets are in-bounds (*)
+ (3) all offsets are monotonically increasing (*)
+ (4) all values are (recursively) valid variant objects (*)
+ */
+
+ // (1)
// Validate the metadata dictionary first, if not already validated, because we pass it
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ // (2), (4)
+ // if we check all values are valid by using offset lookups,
+ // we know all offsets are in bounds if correct
+
+ // note how we do this once!
+ let byte_range = self.header.first_offset_byte()..self.first_value_byte;
+ let offset_bytes = slice_from_slice(self.value, byte_range)?;
+
+ let offset_chunks = offset_bytes.chunks_exact(self.header.offset_size());
+ assert!(offset_chunks.remainder().is_empty()); // guaranteed by shallow validation
Review Comment:
I made this a `debug_assert` over an explicit branch.
The way ranges are created, we can always guarantee it is a multiple of `self.header.offset_size()`.
Shallow validation does the work of deriving these offsets (`.checked_mul(self.header.offset_size())`) so I want to avoid any extraneous work as possible.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2199265078
##########
parquet-variant/src/variant/list.rs:
##########
@@ -209,9 +208,35 @@ impl<'m, 'v> VariantList<'m, 'v> {
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let offset_buffer = slice_from_slice(
Review Comment:
I plan on following up with a PR that removes this check since we can validate the monotonicity of offsets when accessing variants
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "scovich (via GitHub)" <gi...@apache.org>.
scovich commented on PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#issuecomment-3058405343
> avoid materializing offsets + remove redundant checks
Honestly, this one feels like a good fast-follow, rather than something that would block the merge? Unless it's super easy/fast to clean up. Perfection as enemy of good and all that. As @viirya pointed out, this PR adds some validations that were just plain missing before.
Also, as a separate PR we could hopefully even see benchmark results quantifying the impact of the change.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2200764186
##########
parquet-variant/src/decoder.rs:
##########
@@ -200,6 +200,24 @@ impl OffsetSizeBytes {
}
}
+pub(crate) fn map_bytes_to_offsets(
Review Comment:
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.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "scovich (via GitHub)" <gi...@apache.org>.
scovich commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2200568325
##########
parquet-variant/src/decoder.rs:
##########
@@ -200,6 +200,24 @@ impl OffsetSizeBytes {
}
}
+pub(crate) fn map_bytes_to_offsets(
Review Comment:
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.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2196603742
##########
parquet-variant-json/benches/variant_validation.rs:
##########
@@ -0,0 +1,137 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+extern crate parquet_variant;
+extern crate parquet_variant_json;
+
+use criterion::*;
+
+use parquet_variant::{Variant, VariantBuilder};
+use parquet_variant_json::json_to_variant;
+
+fn generate_large_object() -> (Vec<u8>, Vec<u8>) {
+ // 256 elements (keys: 000-255) - each element is an object of 256 elements (240-495) - each
+ // element a list of numbers from 0-127
+ let keys: Vec<String> = (0..=255).map(|n| format!("{n:03}")).collect();
Review Comment:
Can we move the generation of large object out of benchmark? Only benchmarking validation?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2197556647
##########
parquet-variant/src/variant/metadata.rs:
##########
@@ -228,9 +225,48 @@ impl<'m> VariantMetadata<'m> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let offset_bytes = slice_from_slice(
+ self.bytes,
+ self.header.first_offset_byte()..self.first_value_byte,
+ )?;
+
+ let offsets =
+ map_bytes_to_offsets(offset_bytes, self.header.offset_size).collect::<Vec<_>>();
+
+ // Validate offsets are in-bounds and monotonically increasing.
+ // Since shallow validation ensures the first and last offsets are in bounds, we can also verify all offsets
+ // are in-bounds by checking if offsets are monotonically increasing.
+ let are_offsets_monotonic = offsets.is_sorted_by(|a, b| a < b);
+ if !are_offsets_monotonic {
+ return Err(ArrowError::InvalidArgumentError(
+ "offsets not monotonically increasing".to_string(),
+ ));
+ }
+
+ // Verify the string values in the dictionary are UTF-8 encoded strings.
+ let value_buffer = slice_from_slice(self.bytes, self.first_value_byte..)?;
+ let value_str = simdutf8::basic::from_utf8(value_buffer)
Review Comment:
Parquet already has `simdutf8` as (optional) dependency, so I think it makes sense to use it if enabled.
https://github.com/apache/arrow-rs/blob/ff3a2f2c59f0355f8afedb3e9258e1d6307f21ae/parquet/Cargo.toml#L73
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2198159710
##########
parquet-variant/src/variant/metadata.rs:
##########
@@ -228,9 +225,47 @@ impl<'m> VariantMetadata<'m> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let offset_bytes = slice_from_slice(
+ self.bytes,
+ self.header.first_offset_byte()..self.first_value_byte,
+ )?;
+
+ let offsets =
+ map_bytes_to_offsets(offset_bytes, self.header.offset_size).collect::<Vec<_>>();
+
+ // Validate offsets are in-bounds and monotonically increasing.
+ // Since shallow validation ensures the first and last offsets are in bounds, we can also verify all offsets
+ // are in-bounds by checking if offsets are monotonically increasing.
+ let are_offsets_monotonic = offsets.is_sorted_by(|a, b| a < b);
+ if !are_offsets_monotonic {
+ return Err(ArrowError::InvalidArgumentError(
+ "offsets not monotonically increasing".to_string(),
+ ));
+ }
+
+ // Verify the string values in the dictionary are UTF-8 encoded strings.
+ let value_buffer =
+ string_from_slice(self.bytes, 0, self.first_value_byte..self.bytes.len())?;
+
+ if self.header.is_sorted {
+ // Validate the dictionary values are unique and lexicographically sorted
+ let are_dictionary_values_unique_and_sorted = (1..offsets.len())
+ .map(|i| {
+ let field_range = offsets[i - 1]..offsets[i];
+ value_buffer.get(field_range)
+ })
+ .is_sorted_by(|a, b| match (a, b) {
+ (Some(a), Some(b)) => a < b,
Review Comment:
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?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2198282826
##########
parquet-variant/src/variant/object.rs:
##########
@@ -210,9 +209,80 @@ impl<'m, 'v> VariantObject<'m, 'v> {
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let field_id_buffer = slice_from_slice(
+ self.value,
+ self.header.field_ids_start_byte()..self.first_field_offset_byte,
+ )?;
+
+ let field_ids = map_bytes_to_offsets(field_id_buffer, self.header.field_id_size)
+ .collect::<Vec<_>>();
+
+ // Validate all field ids exist in the metadata dictionary and the corresponding field names are lexicographically sorted
+ if self.metadata.is_sorted() {
+ // Since the metadata dictionary has unique and sorted field names, we can also guarantee this object's field names
+ // are lexicographically sorted by their field id ordering
+ if !field_ids.is_sorted() {
+ return Err(ArrowError::InvalidArgumentError(
+ "field names not sorted".to_string(),
+ ));
+ }
+
+ // Since field ids are sorted, if the last field is smaller than the dictionary size,
+ // we also know all field ids are smaller than the dictionary size and in-bounds.
+ if let Some(&last_field_id) = field_ids.last() {
Review Comment:
Yes, per the spec:
> A field_id is an index into the dictionary in the metadata
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2196637245
##########
parquet-variant/src/variant/metadata.rs:
##########
@@ -228,9 +225,48 @@ impl<'m> VariantMetadata<'m> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let offset_bytes = slice_from_slice(
+ self.bytes,
+ self.header.first_offset_byte()..self.first_value_byte,
+ )?;
+
+ let offsets =
+ map_bytes_to_offsets(offset_bytes, self.header.offset_size).collect::<Vec<_>>();
+
+ // Validate offsets are in-bounds and monotonically increasing.
+ // Since shallow validation ensures the first and last offsets are in bounds, we can also verify all offsets
+ // are in-bounds by checking if offsets are monotonically increasing.
+ let are_offsets_monotonic = offsets.is_sorted_by(|a, b| a < b);
+ if !are_offsets_monotonic {
+ return Err(ArrowError::InvalidArgumentError(
+ "offsets not monotonically increasing".to_string(),
+ ));
+ }
+
+ // Verify the string values in the dictionary are UTF-8 encoded strings.
+ let value_buffer = slice_from_slice(self.bytes, self.first_value_byte..)?;
+ let value_str = simdutf8::basic::from_utf8(value_buffer)
+ .map_err(|e| ArrowError::InvalidArgumentError(format!("{e:?}")))?;
Review Comment:
If there is error, will `e` contain the whole invalid bytes? If so, the error output might be hard to read.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2197462082
##########
parquet-variant/src/variant/metadata.rs:
##########
@@ -228,9 +225,48 @@ impl<'m> VariantMetadata<'m> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let offset_bytes = slice_from_slice(
+ self.bytes,
+ self.header.first_offset_byte()..self.first_value_byte,
+ )?;
+
+ let offsets =
+ map_bytes_to_offsets(offset_bytes, self.header.offset_size).collect::<Vec<_>>();
+
+ // Validate offsets are in-bounds and monotonically increasing.
+ // Since shallow validation ensures the first and last offsets are in bounds, we can also verify all offsets
+ // are in-bounds by checking if offsets are monotonically increasing.
+ let are_offsets_monotonic = offsets.is_sorted_by(|a, b| a < b);
+ if !are_offsets_monotonic {
+ return Err(ArrowError::InvalidArgumentError(
+ "offsets not monotonically increasing".to_string(),
+ ));
+ }
+
+ // Verify the string values in the dictionary are UTF-8 encoded strings.
+ let value_buffer = slice_from_slice(self.bytes, self.first_value_byte..)?;
+ let value_str = simdutf8::basic::from_utf8(value_buffer)
Review Comment:
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
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#issuecomment-3060140164
> Looks like there is one final CI check to fix and then I can merge this PR in https://github.com/apache/arrow-rs/actions/runs/16209770665/job/45767524794?pr=7878
>
> I can't push to your PR directly because I don't have permissions in the pydantic fork
>
> If you make PRs from your own fork in the future, I can make changes directly if you think that will help
Hi, I've been trying to figure out why CI is failing. Looking at the warnings, a lot of it is coming from the `parquet` crate.
The warnings related to `parquet-variant` come from `builder.rs`, which this PR doesn't touch.
Fwiw, running `cargo doc` on main also seems to trigger different warnings.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2198198671
##########
parquet-variant/src/variant/object.rs:
##########
@@ -210,9 +209,80 @@ impl<'m, 'v> VariantObject<'m, 'v> {
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let field_id_buffer = slice_from_slice(
+ self.value,
+ self.header.field_ids_start_byte()..self.first_field_offset_byte,
+ )?;
+
+ let field_ids = map_bytes_to_offsets(field_id_buffer, self.header.field_id_size)
+ .collect::<Vec<_>>();
+
+ // Validate all field ids exist in the metadata dictionary and the corresponding field names are lexicographically sorted
+ if self.metadata.is_sorted() {
+ // Since the metadata dictionary has unique and sorted field names, we can also guarantee this object's field names
+ // are lexicographically sorted by their field id ordering
+ if !field_ids.is_sorted() {
+ return Err(ArrowError::InvalidArgumentError(
+ "field names not sorted".to_string(),
+ ));
+ }
+
+ // Since field ids are sorted, if the last field is smaller than the dictionary size,
+ // we also know all field ids are smaller than the dictionary size and in-bounds.
+ if let Some(&last_field_id) = field_ids.last() {
+ if last_field_id >= self.metadata.dictionary_size() {
+ return Err(ArrowError::InvalidArgumentError(
+ "field id is not valid".to_string(),
+ ));
+ }
+ }
+ } else {
+ // The metadata dictionary can't guarantee uniqueness or sortedness, so we have to parse out the corresponding field names
+ // to check lexicographical order
+ let are_field_names_sorted = field_ids
+ .iter()
+ .map(|&i| self.metadata.get(i))
+ .collect::<Result<Vec<_>, _>>()?
+ .is_sorted();
+
+ if !are_field_names_sorted {
Review Comment:
Btw, existing full validation of `VariantObject` doesn't check if its field names are sorted, is it missing previously?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb merged PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2197446882
##########
parquet-variant/src/variant/metadata.rs:
##########
@@ -228,9 +225,48 @@ impl<'m> VariantMetadata<'m> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let offset_bytes = slice_from_slice(
+ self.bytes,
+ self.header.first_offset_byte()..self.first_value_byte,
+ )?;
+
+ let offsets =
+ map_bytes_to_offsets(offset_bytes, self.header.offset_size).collect::<Vec<_>>();
+
+ // Validate offsets are in-bounds and monotonically increasing.
+ // Since shallow validation ensures the first and last offsets are in bounds, we can also verify all offsets
+ // are in-bounds by checking if offsets are monotonically increasing.
+ let are_offsets_monotonic = offsets.is_sorted_by(|a, b| a < b);
+ if !are_offsets_monotonic {
+ return Err(ArrowError::InvalidArgumentError(
+ "offsets not monotonically increasing".to_string(),
+ ));
+ }
+
+ // Verify the string values in the dictionary are UTF-8 encoded strings.
+ let value_buffer = slice_from_slice(self.bytes, self.first_value_byte..)?;
+ let value_str = simdutf8::basic::from_utf8(value_buffer)
+ .map_err(|e| ArrowError::InvalidArgumentError(format!("{e:?}")))?;
+
+ if self.header.is_sorted {
Review Comment:
Yeah, the current validation was written before we supported sorted dictionaries
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2199265078
##########
parquet-variant/src/variant/list.rs:
##########
@@ -209,9 +208,35 @@ impl<'m, 'v> VariantList<'m, 'v> {
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let offset_buffer = slice_from_slice(
Review Comment:
I'm going to follow up with a PR that removes this check since we can validate the monotonicity of offsets when accessing variants
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2199251737
##########
parquet-variant/src/decoder.rs:
##########
@@ -200,6 +200,24 @@ impl OffsetSizeBytes {
}
}
+pub(crate) fn map_bytes_to_offsets(
Review Comment:
Sounds good. I took a look at the codegen, the compiler optimizes out the bounds checks so it can not panic under any circumstance
<img width="1489" height="645" alt="Screenshot 2025-07-10 at 9 28 01 PM" src="https://github.com/user-attachments/assets/1bd581a6-a5fa-40cb-af57-48b46aa45d91" />
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#issuecomment-3060147909
For example, the latest CI run displays errors like:
> Documenting arrow-ord v55.2.0 (/__w/arrow-rs/arrow-rs/arrow-ord)
error: unnecessary parentheses around closure body
--> arrow-ord/src/cmp.rs:276:43
|
276 | let c = |((l, r), n)| ((l ^ r) | (l & r & n));
| ^ ^
|
= note: `-D unused-parens` implied by `-D warnings`
= help: to override `-D warnings` add `#[allow(unused_parens)]`
help: remove these parentheses
|
276 - let c = |((l, r), n)| ((l ^ r) | (l & r & n));
276 + let c = |((l, r), n)| (l ^ r) | (l & r & n);
|
error: could not document `arrow-ord`
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2197697695
##########
parquet-variant-json/benches/variant_validation.rs:
##########
@@ -0,0 +1,137 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+extern crate parquet_variant;
+extern crate parquet_variant_json;
+
+use criterion::*;
+
+use parquet_variant::{Variant, VariantBuilder};
+use parquet_variant_json::json_to_variant;
+
+fn generate_large_object() -> (Vec<u8>, Vec<u8>) {
+ // 256 elements (keys: 000-255) - each element is an object of 256 elements (240-495) - each
+ // element a list of numbers from 0-127
+ let keys: Vec<String> = (0..=255).map(|n| format!("{n:03}")).collect();
Review Comment:
Arg -- that is embarassing. I will push up a fix soon
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2196386781
##########
parquet-variant-json/benches/variant_validation.rs:
##########
@@ -0,0 +1,137 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+extern crate parquet_variant;
+extern crate parquet_variant_json;
+
+use criterion::*;
+
+use parquet_variant::{Variant, VariantBuilder};
+use parquet_variant_json::json_to_variant;
+
+fn generate_large_object() -> (Vec<u8>, Vec<u8>) {
+ // 256 elements (keys: 000-255) - each element is an object of 256 elements (240-495) - each
+ // element a list of numbers from 0-127
+ let keys: Vec<String> = (0..=255).map(|n| format!("{n:03}")).collect();
Review Comment:
See [comment](https://github.com/apache/arrow-rs/pull/7878/files#r2196386599)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#issuecomment-3046114262
BTW I ran the test that takes 30 seconds locally before this PR
- https://github.com/apache/arrow-rs/issues/7872
With this PR it takes only 6.5 seconds 👍
```
PASS [ 6.570s] parquet-variant::test_json_to_variant test_json_to_variant_object_very_large
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2190999047
##########
parquet-variant/src/variant/metadata.rs:
##########
@@ -230,7 +227,98 @@ impl<'m> VariantMetadata<'m> {
if !self.validated {
// Iterate over all string keys in this dictionary in order to prove that the offset
// array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+
+ /*
+ As scovich pointed out, here are the things full validation must do:
Review Comment:
Haha, yes. Fwiw, these comments are strictly for reviewers. This first pass is to make sure the proposed change is directionally sound
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2196388166
##########
parquet-variant-json/benches/variant_validation.rs:
##########
@@ -0,0 +1,137 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+extern crate parquet_variant;
+extern crate parquet_variant_json;
+
+use criterion::*;
+
+use parquet_variant::{Variant, VariantBuilder};
+use parquet_variant_json::json_to_variant;
+
+fn generate_large_object() -> (Vec<u8>, Vec<u8>) {
+ // 256 elements (keys: 000-255) - each element is an object of 256 elements (240-495) - each
+ // element a list of numbers from 0-127
+ let keys: Vec<String> = (0..=255).map(|n| format!("{n:03}")).collect();
+ let innermost_list: String = format!(
+ "[{}]",
+ (0..=127)
+ .map(|n| format!("{n}"))
+ .collect::<Vec<_>>()
+ .join(",")
+ );
+ let inner_keys: Vec<String> = (240..=495).map(|n| format!("{n}")).collect();
+ let inner_object = format!(
+ "{{{}:{}}}",
+ inner_keys
+ .iter()
+ .map(|k| format!("\"{k}\""))
+ .collect::<Vec<String>>()
+ .join(format!(":{innermost_list},").as_str()),
+ innermost_list
+ );
+ let json = format!(
+ "{{{}:{}}}",
+ keys.iter()
+ .map(|k| format!("\"{k}\""))
+ .collect::<Vec<String>>()
+ .join(format!(":{inner_object},").as_str()),
+ inner_object
+ );
+ // Manually verify raw JSON value size
Review Comment:
Oof, that is what I get from lifting this code from test cases
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "scovich (via GitHub)" <gi...@apache.org>.
scovich commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2198213406
##########
parquet-variant/src/variant/object.rs:
##########
@@ -210,9 +209,80 @@ impl<'m, 'v> VariantObject<'m, 'v> {
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let field_id_buffer = slice_from_slice(
+ self.value,
+ self.header.field_ids_start_byte()..self.first_field_offset_byte,
+ )?;
+
+ let field_ids = map_bytes_to_offsets(field_id_buffer, self.header.field_id_size)
+ .collect::<Vec<_>>();
+
+ // Validate all field ids exist in the metadata dictionary and the corresponding field names are lexicographically sorted
+ if self.metadata.is_sorted() {
+ // Since the metadata dictionary has unique and sorted field names, we can also guarantee this object's field names
+ // are lexicographically sorted by their field id ordering
+ if !field_ids.is_sorted() {
+ return Err(ArrowError::InvalidArgumentError(
+ "field names not sorted".to_string(),
+ ));
+ }
+
+ // Since field ids are sorted, if the last field is smaller than the dictionary size,
+ // we also know all field ids are smaller than the dictionary size and in-bounds.
+ if let Some(&last_field_id) = field_ids.last() {
+ if last_field_id >= self.metadata.dictionary_size() {
+ return Err(ArrowError::InvalidArgumentError(
+ "field id is not valid".to_string(),
+ ));
+ }
+ }
+ } else {
+ // The metadata dictionary can't guarantee uniqueness or sortedness, so we have to parse out the corresponding field names
+ // to check lexicographical order
+ let are_field_names_sorted = field_ids
+ .iter()
+ .map(|&i| self.metadata.get(i))
+ .collect::<Result<Vec<_>, _>>()?
+ .is_sorted();
+
+ if !are_field_names_sorted {
Review Comment:
I think you're right. The old validation was only ensuring individual fields names were valid, without comparing them for sortedness.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "scovich (via GitHub)" <gi...@apache.org>.
scovich commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2197669159
##########
parquet-variant/src/variant/list.rs:
##########
@@ -209,9 +208,35 @@ impl<'m, 'v> VariantList<'m, 'v> {
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let offset_buffer = slice_from_slice(
+ self.value,
+ self.header.first_offset_byte()..self.first_value_byte,
+ )?;
+
+ let offsets =
+ map_bytes_to_offsets(offset_buffer, self.header.offset_size).collect::<Vec<_>>();
+
+ // Validate offsets are in-bounds and monotonically increasing.
+ // Since shallow verification checks whether the first and last offsets are in-bounds,
+ // we can also verify all offsets are in-bounds by checking if offsets are monotonically increasing.
+ let are_offsets_monotonic = offsets.is_sorted_by(|a, b| a < b);
+ if !are_offsets_monotonic {
+ return Err(ArrowError::InvalidArgumentError(
+ "offsets are not monotonically increasing".to_string(),
+ ));
+ }
Review Comment:
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?
##########
parquet-variant/src/variant/object.rs:
##########
@@ -210,9 +209,80 @@ impl<'m, 'v> VariantObject<'m, 'v> {
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let field_id_buffer = slice_from_slice(
+ self.value,
+ self.header.field_ids_start_byte()..self.first_field_offset_byte,
+ )?;
+
+ let field_ids = map_bytes_to_offsets(field_id_buffer, self.header.field_id_size)
+ .collect::<Vec<_>>();
+
+ // Validate all field ids exist in the metadata dictionary and the corresponding field names are lexicographically sorted
+ if self.metadata.is_sorted() {
+ // Since the metadata dictionary has unique and sorted field names, we can also guarantee this object's field names
+ // are lexicographically sorted by their field id ordering
+ if !field_ids.is_sorted() {
+ return Err(ArrowError::InvalidArgumentError(
+ "field names not sorted".to_string(),
+ ));
+ }
+
+ // Since field ids are sorted, if the last field is smaller than the dictionary size,
+ // we also know all field ids are smaller than the dictionary size and in-bounds.
+ if let Some(&last_field_id) = field_ids.last() {
+ if last_field_id >= self.metadata.dictionary_size() {
+ return Err(ArrowError::InvalidArgumentError(
+ "field id is not valid".to_string(),
+ ));
+ }
+ }
+ } else {
+ // The metadata dictionary can't guarantee uniqueness or sortedness, so we have to parse out the corresponding field names
+ // to check lexicographical order
+ let are_field_names_sorted = field_ids
+ .iter()
+ .map(|&i| self.metadata.get(i))
+ .collect::<Result<Vec<_>, _>>()?
+ .is_sorted();
+
+ if !are_field_names_sorted {
+ return Err(ArrowError::InvalidArgumentError(
+ "field names not sorted".to_string(),
+ ));
+ }
+
+ // Since field ids are not guaranteed to be sorted, scan over all field ids
+ // and check that field ids are less than dictionary size
+
+ let are_field_ids_in_bounds = field_ids
+ .iter()
+ .all(|&id| id < self.metadata.dictionary_size());
+
+ if !are_field_ids_in_bounds {
+ return Err(ArrowError::InvalidArgumentError(
+ "field id is not valid".to_string(),
+ ));
+ }
+ }
+
+ // Validate whether values are valid variant objects
+ let field_offset_buffer = slice_from_slice(
+ self.value,
+ self.first_field_offset_byte..self.first_value_byte,
+ )?;
+ let num_offsets = field_offset_buffer.len() / self.header.field_offset_size();
+
+ let value_buffer = slice_from_slice(self.value, self.first_value_byte..)?;
+
+ map_bytes_to_offsets(field_offset_buffer, self.header.field_offset_size)
+ .take(num_offsets.saturating_sub(1))
Review Comment:
Shallow validation already ensured the last offset is in bounds, correct?
##########
parquet-variant/src/variant/list.rs:
##########
@@ -209,9 +208,35 @@ impl<'m, 'v> VariantList<'m, 'v> {
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let offset_buffer = slice_from_slice(
+ self.value,
+ self.header.first_offset_byte()..self.first_value_byte,
+ )?;
+
+ let offsets =
+ map_bytes_to_offsets(offset_buffer, self.header.offset_size).collect::<Vec<_>>();
+
+ // Validate offsets are in-bounds and monotonically increasing.
+ // Since shallow verification checks whether the first and last offsets are in-bounds,
+ // we can also verify all offsets are in-bounds by checking if offsets are monotonically increasing.
+ let are_offsets_monotonic = offsets.is_sorted_by(|a, b| a < b);
+ if !are_offsets_monotonic {
+ return Err(ArrowError::InvalidArgumentError(
+ "offsets are not monotonically increasing".to_string(),
+ ));
+ }
Review Comment:
The simplified version would be something like:
```rust
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;
}
}
```
##########
parquet-variant/src/decoder.rs:
##########
@@ -200,6 +200,24 @@ impl OffsetSizeBytes {
}
}
+pub(crate) fn map_bytes_to_offsets(
Review Comment:
Needs a doc comment explaining what it does and the conditions under which it's panic-free?
##########
parquet-variant/src/variant/object.rs:
##########
@@ -210,9 +209,80 @@ impl<'m, 'v> VariantObject<'m, 'v> {
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let field_id_buffer = slice_from_slice(
+ self.value,
+ self.header.field_ids_start_byte()..self.first_field_offset_byte,
+ )?;
+
+ let field_ids = map_bytes_to_offsets(field_id_buffer, self.header.field_id_size)
+ .collect::<Vec<_>>();
+
+ // Validate all field ids exist in the metadata dictionary and the corresponding field names are lexicographically sorted
+ if self.metadata.is_sorted() {
+ // Since the metadata dictionary has unique and sorted field names, we can also guarantee this object's field names
+ // are lexicographically sorted by their field id ordering
+ if !field_ids.is_sorted() {
+ return Err(ArrowError::InvalidArgumentError(
+ "field names not sorted".to_string(),
+ ));
+ }
+
+ // Since field ids are sorted, if the last field is smaller than the dictionary size,
+ // we also know all field ids are smaller than the dictionary size and in-bounds.
+ if let Some(&last_field_id) = field_ids.last() {
+ if last_field_id >= self.metadata.dictionary_size() {
+ return Err(ArrowError::InvalidArgumentError(
+ "field id is not valid".to_string(),
+ ));
+ }
+ }
+ } else {
+ // The metadata dictionary can't guarantee uniqueness or sortedness, so we have to parse out the corresponding field names
+ // to check lexicographical order
+ let are_field_names_sorted = field_ids
+ .iter()
+ .map(|&i| self.metadata.get(i))
+ .collect::<Result<Vec<_>, _>>()?
+ .is_sorted();
+
+ if !are_field_names_sorted {
+ return Err(ArrowError::InvalidArgumentError(
+ "field names not sorted".to_string(),
+ ));
+ }
+
+ // Since field ids are not guaranteed to be sorted, scan over all field ids
+ // and check that field ids are less than dictionary size
+
+ let are_field_ids_in_bounds = field_ids
+ .iter()
+ .all(|&id| id < self.metadata.dictionary_size());
+
+ if !are_field_ids_in_bounds {
+ return Err(ArrowError::InvalidArgumentError(
+ "field id is not valid".to_string(),
+ ));
+ }
Review Comment:
We don't need this check. If any field id were out of bounds, the `collect`at L245 would have already failed.
##########
parquet-variant/src/variant/object.rs:
##########
@@ -210,9 +209,80 @@ impl<'m, 'v> VariantObject<'m, 'v> {
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let field_id_buffer = slice_from_slice(
+ self.value,
+ self.header.field_ids_start_byte()..self.first_field_offset_byte,
+ )?;
+
+ let field_ids = map_bytes_to_offsets(field_id_buffer, self.header.field_id_size)
+ .collect::<Vec<_>>();
+
+ // Validate all field ids exist in the metadata dictionary and the corresponding field names are lexicographically sorted
+ if self.metadata.is_sorted() {
+ // Since the metadata dictionary has unique and sorted field names, we can also guarantee this object's field names
+ // are lexicographically sorted by their field id ordering
+ if !field_ids.is_sorted() {
+ return Err(ArrowError::InvalidArgumentError(
+ "field names not sorted".to_string(),
+ ));
+ }
+
+ // Since field ids are sorted, if the last field is smaller than the dictionary size,
+ // we also know all field ids are smaller than the dictionary size and in-bounds.
+ if let Some(&last_field_id) = field_ids.last() {
+ if last_field_id >= self.metadata.dictionary_size() {
+ return Err(ArrowError::InvalidArgumentError(
+ "field id is not valid".to_string(),
+ ));
+ }
+ }
+ } else {
+ // The metadata dictionary can't guarantee uniqueness or sortedness, so we have to parse out the corresponding field names
+ // to check lexicographical order
+ let are_field_names_sorted = field_ids
+ .iter()
+ .map(|&i| self.metadata.get(i))
+ .collect::<Result<Vec<_>, _>>()?
+ .is_sorted();
+
+ if !are_field_names_sorted {
+ return Err(ArrowError::InvalidArgumentError(
+ "field names not sorted".to_string(),
+ ));
+ }
+
+ // Since field ids are not guaranteed to be sorted, scan over all field ids
+ // and check that field ids are less than dictionary size
+
+ let are_field_ids_in_bounds = field_ids
+ .iter()
+ .all(|&id| id < self.metadata.dictionary_size());
+
+ if !are_field_ids_in_bounds {
+ return Err(ArrowError::InvalidArgumentError(
+ "field id is not valid".to_string(),
+ ));
+ }
+ }
+
+ // Validate whether values are valid variant objects
+ let field_offset_buffer = slice_from_slice(
+ self.value,
+ self.first_field_offset_byte..self.first_value_byte,
+ )?;
+ let num_offsets = field_offset_buffer.len() / self.header.field_offset_size();
+
+ let value_buffer = slice_from_slice(self.value, self.first_value_byte..)?;
+
+ map_bytes_to_offsets(field_offset_buffer, self.header.field_offset_size)
+ .take(num_offsets.saturating_sub(1))
+ .try_for_each(|offset| {
+ let value_bytes = slice_from_slice(value_buffer, offset..)?;
+ Variant::try_new_with_metadata(self.metadata, value_bytes)?;
+
+ Ok::<_, ArrowError>(())
Review Comment:
does this not work for some reason?
```suggestion
Ok(())
```
(`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...)
##########
parquet-variant/src/variant/metadata.rs:
##########
@@ -228,9 +225,47 @@ impl<'m> VariantMetadata<'m> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let offset_bytes = slice_from_slice(
+ self.bytes,
+ self.header.first_offset_byte()..self.first_value_byte,
+ )?;
+
+ let offsets =
+ map_bytes_to_offsets(offset_bytes, self.header.offset_size).collect::<Vec<_>>();
+
+ // Validate offsets are in-bounds and monotonically increasing.
+ // Since shallow validation ensures the first and last offsets are in bounds, we can also verify all offsets
+ // are in-bounds by checking if offsets are monotonically increasing.
+ let are_offsets_monotonic = offsets.is_sorted_by(|a, b| a < b);
+ if !are_offsets_monotonic {
+ return Err(ArrowError::InvalidArgumentError(
+ "offsets not monotonically increasing".to_string(),
+ ));
+ }
Review Comment:
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?
```rust
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:
```rust
pub(crate) fn slice_from_slice<T, I: SliceIndex<[T]> + Clone + Debug>(
bytes: &[T],
index: I,
) -> Result<&I::Output, ArrowError> {
```
##########
parquet-variant/src/variant/object.rs:
##########
@@ -210,9 +209,80 @@ impl<'m, 'v> VariantObject<'m, 'v> {
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let field_id_buffer = slice_from_slice(
+ self.value,
+ self.header.field_ids_start_byte()..self.first_field_offset_byte,
+ )?;
+
+ let field_ids = map_bytes_to_offsets(field_id_buffer, self.header.field_id_size)
+ .collect::<Vec<_>>();
+
+ // Validate all field ids exist in the metadata dictionary and the corresponding field names are lexicographically sorted
+ if self.metadata.is_sorted() {
+ // Since the metadata dictionary has unique and sorted field names, we can also guarantee this object's field names
+ // are lexicographically sorted by their field id ordering
Review Comment:
clever!
##########
parquet-variant/src/variant/object.rs:
##########
@@ -206,13 +205,118 @@ impl<'m, 'v> VariantObject<'m, 'v> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
+ /*
+ (1) the associated variant metadata is [valid] (*)
+ (2) all field ids are valid metadata dictionary entries (*)
+ (3) field ids are lexically ordered according by their corresponding string values (*)
+ (4) all field offsets are in bounds (*)
+ (5) all field values are (recursively) _valid_ variant values (*)
+
+ */
+
+ // (1)
// Validate the metadata dictionary first, if not already validated, because we pass it
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ // (2)
+ // Field ids serve as indexes into the metadata buffer.
+ // As long as we guarantee the largest field id is < dictionary size,
+ // we can guarantee all field ids are valid metadata dictionaries
+
+ // (2), (3)
+ let byte_range = self.header.field_ids_start_byte()..self.first_field_offset_byte;
+ let field_id_bytes = slice_from_slice(self.value, byte_range)?;
+ // let field_id = self.header.field_id_size.unpack_usize(field_id_bytes, i)?;
+
+ let field_id_chunks = field_id_bytes.chunks_exact(self.header.field_id_size());
+ assert!(field_id_chunks.remainder().is_empty()); // guaranteed to be none
+
+ let field_ids = field_id_chunks
+ .map(|chunk| match self.header.field_id_size {
+ OffsetSizeBytes::One => chunk[0] as usize,
+ OffsetSizeBytes::Two => u16::from_le_bytes([chunk[0], chunk[1]]) as usize,
+ OffsetSizeBytes::Three => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], 0]) as usize
+ }
+ OffsetSizeBytes::Four => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]) as usize
+ }
+ })
+ .collect::<Vec<_>>();
Review Comment:
> 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:
```rust
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 is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2192454452
##########
parquet-variant/src/variant/list.rs:
##########
@@ -205,13 +204,62 @@ impl<'m, 'v> VariantList<'m, 'v> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
+ /*
+ (1) the associated variant metadata is [valid] (*)
+ (2) all other offsets are in-bounds (*)
+ (3) all offsets are monotonically increasing (*)
+ (4) all values are (recursively) valid variant objects (*)
+ */
+
+ // (1)
// Validate the metadata dictionary first, if not already validated, because we pass it
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ // (2), (4)
+ // if we check all values are valid by using offset lookups,
+ // we know all offsets are in bounds if correct
+
+ // note how we do this once!
+ let byte_range = self.header.first_offset_byte()..self.first_value_byte;
+ let offset_bytes = slice_from_slice(self.value, byte_range)?;
+
+ let offset_chunks = offset_bytes.chunks_exact(self.header.offset_size());
+ assert!(offset_chunks.remainder().is_empty()); // guaranteed by shallow validation
+
+ let offsets = offset_chunks
+ .map(|chunk| match self.header.offset_size {
+ OffsetSizeBytes::One => chunk[0] as usize,
+ OffsetSizeBytes::Two => u16::from_le_bytes([chunk[0], chunk[1]]) as usize,
+ OffsetSizeBytes::Three => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], 0]) as usize
+ }
+ OffsetSizeBytes::Four => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]) as usize
+ }
+ })
+ .collect::<Vec<_>>();
+
+ // (3)
+ let monotonic_offsets = offsets.is_sorted_by(|a, b| a < b);
+ if !monotonic_offsets {
+ return Err(ArrowError::InvalidArgumentError(
+ "offsets are not monotonically increasing".to_string(),
+ ));
+ }
+
+ // (4)
+
+ let value_buffer = &self.value[self.first_value_byte..];
+
+ for i in 0..offsets.len() - 1 {
+ let start_offset = offsets[i];
+ let end_offset = offsets[i + 1];
+
+ let value_bytes = slice_from_slice(value_buffer, start_offset..end_offset)?;
+ Variant::try_new_with_metadata(self.metadata, value_bytes)?;
Review Comment:
Ah, I was checking this theory in a test case that would perform validation multiple times. I can confirm that we only validate the metadata once.
Here's the repro: https://github.com/pydantic/arrow-rs/pull/new/friendlymatthew/repro-validation
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#issuecomment-3061856301
@viirya fixed the docs CI failure in this PR ❤️
- https://github.com/apache/arrow-rs/pull/7898
So I am merging this PR in to keep the code flowing
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "scovich (via GitHub)" <gi...@apache.org>.
scovich commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2198210560
##########
parquet-variant/src/variant/object.rs:
##########
@@ -210,9 +209,80 @@ impl<'m, 'v> VariantObject<'m, 'v> {
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let field_id_buffer = slice_from_slice(
+ self.value,
+ self.header.field_ids_start_byte()..self.first_field_offset_byte,
+ )?;
+
+ let field_ids = map_bytes_to_offsets(field_id_buffer, self.header.field_id_size)
+ .collect::<Vec<_>>();
+
+ // Validate all field ids exist in the metadata dictionary and the corresponding field names are lexicographically sorted
+ if self.metadata.is_sorted() {
+ // Since the metadata dictionary has unique and sorted field names, we can also guarantee this object's field names
+ // are lexicographically sorted by their field id ordering
+ if !field_ids.is_sorted() {
+ return Err(ArrowError::InvalidArgumentError(
+ "field names not sorted".to_string(),
+ ));
+ }
+
+ // Since field ids are sorted, if the last field is smaller than the dictionary size,
+ // we also know all field ids are smaller than the dictionary size and in-bounds.
+ if let Some(&last_field_id) = field_ids.last() {
+ if last_field_id >= self.metadata.dictionary_size() {
+ return Err(ArrowError::InvalidArgumentError(
+ "field id is not valid".to_string(),
+ ));
+ }
+ }
+ } else {
+ // The metadata dictionary can't guarantee uniqueness or sortedness, so we have to parse out the corresponding field names
Review Comment:
You're right, but all this naming comes from the variant spec 🤷
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2198274030
##########
parquet-variant/src/variant/object.rs:
##########
@@ -210,9 +209,80 @@ impl<'m, 'v> VariantObject<'m, 'v> {
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let field_id_buffer = slice_from_slice(
+ self.value,
+ self.header.field_ids_start_byte()..self.first_field_offset_byte,
+ )?;
+
+ let field_ids = map_bytes_to_offsets(field_id_buffer, self.header.field_id_size)
+ .collect::<Vec<_>>();
+
+ // Validate all field ids exist in the metadata dictionary and the corresponding field names are lexicographically sorted
+ if self.metadata.is_sorted() {
+ // Since the metadata dictionary has unique and sorted field names, we can also guarantee this object's field names
+ // are lexicographically sorted by their field id ordering
+ if !field_ids.is_sorted() {
+ return Err(ArrowError::InvalidArgumentError(
+ "field names not sorted".to_string(),
+ ));
+ }
+
+ // Since field ids are sorted, if the last field is smaller than the dictionary size,
+ // we also know all field ids are smaller than the dictionary size and in-bounds.
+ if let Some(&last_field_id) = field_ids.last() {
+ if last_field_id >= self.metadata.dictionary_size() {
+ return Err(ArrowError::InvalidArgumentError(
+ "field id is not valid".to_string(),
+ ));
+ }
+ }
+ } else {
+ // The metadata dictionary can't guarantee uniqueness or sortedness, so we have to parse out the corresponding field names
Review Comment:
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.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2191371300
##########
parquet-variant/src/variant/list.rs:
##########
@@ -205,13 +204,62 @@ impl<'m, 'v> VariantList<'m, 'v> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
+ /*
+ (1) the associated variant metadata is [valid] (*)
+ (2) all other offsets are in-bounds (*)
+ (3) all offsets are monotonically increasing (*)
+ (4) all values are (recursively) valid variant objects (*)
+ */
+
+ // (1)
// Validate the metadata dictionary first, if not already validated, because we pass it
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ // (2), (4)
+ // if we check all values are valid by using offset lookups,
+ // we know all offsets are in bounds if correct
+
+ // note how we do this once!
+ let byte_range = self.header.first_offset_byte()..self.first_value_byte;
+ let offset_bytes = slice_from_slice(self.value, byte_range)?;
+
+ let offset_chunks = offset_bytes.chunks_exact(self.header.offset_size());
+ assert!(offset_chunks.remainder().is_empty()); // guaranteed by shallow validation
+
+ let offsets = offset_chunks
+ .map(|chunk| match self.header.offset_size {
+ OffsetSizeBytes::One => chunk[0] as usize,
+ OffsetSizeBytes::Two => u16::from_le_bytes([chunk[0], chunk[1]]) as usize,
+ OffsetSizeBytes::Three => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], 0]) as usize
+ }
+ OffsetSizeBytes::Four => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]) as usize
+ }
+ })
+ .collect::<Vec<_>>();
+
+ // (3)
+ let monotonic_offsets = offsets.is_sorted_by(|a, b| a < b);
+ if !monotonic_offsets {
+ return Err(ArrowError::InvalidArgumentError(
+ "offsets are not monotonically increasing".to_string(),
+ ));
+ }
+
+ // (4)
+
+ let value_buffer = &self.value[self.first_value_byte..];
+
+ for i in 0..offsets.len() - 1 {
+ let start_offset = offsets[i];
+ let end_offset = offsets[i + 1];
+
+ let value_bytes = slice_from_slice(value_buffer, start_offset..end_offset)?;
+ Variant::try_new_with_metadata(self.metadata, value_bytes)?;
Review Comment:
Yeah, I've been thinking about this. Any time we need to recursively validate a variant, by way of object fields or list elements, we will eagerly validate the `VariantMetadata` again and again.
We can definitely avoid work here. I will think about this more and follow up in a later PR
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "scovich (via GitHub)" <gi...@apache.org>.
scovich commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2192447006
##########
parquet-variant/src/variant/list.rs:
##########
@@ -205,13 +204,62 @@ impl<'m, 'v> VariantList<'m, 'v> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
+ /*
+ (1) the associated variant metadata is [valid] (*)
+ (2) all other offsets are in-bounds (*)
+ (3) all offsets are monotonically increasing (*)
+ (4) all values are (recursively) valid variant objects (*)
+ */
+
+ // (1)
// Validate the metadata dictionary first, if not already validated, because we pass it
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ // (2), (4)
+ // if we check all values are valid by using offset lookups,
+ // we know all offsets are in bounds if correct
+
+ // note how we do this once!
+ let byte_range = self.header.first_offset_byte()..self.first_value_byte;
+ let offset_bytes = slice_from_slice(self.value, byte_range)?;
+
+ let offset_chunks = offset_bytes.chunks_exact(self.header.offset_size());
+ assert!(offset_chunks.remainder().is_empty()); // guaranteed by shallow validation
+
+ let offsets = offset_chunks
+ .map(|chunk| match self.header.offset_size {
+ OffsetSizeBytes::One => chunk[0] as usize,
+ OffsetSizeBytes::Two => u16::from_le_bytes([chunk[0], chunk[1]]) as usize,
+ OffsetSizeBytes::Three => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], 0]) as usize
+ }
+ OffsetSizeBytes::Four => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]) as usize
+ }
+ })
+ .collect::<Vec<_>>();
+
+ // (3)
+ let monotonic_offsets = offsets.is_sorted_by(|a, b| a < b);
+ if !monotonic_offsets {
+ return Err(ArrowError::InvalidArgumentError(
+ "offsets are not monotonically increasing".to_string(),
+ ));
+ }
+
+ // (4)
+
+ let value_buffer = &self.value[self.first_value_byte..];
Review Comment:
NOTE: `[]` still pays the branch to bounds check... it just panics instead of returning a Result when something goes wrong.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2196081537
##########
parquet-variant-json/benches/variant_validation.rs:
##########
@@ -0,0 +1,137 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+extern crate parquet_variant;
+extern crate parquet_variant_json;
+
+use criterion::*;
+
+use parquet_variant::{Variant, VariantBuilder};
+use parquet_variant_json::json_to_variant;
+
+fn generate_large_object() -> (Vec<u8>, Vec<u8>) {
+ // 256 elements (keys: 000-255) - each element is an object of 256 elements (240-495) - each
+ // element a list of numbers from 0-127
+ let keys: Vec<String> = (0..=255).map(|n| format!("{n:03}")).collect();
Review Comment:
I think a non trivial amount of the time being measured by this benchmark is the creation of the JSON string...
##########
parquet-variant-json/benches/variant_validation.rs:
##########
@@ -0,0 +1,137 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+extern crate parquet_variant;
Review Comment:
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 calling`Variant::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
##########
parquet-variant/src/variant/list.rs:
##########
@@ -209,9 +208,35 @@ impl<'m, 'v> VariantList<'m, 'v> {
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let offset_buffer = slice_from_slice(
Review Comment:
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
```rust
fn validate_offsets(offset_buffer: &[u8], num_offsets: usize, offset_size: OffsetSize, max_valid_offset: usize) {
...
}
```
Or something 🤔
##########
parquet-variant-json/benches/variant_validation.rs:
##########
@@ -0,0 +1,137 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+extern crate parquet_variant;
+extern crate parquet_variant_json;
+
+use criterion::*;
+
+use parquet_variant::{Variant, VariantBuilder};
+use parquet_variant_json::json_to_variant;
+
+fn generate_large_object() -> (Vec<u8>, Vec<u8>) {
+ // 256 elements (keys: 000-255) - each element is an object of 256 elements (240-495) - each
+ // element a list of numbers from 0-127
+ let keys: Vec<String> = (0..=255).map(|n| format!("{n:03}")).collect();
+ let innermost_list: String = format!(
+ "[{}]",
+ (0..=127)
+ .map(|n| format!("{n}"))
+ .collect::<Vec<_>>()
+ .join(",")
+ );
+ let inner_keys: Vec<String> = (240..=495).map(|n| format!("{n}")).collect();
+ let inner_object = format!(
+ "{{{}:{}}}",
+ inner_keys
+ .iter()
+ .map(|k| format!("\"{k}\""))
+ .collect::<Vec<String>>()
+ .join(format!(":{innermost_list},").as_str()),
+ innermost_list
+ );
+ let json = format!(
+ "{{{}:{}}}",
+ keys.iter()
+ .map(|k| format!("\"{k}\""))
+ .collect::<Vec<String>>()
+ .join(format!(":{inner_object},").as_str()),
+ inner_object
+ );
+ // Manually verify raw JSON value size
Review Comment:
this comment seems incorrect
##########
parquet-variant/src/variant/object.rs:
##########
@@ -210,9 +209,77 @@ impl<'m, 'v> VariantObject<'m, 'v> {
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let field_id_buffer = slice_from_slice(
+ self.value,
+ self.header.field_ids_start_byte()..self.first_field_offset_byte,
+ )?;
+
+ let field_ids = map_bytes_to_offsets(field_id_buffer, self.header.field_id_size)
+ .collect::<Vec<_>>();
+
+ // Validate all field ids exist in the metadata dictionary and the corresponding field names are lexicographically sorted
+ if self.metadata.is_sorted() {
+ // Since the metadata dictionary has unique and sorted field names, we can also guarantee this object's field names
+ // are lexicographically sorted by their field id ordering
+ if !field_ids.is_sorted() {
+ return Err(ArrowError::InvalidArgumentError(
+ "field names not sorted".to_string(),
+ ));
+ }
+
+ // Since field ids are sorted, if the last field is smaller than the dictionary size,
+ // we also know all field ids are smaller than the dictionary size and in-bounds.
+ if let Some(&last_field_id) = field_ids.last() {
+ if last_field_id >= self.metadata.dictionary_size() {
+ return Err(ArrowError::InvalidArgumentError(
+ "field id is not valid".to_string(),
+ ));
+ }
+ }
+ } else {
+ // The metadata dictionary can't guarantee uniqueness or sortedness, so we have to parse out the corresponding field names
+ // to check lexicographical order
+ let are_field_names_sorted = field_ids
+ .iter()
+ .map(|&i| self.metadata.get(i))
+ .collect::<Result<Vec<_>, _>>()?
+ .is_sorted();
+
+ if !are_field_names_sorted {
+ return Err(ArrowError::InvalidArgumentError(
+ "field names not sorted".to_string(),
+ ));
+ }
+
+ // Since field ids aren't guaranteed to be sorted, scan through the field ids and pick the largest field id in this object.
+ // If the largest field id is smaller than the dictionary size, we also know all field ids are smaller than the dictionary size and in-bounds.
Review Comment:
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
##########
parquet-variant/src/variant/metadata.rs:
##########
@@ -228,9 +225,48 @@ impl<'m> VariantMetadata<'m> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let offset_bytes = slice_from_slice(
+ self.bytes,
+ self.header.first_offset_byte()..self.first_value_byte,
+ )?;
+
+ let offsets =
+ map_bytes_to_offsets(offset_bytes, self.header.offset_size).collect::<Vec<_>>();
+
+ // Validate offsets are in-bounds and monotonically increasing.
+ // Since shallow validation ensures the first and last offsets are in bounds, we can also verify all offsets
+ // are in-bounds by checking if offsets are monotonically increasing.
+ let are_offsets_monotonic = offsets.is_sorted_by(|a, b| a < b);
+ if !are_offsets_monotonic {
+ return Err(ArrowError::InvalidArgumentError(
+ "offsets not monotonically increasing".to_string(),
+ ));
+ }
+
+ // Verify the string values in the dictionary are UTF-8 encoded strings.
+ let value_buffer = slice_from_slice(self.bytes, self.first_value_byte..)?;
+ let value_str = simdutf8::basic::from_utf8(value_buffer)
Review Comment:
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
##########
parquet-variant/src/variant/object.rs:
##########
@@ -206,13 +205,118 @@ impl<'m, 'v> VariantObject<'m, 'v> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
+ /*
+ (1) the associated variant metadata is [valid] (*)
+ (2) all field ids are valid metadata dictionary entries (*)
+ (3) field ids are lexically ordered according by their corresponding string values (*)
+ (4) all field offsets are in bounds (*)
+ (5) all field values are (recursively) _valid_ variant values (*)
+
+ */
+
+ // (1)
// Validate the metadata dictionary first, if not already validated, because we pass it
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ // (2)
+ // Field ids serve as indexes into the metadata buffer.
+ // As long as we guarantee the largest field id is < dictionary size,
+ // we can guarantee all field ids are valid metadata dictionaries
+
+ // (2), (3)
+ let byte_range = self.header.field_ids_start_byte()..self.first_field_offset_byte;
+ let field_id_bytes = slice_from_slice(self.value, byte_range)?;
+ // let field_id = self.header.field_id_size.unpack_usize(field_id_bytes, i)?;
+
+ let field_id_chunks = field_id_bytes.chunks_exact(self.header.field_id_size());
+ assert!(field_id_chunks.remainder().is_empty()); // guaranteed to be none
+
+ let field_ids = field_id_chunks
+ .map(|chunk| match self.header.field_id_size {
+ OffsetSizeBytes::One => chunk[0] as usize,
+ OffsetSizeBytes::Two => u16::from_le_bytes([chunk[0], chunk[1]]) as usize,
+ OffsetSizeBytes::Three => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], 0]) as usize
+ }
+ OffsetSizeBytes::Four => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]) as usize
+ }
+ })
+ .collect::<Vec<_>>();
Review Comment:
I agree -- it seems unecessary to allocate and copy all the values into a Vec here
##########
parquet-variant-json/benches/variant_validation.rs:
##########
@@ -0,0 +1,137 @@
+// Licensed to the Apache Software Foundation (ASF) under one
Review Comment:
I ran these benchmarks locally
```shell
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)
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2196635404
##########
parquet-variant/src/variant/metadata.rs:
##########
@@ -228,9 +225,48 @@ impl<'m> VariantMetadata<'m> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let offset_bytes = slice_from_slice(
+ self.bytes,
+ self.header.first_offset_byte()..self.first_value_byte,
+ )?;
+
+ let offsets =
+ map_bytes_to_offsets(offset_bytes, self.header.offset_size).collect::<Vec<_>>();
+
+ // Validate offsets are in-bounds and monotonically increasing.
+ // Since shallow validation ensures the first and last offsets are in bounds, we can also verify all offsets
+ // are in-bounds by checking if offsets are monotonically increasing.
+ let are_offsets_monotonic = offsets.is_sorted_by(|a, b| a < b);
+ if !are_offsets_monotonic {
+ return Err(ArrowError::InvalidArgumentError(
+ "offsets not monotonically increasing".to_string(),
+ ));
+ }
+
+ // Verify the string values in the dictionary are UTF-8 encoded strings.
+ let value_buffer = slice_from_slice(self.bytes, self.first_value_byte..)?;
+ let value_str = simdutf8::basic::from_utf8(value_buffer)
Review Comment:
What is the difference between the currently used `str::from_utf8` and this `simdutf8::basic::from_utf8`?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#issuecomment-3052771499
Hi @viirya, I would appreciate your thoughts on this PR as well
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2197689039
##########
parquet-variant-json/benches/variant_validation.rs:
##########
@@ -0,0 +1,137 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+extern crate parquet_variant;
+extern crate parquet_variant_json;
+
+use criterion::*;
+
+use parquet_variant::{Variant, VariantBuilder};
+use parquet_variant_json::json_to_variant;
+
+fn generate_large_object() -> (Vec<u8>, Vec<u8>) {
+ // 256 elements (keys: 000-255) - each element is an object of 256 elements (240-495) - each
+ // element a list of numbers from 0-127
+ let keys: Vec<String> = (0..=255).map(|n| format!("{n:03}")).collect();
Review Comment:
Yeah, I think that would be useful. I did some profiling at more than half the time of this benchmark is spent parsing JSON
<img width="1263" height="955" alt="Screenshot 2025-07-10 at 9 06 29 AM" src="https://github.com/user-attachments/assets/c581796b-fac1-4fb4-89ef-f681a0896ecb" />
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2192450387
##########
parquet-variant/src/variant/list.rs:
##########
@@ -205,13 +204,62 @@ impl<'m, 'v> VariantList<'m, 'v> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
+ /*
+ (1) the associated variant metadata is [valid] (*)
+ (2) all other offsets are in-bounds (*)
+ (3) all offsets are monotonically increasing (*)
+ (4) all values are (recursively) valid variant objects (*)
+ */
+
+ // (1)
// Validate the metadata dictionary first, if not already validated, because we pass it
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ // (2), (4)
+ // if we check all values are valid by using offset lookups,
+ // we know all offsets are in bounds if correct
+
+ // note how we do this once!
+ let byte_range = self.header.first_offset_byte()..self.first_value_byte;
+ let offset_bytes = slice_from_slice(self.value, byte_range)?;
+
+ let offset_chunks = offset_bytes.chunks_exact(self.header.offset_size());
+ assert!(offset_chunks.remainder().is_empty()); // guaranteed by shallow validation
+
+ let offsets = offset_chunks
+ .map(|chunk| match self.header.offset_size {
+ OffsetSizeBytes::One => chunk[0] as usize,
+ OffsetSizeBytes::Two => u16::from_le_bytes([chunk[0], chunk[1]]) as usize,
+ OffsetSizeBytes::Three => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], 0]) as usize
+ }
+ OffsetSizeBytes::Four => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]) as usize
+ }
+ })
+ .collect::<Vec<_>>();
+
+ // (3)
+ let monotonic_offsets = offsets.is_sorted_by(|a, b| a < b);
+ if !monotonic_offsets {
+ return Err(ArrowError::InvalidArgumentError(
+ "offsets are not monotonically increasing".to_string(),
+ ));
+ }
+
+ // (4)
+
+ let value_buffer = &self.value[self.first_value_byte..];
Review Comment:
Yup, we should be using `slice_from_slice` throughout this PR
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2198170411
##########
parquet-variant/src/variant/object.rs:
##########
@@ -210,9 +209,80 @@ impl<'m, 'v> VariantObject<'m, 'v> {
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let field_id_buffer = slice_from_slice(
+ self.value,
+ self.header.field_ids_start_byte()..self.first_field_offset_byte,
+ )?;
+
+ let field_ids = map_bytes_to_offsets(field_id_buffer, self.header.field_id_size)
+ .collect::<Vec<_>>();
+
+ // Validate all field ids exist in the metadata dictionary and the corresponding field names are lexicographically sorted
+ if self.metadata.is_sorted() {
+ // Since the metadata dictionary has unique and sorted field names, we can also guarantee this object's field names
+ // are lexicographically sorted by their field id ordering
+ if !field_ids.is_sorted() {
+ return Err(ArrowError::InvalidArgumentError(
+ "field names not sorted".to_string(),
+ ));
+ }
+
+ // Since field ids are sorted, if the last field is smaller than the dictionary size,
+ // we also know all field ids are smaller than the dictionary size and in-bounds.
+ if let Some(&last_field_id) = field_ids.last() {
+ if last_field_id >= self.metadata.dictionary_size() {
+ return Err(ArrowError::InvalidArgumentError(
+ "field id is not valid".to_string(),
+ ));
+ }
+ }
+ } else {
+ // The metadata dictionary can't guarantee uniqueness or sortedness, so we have to parse out the corresponding field names
Review Comment:
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.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2196640023
##########
parquet-variant/src/variant/metadata.rs:
##########
@@ -228,9 +225,48 @@ impl<'m> VariantMetadata<'m> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let offset_bytes = slice_from_slice(
+ self.bytes,
+ self.header.first_offset_byte()..self.first_value_byte,
+ )?;
+
+ let offsets =
+ map_bytes_to_offsets(offset_bytes, self.header.offset_size).collect::<Vec<_>>();
+
+ // Validate offsets are in-bounds and monotonically increasing.
+ // Since shallow validation ensures the first and last offsets are in bounds, we can also verify all offsets
+ // are in-bounds by checking if offsets are monotonically increasing.
+ let are_offsets_monotonic = offsets.is_sorted_by(|a, b| a < b);
+ if !are_offsets_monotonic {
+ return Err(ArrowError::InvalidArgumentError(
+ "offsets not monotonically increasing".to_string(),
+ ));
+ }
+
+ // Verify the string values in the dictionary are UTF-8 encoded strings.
+ let value_buffer = slice_from_slice(self.bytes, self.first_value_byte..)?;
+ let value_str = simdutf8::basic::from_utf8(value_buffer)
+ .map_err(|e| ArrowError::InvalidArgumentError(format!("{e:?}")))?;
+
+ if self.header.is_sorted {
Review Comment:
Hmm, is this a new check? Seems exiting `VariantMetadata`'s `with_full_validation` doesn't have this check?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "scovich (via GitHub)" <gi...@apache.org>.
scovich commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2197654158
##########
parquet-variant/src/variant/metadata.rs:
##########
@@ -228,9 +225,48 @@ impl<'m> VariantMetadata<'m> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let offset_bytes = slice_from_slice(
+ self.bytes,
+ self.header.first_offset_byte()..self.first_value_byte,
+ )?;
+
+ let offsets =
+ map_bytes_to_offsets(offset_bytes, self.header.offset_size).collect::<Vec<_>>();
+
+ // Validate offsets are in-bounds and monotonically increasing.
+ // Since shallow validation ensures the first and last offsets are in bounds, we can also verify all offsets
+ // are in-bounds by checking if offsets are monotonically increasing.
+ let are_offsets_monotonic = offsets.is_sorted_by(|a, b| a < b);
+ if !are_offsets_monotonic {
+ return Err(ArrowError::InvalidArgumentError(
+ "offsets not monotonically increasing".to_string(),
+ ));
+ }
+
+ // Verify the string values in the dictionary are UTF-8 encoded strings.
+ let value_buffer = slice_from_slice(self.bytes, self.first_value_byte..)?;
+ let value_str = simdutf8::basic::from_utf8(value_buffer)
+ .map_err(|e| ArrowError::InvalidArgumentError(format!("{e:?}")))?;
+
+ if self.header.is_sorted {
+ // Validate the dictionary values are unique and lexicographically sorted
+ let are_dictionary_values_unique_and_sorted = (1..offsets.len())
+ .map(|i| {
+ let field_range = offsets[i - 1]..offsets[i];
+ value_str.get(field_range)
+ })
Review Comment:
nit:
```suggestion
.map(|i| value_str.get(offsets[i - 1]..offsets[i]))
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2198159710
##########
parquet-variant/src/variant/metadata.rs:
##########
@@ -228,9 +225,47 @@ impl<'m> VariantMetadata<'m> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let offset_bytes = slice_from_slice(
+ self.bytes,
+ self.header.first_offset_byte()..self.first_value_byte,
+ )?;
+
+ let offsets =
+ map_bytes_to_offsets(offset_bytes, self.header.offset_size).collect::<Vec<_>>();
+
+ // Validate offsets are in-bounds and monotonically increasing.
+ // Since shallow validation ensures the first and last offsets are in bounds, we can also verify all offsets
+ // are in-bounds by checking if offsets are monotonically increasing.
+ let are_offsets_monotonic = offsets.is_sorted_by(|a, b| a < b);
+ if !are_offsets_monotonic {
+ return Err(ArrowError::InvalidArgumentError(
+ "offsets not monotonically increasing".to_string(),
+ ));
+ }
+
+ // Verify the string values in the dictionary are UTF-8 encoded strings.
+ let value_buffer =
+ string_from_slice(self.bytes, 0, self.first_value_byte..self.bytes.len())?;
+
+ if self.header.is_sorted {
+ // Validate the dictionary values are unique and lexicographically sorted
+ let are_dictionary_values_unique_and_sorted = (1..offsets.len())
+ .map(|i| {
+ let field_range = offsets[i - 1]..offsets[i];
+ value_buffer.get(field_range)
+ })
+ .is_sorted_by(|a, b| match (a, b) {
+ (Some(a), Some(b)) => a < b,
Review Comment:
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?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#issuecomment-3060134025
Looks like there is one final CI check to fix and then I can merge this PR in https://github.com/apache/arrow-rs/actions/runs/16209770665/job/45767524794?pr=7878
I can't push to your PR directly because I don't have permissions in the pydantic fork
If you make PRs from your own fork in the future, I can make changes directly if you think that will help
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#issuecomment-3058441512
> > avoid materializing offsets + remove redundant checks
>
> Honestly, this one feels like a good fast-follow, rather than something that would block the merge? Unless it's super easy/fast to clean up. Perfection as enemy of good and all that. This PR is already a drastic improvement over the current validation. And as @viirya pointed out, this PR adds some validations that were just plain missing before.
>
> Also, as a separate PR we could hopefully even see benchmark results quantifying the impact of the change.
Sounds good. I'll get the benchmarks cleaned up and kick the rest over for another PR
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "scovich (via GitHub)" <gi...@apache.org>.
scovich commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2190880881
##########
parquet-variant/src/variant/list.rs:
##########
@@ -205,13 +204,62 @@ impl<'m, 'v> VariantList<'m, 'v> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
+ /*
+ (1) the associated variant metadata is [valid] (*)
+ (2) all other offsets are in-bounds (*)
+ (3) all offsets are monotonically increasing (*)
+ (4) all values are (recursively) valid variant objects (*)
+ */
+
+ // (1)
// Validate the metadata dictionary first, if not already validated, because we pass it
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ // (2), (4)
+ // if we check all values are valid by using offset lookups,
+ // we know all offsets are in bounds if correct
+
+ // note how we do this once!
+ let byte_range = self.header.first_offset_byte()..self.first_value_byte;
+ let offset_bytes = slice_from_slice(self.value, byte_range)?;
+
+ let offset_chunks = offset_bytes.chunks_exact(self.header.offset_size());
+ assert!(offset_chunks.remainder().is_empty()); // guaranteed by shallow validation
Review Comment:
We're in a method that returns `Result`... why not use it instead of having to worry whether shallow validation covered the corner case?
##########
parquet-variant/src/variant/list.rs:
##########
@@ -205,13 +204,62 @@ impl<'m, 'v> VariantList<'m, 'v> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
+ /*
+ (1) the associated variant metadata is [valid] (*)
+ (2) all other offsets are in-bounds (*)
+ (3) all offsets are monotonically increasing (*)
+ (4) all values are (recursively) valid variant objects (*)
+ */
+
+ // (1)
// Validate the metadata dictionary first, if not already validated, because we pass it
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ // (2), (4)
+ // if we check all values are valid by using offset lookups,
+ // we know all offsets are in bounds if correct
+
+ // note how we do this once!
+ let byte_range = self.header.first_offset_byte()..self.first_value_byte;
+ let offset_bytes = slice_from_slice(self.value, byte_range)?;
+
+ let offset_chunks = offset_bytes.chunks_exact(self.header.offset_size());
+ assert!(offset_chunks.remainder().is_empty()); // guaranteed by shallow validation
+
+ let offsets = offset_chunks
+ .map(|chunk| match self.header.offset_size {
+ OffsetSizeBytes::One => chunk[0] as usize,
+ OffsetSizeBytes::Two => u16::from_le_bytes([chunk[0], chunk[1]]) as usize,
+ OffsetSizeBytes::Three => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], 0]) as usize
+ }
+ OffsetSizeBytes::Four => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]) as usize
+ }
+ })
+ .collect::<Vec<_>>();
+
+ // (3)
+ let monotonic_offsets = offsets.is_sorted_by(|a, b| a < b);
+ if !monotonic_offsets {
+ return Err(ArrowError::InvalidArgumentError(
+ "offsets are not monotonically increasing".to_string(),
+ ));
+ }
+
+ // (4)
+
+ let value_buffer = &self.value[self.first_value_byte..];
+
+ for i in 0..offsets.len() - 1 {
+ let start_offset = offsets[i];
+ let end_offset = offsets[i + 1];
Review Comment:
consider doing:
```suggestion
for i in 1..offsets.len() {
let start_offset = offsets[i - 1];
let end_offset = offsets[i];
```
##########
parquet-variant/src/variant/list.rs:
##########
@@ -205,13 +204,62 @@ impl<'m, 'v> VariantList<'m, 'v> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
+ /*
+ (1) the associated variant metadata is [valid] (*)
+ (2) all other offsets are in-bounds (*)
+ (3) all offsets are monotonically increasing (*)
+ (4) all values are (recursively) valid variant objects (*)
+ */
+
+ // (1)
// Validate the metadata dictionary first, if not already validated, because we pass it
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ // (2), (4)
+ // if we check all values are valid by using offset lookups,
+ // we know all offsets are in bounds if correct
+
+ // note how we do this once!
+ let byte_range = self.header.first_offset_byte()..self.first_value_byte;
+ let offset_bytes = slice_from_slice(self.value, byte_range)?;
+
+ let offset_chunks = offset_bytes.chunks_exact(self.header.offset_size());
+ assert!(offset_chunks.remainder().is_empty()); // guaranteed by shallow validation
+
+ let offsets = offset_chunks
+ .map(|chunk| match self.header.offset_size {
+ OffsetSizeBytes::One => chunk[0] as usize,
+ OffsetSizeBytes::Two => u16::from_le_bytes([chunk[0], chunk[1]]) as usize,
+ OffsetSizeBytes::Three => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], 0]) as usize
+ }
+ OffsetSizeBytes::Four => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]) as usize
Review Comment:
Is this faster and/or simpler than try_into from slice to array?
##########
parquet-variant/src/variant/metadata.rs:
##########
@@ -230,7 +227,98 @@ impl<'m> VariantMetadata<'m> {
if !self.validated {
// Iterate over all string keys in this dictionary in order to prove that the offset
// array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+
+ /*
+ As scovich pointed out, here are the things full validation must do:
+
+ (1) all other offsets are in-bounds (*)
+ (2) all offsets are monotonically increasing (*)
+ (3) all values are valid utf-8 (*)
+
+ I propose we add another validation check
+ (4) if sorted dictionary, check if dictionary fields are sorted
+
+ Doing this check will help us in objects with sorted dictionaries,
+ since we can guarantee sortedness by checking if field ids are increasing.
+ */
+
+ // (1) (2)
+ // Since shallow validation already computes the first and last offset
+ // if we guarantee monotonicity for all offsets, then we know they are all in-bounds
+
+ // notice how we do this ceremony only once!
+ let offset_byte_range = self.header.first_offset_byte()..self.first_value_byte;
+ let offset_bytes = slice_from_slice(self.bytes, offset_byte_range)?;
+
+ let offsets = offset_bytes
+ .chunks_exact(self.header.offset_size())
+ .map(|chunk| {
+ // at this point, we know for a _fact_ that chunk will have `offset_size` bytes
+
+ match self.header.offset_size {
+ OffsetSizeBytes::One => chunk[0].into(),
+ OffsetSizeBytes::Two => u16::from_le_bytes([chunk[0], chunk[1]]).into(),
+ OffsetSizeBytes::Three => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], 0]) as usize
+ }
+ OffsetSizeBytes::Four => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]) as usize
+ }
+ }
+ })
+ .collect::<Vec<usize>>();
+
+ let offsets_monotonically_increasing = offsets.is_sorted_by(|a, b| a < b);
+
+ if !offsets_monotonically_increasing {
+ return Err(ArrowError::InvalidArgumentError(
+ "offsets not monotonically increasing".to_string(),
+ ));
+ }
+
+ // (3)
+ // We don't take advantage of the values being packed side by side.
+ // For every value, we rerequest the entire value buffer and then slice into _just_ that value
+ // and parse into a str
+
+ // This looks like a great place to do vectorized utf8 validation
+ // plus, all subsequent attempts at parsing out values as a &str can be done using
+ // String::from_utf8_unchecked
+
+ let value_bytes = slice_from_slice(self.bytes, self.first_value_byte..)?;
+ let value_str = simdutf8::basic::from_utf8(value_bytes)
+ .map_err(|e| ArrowError::InvalidArgumentError(format!("{e:?}")))?;
+
+ // (4)
+ // if the metadata header marked this variant as having a sorted dictionary,
+ // we must check whether the fields are actually sorted
+
+ if self.header.is_sorted {
+ let mut prev_field_name = None;
+ let mut is_sorted = true;
+
+ for i in 0..offsets.len() - 1 {
+ if !is_sorted {
+ return Err(ArrowError::InvalidArgumentError(
+ "variant marked as having sorted dictionary but is unsorted"
+ .to_string(),
+ ));
+ }
+
+ let offset_range = offsets[i]..offsets[i + 1];
+
+ let field_name = value_str
+ .get(offset_range)
+ .ok_or_else(|| overflow_error("overflowed"))?;
+
+ if let Some(prev_field_name) = prev_field_name {
+ is_sorted = is_sorted && prev_field_name < field_name;
+ }
Review Comment:
by deferring the check to the next iteration, we risk missing the case where the last pair breaks ordering? Combined with the above, a better control flow might be (again, in a helper function so we can use `?`):
```rust
let Some(prev_offset) = offset_chunks.next().transpose()? else {
return Ok(());
};
let field_names = offsets.scan(prev_offset, |prev_offset, offset| {
let offset = offset?;
if *prev_offset >= offset {
return Err(... offset not monotonic ...);
}
let offset_range = prev_offset..offset;
*prev_offset = offset;
value_str
.get(offset_range)
.ok_or_else(|| overflow_error("overflowed"))
};
let Some(mut prev_field_name) = field_names.next().transpose()? else {
return Ok(()); // empty dictionary, nothing to validate
};
for field_name in field_names {
let field_name = field_name?;
if self.header.is_sorted && prev_field_name >= field_name {
return Err(... not sorted or has a duplicate key ...);
}
prev_field_name = field_name;
}
```
##########
parquet-variant/src/variant/list.rs:
##########
@@ -205,13 +204,62 @@ impl<'m, 'v> VariantList<'m, 'v> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
+ /*
+ (1) the associated variant metadata is [valid] (*)
+ (2) all other offsets are in-bounds (*)
+ (3) all offsets are monotonically increasing (*)
+ (4) all values are (recursively) valid variant objects (*)
+ */
+
+ // (1)
// Validate the metadata dictionary first, if not already validated, because we pass it
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ // (2), (4)
+ // if we check all values are valid by using offset lookups,
+ // we know all offsets are in bounds if correct
+
+ // note how we do this once!
+ let byte_range = self.header.first_offset_byte()..self.first_value_byte;
+ let offset_bytes = slice_from_slice(self.value, byte_range)?;
+
+ let offset_chunks = offset_bytes.chunks_exact(self.header.offset_size());
+ assert!(offset_chunks.remainder().is_empty()); // guaranteed by shallow validation
+
+ let offsets = offset_chunks
+ .map(|chunk| match self.header.offset_size {
+ OffsetSizeBytes::One => chunk[0] as usize,
+ OffsetSizeBytes::Two => u16::from_le_bytes([chunk[0], chunk[1]]) as usize,
+ OffsetSizeBytes::Three => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], 0]) as usize
+ }
+ OffsetSizeBytes::Four => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]) as usize
+ }
+ })
+ .collect::<Vec<_>>();
+
+ // (3)
+ let monotonic_offsets = offsets.is_sorted_by(|a, b| a < b);
Review Comment:
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 `?`:
```rust
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(())
}
```
##########
parquet-variant/src/variant/list.rs:
##########
@@ -205,13 +204,62 @@ impl<'m, 'v> VariantList<'m, 'v> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
+ /*
+ (1) the associated variant metadata is [valid] (*)
+ (2) all other offsets are in-bounds (*)
+ (3) all offsets are monotonically increasing (*)
+ (4) all values are (recursively) valid variant objects (*)
+ */
+
+ // (1)
// Validate the metadata dictionary first, if not already validated, because we pass it
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ // (2), (4)
+ // if we check all values are valid by using offset lookups,
+ // we know all offsets are in bounds if correct
+
+ // note how we do this once!
+ let byte_range = self.header.first_offset_byte()..self.first_value_byte;
+ let offset_bytes = slice_from_slice(self.value, byte_range)?;
+
+ let offset_chunks = offset_bytes.chunks_exact(self.header.offset_size());
+ assert!(offset_chunks.remainder().is_empty()); // guaranteed by shallow validation
+
+ let offsets = offset_chunks
+ .map(|chunk| match self.header.offset_size {
+ OffsetSizeBytes::One => chunk[0] as usize,
+ OffsetSizeBytes::Two => u16::from_le_bytes([chunk[0], chunk[1]]) as usize,
+ OffsetSizeBytes::Three => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], 0]) as usize
+ }
+ OffsetSizeBytes::Four => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]) as usize
+ }
+ })
+ .collect::<Vec<_>>();
+
+ // (3)
+ let monotonic_offsets = offsets.is_sorted_by(|a, b| a < b);
Review Comment:
Why not [`Iterator::is_sorted_by`](https://doc.rust-lang.org/std/iter/trait.Iterator.html?search=_sorted#method.is_sorted_by)?
```rust
let offsets_monotonically_increasing = offset_chunks
.map(...)
.is_sorted_by(...);
```
(again below)
##########
parquet-variant/src/variant/list.rs:
##########
@@ -205,13 +204,62 @@ impl<'m, 'v> VariantList<'m, 'v> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
+ /*
+ (1) the associated variant metadata is [valid] (*)
+ (2) all other offsets are in-bounds (*)
+ (3) all offsets are monotonically increasing (*)
+ (4) all values are (recursively) valid variant objects (*)
+ */
+
+ // (1)
// Validate the metadata dictionary first, if not already validated, because we pass it
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ // (2), (4)
+ // if we check all values are valid by using offset lookups,
+ // we know all offsets are in bounds if correct
+
+ // note how we do this once!
+ let byte_range = self.header.first_offset_byte()..self.first_value_byte;
+ let offset_bytes = slice_from_slice(self.value, byte_range)?;
+
+ let offset_chunks = offset_bytes.chunks_exact(self.header.offset_size());
+ assert!(offset_chunks.remainder().is_empty()); // guaranteed by shallow validation
+
+ let offsets = offset_chunks
+ .map(|chunk| match self.header.offset_size {
+ OffsetSizeBytes::One => chunk[0] as usize,
+ OffsetSizeBytes::Two => u16::from_le_bytes([chunk[0], chunk[1]]) as usize,
+ OffsetSizeBytes::Three => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], 0]) as usize
+ }
+ OffsetSizeBytes::Four => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]) as usize
+ }
+ })
+ .collect::<Vec<_>>();
+
+ // (3)
+ let monotonic_offsets = offsets.is_sorted_by(|a, b| a < b);
+ if !monotonic_offsets {
+ return Err(ArrowError::InvalidArgumentError(
+ "offsets are not monotonically increasing".to_string(),
+ ));
+ }
+
+ // (4)
+
+ let value_buffer = &self.value[self.first_value_byte..];
Review Comment:
again, why risk panic?
```suggestion
let value_buffer = slice_from_slice(self.value, self.first_value_byte..)?;
```
##########
parquet-variant/src/variant/metadata.rs:
##########
@@ -230,7 +227,98 @@ impl<'m> VariantMetadata<'m> {
if !self.validated {
// Iterate over all string keys in this dictionary in order to prove that the offset
// array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+
+ /*
+ As scovich pointed out, here are the things full validation must do:
+
+ (1) all other offsets are in-bounds (*)
+ (2) all offsets are monotonically increasing (*)
+ (3) all values are valid utf-8 (*)
+
+ I propose we add another validation check
+ (4) if sorted dictionary, check if dictionary fields are sorted
Review Comment:
👍
##########
parquet-variant/src/variant/metadata.rs:
##########
@@ -230,7 +227,98 @@ impl<'m> VariantMetadata<'m> {
if !self.validated {
// Iterate over all string keys in this dictionary in order to prove that the offset
// array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+
+ /*
+ As scovich pointed out, here are the things full validation must do:
Review Comment:
aside: flattering, but prob not super helpful to reference random github handles in the code?
##########
parquet-variant/src/variant/list.rs:
##########
@@ -205,13 +204,62 @@ impl<'m, 'v> VariantList<'m, 'v> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
+ /*
+ (1) the associated variant metadata is [valid] (*)
+ (2) all other offsets are in-bounds (*)
+ (3) all offsets are monotonically increasing (*)
+ (4) all values are (recursively) valid variant objects (*)
+ */
+
+ // (1)
// Validate the metadata dictionary first, if not already validated, because we pass it
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ // (2), (4)
+ // if we check all values are valid by using offset lookups,
+ // we know all offsets are in bounds if correct
+
+ // note how we do this once!
+ let byte_range = self.header.first_offset_byte()..self.first_value_byte;
+ let offset_bytes = slice_from_slice(self.value, byte_range)?;
+
+ let offset_chunks = offset_bytes.chunks_exact(self.header.offset_size());
+ assert!(offset_chunks.remainder().is_empty()); // guaranteed by shallow validation
+
+ let offsets = offset_chunks
+ .map(|chunk| match self.header.offset_size {
+ OffsetSizeBytes::One => chunk[0] as usize,
+ OffsetSizeBytes::Two => u16::from_le_bytes([chunk[0], chunk[1]]) as usize,
+ OffsetSizeBytes::Three => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], 0]) as usize
+ }
+ OffsetSizeBytes::Four => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]) as usize
+ }
+ })
+ .collect::<Vec<_>>();
+
+ // (3)
+ let monotonic_offsets = offsets.is_sorted_by(|a, b| a < b);
+ if !monotonic_offsets {
+ return Err(ArrowError::InvalidArgumentError(
+ "offsets are not monotonically increasing".to_string(),
+ ));
+ }
+
+ // (4)
+
+ let value_buffer = &self.value[self.first_value_byte..];
+
+ for i in 0..offsets.len() - 1 {
+ let start_offset = offsets[i];
+ let end_offset = offsets[i + 1];
+
+ let value_bytes = slice_from_slice(value_buffer, start_offset..end_offset)?;
+ Variant::try_new_with_metadata(self.metadata, value_bytes)?;
Review Comment:
At some point, copying that fat metadata over and over will be a meaningful contributor to the total cost.
Are we _sure_ it's ~free?
If not sure, should we somehow allow creating variant instances with metadata references, at least internally for validation purposes?
##########
parquet-variant/src/variant/object.rs:
##########
@@ -206,13 +205,118 @@ impl<'m, 'v> VariantObject<'m, 'v> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
+ /*
+ (1) the associated variant metadata is [valid] (*)
+ (2) all field ids are valid metadata dictionary entries (*)
+ (3) field ids are lexically ordered according by their corresponding string values (*)
+ (4) all field offsets are in bounds (*)
+ (5) all field values are (recursively) _valid_ variant values (*)
+
+ */
+
+ // (1)
// Validate the metadata dictionary first, if not already validated, because we pass it
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ // (2)
+ // Field ids serve as indexes into the metadata buffer.
+ // As long as we guarantee the largest field id is < dictionary size,
+ // we can guarantee all field ids are valid metadata dictionaries
+
+ // (2), (3)
+ let byte_range = self.header.field_ids_start_byte()..self.first_field_offset_byte;
+ let field_id_bytes = slice_from_slice(self.value, byte_range)?;
+ // let field_id = self.header.field_id_size.unpack_usize(field_id_bytes, i)?;
+
+ let field_id_chunks = field_id_bytes.chunks_exact(self.header.field_id_size());
+ assert!(field_id_chunks.remainder().is_empty()); // guaranteed to be none
+
+ let field_ids = field_id_chunks
+ .map(|chunk| match self.header.field_id_size {
+ OffsetSizeBytes::One => chunk[0] as usize,
+ OffsetSizeBytes::Two => u16::from_le_bytes([chunk[0], chunk[1]]) as usize,
+ OffsetSizeBytes::Three => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], 0]) as usize
+ }
+ OffsetSizeBytes::Four => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]) as usize
+ }
+ })
+ .collect::<Vec<_>>();
Review Comment:
As above, I expect it will be straightforward to avoid materializing these iterators
(again below)
##########
parquet-variant/src/variant/metadata.rs:
##########
@@ -230,7 +227,98 @@ impl<'m> VariantMetadata<'m> {
if !self.validated {
// Iterate over all string keys in this dictionary in order to prove that the offset
// array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+
+ /*
+ As scovich pointed out, here are the things full validation must do:
+
+ (1) all other offsets are in-bounds (*)
+ (2) all offsets are monotonically increasing (*)
+ (3) all values are valid utf-8 (*)
+
+ I propose we add another validation check
+ (4) if sorted dictionary, check if dictionary fields are sorted
+
+ Doing this check will help us in objects with sorted dictionaries,
+ since we can guarantee sortedness by checking if field ids are increasing.
+ */
+
+ // (1) (2)
+ // Since shallow validation already computes the first and last offset
+ // if we guarantee monotonicity for all offsets, then we know they are all in-bounds
+
+ // notice how we do this ceremony only once!
+ let offset_byte_range = self.header.first_offset_byte()..self.first_value_byte;
+ let offset_bytes = slice_from_slice(self.bytes, offset_byte_range)?;
+
+ let offsets = offset_bytes
+ .chunks_exact(self.header.offset_size())
+ .map(|chunk| {
+ // at this point, we know for a _fact_ that chunk will have `offset_size` bytes
+
+ match self.header.offset_size {
+ OffsetSizeBytes::One => chunk[0].into(),
+ OffsetSizeBytes::Two => u16::from_le_bytes([chunk[0], chunk[1]]).into(),
+ OffsetSizeBytes::Three => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], 0]) as usize
+ }
+ OffsetSizeBytes::Four => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]) as usize
+ }
+ }
+ })
+ .collect::<Vec<usize>>();
+
+ let offsets_monotonically_increasing = offsets.is_sorted_by(|a, b| a < b);
Review Comment:
As above, no need to materialize the iterator if we combine the checks into a single loop?
(but also see comment below)
##########
parquet-variant/src/variant/metadata.rs:
##########
@@ -230,7 +227,98 @@ impl<'m> VariantMetadata<'m> {
if !self.validated {
// Iterate over all string keys in this dictionary in order to prove that the offset
// array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+
+ /*
+ As scovich pointed out, here are the things full validation must do:
+
+ (1) all other offsets are in-bounds (*)
+ (2) all offsets are monotonically increasing (*)
+ (3) all values are valid utf-8 (*)
+
+ I propose we add another validation check
+ (4) if sorted dictionary, check if dictionary fields are sorted
+
+ Doing this check will help us in objects with sorted dictionaries,
+ since we can guarantee sortedness by checking if field ids are increasing.
+ */
+
+ // (1) (2)
+ // Since shallow validation already computes the first and last offset
+ // if we guarantee monotonicity for all offsets, then we know they are all in-bounds
+
+ // notice how we do this ceremony only once!
+ let offset_byte_range = self.header.first_offset_byte()..self.first_value_byte;
+ let offset_bytes = slice_from_slice(self.bytes, offset_byte_range)?;
+
+ let offsets = offset_bytes
+ .chunks_exact(self.header.offset_size())
+ .map(|chunk| {
+ // at this point, we know for a _fact_ that chunk will have `offset_size` bytes
+
+ match self.header.offset_size {
+ OffsetSizeBytes::One => chunk[0].into(),
+ OffsetSizeBytes::Two => u16::from_le_bytes([chunk[0], chunk[1]]).into(),
+ OffsetSizeBytes::Three => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], 0]) as usize
+ }
+ OffsetSizeBytes::Four => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]) as usize
+ }
+ }
+ })
+ .collect::<Vec<usize>>();
+
+ let offsets_monotonically_increasing = offsets.is_sorted_by(|a, b| a < b);
+
+ if !offsets_monotonically_increasing {
+ return Err(ArrowError::InvalidArgumentError(
+ "offsets not monotonically increasing".to_string(),
+ ));
+ }
+
+ // (3)
+ // We don't take advantage of the values being packed side by side.
+ // For every value, we rerequest the entire value buffer and then slice into _just_ that value
+ // and parse into a str
+
+ // This looks like a great place to do vectorized utf8 validation
+ // plus, all subsequent attempts at parsing out values as a &str can be done using
+ // String::from_utf8_unchecked
+
+ let value_bytes = slice_from_slice(self.bytes, self.first_value_byte..)?;
+ let value_str = simdutf8::basic::from_utf8(value_bytes)
+ .map_err(|e| ArrowError::InvalidArgumentError(format!("{e:?}")))?;
+
+ // (4)
+ // if the metadata header marked this variant as having a sorted dictionary,
+ // we must check whether the fields are actually sorted
+
+ if self.header.is_sorted {
+ let mut prev_field_name = None;
+ let mut is_sorted = true;
+
+ for i in 0..offsets.len() - 1 {
Review Comment:
as above, `1..offsets.len()` and adjust indexing below?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2190999047
##########
parquet-variant/src/variant/metadata.rs:
##########
@@ -230,7 +227,98 @@ impl<'m> VariantMetadata<'m> {
if !self.validated {
// Iterate over all string keys in this dictionary in order to prove that the offset
// array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+
+ /*
+ As scovich pointed out, here are the things full validation must do:
Review Comment:
Haha, yes. Fwiw, these comments are strictly for reviewers. This first pass was to ensure the proposed change was directionally sound
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "scovich (via GitHub)" <gi...@apache.org>.
scovich commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2192432185
##########
parquet-variant/src/variant/list.rs:
##########
@@ -205,13 +204,62 @@ impl<'m, 'v> VariantList<'m, 'v> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
+ /*
+ (1) the associated variant metadata is [valid] (*)
+ (2) all other offsets are in-bounds (*)
+ (3) all offsets are monotonically increasing (*)
+ (4) all values are (recursively) valid variant objects (*)
+ */
+
+ // (1)
// Validate the metadata dictionary first, if not already validated, because we pass it
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ // (2), (4)
+ // if we check all values are valid by using offset lookups,
+ // we know all offsets are in bounds if correct
+
+ // note how we do this once!
+ let byte_range = self.header.first_offset_byte()..self.first_value_byte;
+ let offset_bytes = slice_from_slice(self.value, byte_range)?;
+
+ let offset_chunks = offset_bytes.chunks_exact(self.header.offset_size());
+ assert!(offset_chunks.remainder().is_empty()); // guaranteed by shallow validation
+
+ let offsets = offset_chunks
+ .map(|chunk| match self.header.offset_size {
+ OffsetSizeBytes::One => chunk[0] as usize,
+ OffsetSizeBytes::Two => u16::from_le_bytes([chunk[0], chunk[1]]) as usize,
+ OffsetSizeBytes::Three => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], 0]) as usize
+ }
+ OffsetSizeBytes::Four => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]) as usize
+ }
+ })
+ .collect::<Vec<_>>();
+
+ // (3)
+ let monotonic_offsets = offsets.is_sorted_by(|a, b| a < b);
+ if !monotonic_offsets {
+ return Err(ArrowError::InvalidArgumentError(
+ "offsets are not monotonically increasing".to_string(),
+ ));
+ }
+
+ // (4)
+
+ let value_buffer = &self.value[self.first_value_byte..];
+
+ for i in 0..offsets.len() - 1 {
+ let start_offset = offsets[i];
+ let end_offset = offsets[i + 1];
+
+ let value_bytes = slice_from_slice(value_buffer, start_offset..end_offset)?;
+ Variant::try_new_with_metadata(self.metadata, value_bytes)?;
Review Comment:
I _think_ we wouldn't repeatedly validate the metadata, because invoking its `with_full_validation` method annotates the object accordingly, and the list/object `with_full_validation` validates the metadata first.
I was more referring to the repeated copying of 80-ish bytes that comprise the `VariantMetadata` struct, see e.g.
* https://github.com/apache/arrow-rs/issues/7831
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#issuecomment-3058305633
> I have sort of lost track of the current state of this PR. Is it something we want to merge and then do follow ons? If so, can we file some tickets to track those follow ons? Or do we want to keep working on this PR?
>
> I would like to improve the benchmarks to more cleanly separate the validation benchmarks from JSON parsing benchmarks.
Hi, I would like to spend a bit more time on this. @scovich raised some good points about redundant checks which will remove the need to collect offsets.
Here is my checklist for this PR:
- [ ] avoid materializing offsets + remove redundant checks
- [ ] better documentation
- [ ] fix the validation benchmark and move them back to `parquet-variant`
- [ ] make the offset validation DRY by moving it to a freestanding method
The `simdutf8` stuff can be incorporated as a follow up PR.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#issuecomment-3060156882
> For example, the latest CI run displays errors like:
>
> > Documenting arrow-ord v55.2.0 (/__w/arrow-rs/arrow-rs/arrow-ord)
> > error: unnecessary parentheses around closure body
> > --> arrow-ord/src/cmp.rs:276:43
> > |
> > 276 | let c = |((l, r), n)| ((l ^ r) | (l & r & n));
> > | ^ ^
> > |
> > = note: `-D unused-parens` implied by `-D warnings`
> > = help: to override `-D warnings` add `#[allow(unused_parens)]`
> > help: remove these parentheses
> > |
> > 276 - let c = |((l, r), n)| ((l ^ r) | (l & r & n));
> > 276 + let c = |((l, r), n)| (l ^ r) | (l & r & n);
> > |
>
> error: could not document `arrow-ord`
Looks to me like the latest nightly rust got more strict and for some reason we build docs with nightly in this crate
So to reproduce locally I bet you can do
```shell
rustup toolchain install nightly
cargo +nightly doc --document-private-items --no-deps --workspace --all-features
```
So in other words it is not related to your PR and CI would likely fail on main if we re-ran it
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#issuecomment-3061858253
Thanks again. @friendlymatthew can you make sure any follow on tasks we identified are properly tracked with tickets?
Thank you again@
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "friendlymatthew (via GitHub)" <gi...@apache.org>.
friendlymatthew commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2196412403
##########
parquet-variant/src/variant/object.rs:
##########
@@ -206,13 +205,118 @@ impl<'m, 'v> VariantObject<'m, 'v> {
/// [validation]: Self#Validation
pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
if !self.validated {
+ /*
+ (1) the associated variant metadata is [valid] (*)
+ (2) all field ids are valid metadata dictionary entries (*)
+ (3) field ids are lexically ordered according by their corresponding string values (*)
+ (4) all field offsets are in bounds (*)
+ (5) all field values are (recursively) _valid_ variant values (*)
+
+ */
+
+ // (1)
// Validate the metadata dictionary first, if not already validated, because we pass it
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ // (2)
+ // Field ids serve as indexes into the metadata buffer.
+ // As long as we guarantee the largest field id is < dictionary size,
+ // we can guarantee all field ids are valid metadata dictionaries
+
+ // (2), (3)
+ let byte_range = self.header.field_ids_start_byte()..self.first_field_offset_byte;
+ let field_id_bytes = slice_from_slice(self.value, byte_range)?;
+ // let field_id = self.header.field_id_size.unpack_usize(field_id_bytes, i)?;
+
+ let field_id_chunks = field_id_bytes.chunks_exact(self.header.field_id_size());
+ assert!(field_id_chunks.remainder().is_empty()); // guaranteed to be none
+
+ let field_ids = field_id_chunks
+ .map(|chunk| match self.header.field_id_size {
+ OffsetSizeBytes::One => chunk[0] as usize,
+ OffsetSizeBytes::Two => u16::from_le_bytes([chunk[0], chunk[1]]) as usize,
+ OffsetSizeBytes::Three => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], 0]) as usize
+ }
+ OffsetSizeBytes::Four => {
+ u32::from_le_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]) as usize
+ }
+ })
+ .collect::<Vec<_>>();
Review Comment:
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
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Variant] Speedup validation [arrow-rs]
Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on code in PR #7878:
URL: https://github.com/apache/arrow-rs/pull/7878#discussion_r2198178016
##########
parquet-variant/src/variant/object.rs:
##########
@@ -210,9 +209,80 @@ impl<'m, 'v> VariantObject<'m, 'v> {
// by value to all the children (who would otherwise re-validate it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
- // Iterate over all string keys in this dictionary in order to prove that the offset
- // array is valid, all offsets are in bounds, and all string bytes are valid utf-8.
- validate_fallible_iterator(self.iter_try())?;
+ let field_id_buffer = slice_from_slice(
+ self.value,
+ self.header.field_ids_start_byte()..self.first_field_offset_byte,
+ )?;
+
+ let field_ids = map_bytes_to_offsets(field_id_buffer, self.header.field_id_size)
+ .collect::<Vec<_>>();
+
+ // Validate all field ids exist in the metadata dictionary and the corresponding field names are lexicographically sorted
+ if self.metadata.is_sorted() {
+ // Since the metadata dictionary has unique and sorted field names, we can also guarantee this object's field names
+ // are lexicographically sorted by their field id ordering
+ if !field_ids.is_sorted() {
+ return Err(ArrowError::InvalidArgumentError(
+ "field names not sorted".to_string(),
+ ));
+ }
+
+ // Since field ids are sorted, if the last field is smaller than the dictionary size,
+ // we also know all field ids are smaller than the dictionary size and in-bounds.
+ if let Some(&last_field_id) = field_ids.last() {
Review Comment:
One question, is field id started from 0 and all field ids are continuous?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org