jayzhan211 commented on code in PR #26793:
URL: https://github.com/apache/datafusion/pull/26793#discussion_r4434111954
##########
datafusion/physical-plan/src/joins/hash_join/exec.rs:
##########
@@ -3217,28 +3216,38 @@ fn build_in_memory(
// Arc is used instead of Box to allow sharing with
SharedBuildAccumulator for hash map pushdown
let mut hashmap = new_join_hashmap(num_rows, &mut reservation,
metrics)?;
+ // Every slice shares the whole dictionary of a dictionary key, which
+ // `create_hashes` hashes on each call: a slice at least as long as the
+ // dictionary keeps that cost linear in the build rows.
+ let chunk_rows = left_values
+ .iter()
+ .filter_map(|values| values.as_any_dictionary_opt())
+ .map(|dict| dict.values().len())
+ .fold(max_batch_rows, usize::max);
Review Comment:
@dwsmith1983 thanks for applying the dictionary fix. One case I missed in my
first pass: this check only sees top-level dictionaries, so a dictionary inside
a struct or list key still has its whole values hashed on every slice, and
ListView keys hash their whole child the same way. With 8192-row build batches
and a separate 1000-value dictionary per batch, 256 batches take 11.1 → 65.5 ms
for `Struct<Dictionary>` and 22.9 → 158.9 ms for `ListView<Int32>` (base →
head, release build).
Walking the key's `ArrayData` brings them back to 11.0 ms and 19.1 ms, and
the top-level dictionary case stays as it is now. Add this next to
`array_map_key_range` (plus `ArrayData` in the `arrow::array` import and
`DataType` from the existing `arrow_schema` import; `AsArray` is then unused):
```rs
/// The length of the longest values array under `data` that `create_hashes`
/// hashes in full whatever slice of `data` it gets: the values of a
/// dictionary or a list view, at any depth.
fn unsliced_hash_len(data: &ArrayData) -> usize {
let own = match data.data_type() {
DataType::Dictionary(_, _)
| DataType::ListView(_)
| DataType::LargeListView(_) => data.child_data()[0].len(),
_ => 0,
};
data.child_data()
.iter()
.map(unsliced_hash_len)
.fold(own, usize::max)
}
```
```suggestion
// Every slice shares the whole values of a dictionary or list view,
// at any depth of a key, which `create_hashes` hashes on each call:
a
// slice at least as long as those values keeps that cost linear in
// the build rows.
let chunk_rows = left_values
.iter()
.map(|values| unsliced_hash_len(&values.to_data()))
.fold(max_batch_rows, usize::max);
```
Could you also add this test? It separates the rule from both "top-level
dictionary only" (the struct case) and "any child" (the plain list case). The
`HashJoinExec` doc around line 683 ("or the longest key dictionary") would need
the same wording update.
```rs
/// Only values a slice cannot cut count: a dictionary or a list view,
/// also below a struct, but not the child of a list.
#[test]
fn unsliced_hash_len_counts_shared_values_at_any_depth() -> Result<()> {
let dict: ArrayRef = Arc::new(DictionaryArray::<Int32Type>::try_new(
Int32Array::from(vec![0, 1]),
Arc::new(StringArray::from(vec!["a", "b", "c", "d", "e"])),
)?);
let in_struct: ArrayRef = Arc::new(StructArray::from(vec![(
Arc::new(Field::new("d", dict.data_type().clone(), false)),
Arc::clone(&dict),
)]));
let list_view: ArrayRef = Arc::new(ListViewArray::new(
Arc::new(Field::new_list_field(DataType::Int32, false)),
ScalarBuffer::from(vec![0, 1]),
ScalarBuffer::from(vec![1, 1]),
Arc::new(Int32Array::from(vec![1, 2, 3, 4])),
None,
));
let list: ArrayRef =
Arc::new(ListArray::from_iter_primitive::<Int32Type, _, _>(vec![Some(
vec![Some(1), Some(2), Some(3)],
)]));
for (array, expected) in [
(dict.slice(1, 1), 5),
(in_struct.slice(1, 1), 5),
(list_view.slice(0, 1), 4),
(list, 0),
] {
assert_eq!(unsliced_hash_len(&array.to_data()), expected);
}
Ok(())
}
```
--
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]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
