Rich-T-kid commented on code in PR #10927:
URL: https://github.com/apache/arrow-rs/pull/10927#discussion_r3896072766
##########
arrow-select/src/concat.rs:
##########
@@ -1708,6 +1708,124 @@ mod tests {
assert_eq!(array.logical_null_count(), 10);
}
+ #[test]
+ fn concat_string_view_dictionary_merges_duplicate_values() {
+ // Two independently-built `Dictionary<UInt8, Utf8View>` arrays
holding the
+ // same 200 distinct values. Naively concatenating their dictionaries
yields
+ // 400 entries, which overflows the u8 key range, but the distinct
values do
+ // fit -- so the values must be merged and deduplicated instead. This
mirrors
+ // a `Dictionary<UInt16, Utf8View>` column read in several partitions,
each
+ // building its own dictionary, and then combined.
Review Comment:
nit: we should trim this. we dont need the
>This mirrors a `Dictionary<UInt16, Utf8View>` column read in several
partitions, each building its own dictionary, and then combined.
##########
arrow-select/src/concat.rs:
##########
@@ -1708,6 +1708,124 @@ mod tests {
assert_eq!(array.logical_null_count(), 10);
}
+ #[test]
+ fn concat_string_view_dictionary_merges_duplicate_values() {
+ // Two independently-built `Dictionary<UInt8, Utf8View>` arrays
holding the
+ // same 200 distinct values. Naively concatenating their dictionaries
yields
+ // 400 entries, which overflows the u8 key range, but the distinct
values do
+ // fit -- so the values must be merged and deduplicated instead. This
mirrors
+ // a `Dictionary<UInt16, Utf8View>` column read in several partitions,
each
+ // building its own dictionary, and then combined.
+ let dict = |offset: usize| {
+ let values: StringViewArray = (0..200).map(|i|
Some(format!("v{i}"))).collect();
+ let keys = UInt8Array::from_iter_values((0..200).map(|i| (i +
offset) as u8 % 200));
+ DictionaryArray::<UInt8Type>::new(keys, Arc::new(values))
+ };
+ let (a, b) = (dict(0), dict(7));
+
+ let combined = concat(&[&a, &b]).unwrap();
+ let combined = combined.as_dictionary::<UInt8Type>();
+
+ assert_eq!(combined.len(), 400);
+ assert_eq!(combined.values().data_type(), &DataType::Utf8View);
+ assert!(combined.values().len() < 400);
+
+ let values = combined.values().as_string_view();
+ let actual: Vec<_> = combined
+ .keys()
+ .values()
+ .iter()
+ .map(|k| values.value(*k as usize))
+ .collect();
+ let expected: Vec<_> = [&a, &b]
+ .iter()
+ .flat_map(|d| {
+ let v = d.values().as_string_view();
+ d.keys()
+ .values()
+ .iter()
+ .map(|k| v.value(*k as usize))
+ .collect::<Vec<_>>()
+ })
+ .collect();
+ assert_eq!(actual, expected);
+ }
+
+ #[test]
+ fn concat_binary_view_dictionary_merges_duplicate_values() {
+ // Same as `concat_string_view_dictionary_merges_duplicate_values`,
for the
+ // other view-typed dictionary value layout.
+ let dict = || {
+ let values: BinaryViewArray = (0..200u32)
+ .map(|i| Some(i.to_le_bytes().to_vec()))
+ .collect();
+ let keys = UInt8Array::from_iter_values(0..200);
+ DictionaryArray::<UInt8Type>::new(keys, Arc::new(values))
+ };
+
+ let combined = concat(&[&dict(), &dict()]).unwrap();
+ let combined = combined.as_dictionary::<UInt8Type>();
+
+ assert_eq!(combined.len(), 400);
+ assert_eq!(combined.values().data_type(), &DataType::BinaryView);
+ assert!(combined.values().len() < 400);
+
+ let values = combined.values().as_binary_view();
+ let actual: Vec<_> = combined
+ .keys()
+ .values()
+ .iter()
+ .map(|k| values.value(*k as usize))
+ .collect();
+ let expected: Vec<_> = (0..2)
+ .flat_map(|_| (0..200u32).map(|i| i.to_le_bytes().to_vec()))
+ .collect();
+ assert_eq!(actual, expected);
+ }
+
+ #[test]
+ fn concat_dictionary_merges_values_of_many_arrays() {
+ // Four dictionaries over the same 200 distinct values. Concatenating
+ // their values would need 800 keys, well past the u8 key range, so
this
+ // only succeeds if the merge deduplicates them.
+ let dicts: Vec<_> = (0..4)
+ .map(|d| {
+ let values: StringArray = (0..200).map(|i|
Some(format!("v{i}"))).collect();
+ let keys = UInt8Array::from_iter_values((0..200).map(|i| (i +
d * 17) as u8 % 200));
+ DictionaryArray::<UInt8Type>::new(keys, Arc::new(values))
+ })
+ .collect();
+ let refs: Vec<&dyn Array> = dicts.iter().map(|d| d as &dyn
Array).collect();
+
+ let combined = concat(&refs).unwrap();
+ let combined = combined.as_dictionary::<UInt8Type>();
+
+ assert_eq!(combined.len(), 800);
+ // Every key is addressable; how far below 200 the merge gets depends
on
+ // whether the best-effort interner sufficed or the exact retry ran
+ assert!(u8::try_from(combined.values().len()).is_ok());
Review Comment:
Im confused, this always de-dupe the values right? is it possible for only
some of the values to be deduplicated? if not
```suggestion
// Every key is addressable; how far below 200 the merge gets
depends on
// whether the best-effort interner sufficed or the exact retry ran
assert!(u8::try_from(combined.values().len()).is_ok());
assert_eq!(total_values_len,200)
```
##########
arrow-select/src/dictionary.rs:
##########
@@ -380,6 +464,58 @@ mod tests {
use arrow_buffer::{BooleanBuffer, Buffer, NullBuffer, OffsetBuffer};
use std::sync::Arc;
+ use arrow_array::types::UInt16Type;
+ use arrow_array::{StringViewArray, UInt16Array};
+
+ #[test]
+ #[cfg_attr(miri, ignore)] // Takes too long
+ fn merge_string_view_dictionaries_deduplicates_exactly() {
+ // Four dictionaries over the same values: 60000 distinct strings, an
+ // empty string and a null. Concatenating them would need 240008 keys,
+ // far past the UInt16 range, while the distinct values leave room to
+ // spare -- so the merge has to deduplicate them exactly. At this
+ // cardinality the best-effort interner alone leaves thousands of
+ // duplicates behind and overflows, which forces the exact retry.
+ const DISTINCT: usize = 60000;
Review Comment:
I think we can make this test smaller by using u8 key type and having far
less distinct values. The same things are being tested but this way this test
requires less compute and we dont need to skip the miri check
##########
arrow-select/src/dictionary.rs:
##########
@@ -140,6 +142,10 @@ impl<'a, V> Interner<'a, V> {
}
}
+/// For each referenced value of a dictionary, its index within that
dictionary's
+/// values and its bytes (`None` for a null value)
+type MaskedValues<'a> = Vec<(usize, Option<&'a [u8]>)>;
Review Comment:
nice, this is very neat and makes the code easier to follow
##########
arrow-select/src/concat.rs:
##########
@@ -1708,6 +1708,124 @@ mod tests {
assert_eq!(array.logical_null_count(), 10);
}
+ #[test]
+ fn concat_string_view_dictionary_merges_duplicate_values() {
+ // Two independently-built `Dictionary<UInt8, Utf8View>` arrays
holding the
+ // same 200 distinct values. Naively concatenating their dictionaries
yields
+ // 400 entries, which overflows the u8 key range, but the distinct
values do
+ // fit -- so the values must be merged and deduplicated instead. This
mirrors
+ // a `Dictionary<UInt16, Utf8View>` column read in several partitions,
each
+ // building its own dictionary, and then combined.
+ let dict = |offset: usize| {
+ let values: StringViewArray = (0..200).map(|i|
Some(format!("v{i}"))).collect();
+ let keys = UInt8Array::from_iter_values((0..200).map(|i| (i +
offset) as u8 % 200));
+ DictionaryArray::<UInt8Type>::new(keys, Arc::new(values))
+ };
+ let (a, b) = (dict(0), dict(7));
+
+ let combined = concat(&[&a, &b]).unwrap();
+ let combined = combined.as_dictionary::<UInt8Type>();
+
+ assert_eq!(combined.len(), 400);
+ assert_eq!(combined.values().data_type(), &DataType::Utf8View);
+ assert!(combined.values().len() < 400);
Review Comment:
```suggestion
assert_eq!(combined.values().len(),200);
```
##########
arrow-select/src/concat.rs:
##########
@@ -1708,6 +1708,124 @@ mod tests {
assert_eq!(array.logical_null_count(), 10);
}
+ #[test]
+ fn concat_string_view_dictionary_merges_duplicate_values() {
+ // Two independently-built `Dictionary<UInt8, Utf8View>` arrays
holding the
+ // same 200 distinct values. Naively concatenating their dictionaries
yields
+ // 400 entries, which overflows the u8 key range, but the distinct
values do
+ // fit -- so the values must be merged and deduplicated instead. This
mirrors
+ // a `Dictionary<UInt16, Utf8View>` column read in several partitions,
each
+ // building its own dictionary, and then combined.
+ let dict = |offset: usize| {
+ let values: StringViewArray = (0..200).map(|i|
Some(format!("v{i}"))).collect();
+ let keys = UInt8Array::from_iter_values((0..200).map(|i| (i +
offset) as u8 % 200));
+ DictionaryArray::<UInt8Type>::new(keys, Arc::new(values))
+ };
+ let (a, b) = (dict(0), dict(7));
+
+ let combined = concat(&[&a, &b]).unwrap();
+ let combined = combined.as_dictionary::<UInt8Type>();
+
+ assert_eq!(combined.len(), 400);
+ assert_eq!(combined.values().data_type(), &DataType::Utf8View);
+ assert!(combined.values().len() < 400);
+
+ let values = combined.values().as_string_view();
+ let actual: Vec<_> = combined
+ .keys()
+ .values()
+ .iter()
+ .map(|k| values.value(*k as usize))
+ .collect();
+ let expected: Vec<_> = [&a, &b]
+ .iter()
+ .flat_map(|d| {
+ let v = d.values().as_string_view();
+ d.keys()
+ .values()
+ .iter()
+ .map(|k| v.value(*k as usize))
+ .collect::<Vec<_>>()
+ })
+ .collect();
+ assert_eq!(actual, expected);
+ }
+
+ #[test]
+ fn concat_binary_view_dictionary_merges_duplicate_values() {
+ // Same as `concat_string_view_dictionary_merges_duplicate_values`,
for the
+ // other view-typed dictionary value layout.
Review Comment:
I dont think this is needed. both stringview/binaryview are pretty much the
exact same structure. 1 test should be fine
--
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]
