Skip to content

Commit 8a4222e

Browse files
committed
perf: size hash join build slices by nested dictionary and list view values
create_hashes hashes everything beneath a dictionary or list view in full on every call, whatever slice it gets, and that holds below structs and lists too. Walk each key's ArrayData for the longest such array and make the build slices at least that long, capped at the build row count, so struct or list keys holding dictionaries and list view keys stay linear in the build rows.
1 parent b2a56c3 commit 8a4222e

1 file changed

Lines changed: 100 additions & 13 deletions

File tree

  • datafusion/physical-plan/src/joins/hash_join

‎datafusion/physical-plan/src/joins/hash_join/exec.rs‎

Lines changed: 100 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -58,7 +58,7 @@ use crate::{
5858
metrics::{ExecutionPlanMetricsSet, MetricsSet},
5959
};
6060

61-
use arrow::array::{Array, ArrayRef, AsArray, BooleanBufferBuilder};
61+
use arrow::array::{Array, ArrayData, ArrayRef, BooleanBufferBuilder};
6262
use arrow::compute::concat_batches;
6363
use arrow::datatypes::SchemaRef;
6464
use arrow::record_batch::RecordBatch;
@@ -103,6 +103,30 @@ pub(crate) const HASH_JOIN_SEED: SeededRandomState =
103103

104104
const ARRAY_MAP_CREATED_COUNT_METRIC_NAME: &str = "array_map_created_count";
105105

106+
/// The length of the longest array under `data` that `create_hashes` hashes
107+
/// in full whatever slice of `data` it gets: everything beneath a dictionary
108+
/// or a list view, at any depth.
109+
fn unsliced_hash_len(data: &ArrayData) -> usize {
110+
let own = match data.data_type() {
111+
DataType::Dictionary(_, _)
112+
| DataType::ListView(_)
113+
| DataType::LargeListView(_) => subtree_max_len(&data.child_data()[0]),
114+
_ => 0,
115+
};
116+
data.child_data()
117+
.iter()
118+
.map(unsliced_hash_len)
119+
.fold(own, usize::max)
120+
}
121+
122+
/// The longest array anywhere in `data`, including `data` itself.
123+
fn subtree_max_len(data: &ArrayData) -> usize {
124+
data.child_data()
125+
.iter()
126+
.map(subtree_max_len)
127+
.fold(data.len(), usize::max)
128+
}
129+
106130
/// Decides whether the build side should be joined with an [`ArrayMap`]
107131
/// (perfect hash join), returning the `(min, max)` key range to build it over.
108132
///
@@ -681,8 +705,9 @@ impl From<&HashJoinExec> for HashJoinExecBuilder {
681705
/// with smaller indices "on the top" of hash table. The build-side batches are first
682706
/// concatenated in their input order. The hash table is then filled from slices of the
683707
/// concatenated batch, at most as long as the largest build-side batch (or the longest
684-
/// key dictionary, when that is longer), starting from the last slice. Each slice is
685-
/// inserted with the offset of its first row in the concatenated batch.
708+
/// values under a dictionary or list view in a key, when that is longer), starting
709+
/// from the last slice. Each slice is inserted with the offset of its first row in
710+
/// the concatenated batch.
686711
///
687712
/// Example of build phase for 3 record batches, filled from slices of 3 rows:
688713
///
@@ -3216,14 +3241,15 @@ fn build_in_memory(
32163241
// Arc is used instead of Box to allow sharing with SharedBuildAccumulator for hash map pushdown
32173242
let mut hashmap = new_join_hashmap(num_rows, &mut reservation, metrics)?;
32183243

3219-
// Every slice shares the whole dictionary of a dictionary key, which
3220-
// `create_hashes` hashes on each call: a slice at least as long as the
3221-
// dictionary keeps that cost linear in the build rows.
3244+
// Every slice shares everything beneath a dictionary or list view,
3245+
// at any depth of a key, which `create_hashes` hashes on each call: a
3246+
// slice at least as long as the longest of those arrays keeps that
3247+
// cost linear in the build rows. No slice is longer than the build side.
32223248
let chunk_rows = left_values
32233249
.iter()
3224-
.filter_map(|values| values.as_any_dictionary_opt())
3225-
.map(|dict| dict.values().len())
3226-
.fold(max_batch_rows, usize::max);
3250+
.map(|values| unsliced_hash_len(&values.to_data()))
3251+
.fold(max_batch_rows, usize::max)
3252+
.min(num_rows);
32273253

32283254
let scratch_reservation = reservation.new_empty();
32293255
if prepared {
@@ -3234,7 +3260,7 @@ fn build_in_memory(
32343260
)?)?;
32353261
}
32363262
// The maximum is known: avoid geometric growth and its excess capacity.
3237-
let mut hashes_buffer = Vec::with_capacity(chunk_rows.min(num_rows));
3263+
let mut hashes_buffer = Vec::with_capacity(chunk_rows);
32383264
// `chunk_rows` is 0 when the build side is empty
32393265
let chunk_rows = chunk_rows.max(1);
32403266

@@ -3478,10 +3504,11 @@ mod tests {
34783504
use crate::joins::join_hash_map::ProbeOffset::AtRow;
34793505
use arrow::array::{
34803506
Array, ArrayRef, AsArray, BinaryViewArray, Date32Array, DictionaryArray,
3481-
Float32Array, Float64Array, Int32Array, Int64Array, StringArray, StringViewArray,
3482-
StructArray, UInt32Array, UInt64Array,
3507+
FixedSizeListArray, Float32Array, Float64Array, Int32Array, Int64Array,
3508+
ListArray, ListViewArray, StringArray, StringViewArray, StructArray, UInt32Array,
3509+
UInt64Array,
34833510
};
3484-
use arrow::buffer::NullBuffer;
3511+
use arrow::buffer::{NullBuffer, OffsetBuffer, ScalarBuffer};
34853512
use arrow::datatypes::{DataType, Field, Float32Type, Float64Type, Int32Type};
34863513
use datafusion_common::hash_utils::create_hashes;
34873514
use datafusion_common::stats::Precision;
@@ -5146,6 +5173,66 @@ mod tests {
51465173
Ok(())
51475174
}
51485175

5176+
/// Only what a slice cannot cut counts, which is everything below a
5177+
/// dictionary or a list view, also below a struct or a list, but not the
5178+
/// child of a plain list or fixed size list.
5179+
#[test]
5180+
fn unsliced_hash_len_counts_shared_values_at_any_depth() -> Result<()> {
5181+
let dict: ArrayRef = Arc::new(DictionaryArray::<Int32Type>::try_new(
5182+
Int32Array::from(vec![0, 1]),
5183+
Arc::new(StringArray::from(vec!["a", "b", "c", "d", "e"])),
5184+
)?);
5185+
let in_struct: ArrayRef = Arc::new(StructArray::from(vec![(
5186+
Arc::new(Field::new("d", dict.data_type().clone(), false)),
5187+
Arc::clone(&dict),
5188+
)]));
5189+
let list_view: ArrayRef = Arc::new(ListViewArray::new(
5190+
Arc::new(Field::new_list_field(DataType::Int32, false)),
5191+
ScalarBuffer::from(vec![0, 1]),
5192+
ScalarBuffer::from(vec![1, 1]),
5193+
Arc::new(Int32Array::from(vec![1, 2, 3, 4])),
5194+
None,
5195+
));
5196+
let list: ArrayRef =
5197+
Arc::new(ListArray::from_iter_primitive::<Int32Type, _, _>(vec![
5198+
Some(vec![Some(1), Some(2), Some(3)]),
5199+
Some(vec![Some(4), Some(5), Some(6), Some(7)]),
5200+
]));
5201+
let fixed_size_list: ArrayRef = Arc::new(FixedSizeListArray::new(
5202+
Arc::new(Field::new_list_field(DataType::Int32, false)),
5203+
2,
5204+
Arc::new(Int32Array::from(vec![1, 2, 3, 4, 5, 6])),
5205+
None,
5206+
));
5207+
let list_of_dict: ArrayRef = Arc::new(ListArray::new(
5208+
Arc::new(Field::new_list_field(dict.data_type().clone(), false)),
5209+
OffsetBuffer::from_lengths([1, 1]),
5210+
Arc::clone(&dict),
5211+
None,
5212+
));
5213+
let dict_of_list: ArrayRef = Arc::new(DictionaryArray::<Int32Type>::try_new(
5214+
Int32Array::from(vec![0, 1]),
5215+
Arc::clone(&list),
5216+
)?);
5217+
for (array, expected) in [
5218+
(dict.slice(1, 1), 5),
5219+
(in_struct.slice(1, 1), 5),
5220+
(list_view.slice(0, 1), 4),
5221+
(list.slice(0, 1), 0),
5222+
(fixed_size_list.slice(1, 1), 0),
5223+
(list_of_dict.slice(1, 1), 5),
5224+
(dict_of_list.slice(1, 1), 7),
5225+
] {
5226+
assert_eq!(
5227+
unsliced_hash_len(&array.to_data()),
5228+
expected,
5229+
"{}",
5230+
array.data_type()
5231+
);
5232+
}
5233+
Ok(())
5234+
}
5235+
51495236
/// Build batches sharing one key dictionary that is longer than each batch
51505237
/// fill the hash map from slices longer than the batches, which must join
51515238
/// as if the build side were a single batch.

0 commit comments

Comments
 (0)