You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "XiangpengHao (via GitHub)" <gi...@apache.org> on 2024/07/04 21:27:15 UTC
[PR] Deduplication strings/binarys when building view types [arrow-rs]
XiangpengHao opened a new pull request, #6005:
URL: https://github.com/apache/arrow-rs/pull/6005
# Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123.
-->
Closes #5910.
# Rationale for this change
As discussed in #5910, when the array of strings have low number of unique values, it makes sense to deduplicate them while building it, especially when invoking `gc`
This pr implements an optional mechanism to deduplicate the strings. This is turned off by default, as it may slow down building array if the array is mostly unique.
However, the `gc` will by default enable it, so that gc generates an optimal layout.
<!--
Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes.
-->
# What changes are included in this PR?
<!--
There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR.
-->
# Are there any user-facing changes?
<!--
If there are user-facing changes then we may require documentation to be updated before approving the PR.
-->
<!---
If there are any breaking changes to public APIs, please add the `breaking change` label.
-->
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Deduplicate strings/binarys when building view types [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb merged PR #6005:
URL: https://github.com/apache/arrow-rs/pull/6005
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Deduplicate strings/binarys when building view types [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #6005:
URL: https://github.com/apache/arrow-rs/pull/6005#discussion_r1667363866
##########
arrow-array/src/builder/generic_bytes_view_builder.rs:
##########
@@ -199,6 +235,36 @@ impl<T: ByteViewType + ?Sized> GenericByteViewBuilder<T> {
return;
}
+ // if string is long, we can optionally check duplication.
Review Comment:
This comment seems incorrect -- this code checks deduplication if there is string tracking enabled, not if the string is long
##########
arrow-array/src/builder/generic_bytes_view_builder.rs:
##########
@@ -57,6 +58,7 @@ pub struct GenericByteViewBuilder<T: ByteViewType + ?Sized> {
completed: Vec<Buffer>,
in_progress: Vec<u8>,
block_size: u32,
+ string_tracker: Option<(HashTable<usize>, ahash::RandomState)>, // map <string hash> -> <index to the views>
Review Comment:
```suggestion
/// Some if deduplicating strings
/// map `<string hash> -> <index to the views>`
string_tracker: Option<(HashTable<usize>, ahash::RandomState)>
```
##########
arrow-array/src/builder/generic_bytes_view_builder.rs:
##########
@@ -83,6 +86,19 @@ impl<T: ByteViewType + ?Sized> GenericByteViewBuilder<T> {
Self { block_size, ..self }
}
+ /// Deduplicate strings while building the array
Review Comment:
Calling this `with_dedupliate_strings()` rather than `deduplicate_strings` might make it more obvious it is a builder style API, but that is just a preference
I think putting a space between the description will make the docs render nicely (the first sentence / line is used for the summary display)
💯 for explaining the tradeoff when using this option.
```suggestion
/// Deduplicate strings while building the array
///
```
##########
arrow-array/src/builder/generic_bytes_view_builder.rs:
##########
@@ -199,6 +235,36 @@ impl<T: ByteViewType + ?Sized> GenericByteViewBuilder<T> {
return;
}
+ // if string is long, we can optionally check duplication.
+ let hash_val = match &self.string_tracker {
+ Some((ht, hasher)) => {
+ let hash_val = hasher.hash_one(v);
+
+ // we can not use ht.entry here because we are under immutable borrow.
+ let find = ht.find(hash_val, |idx| {
+ let stored_value = self.get_value(*idx);
+ v == stored_value
+ });
+
+ // If the string already exists, we will directly use the view
+ if let Some(idx) = find {
+ self.views_builder
+ .append(self.views_builder.as_slice()[*idx]);
+ self.null_buffer_builder.append_non_null();
+ return;
+ }
+ // return the hash value to be reused later.
+ Some(hash_val)
+ }
+ None => None,
+ };
+ let view_idx = self.views_builder.len();
+ if let Some(hash_val) = hash_val {
Review Comment:
you might be abkle to avoid the unwrap by duplicating the `view_idx = self.views_builder.len()` in the if ... above. I think this way is fine too I just wanted to point it out
##########
arrow-array/src/builder/generic_bytes_view_builder.rs:
##########
@@ -199,6 +235,36 @@ impl<T: ByteViewType + ?Sized> GenericByteViewBuilder<T> {
return;
}
+ // if string is long, we can optionally check duplication.
+ let hash_val = match &self.string_tracker {
+ Some((ht, hasher)) => {
+ let hash_val = hasher.hash_one(v);
+
+ // we can not use ht.entry here because we are under immutable borrow.
Review Comment:
One pattern that can be used to use `ht.entry` if you want is something like
```rust
if let Some(ht) = self.string_tracker.take() {
...
// put the hash table back
self.string_tracker = Some(ht)
}
```
##########
arrow-array/src/builder/generic_bytes_view_builder.rs:
##########
@@ -357,6 +423,40 @@ mod tests {
use super::*;
use crate::Array;
+ #[test]
+ fn test_string_view_deduplicate() {
+ let mut builder = StringViewBuilder::new().deduplicate_strings();
+
+ let duplicated_value = "long string to test string view";
+ builder.append_value(duplicated_value);
+ builder.append_value("short");
+ builder.append_value(duplicated_value);
+ builder.append_null();
+ builder.append_value(duplicated_value);
+
+ let array = builder.finish_cloned();
+ array.to_data().validate_full().unwrap();
+ assert_eq!(array.data_buffers().len(), 1);
Review Comment:
I think this test would pass even if the deduplicate strings was not enabled
Perhaps you could add an assert that `array.data_buffers()[0].len() == duplicated_value.len()` only 🤔
##########
arrow-array/src/builder/generic_bytes_view_builder.rs:
##########
@@ -357,6 +423,40 @@ mod tests {
use super::*;
use crate::Array;
+ #[test]
+ fn test_string_view_deduplicate() {
Review Comment:
Can you please also add coverage when the duplicated string is in finished buffer (aka a buffer other than the current one)?
Maybe that can be done by setting capacity to `duplicated_value.len() *2` or something
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Deduplicate strings/binarys when building view types [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #6005:
URL: https://github.com/apache/arrow-rs/pull/6005#discussion_r1667671328
##########
arrow-array/src/builder/generic_bytes_view_builder.rs:
##########
@@ -357,6 +431,42 @@ mod tests {
use super::*;
use crate::Array;
+ #[test]
+ fn test_string_view_deduplicate() {
+ let value_1 = "long string to test string view";
+ let value_2 = "not so similar string but long";
+
+ let mut builder = StringViewBuilder::new()
+ .with_deduplicate_strings()
+ .with_block_size(value_1.len() as u32 * 2); // so that we will have multiple buffers
Review Comment:
💯
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org