Re: [PR] [Variant] Speedup validation [arrow-rs]
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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::>();
+
+// 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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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::>();
+
+// 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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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::>();
+
+// 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::, _>>()?
+.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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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::>();
+
+// 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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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::>();
+
+// 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::, _>>()?
+.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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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::>();
+
+// 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::, _>>()?
+.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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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::>();
+
+// 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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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::>();
+
+// 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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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 {
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::>();
+
+// 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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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 {
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::>();
+
+// 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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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::>();
+
+// 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::>();
+
+// 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::, _>>()?
+.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 {
+
Re: [PR] [Variant] Speedup validation [arrow-rs]
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, Vec) {
+// 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 = (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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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, Vec) {
+// 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 = (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
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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 {
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::>();
+
+// 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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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 {
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::>();
+
+// 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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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 {
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::>();
+
+// 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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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 {
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::>();
+
+// 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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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 {
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::>();
+
+// 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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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 {
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::>();
+
+// 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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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 {
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::>();
+
+// 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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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, Vec) {
+// 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 = (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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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 {
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::>();
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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, Vec) {
+// 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 = (0..=255).map(|n| format!("{n:03}")).collect();
+let innermost_list: String = format!(
+"[{}]",
+(0..=127)
+.map(|n| format!("{n}"))
+.collect::>()
+.join(",")
+);
+let inner_keys: Vec = (240..=495).map(|n|
format!("{n}")).collect();
+let inner_object = format!(
+"{{{}:{}}}",
+inner_keys
+.iter()
+.map(|k| format!("\"{k}\""))
+.collect::>()
+.join(format!(":{innermost_list},").as_str()),
+innermost_list
+);
+let json = format!(
+"{{{}:{}}}",
+keys.iter()
+.map(|k| format!("\"{k}\""))
+.collect::>()
+.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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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, Vec) {
+// 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 = (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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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, Vec) {
+// 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 = (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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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, Vec) {
+// 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 = (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"
Re: [PR] [Variant] Speedup validation [arrow-rs]
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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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 {
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::>();
+
+// (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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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 {
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::>();
+
+// (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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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 {
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::>();
+
+// (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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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 {
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::>();
+
+// (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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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 {
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::>();
+
+// (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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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 {
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::>();
+
+// (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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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 {
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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 {
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 {
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::>();
+
+// (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
Re: [PR] [Variant] Speedup validation [arrow-rs]
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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
Re: [PR] [Variant] Speedup validation [arrow-rs]
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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
[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: 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
