Skip to content

Commit 0923424

Browse files
authored
Merge branch 'main' into fix/single-distinct-groupby-memory-usage
2 parents 0c76607 + 334f293 commit 0923424

12 files changed

Lines changed: 1450 additions & 6 deletions

File tree

‎datafusion/common/src/config.rs‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -925,6 +925,29 @@ config_namespace! {
925925
/// Support for build_side.num_rows() >= u32::MAX will be added in the future.
926926
pub perfect_hash_join_min_key_density: f64, default = 0.15
927927

928+
/// Enable an exact integer membership prefilter for hash joins with a single
929+
/// integer key when the build side uses a hash table and the join is not
930+
/// null-aware. It skips lookups for absent keys while retaining NULLs and
931+
/// probe rows for the original join logic.
932+
pub enable_join_integer_prefilter: bool, default = false
933+
934+
/// Maximum number of integer values covered by the join prefilter bitmap
935+
/// (`max_key - min_key + 1`). Zero disables bitmap construction.
936+
/// Larger ranges fall back to normal hash table lookups.
937+
pub join_integer_prefilter_max_key_range: u64, default = 262144
938+
939+
/// The integer prefilter must prune more than this fraction of all sampled
940+
/// probe rows, including NULLs, to keep filtering. Must be finite and in
941+
/// [0, 1], validated when executing the join.
942+
pub join_integer_prefilter_min_pruning_ratio: f64, default = 0.5
943+
944+
/// Minimum input probe rows in each integer prefilter sampling window,
945+
/// including NULLs. Must be greater than zero. Windows end at batch boundaries.
946+
/// Unprofitable samples initially pause for 10 times this many input rows;
947+
/// consecutive failures double the pause up to 128 times. A profitable
948+
/// sample resets the pause to 10 times this many rows.
949+
pub join_integer_prefilter_sample_rows: ConfigNonZeroUsize, default = non_zero_usize_default(12288)
950+
928951
/// When set to true, record batches will be examined between each operator and
929952
/// small batches will be coalesced into larger batches. This is helpful when there
930953
/// are highly selective filters or joins that could produce tiny output batches. The

‎datafusion/physical-plan/Cargo.toml‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -173,6 +173,11 @@ name = "compute_statistics"
173173
harness = false
174174
name = "dictionary_group_values"
175175

176+
[[bench]]
177+
harness = false
178+
name = "hash_join_probe"
179+
required-features = ["test_utils"]
180+
176181
[[bench]]
177182
harness = false
178183
name = "hash_join_semi_anti"
Lines changed: 282 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,282 @@
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+
//! Full in-memory HashJoin execution, including build, with fixed Int32 workloads.
19+
//! All inputs carry an Int32 data column and a Utf8 payload column.
20+
//! Session settings use the standard DataFusion environment configuration.
21+
22+
use std::hint::black_box;
23+
use std::sync::Arc;
24+
25+
use arrow::array::{ArrayRef, Int32Array, StringArray};
26+
use arrow::datatypes::{DataType, Field, Schema, SchemaRef};
27+
use arrow::record_batch::RecordBatch;
28+
use criterion::{Criterion, criterion_group, criterion_main};
29+
use datafusion_common::{JoinType, NullEquality};
30+
use datafusion_execution::TaskContext;
31+
use datafusion_execution::config::SessionConfig;
32+
use datafusion_physical_expr::expressions::col;
33+
use datafusion_physical_plan::joins::{HashJoinExec, PartitionMode};
34+
use datafusion_physical_plan::test::TestMemoryExec;
35+
use datafusion_physical_plan::{ExecutionPlan, collect};
36+
use tokio::runtime::Runtime;
37+
38+
const BATCH_SIZE: usize = 8_192;
39+
const BUILD_ROWS: usize = 20_000;
40+
const PROBE_ROWS: usize = 1_000_000;
41+
const LARGE_BUILD_ROWS: usize = 100_000;
42+
const SPARSE_KEY_STEP: i32 = 10;
43+
const DENSE_KEY_STEP: i32 = 1;
44+
const HIT_EVERY: usize = 10;
45+
46+
#[derive(Clone, Copy)]
47+
enum Pattern {
48+
AllHit,
49+
InterleavedLowHit,
50+
ClusteredLowHit,
51+
HighToLow,
52+
}
53+
54+
fn make_batches(
55+
rows: usize,
56+
build_rows: usize,
57+
key_step: i32,
58+
pattern: Pattern,
59+
schema: &SchemaRef,
60+
) -> Vec<RecordBatch> {
61+
let mut hits = 0;
62+
(0..rows)
63+
.step_by(BATCH_SIZE)
64+
.map(|start| {
65+
let end = (start + BATCH_SIZE).min(rows);
66+
let keys = Int32Array::from_iter_values((start..end).map(|row| {
67+
let hit = match pattern {
68+
Pattern::AllHit => true,
69+
Pattern::InterleavedLowHit => row % HIT_EVERY == 0,
70+
Pattern::ClusteredLowHit => row < rows / HIT_EVERY,
71+
Pattern::HighToLow => row < rows / 2 || row % HIT_EVERY == 0,
72+
};
73+
if hit {
74+
let key = (hits % build_rows) as i32 * key_step;
75+
hits += 1;
76+
key
77+
} else {
78+
// Every hole stays strictly between the build min and max.
79+
(row % (build_rows - 1)) as i32 * key_step + 1
80+
}
81+
}));
82+
let columns: Vec<ArrayRef> = vec![
83+
Arc::new(keys),
84+
Arc::new(Int32Array::from_iter_values(
85+
(start..end).map(|row| row as i32),
86+
)),
87+
Arc::new(StringArray::from_iter_values(
88+
(start..end).map(|row| format!("{row}")),
89+
)),
90+
];
91+
RecordBatch::try_new(Arc::clone(schema), columns).unwrap()
92+
})
93+
.collect()
94+
}
95+
96+
fn make_join(
97+
build_batches: &[RecordBatch],
98+
probe_batches: &[RecordBatch],
99+
join_type: JoinType,
100+
) -> Arc<dyn ExecutionPlan> {
101+
let schema = build_batches[0].schema();
102+
let build = TestMemoryExec::try_new_exec(
103+
&[build_batches.to_vec()],
104+
Arc::clone(&schema),
105+
None,
106+
)
107+
.unwrap();
108+
let probe = TestMemoryExec::try_new_exec(
109+
&[probe_batches.to_vec()],
110+
Arc::clone(&schema),
111+
None,
112+
)
113+
.unwrap();
114+
Arc::new(
115+
HashJoinExec::try_new(
116+
build,
117+
probe,
118+
vec![(col("key", &schema).unwrap(), col("key", &schema).unwrap())],
119+
None,
120+
&join_type,
121+
None,
122+
PartitionMode::CollectLeft,
123+
NullEquality::NullEqualsNothing,
124+
false,
125+
)
126+
.unwrap(),
127+
)
128+
}
129+
130+
fn bench_hash_join_probe(c: &mut Criterion) {
131+
let rt = Runtime::new().unwrap();
132+
let config = SessionConfig::from_env()
133+
.unwrap()
134+
.with_batch_size(BATCH_SIZE);
135+
let context = Arc::new(TaskContext::default().with_session_config(config));
136+
let schema = Arc::new(Schema::new(vec![
137+
Field::new("key", DataType::Int32, false),
138+
Field::new("data", DataType::Int32, false),
139+
Field::new("payload", DataType::Utf8, false),
140+
]));
141+
let mut group = c.benchmark_group("hash_join_probe");
142+
for (name, join_type, pattern, build_rows, probe_rows, key_step) in [
143+
(
144+
"right_semi_interleaved_10pct",
145+
JoinType::RightSemi,
146+
Pattern::InterleavedLowHit,
147+
BUILD_ROWS,
148+
PROBE_ROWS,
149+
SPARSE_KEY_STEP,
150+
),
151+
(
152+
"right_semi_all_hit",
153+
JoinType::RightSemi,
154+
Pattern::AllHit,
155+
BUILD_ROWS,
156+
PROBE_ROWS,
157+
SPARSE_KEY_STEP,
158+
),
159+
(
160+
"right_anti_interleaved_10pct",
161+
JoinType::RightAnti,
162+
Pattern::InterleavedLowHit,
163+
BUILD_ROWS,
164+
PROBE_ROWS,
165+
SPARSE_KEY_STEP,
166+
),
167+
(
168+
"right_anti_all_hit",
169+
JoinType::RightAnti,
170+
Pattern::AllHit,
171+
BUILD_ROWS,
172+
PROBE_ROWS,
173+
SPARSE_KEY_STEP,
174+
),
175+
(
176+
"inner_interleaved_10pct",
177+
JoinType::Inner,
178+
Pattern::InterleavedLowHit,
179+
BUILD_ROWS,
180+
PROBE_ROWS,
181+
SPARSE_KEY_STEP,
182+
),
183+
(
184+
"inner_all_hit",
185+
JoinType::Inner,
186+
Pattern::AllHit,
187+
BUILD_ROWS,
188+
PROBE_ROWS,
189+
SPARSE_KEY_STEP,
190+
),
191+
(
192+
"right_semi_clustered_10pct",
193+
JoinType::RightSemi,
194+
Pattern::ClusteredLowHit,
195+
BUILD_ROWS,
196+
PROBE_ROWS,
197+
SPARSE_KEY_STEP,
198+
),
199+
(
200+
"right_anti_clustered_10pct",
201+
JoinType::RightAnti,
202+
Pattern::ClusteredLowHit,
203+
BUILD_ROWS,
204+
PROBE_ROWS,
205+
SPARSE_KEY_STEP,
206+
),
207+
(
208+
"right_semi_high_to_low",
209+
JoinType::RightSemi,
210+
Pattern::HighToLow,
211+
BUILD_ROWS,
212+
PROBE_ROWS,
213+
SPARSE_KEY_STEP,
214+
),
215+
(
216+
"right_anti_high_to_low",
217+
JoinType::RightAnti,
218+
Pattern::HighToLow,
219+
BUILD_ROWS,
220+
PROBE_ROWS,
221+
SPARSE_KEY_STEP,
222+
),
223+
(
224+
"right_semi_single_batch_all_hit",
225+
JoinType::RightSemi,
226+
Pattern::AllHit,
227+
BUILD_ROWS,
228+
BATCH_SIZE,
229+
SPARSE_KEY_STEP,
230+
),
231+
(
232+
"right_semi_dense_100k_all_hit",
233+
JoinType::RightSemi,
234+
Pattern::AllHit,
235+
LARGE_BUILD_ROWS,
236+
PROBE_ROWS,
237+
DENSE_KEY_STEP,
238+
),
239+
(
240+
"right_semi_sparse_100k_all_hit",
241+
JoinType::RightSemi,
242+
Pattern::AllHit,
243+
LARGE_BUILD_ROWS,
244+
PROBE_ROWS,
245+
SPARSE_KEY_STEP,
246+
),
247+
] {
248+
let build =
249+
make_batches(build_rows, build_rows, key_step, Pattern::AllHit, &schema);
250+
let probe = make_batches(probe_rows, build_rows, key_step, pattern, &schema);
251+
let run = || {
252+
let join = make_join(&build, &probe, join_type);
253+
rt.block_on(collect(join, Arc::clone(&context))).unwrap()
254+
};
255+
256+
let hits = match pattern {
257+
Pattern::AllHit => probe_rows,
258+
Pattern::InterleavedLowHit | Pattern::ClusteredLowHit => {
259+
probe_rows / HIT_EVERY
260+
}
261+
Pattern::HighToLow => probe_rows / 2 + probe_rows / 2 / HIT_EVERY,
262+
};
263+
let expected_rows = if join_type == JoinType::RightAnti {
264+
probe_rows - hits
265+
} else {
266+
hits
267+
};
268+
let output = run();
269+
assert_eq!(
270+
output.iter().map(RecordBatch::num_rows).sum::<usize>(),
271+
expected_rows,
272+
"{name}",
273+
);
274+
drop(output);
275+
276+
group.bench_function(name, |b| b.iter(|| black_box(run())));
277+
}
278+
group.finish();
279+
}
280+
281+
criterion_group!(benches, bench_hash_join_probe);
282+
criterion_main!(benches);

0 commit comments

Comments
 (0)