Skip to content

Commit c7d903b

Browse files
committed
refactor: Rewrite Hash Join's regular (inner/left/right/full) join path
1 parent a23b89f commit c7d903b

9 files changed

Lines changed: 1199 additions & 74 deletions

File tree

‎datafusion/common/src/config.rs‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -980,6 +980,12 @@ config_namespace! {
980980
/// See <https://github.com/apache/datafusion/issues/22710> for details.
981981
pub enable_migration_aggregate: bool, default = true
982982

983+
/// Whether inner, left outer, right outer, and full outer hash joins use
984+
/// the refactored implementation. When set to `false`, these joins use
985+
/// the existing implementation. Other join types always use the existing
986+
/// implementation.
987+
pub enable_migration_hash_join: bool, default = true
988+
983989
/// Sets the compression codec used when spilling data to disk.
984990
///
985991
/// Since datafusion writes spill files using the Arrow IPC Stream format,
Lines changed: 196 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,196 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
//! Build preparation and shared data for regular hash joins.
19+
//!
20+
//! Collection is shared across probe partitions in `CollectLeft` mode. Before
21+
//! probing, each partition also waits for the join's dynamic filter to be ready.
22+
//! The prepared result contains only the data and coordination regular joins need.
23+
24+
use std::sync::Arc;
25+
26+
use arrow::array::{BooleanBufferBuilder, UInt64Array};
27+
use arrow::buffer::BooleanBuffer;
28+
use datafusion_common::Result;
29+
use futures::future::poll_fn;
30+
use parking_lot::Mutex;
31+
32+
use super::exec::JoinBuildData;
33+
use crate::joins::PartitionMode;
34+
use crate::joins::hash_join::shared_bounds::{
35+
PartitionBounds, PartitionBuildData, SharedBuildAccumulator,
36+
};
37+
use crate::joins::utils::{BuildProbeJoinMetrics, OnceFut};
38+
39+
/// [`JoinBuildData`] plus cross-partition coordination, only one partition is
40+
/// responsible for final build-side unmatched output for Left/Full joins.
41+
pub(super) struct JoinBuildState {
42+
unmatched: Option<Mutex<UnmatchedRows>>,
43+
// Keep the build lease last: its reservation also covers the bitmap.
44+
pub(super) data: Arc<JoinBuildData>,
45+
}
46+
47+
struct UnmatchedRows {
48+
visited: BooleanBufferBuilder,
49+
remaining_probes: usize,
50+
}
51+
52+
impl JoinBuildState {
53+
pub(super) fn new(
54+
data: Arc<JoinBuildData>,
55+
visited: Option<BooleanBufferBuilder>,
56+
probe_partitions: usize,
57+
) -> Self {
58+
Self {
59+
unmatched: visited.map(|visited| {
60+
Mutex::new(UnmatchedRows {
61+
visited,
62+
remaining_probes: probe_partitions,
63+
})
64+
}),
65+
data,
66+
}
67+
}
68+
69+
/// Record matches after the ON filter has accepted them.
70+
pub(super) fn record_matches(&self, indices: &UInt64Array) {
71+
if let Some(unmatched) = &self.unmatched {
72+
let mut unmatched = unmatched.lock();
73+
for index in indices.iter().flatten() {
74+
unmatched.visited.set_bit(index as usize, true);
75+
}
76+
}
77+
}
78+
79+
/// Report actual probe EOF; a fetch cutoff must not call this.
80+
pub(super) fn finish_probe(&self) -> Option<BooleanBuffer> {
81+
let mut unmatched = self.unmatched.as_ref()?.lock();
82+
// Counting and snapshotting under the same lock ensures the last probe
83+
// sees every sibling's matches and is the only one to emit unmatched rows.
84+
unmatched.remaining_probes -= 1;
85+
(unmatched.remaining_probes == 0).then(|| unmatched.visited.finish_cloned())
86+
}
87+
}
88+
89+
/// Collecting the build side data of hash join.
90+
///
91+
/// It handles coordination/syncrhonization among all parallel paartitions for:
92+
/// - Input batches collecting
93+
/// - Dynamic filter preparation
94+
pub(super) struct HashJoinBuild {
95+
partition: usize,
96+
mode: PartitionMode,
97+
98+
// ---------------------------------------------------
99+
// Shared structures for coordiation among partitions.
100+
// ---------------------------------------------------
101+
/// Coordination for dynamic filter
102+
build_accumulator: Option<Arc<SharedBuildAccumulator>>,
103+
/// Coordination for buffered input batches
104+
left_fut: OnceFut<JoinBuildState>,
105+
106+
metrics: BuildProbeJoinMetrics,
107+
}
108+
109+
impl HashJoinBuild {
110+
pub(super) fn new(
111+
partition: usize,
112+
mode: PartitionMode,
113+
left_fut: OnceFut<JoinBuildState>,
114+
build_accumulator: Option<Arc<SharedBuildAccumulator>>,
115+
metrics: BuildProbeJoinMetrics,
116+
) -> Self {
117+
Self {
118+
partition,
119+
mode,
120+
build_accumulator,
121+
left_fut,
122+
metrics,
123+
}
124+
}
125+
126+
/// Prepare the build-side data and handle coordinations.
127+
///
128+
/// It handles coordination for build-side data preparation, and dynamic filters.
129+
///
130+
/// Example for coordination for build-side data: (coordination for dynamic
131+
/// filter is similar, after all partition is done, it can publish the dynamic
132+
/// filter to pre-filter probe side)
133+
///
134+
/// ```text
135+
/// With shared build-side configuration:
136+
/// - partition0: call `prepare()`, and execute and cache all build-side data
137+
/// - partition1~k: call `prepare()` for synchronization, wait partition 0 finish
138+
/// and reuse the shared build-side data
139+
/// ```
140+
pub(super) async fn prepare(mut self) -> Result<Arc<JoinBuildState>> {
141+
let build = poll_fn(|cx| {
142+
// Count active polling time, excluding time suspended on input.
143+
let _timer = self.metrics.build_time.timer();
144+
self.left_fut.get_shared(cx)
145+
})
146+
.await?;
147+
148+
if let Some(accumulator) = &self.build_accumulator {
149+
let data = &build.data;
150+
let pushdown = data.membership.clone();
151+
let bounds = data
152+
.bounds
153+
.clone()
154+
.unwrap_or_else(|| PartitionBounds::new(vec![]));
155+
// Dictionary keys can point at NULL values without physical NULL keys.
156+
let keys_have_null = data
157+
.values
158+
.iter()
159+
.any(|array| array.logical_null_count() > 0);
160+
let report = match self.mode {
161+
PartitionMode::Partitioned => PartitionBuildData::Partitioned {
162+
partition_id: self.partition,
163+
pushdown,
164+
bounds,
165+
keys_have_null,
166+
},
167+
PartitionMode::CollectLeft => PartitionBuildData::CollectLeft {
168+
pushdown,
169+
bounds,
170+
keys_have_null,
171+
},
172+
PartitionMode::Auto => {
173+
unreachable!("PartitionMode::Auto must be resolved before execution")
174+
}
175+
};
176+
177+
// Handle coordination for dynamic filter
178+
accumulator.report_build_data(report).await?;
179+
}
180+
Ok(build)
181+
}
182+
}
183+
184+
impl Drop for HashJoinBuild {
185+
fn drop(&mut self) {
186+
if self.mode == PartitionMode::Partitioned
187+
&& let Some(accumulator) = &self.build_accumulator
188+
{
189+
// A LIMIT may drop a stream before it reports. Unblock siblings,
190+
// keeping that partition's filter permissive: unknown is not empty.
191+
// The accumulator ignores cancellation after a report, including a
192+
// report whose future was dropped while waiting for other partitions.
193+
accumulator.report_canceled_partition(self.partition);
194+
}
195+
}
196+
}

0 commit comments

Comments
 (0)