Skip to content

Commit 09c18bf

Browse files
committed
perf: keep hash join build linear with dictionary keys
Every slice of the concatenated build batch shares the whole key dictionary, and create_hashes hashes all of it on each call, so the build grew quadratically with the number of batches. Make each slice at least as long as the longest key dictionary, and add a test where the build batches share a dictionary longer than any batch.
1 parent 5fa4c1a commit 09c18bf

1 file changed

Lines changed: 98 additions & 8 deletions

File tree

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

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

Lines changed: 98 additions & 8 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, BooleanBufferBuilder};
61+
use arrow::array::{Array, ArrayRef, AsArray, BooleanBufferBuilder};
6262
use arrow::compute::concat_batches;
6363
use arrow::datatypes::SchemaRef;
6464
use arrow::record_batch::RecordBatch;
@@ -680,8 +680,9 @@ impl From<&HashJoinExec> for HashJoinExecBuilder {
680680
/// hash table is updated by iterating the build-side rows in reverse order, which keeps rows
681681
/// with smaller indices "on the top" of hash table. The build-side batches are first
682682
/// concatenated in their input order. The hash table is then filled from slices of the
683-
/// concatenated batch, at most as long as the largest build-side batch, starting from the
684-
/// last slice. Each slice is inserted with the offset of its first row in the concatenated batch.
683+
/// 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.
685686
///
686687
/// Example of build phase for 3 record batches, filled from slices of 3 rows:
687688
///
@@ -3222,20 +3223,29 @@ fn build_in_memory(
32223223
// Arc is used instead of Box to allow sharing with SharedBuildAccumulator for hash map pushdown
32233224
let mut hashmap = new_join_hashmap(num_rows, &mut reservation, metrics)?;
32243225

3226+
// Every slice shares the whole dictionary of a dictionary key, which
3227+
// `create_hashes` hashes on each call: a slice at least as long as the
3228+
// dictionary keeps that cost linear in the build rows.
3229+
let chunk_rows = left_values
3230+
.iter()
3231+
.filter_map(|values| values.as_any_dictionary_opt())
3232+
.map(|dict| dict.values().len())
3233+
.fold(max_batch_rows, usize::max);
3234+
32253235
let scratch_reservation = reservation.new_empty();
32263236
if prepared {
32273237
scratch_reservation.try_grow(prepared::prepared_scratch_bytes(
3228-
max_batch_rows,
3238+
chunk_rows,
32293239
on_left.len(),
32303240
null_equality,
32313241
)?)?;
32323242
}
32333243
// The maximum is known: avoid geometric growth and its excess capacity.
3234-
let mut hashes_buffer = Vec::with_capacity(max_batch_rows);
3235-
// `max_batch_rows` is 0 when the build side is empty
3236-
let chunk_rows = max_batch_rows.max(1);
3244+
let mut hashes_buffer = Vec::with_capacity(chunk_rows.min(num_rows));
3245+
// `chunk_rows` is 0 when the build side is empty
3246+
let chunk_rows = chunk_rows.max(1);
32373247

3238-
// Update the hashmap from slices of at most `max_batch_rows` rows,
3248+
// Update the hashmap from slices of at most `chunk_rows` rows,
32393249
// starting from the last one, so rows with smaller indices end up on
32403250
// top of the chains. Each slice is indexed at its offset in `batch`.
32413251
for offset in (0..num_rows).step_by(chunk_rows).rev() {
@@ -5143,6 +5153,86 @@ mod tests {
51435153
Ok(())
51445154
}
51455155

5156+
/// Build batches sharing one key dictionary that is longer than each batch
5157+
/// fill the hash map from slices longer than the batches, which must join
5158+
/// as if the build side were a single batch.
5159+
#[tokio::test]
5160+
async fn join_keeps_build_order_with_dictionary_keys() -> Result<()> {
5161+
let dict_type =
5162+
DataType::Dictionary(Box::new(DataType::Int32), Box::new(DataType::Utf8));
5163+
let schema = Arc::new(Schema::new(vec![
5164+
Field::new("a1", DataType::Int32, false),
5165+
Field::new("b1", dict_type.clone(), true),
5166+
]));
5167+
// Concatenation keeps a dictionary shared by every batch as is, so the
5168+
// 12 build rows are filled from slices of 5 rows: [0, 5), [5, 10) and
5169+
// [10, 12), each crossing the 2-row batch boundaries.
5170+
let values: ArrayRef = Arc::new(StringArray::from(vec!["x", "y", "z", "w", "v"]));
5171+
let batch = |a: Vec<i32>, keys: Vec<Option<i32>>| -> Result<RecordBatch> {
5172+
let b1 = DictionaryArray::<Int32Type>::try_new(
5173+
Int32Array::from(keys),
5174+
Arc::clone(&values),
5175+
)?;
5176+
Ok(RecordBatch::try_new(
5177+
Arc::clone(&schema),
5178+
vec![Arc::new(Int32Array::from(a)), Arc::new(b1)],
5179+
)?)
5180+
};
5181+
let batches = vec![
5182+
batch(vec![1, 2], vec![Some(0), None])?,
5183+
batch(vec![3, 4], vec![Some(1), Some(2)])?,
5184+
batch(vec![5, 6], vec![Some(0), Some(1)])?,
5185+
batch(vec![7, 8], vec![Some(3), Some(0)])?,
5186+
batch(vec![9, 10], vec![None, Some(1)])?,
5187+
batch(vec![11, 12], vec![Some(0), Some(1)])?,
5188+
];
5189+
let right_schema = Arc::new(Schema::new(vec![
5190+
Field::new("a2", DataType::Int32, false),
5191+
Field::new("b2", dict_type, true),
5192+
]));
5193+
let right = RecordBatch::try_new(
5194+
Arc::clone(&right_schema),
5195+
vec![
5196+
Arc::new(Int32Array::from(vec![10, 30])),
5197+
Arc::new(DictionaryArray::<Int32Type>::try_new(
5198+
Int32Array::from(vec![0, 1]),
5199+
Arc::new(StringArray::from(vec!["x", "y"])),
5200+
)?),
5201+
],
5202+
)?;
5203+
let on = vec![(
5204+
Arc::new(Column::new_with_schema("b1", &schema)?) as _,
5205+
Arc::new(Column::new_with_schema("b2", &right_schema)?) as _,
5206+
)];
5207+
let left = TestMemoryExec::try_new_exec(&[batches], Arc::clone(&schema), None)?;
5208+
let right = TestMemoryExec::try_new_exec(&[vec![right]], right_schema, None)?;
5209+
let (_, output, _) = join_collect(
5210+
left,
5211+
right,
5212+
on,
5213+
&JoinType::Inner,
5214+
NullEquality::NullEqualsNothing,
5215+
prepare_task_ctx(8192, false),
5216+
)
5217+
.await?;
5218+
5219+
assert_snapshot!(batches_to_string(&output), @r"
5220+
+----+----+----+----+
5221+
| a1 | b1 | a2 | b2 |
5222+
+----+----+----+----+
5223+
| 1 | x | 10 | x |
5224+
| 5 | x | 10 | x |
5225+
| 8 | x | 10 | x |
5226+
| 11 | x | 10 | x |
5227+
| 3 | y | 30 | y |
5228+
| 6 | y | 30 | y |
5229+
| 10 | y | 30 | y |
5230+
| 12 | y | 30 | y |
5231+
+----+----+----+----+
5232+
");
5233+
Ok(())
5234+
}
5235+
51465236
/// A build side without any batch has no rows to fill the hash map from.
51475237
#[tokio::test]
51485238
async fn join_build_side_without_batches() -> Result<()> {

0 commit comments

Comments
 (0)