Skip to content

Commit 8c34ddb

Browse files
committed
refactor: hash slices of the evaluated build keys
The build loop sliced the concatenated batch and evaluated the join keys again on every slice, although `left_values` already holds them. Hashing slices of `left_values` skips that work for expression keys and hashes the same arrays the probe side compares against.
1 parent da5fc00 commit 8c34ddb

1 file changed

Lines changed: 16 additions & 11 deletions

File tree

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

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

Lines changed: 16 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -31,7 +31,8 @@ use crate::joins::key_range_bitmap::KeyRangeBitmap;
3131
use crate::joins::probe_completion::{Completion, ProbeCompletion};
3232
use crate::joins::utils::{
3333
OnceAsync, OnceFut, asymmetric_join_output_partitioning, emits_unmatched_left_rows,
34-
is_existence_join, reorder_output_after_swap, swap_join_projection, update_hash,
34+
is_existence_join, reorder_output_after_swap, swap_join_projection,
35+
update_hash_from_values,
3536
};
3637
use crate::joins::{JoinOn, JoinOnRef, PartitionMode, ReservedMap, SharedBitmapBuilder};
3738
use crate::metrics::{Count, MetricBuilder, MetricCategory};
@@ -746,15 +747,15 @@ impl From<&HashJoinExec> for HashJoinExecBuilder {
746747
/// ┌──────────────────────────┐
747748
/// │ idx │ hashmap.insert(row-hash, row-idx + offset)
748749
/// ┌───────┐ │ ┌───────┐ │
749-
/// Batch 1 │ Row 1 │ │ Slice 1 │ Row 1 │ 0 │ 1) update_hash for slice 3 with offset 6
750+
/// Batch 1 │ Row 1 │ │ Slice 1 │ Row 1 │ 0 │ 1) hash slice 3 at offset 6
750751
/// │ Row 2 │ │ │ Row 2 │ 1 │ - hashmap.insert(Row 7, idx 6)
751752
/// └───────┘ │ │ Row 3 │ 2 │
752-
/// │ └───────┘ │ 2) update_hash for slice 2 with offset 3
753+
/// │ └───────┘ │ 2) hash slice 2 at offset 3
753754
/// ┌───────┐ │ │ - hashmap.insert(Row 6, idx 5)
754755
/// Batch 2 │ Row 3 │ │ ┌───────┐ │ - hashmap.insert(Row 5, idx 4)
755756
/// │ Row 4 │ │ Slice 2 │ Row 4 │ 3 │ - hashmap.insert(Row 4, idx 3)
756757
/// │ Row 5 │ │ │ Row 5 │ 4 │
757-
/// └───────┘ │ │ Row 6 │ 5 │ 3) update_hash for slice 1 with offset 0
758+
/// └───────┘ │ │ Row 6 │ 5 │ 3) hash slice 1 at offset 0
758759
/// │ └───────┘ │ - hashmap.insert(Row 3, idx 2)
759760
/// ┌───────┐ │ │ - hashmap.insert(Row 2, idx 1)
760761
/// Batch 3 │ Row 6 │ │ ┌───────┐ │ - hashmap.insert(Row 1, idx 0)
@@ -3297,15 +3298,19 @@ fn build_in_memory(
32973298
// `chunk_rows` is 0 when the build side is empty
32983299
let chunk_rows = chunk_rows.max(1);
32993300

3300-
// Update the hashmap from slices of at most `chunk_rows` rows,
3301-
// starting from the last one, so rows with smaller indices end up on
3302-
// top of the chains. Each slice is indexed at its offset in `batch`.
3301+
// Update the hashmap from slices of the key arrays `left_values` of at
3302+
// most `chunk_rows` rows, starting from the last one, so rows with
3303+
// smaller indices end up on top of the chains. Each slice is indexed at
3304+
// its offset in `batch`.
33033305
for offset in (0..num_rows).step_by(chunk_rows).rev() {
3304-
let chunk = batch.slice(offset, chunk_rows.min(num_rows - offset));
3306+
let len = chunk_rows.min(num_rows - offset);
3307+
let chunk: Vec<ArrayRef> = left_values
3308+
.iter()
3309+
.map(|values| values.slice(offset, len))
3310+
.collect();
33053311
hashes_buffer.clear();
3306-
hashes_buffer.resize(chunk.num_rows(), 0);
3307-
update_hash(
3308-
on_left,
3312+
hashes_buffer.resize(len, 0);
3313+
update_hash_from_values(
33093314
&chunk,
33103315
&mut *hashmap,
33113316
offset,

0 commit comments

Comments
 (0)