Skip to content

Commit acf5c89

Browse files
authored
feat: support reusable prepared hash-join builds (apache#25491)
## Which issue does this PR close? Part of [Comet apache#6013](apache/datafusion-comet#6013). [Comet apache#6037](apache/datafusion-comet#6037) uses this API. The shared row-index accounting fix in [apache#25508](apache#25508) is included in the base branch. ## Rationale for this change Independent joins against the same build snapshot repeat preparation and retain separate hash tables. `CollectLeft` shares a build among partitions of one join, but cannot share it across independently created plans. For example, eight concurrent requests joining events to the same users snapshot can share one users lookup while probing their own event batches. Preparing that lookup once avoids seven redundant builds. Applications can replace the snapshot while existing consumers finish with the old one. This supports both Comet broadcast tasks and other DataFusion applications. Comet creates independent native joins for its executor tasks, so their existing builds can overlap across task slots. The intended benefit is sharing one retained build batch and hash table and avoiding repeated materialization and hashing work. Removing repeated builds does not imply a proportional latency improvement: cold consumers wait for preparation, then probe independently. Latency depends on scheduling, contention, build size, coordination, and whether a prepared build is already retained. This PR does not establish end-to-end Comet latency, process CPU-time, or RSS savings. ## What changes are included in this PR? `HashJoinExec::prepare_build` returns an immutable `PreparedHashJoinBuild` that compatible joins attach explicitly: ```rust let prepared = first_join .prepare_build(users_snapshot, durable_pool, config) .await?; let first = first_join.builder() .with_prepared_build(Arc::clone(&prepared)) .build()?; let second = second_join.builder() .with_prepared_build(prepared) .build()?; ``` Consumers share build rows, lookup storage, and the retained memory reservation. Probe progress, residual predicates, and dynamic filters remain independent. Preparation charges retained data and temporary working memory; errors and cancellation release unfinished work. Concatenation alignment is charged once per output buffer, so small input batches do not multiply that reservation. Supported builds use non-spilling `CollectLeft` inner joins, direct-column keys with matching types, and fixed-width or UTF-8 build columns. Attachment and execution check schema, keys, and null equality, replaces the unused build subtree with a schema placeholder, and preserves the handle through supported resets and projections. Prepared state is process-local and cannot be serialized. The caller owns snapshot identity, concurrent preparation, and eviction. Input buffers must survive producer cleanup, and the supplied pool must cover every consumer. Attach after physical optimization, supply fresh probe plans and dynamic-filter expressions, and retain a build handle while any associated filter outlives its plan. Compatibility checks cannot verify snapshot contents. ## What is the testing strategy for this PR? Fifteen focused tests cover equivalence with ordinary joins, both null-equality modes, empty and duplicate keys, batch boundaries, concurrent consumers with independent filters and predicates, plan rewrites, public key changes after attachment, admission failures, small-batch concatenation under a fixed memory limit, cancellation, and buffer/reservation lifetimes. The latest regressions exercise under-admission without shrinking the reservation, checked copy/scratch arithmetic, and IN-list buffer sharing across one/two keys and one/two input batches. Existing serialization coverage rejects prepared state; the API example is a doctest. The benchmark checks outputs across 24 cases. Prepared copy and scratch sizing retain checked arithmetic. A concat output that exceeds its admitted bound returns an error in every build profile before shrinking the reservation. Numeric IN-list membership shares the retained batch's key buffers; charging its full array size again would duplicate that payload charge. General array/schema metadata and consumer-local filter expressions are outside the buffer reservation. Validation of [8a964a8](apache@8a964a8) passed: all 15 focused prepared-build tests in the normal `ci` profile; `cargo fmt --all`; full workspace Clippy with all targets/features and `-D warnings`; the complete repository lint suite, including Rust and HTML documentation builds; and the extended workspace suite (12,159 Rust tests and all 524 SQL logic files, with 8 Rust tests ignored). All 15 prepared-build tests also passed in the optimized `release-nonlto` profile. The public-key-mutation regression was verified to fail before restoring execution-time validation: the ordinary join returned its two expected rows while the stale prepared lookup returned none. With the guard restored, the mutated descriptor is rejected with a planning error. Local validation used Rust 1.98.1 and temporary source overrides for the official Arrow 60.0.0 (`ef1fa157`), object_store 0.14.2 (`279572ea`), and sqlparser 0.63.0 (`85b1a6f2`) releases. Dependency overrides and generated lockfile changes are not included. The rebased head has not been benchmarked. ```bash cargo bench -p datafusion-physical-plan --features test_utils --profile release-nonlto --bench prepared_hash_join ``` ## Are there any user-facing changes? Opt-in Rust APIs and an `EXPLAIN` marker for prepared builds. Ordinary SQL planning and join selection are unchanged.
1 parent 6a792c6 commit acf5c89

10 files changed

Lines changed: 1817 additions & 115 deletions

File tree

‎datafusion/physical-plan/Cargo.toml‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -177,6 +177,11 @@ harness = false
177177
name = "hash_join_semi_anti"
178178
required-features = ["test_utils"]
179179

180+
[[bench]]
181+
harness = false
182+
name = "prepared_hash_join"
183+
required-features = ["test_utils"]
184+
180185
[[bench]]
181186
harness = false
182187
name = "multi_group_by"
Lines changed: 272 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,272 @@
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+
//! Independent INNER joins over the same in-memory build snapshot.
19+
//!
20+
//! SQL planning does not expose prepared builds, so these benchmarks exercise
21+
//! the public execution API. Cases vary build size, integer/string keys, and
22+
//! concurrent consumers. Every consumer probes 4096 rows with 50% matches.
23+
//! `cold` includes preparation; `warm` retains a build across iterations.
24+
//! Input generation is excluded, but plan construction and draining outputs are
25+
//! timed. This does not measure Comet decoding, its cache, or its single-flight
26+
//! wait. Sparse integer keys avoid perfect-hash selection.
27+
28+
use std::hint::black_box;
29+
use std::sync::Arc;
30+
use std::time::Duration;
31+
32+
use arrow::array::{ArrayRef, Int64Array, RecordBatch, StringArray};
33+
use arrow::datatypes::{DataType, Field, Schema};
34+
use criterion::{BenchmarkId, Criterion, criterion_group, criterion_main};
35+
use datafusion_common::{JoinType, Result};
36+
use datafusion_common_runtime::SpawnedTask;
37+
use datafusion_execution::TaskContext;
38+
use datafusion_physical_expr::expressions::col;
39+
use datafusion_physical_plan::ExecutionPlan;
40+
use datafusion_physical_plan::joins::{
41+
HashJoinExec, HashJoinExecBuilder, PartitionMode, PreparedHashJoinBuild,
42+
};
43+
use datafusion_physical_plan::memory::MemoryStream;
44+
use datafusion_physical_plan::test::TestMemoryExec;
45+
use futures::TryStreamExt;
46+
use tokio::runtime::Builder;
47+
use tokio::sync::Barrier;
48+
49+
const PROBE_ROWS: usize = 4096;
50+
51+
struct Workload {
52+
build: Vec<RecordBatch>,
53+
probe: RecordBatch,
54+
expected_sum: i64,
55+
}
56+
57+
impl Workload {
58+
fn new(build_rows: usize, strings: bool) -> Self {
59+
let batch = |keys: Vec<usize>| {
60+
let array: ArrayRef = if strings {
61+
Arc::new(StringArray::from_iter_values(
62+
keys.iter().map(|key| format!("key-{key:08}")),
63+
))
64+
} else {
65+
Arc::new(Int64Array::from_iter_values(
66+
keys.iter().map(|key| (key * 17) as i64),
67+
))
68+
};
69+
RecordBatch::try_new(
70+
Arc::new(Schema::new(vec![
71+
Field::new("key", array.data_type().clone(), false),
72+
Field::new("payload", DataType::Int64, false),
73+
])),
74+
vec![
75+
array,
76+
Arc::new(Int64Array::from_iter_values(
77+
keys.iter().map(|key| *key as i64),
78+
)),
79+
],
80+
)
81+
.unwrap()
82+
};
83+
let build = batch((0..build_rows).collect());
84+
let probe = batch(
85+
(0..PROBE_ROWS)
86+
.map(|i| (i / 2) % build_rows + (i % 2) * build_rows)
87+
.collect(),
88+
);
89+
Self {
90+
build: (0..build_rows)
91+
.step_by(8192)
92+
.map(|offset| build.slice(offset, (build_rows - offset).min(8192)))
93+
.collect(),
94+
probe,
95+
expected_sum: (0..PROBE_ROWS / 2).map(|i| (i % build_rows) as i64).sum(),
96+
}
97+
}
98+
99+
fn join(&self) -> Result<HashJoinExec> {
100+
let schema = self.probe.schema();
101+
HashJoinExecBuilder::new(
102+
TestMemoryExec::try_new_exec(
103+
std::slice::from_ref(&self.build),
104+
Arc::clone(&schema),
105+
None,
106+
)?,
107+
TestMemoryExec::try_new_exec(
108+
&[vec![self.probe.clone()]],
109+
Arc::clone(&schema),
110+
None,
111+
)?,
112+
vec![(col("key", &schema)?, col("key", &schema)?)],
113+
JoinType::Inner,
114+
)
115+
.with_partition_mode(PartitionMode::CollectLeft)
116+
.build()
117+
}
118+
119+
async fn prepare(
120+
&self,
121+
join: &HashJoinExec,
122+
context: &TaskContext,
123+
) -> Result<Arc<PreparedHashJoinBuild>> {
124+
join.prepare_build(
125+
Box::pin(MemoryStream::try_new(
126+
self.build.clone(),
127+
self.probe.schema(),
128+
None,
129+
)?),
130+
Arc::clone(context.memory_pool()),
131+
Arc::clone(context.session_config().options()),
132+
)
133+
.await
134+
}
135+
}
136+
137+
#[derive(Clone, Copy)]
138+
enum Mode {
139+
Rebuild,
140+
Cold,
141+
Warm,
142+
}
143+
144+
impl Mode {
145+
fn name(self) -> &'static str {
146+
match self {
147+
Self::Rebuild => "rebuild",
148+
Self::Cold => "cold",
149+
Self::Warm => "warm",
150+
}
151+
}
152+
}
153+
154+
async fn run(
155+
workload: &Workload,
156+
consumers: usize,
157+
mode: Mode,
158+
warm: Option<Arc<PreparedHashJoinBuild>>,
159+
context: Arc<TaskContext>,
160+
) -> Result<(usize, i64)> {
161+
let joins = (0..consumers)
162+
.map(|_| workload.join())
163+
.collect::<Result<Vec<_>>>()?;
164+
let prepared = match mode {
165+
Mode::Rebuild => None,
166+
Mode::Cold => Some(workload.prepare(&joins[0], &context).await?),
167+
Mode::Warm => warm,
168+
};
169+
let start = Arc::new(Barrier::new(consumers));
170+
let tasks = joins
171+
.into_iter()
172+
.map(|join| {
173+
let join = match &prepared {
174+
Some(build) => join
175+
.builder()
176+
.with_prepared_build(Arc::clone(build))
177+
.build()?,
178+
None => join,
179+
};
180+
let context = Arc::clone(&context);
181+
let start = Arc::clone(&start);
182+
Ok(SpawnedTask::spawn(async move {
183+
start.wait().await;
184+
let mut stream = join.execute(0, context)?;
185+
let mut result = (0, 0);
186+
while let Some(batch) = stream.try_next().await? {
187+
result.0 += batch.num_rows();
188+
let payload = batch
189+
.column(1)
190+
.as_any()
191+
.downcast_ref::<Int64Array>()
192+
.unwrap();
193+
result.1 += payload.values().iter().sum::<i64>();
194+
}
195+
Ok::<_, datafusion_common::DataFusionError>(result)
196+
}))
197+
})
198+
.collect::<Result<Vec<_>>>()?;
199+
let mut result = (0, 0);
200+
for task in tasks {
201+
let (rows, sum) = task.await.unwrap()?;
202+
result.0 += rows;
203+
result.1 += sum;
204+
}
205+
Ok(result)
206+
}
207+
208+
fn benchmark(c: &mut Criterion) {
209+
let runtime = Builder::new_multi_thread()
210+
.worker_threads(4)
211+
.enable_all()
212+
.build()
213+
.unwrap();
214+
let mut group = c.benchmark_group("prepared_hash_join");
215+
group.sample_size(20);
216+
group.warm_up_time(Duration::from_millis(500));
217+
group.measurement_time(Duration::from_secs(2));
218+
219+
for (key_type, strings) in [("int64", false), ("utf8", true)] {
220+
for rows in [64, 65536] {
221+
let workload = Workload::new(rows, strings);
222+
for consumers in [1, 4] {
223+
for mode in [Mode::Rebuild, Mode::Cold, Mode::Warm] {
224+
let context = Arc::new(TaskContext::default());
225+
let warm = matches!(mode, Mode::Warm).then(|| {
226+
runtime
227+
.block_on(
228+
workload.prepare(&workload.join().unwrap(), &context),
229+
)
230+
.unwrap()
231+
});
232+
let output = runtime
233+
.block_on(run(
234+
&workload,
235+
consumers,
236+
mode,
237+
warm.clone(),
238+
Arc::clone(&context),
239+
))
240+
.unwrap();
241+
assert_eq!(
242+
output,
243+
(
244+
consumers * PROBE_ROWS / 2,
245+
consumers as i64 * workload.expected_sum
246+
)
247+
);
248+
let case = format!("{key_type}/{rows}/{consumers}_consumers");
249+
group.bench_function(BenchmarkId::new(mode.name(), case), |b| {
250+
b.iter(|| {
251+
black_box(
252+
runtime
253+
.block_on(run(
254+
&workload,
255+
consumers,
256+
mode,
257+
warm.clone(),
258+
Arc::clone(&context),
259+
))
260+
.unwrap(),
261+
)
262+
});
263+
});
264+
}
265+
}
266+
}
267+
}
268+
group.finish();
269+
}
270+
271+
criterion_group!(benches, benchmark);
272+
criterion_main!(benches);

0 commit comments

Comments
 (0)