Skip to content

Commit 334f293

Browse files
authored
perf: Add an adaptive integer membership prefilter for hash joins (apache#25363)
## Which issue does this PR close? <!-- We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes apache#123` indicates that this PR will close issue apache#123. --> - Closes #. ## Rationale for this change <!-- Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed. Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes. Please explain the problem you are trying to solve in terms of the user-visible behavior, rather than the implementation. For example, "The code in `foo.rs` doesn't handle nulls" is a symptom of the implementation. "COUNT(DISTINCT) returns wrong results when the column contains nulls" is the user-visible problem. --> Hash joins can spend substantial time looking up probe keys that do not exist on the build side. For a single integer key with a bounded range, an exact membership bitmap can reject these keys cheaply before hash table lookup. This helps when many nonmatching keys reach the join, including when dynamic filters cannot be pushed down to the input. For example, in the measured TPC-H SF1 plans, the `RightSemi` join on `part.p_partkey = lineitem.l_partkey` receives approximately 6 million probe rows. With memtable inputs or the default Parquet configuration: - **Q8:** Only **0.73%** of probe rows match the filtered build side, resulting in approximately 5.96 million unsuccessful hash table lookups. - **Q9:** Only **5.32%** of probe rows match the filtered build side, resulting in approximately 5.68 million unsuccessful hash table lookups. These low probe hit rates leave substantial room to avoid unsuccessful lookups, reflected in both the query-latency and operator-level measurements below. The extra membership check is less useful when most keys match. An adaptive policy pauses filtering when the observed pruning ratio is low and periodically samples again as the input changes. ## What changes are included in this PR? <!-- There is no need to duplicate the description in the issue here, but it is sometimes worth providing a summary of the individual changes in this PR. --> - Build an optional integer membership bitmap for eligible single-key HashMap joins in both CollectLeft and Partitioned modes. ArrayMap and null-aware joins retain their existing paths. - Generate a lookup mask for each probe batch, skipping hash table lookups for absent keys. Preserve the original probe rows and NULL handling so outer, anti, and mark join semantics remain unchanged. Hash computation is unchanged. - Track pruning independently in each probe stream. Unproductive sampling windows trigger progressively longer pauses; productive samples reset the pause interval. - Account for bitmap and mask memory through the memory pool, falling back to normal lookup when an optional reservation cannot be satisfied. - Add configuration, documentation, creation/pruning metrics, and the `hash_join_probe` microbenchmark. ## What is the testing strategy for this PR? <!-- We typically require tests for all PRs in order to: 1. Prevent the code from being accidentally broken by subsequent changes 2. Serve as another way to document the expected behavior of the code Briefly describe how this PR is tested, and point to the specific tests you added. For example: 'This new feature is covered by the `sqllogictest` cases added in `foo.slt`'. If this PR does not add tests, explain why. For example, if the change is already covered by existing tests, please mention it. You should also check the `codecov` bot reply on this PR to confirm the changed code is exercised. --> - Unit tests cover membership and integer boundaries, range overflow, bitmap boundaries, adaptive sampling/backoff, and sliced validity masks. - HashJoin tests cover fallback paths, memory reservation failures, and independent probe-stream adaptation with a shared build bitmap. - `hash_join_integer_prefilter.slt` covers duplicate matches, unmatched rows, NULL equality, inner/full/semi/anti joins, null-aware IN/NOT IN behavior, range limits, and creation/pruning metrics. ## Are there any user-facing changes? <!-- If there are user-facing changes then we may require documentation to be updated before approving the PR. If there are any breaking changes to public APIs, please add the `api change` label. --> The feature is opt-in and disabled by default. It can be enabled with: ```sql SET datafusion.execution.enable_join_integer_prefilter = true; ``` Additional execution options control the maximum key range (default `262144`), minimum pruning ratio (`0.5`), and sampling window (`12288` input rows). The metrics `integer_prefilter_created_count` and `probe_prefilter_rows_pruned` expose whether the prefilter was created and how many probe rows skipped lookup. Query results are unchanged. ## Benchmarks ### Microbench: `hash_join_probe` | Workload | Main | Off | On | On vs main | |---|---:|---:|---:|---:| | RightSemi, 10% interleaved hits | 5.335 | 5.293 | 3.985 | -25.3% | | RightAnti, 10% interleaved hits | 10.849 | 10.933 | 9.479 | -12.6% | | Inner, 10% interleaved hits | 6.114 | 6.164 | 4.802 | -21.4% | | RightSemi, 10% clustered hits | 4.286 | 4.338 | 3.549 | -17.2% | | RightAnti, 10% clustered hits | 10.172 | 11.633 | 8.969 | -11.8% | | RightSemi, all hits | 13.066 | 12.897 | 13.061 | -0.0% | | RightAnti, all hits | 5.920 | 5.924 | 6.112 | +3.2% | | Inner, all hits | 19.235 | 19.567 | 19.565 | +1.7% | | RightSemi, high-to-low hit rate | 9.096 | 9.405 | 9.203 | +1.2% | | RightAnti, high-to-low hit rate | 8.480 | 8.478 | 8.408 | -0.8% | | RightSemi, single probe batch, all hits | 0.205 | 0.217 | 0.258 | +25.9% | | RightSemi, dense 100K build, all hits | 10.172 | 10.264 | 10.107 | -0.6% | | RightSemi, sparse 100K build, all hits | 15.579 | 15.568 | 15.567 | -0.1% | ### TPC-H with memtable | Query | Main | Off | On | On vs main | |---|---:|---:|---:|---:| | Q8 | 25.332 | 23.381 | 16.080 | -36.5% | | Q9 | 48.990 | 46.381 | 41.653 | -15.0% | | Q17 | 67.344 | 66.039 | 43.156 | -35.9% | ### TPC-H with parquet with the default `datafusion.execution.parquet.pushdown_filters=false` | Query | Main | Off | On | On vs main | | ----- | -----: | -----: | -----: | ---------: | | Q8 | 63.736 | 63.243 | 58.271 | -8.6% | | Q9 | 76.014 | 74.103 | 70.175 | -7.7% | ### Target HashJoin `join_time` The following table measures the `CollectLeft` / `RightSemi` HashMap join on `part.p_partkey = lineitem.l_partkey` described above. It reports **operator `join_time`, summed across the four probe partitions**, separately from end-to-end query latency. | Input | Query | Main | Off | On | On vs main | | ----------------- | ----- | -----: | -----: | -----: | ---------: | | MemTable | Q8 | 29.330 | 29.625 | 12.045 | -58.9% | | MemTable | Q9 | 39.985 | 40.010 | 26.415 | -33.9% | | Parquet (default) | Q8 | 29.685 | 29.820 | 11.190 | -62.3% | | Parquet (default) | Q9 | 35.830 | 35.305 | 20.525 | -42.7% |
1 parent 4e6e564 commit 334f293

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)