Skip to content

Commit 4bb9f8d

Browse files
gruuyaclaudejayzhan211
authored
Prune hash join probe side via a build-side key range bitmap (apache#25602)
## 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 apache#25291. - Alternative to apache#25292. ## 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. --> Avoid scanning redundant files/row-groups/pages in the probe side of hash joins, based on the values dictated by the build side. ## 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. --> - wiring up PushdownStrategy::Map/HashTableLookupExpr to carry a representation of the build side values from a hash join, through - `KeyRangeBitmap` implementation, which maps the build-side values array into a finite-sized bitmap bucket, and can answer probing questions for certain ranges - extend `build_predicate_expression` to build the associated pruning expression from `HashTableLookupExpr` using the new `KeyRangeBitmapPruningExpr`, which implements `PhysicalExpr` on top of `KeyRangeBitmap` - also extend `build_predicate_expression` so that it now pushes down pruning for `CaseExprs`, since that also unlocks the partitioned hash-join scenario this pr targets ## 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. --> A number of unit tests added, and one SLT added. Also verified on the query shape that motivated the original issue ```sql > copy (select i as k, random() as v from generate_series(0, 1999999) t(i)) to '/tmp/fact.parquet' stored as parquet options ('format.max_row_group_size' '1000'); +---------+ | count | +---------+ | 2000000 | +---------+ 1 row(s) fetched. Elapsed 0.093 seconds. > create external table fact stored as parquet location '/tmp/fact.parquet'; 0 row(s) fetched. Elapsed 0.008 seconds. > create table dim as select i as k from generate_series(0, 1999999) t(i) where i % 10000 < 200; 0 row(s) fetched. Elapsed 0.014 seconds. > select count(*), sum(v) from fact join dim on fact.k = dim.k; select count(*), sum(v) from fact join dim on fact.k = dim.k; select count(*), sum(v) from fact join dim on fact.k = dim.k; select count(*), sum(v) from fact join dim on fact.k = dim.k; +----------+--------------------+ | count(*) | sum(fact.v) | +----------+--------------------+ | 40000 | 20121.308621485692 | +----------+--------------------+ 1 row(s) fetched. Elapsed 0.031 seconds. +----------+--------------------+ | count(*) | sum(fact.v) | +----------+--------------------+ | 40000 | 20121.308621485692 | +----------+--------------------+ 1 row(s) fetched. Elapsed 0.017 seconds. +----------+-------------------+ | count(*) | sum(fact.v) | +----------+-------------------+ | 40000 | 20121.30862148569 | +----------+-------------------+ 1 row(s) fetched. Elapsed 0.011 seconds. +----------+-------------------+ | count(*) | sum(fact.v) | +----------+-------------------+ | 40000 | 20121.30862148569 | +----------+-------------------+ 1 row(s) fetched. Elapsed 0.011 seconds. > explain analyze select count(*), sum(v) from fact join dim on fact.k = dim.k; ... | | DataSourceExec: file_groups={12 groups: [[tmp/fact.parquet:0..1927333], [tmp/fact.parquet:1927333..3854666], [tmp/fact.parquet:3854666..5781999], [tmp/fact.parquet:5781999..7709332], [tmp/fact.parquet:7709332..9636665], ...]}, projection=[k, v], output_ordering=[k@0 ASC NULLS LAST], file_type=parquet, predicate=DynamicFilter [ k@0 >= 0 AND k@0 <= 1990199 AND hash_lookup ], dynamic_rg_pruning=eligible, pruning_predicate=k_null_count@1 != row_count@2 AND k_max@0 >= 0 AND k_null_count@1 != row_count@2 AND k_min@3 <= 1990199 AND k_null_count@1 != row_count@2 AND KEY_RANGE_BITMAP(k_min@3, k_max@0, 20000/1048576 buckets), required_guarantees=[], metrics=[output_rows=200.0 K, elapsed_compute=9.65ms, output_bytes=25.0 MB, output_batches=200, files_ranges_pruned_statistics=12 total → 12 matched, row_groups_pruned_statistics=2.00 K total → 200 matched, row_groups_pruned_bloom_filter=200 total → 200 matched, page_index_pages_pruned=200 total → 200 matched, page_index_rows_pruned=200.0 K total → 200.0 K matched, limit_pruned_row_groups=0 total → 0 matched, batches_split=0, bytes_processed=22.1 MB, bytes_scanned=2.1 MB, file_open_errors=0, file_scan_errors=0, files_opened=12, files_processed=12, num_predicate_creation_errors=0, predicate_evaluation_errors=0, pushdown_rows_matched=0, pushdown_rows_pruned=0, row_groups_pruned_dynamic_filter=0, predicate_cache_inner_records=0, predicate_cache_records=0, bloom_filter_eval_time=64.23µs, metadata_load_time=345.27µs, page_index_eval_time=1.33ms, row_pushdown_eval_time=36ns, statistics_eval_time=896.06µs, time_elapsed_opening=6.99ms, time_elapsed_processing=24.90ms, time_elapsed_scanning_total=224.99ms, time_elapsed_scanning_until_data=25.01ms, output_rows_skew=1.19%, scan_efficiency_ratio=9.7% (2.24 M/23.13 M)] | ... ``` ## 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. --> --------- Co-authored-by: Claude Opus 5 (1M context) <[email protected]> Co-authored-by: Jay Zhan <[email protected]>
1 parent 348553b commit 4bb9f8d

14 files changed

Lines changed: 877 additions & 48 deletions

File tree

‎Cargo.lock‎

Lines changed: 1 addition & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

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

Lines changed: 105 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -40,6 +40,7 @@ use crate::joins::hash_join::stream::{
4040
BuildSide, BuildSideInitialState, HashJoinStream, HashJoinStreamState,
4141
};
4242
use crate::joins::join_hash_map::{JoinHashMapU32, JoinHashMapU64};
43+
use crate::joins::key_range_bitmap::KeyRangeBitmap;
4344
use crate::joins::utils::{
4445
OnceAsync, OnceFut, asymmetric_join_output_partitioning, emits_unmatched_left_rows,
4546
is_existence_join, reorder_output_after_swap, swap_join_projection, update_hash,
@@ -3318,7 +3319,10 @@ async fn collect_left_input(
33183319

33193320
let map = Arc::new(join_hash_map);
33203321

3321-
let membership = if num_rows == 0 {
3322+
// For an ordinary build, nothing reads the strategy unless this join's own
3323+
// dynamic filter accumulator exists. A prepared build is shared with joins
3324+
// decided later, so it must always be ready to serve one.
3325+
let membership = if num_rows == 0 || (!prepared && !should_compute_dynamic_filters) {
33223326
PushdownStrategy::Empty
33233327
} else {
33243328
// If the build side is small enough we can use IN list pushdown.
@@ -3328,19 +3332,45 @@ async fn collect_left_input(
33283332
.iter()
33293333
.map(|arr| arr.get_array_memory_size())
33303334
.sum::<usize>();
3331-
if left_values.is_empty()
3332-
|| left_values[0].is_empty()
3333-
|| estimated_size > config.optimizer.hash_join_inlist_pushdown_max_size
3334-
|| map.num_of_distinct_key()
3335-
> config
3335+
3336+
let pushdown_inlist = !left_values.is_empty()
3337+
&& !left_values[0].is_empty()
3338+
&& estimated_size <= config.optimizer.hash_join_inlist_pushdown_max_size
3339+
&& map.num_of_distinct_key()
3340+
<= config
33363341
.optimizer
3337-
.hash_join_inlist_pushdown_max_distinct_values
3342+
.hash_join_inlist_pushdown_max_distinct_values;
3343+
3344+
if pushdown_inlist
3345+
&& let Some(in_list_values) = build_struct_inlist_values(&left_values)?
33383346
{
3339-
PushdownStrategy::Map(Arc::clone(&map))
3340-
} else if let Some(in_list_values) = build_struct_inlist_values(&left_values)? {
33413347
PushdownStrategy::InList(in_list_values)
33423348
} else {
3343-
PushdownStrategy::Map(Arc::clone(&map))
3349+
// Past the InList threshold use a bucket bitmap for container pruning.
3350+
let pruning_bitmap = match (left_values.as_slice(), bounds.as_ref()) {
3351+
([keys], Some(bounds)) if !keys.is_empty() => bounds
3352+
.get_column_bounds(0)
3353+
.and_then(|b| {
3354+
KeyRangeBitmap::try_new(
3355+
keys,
3356+
&b.min,
3357+
&b.max,
3358+
map.num_of_distinct_key(),
3359+
)
3360+
})
3361+
.map(Arc::new),
3362+
_ => None,
3363+
};
3364+
// Held for the join's lifetime, so charge it like the maps; it is
3365+
// optional, so skip it rather than fail when the pool is full.
3366+
let pruning_bitmap = pruning_bitmap.filter(|bitmap| {
3367+
let ok = reservation.try_grow(bitmap.size()).is_ok();
3368+
if ok {
3369+
metrics.build_mem_used.add(bitmap.size());
3370+
}
3371+
ok
3372+
});
3373+
PushdownStrategy::Map(Arc::clone(&map), pruning_bitmap)
33443374
}
33453375
};
33463376

@@ -3519,6 +3549,71 @@ mod tests {
35193549
Ok(())
35203550
}
35213551

3552+
/// Runs a join whose 200 keys spread over 2M would size a pruning bitmap
3553+
/// at the 128 KiB cap, and reports the bytes the build side reserved.
3554+
///
3555+
/// Forces the IN-list threshold off: under `force_hash_collisions` every
3556+
/// key hashes to the same bucket, so `num_of_distinct_key()` no longer
3557+
/// reflects the real 200 distinct keys and would otherwise take the
3558+
/// IN-list branch instead of the one under test.
3559+
async fn build_mem_used(limit: usize, dynamic_filters: bool) -> Result<usize> {
3560+
let schema = Arc::new(Schema::new(vec![Field::new("k", DataType::Int64, false)]));
3561+
let batch = |keys: Vec<i64>| {
3562+
let column = Arc::new(Int64Array::from(keys)) as ArrayRef;
3563+
let batch = RecordBatch::try_new(Arc::clone(&schema), vec![column])?;
3564+
TestMemoryExec::try_new_exec(&[vec![batch]], Arc::clone(&schema), None)
3565+
};
3566+
let on = vec![(
3567+
Arc::new(Column::new_with_schema("k", &schema)?) as _,
3568+
Arc::new(Column::new_with_schema("k", &schema)?) as _,
3569+
)];
3570+
let build = batch((0..200).map(|i| i * 10_000).collect())?;
3571+
let probe = batch(vec![0, 500_000, 1_500_000])?;
3572+
let join = if dynamic_filters {
3573+
hash_join_with_dynamic_filter(build, probe, on, JoinType::Inner)?.0
3574+
} else {
3575+
join(
3576+
build,
3577+
probe,
3578+
on,
3579+
&JoinType::Inner,
3580+
NullEquality::NullEqualsNothing,
3581+
)?
3582+
};
3583+
3584+
let runtime = RuntimeEnvBuilder::new()
3585+
.with_memory_limit(limit, 1.0)
3586+
.build_arc()?;
3587+
let mut config = SessionConfig::new();
3588+
config
3589+
.options_mut()
3590+
.optimizer
3591+
.hash_join_inlist_pushdown_max_size = 0;
3592+
let task_ctx = Arc::new(
3593+
TaskContext::default()
3594+
.with_runtime(runtime)
3595+
.with_session_config(config),
3596+
);
3597+
let batches = common::collect(join.execute(0, task_ctx)?).await?;
3598+
assert_eq!(batches.iter().map(|b| b.num_rows()).sum::<usize>(), 3);
3599+
Ok(join
3600+
.metrics()
3601+
.unwrap()
3602+
.sum_by_name("build_mem_used")
3603+
.unwrap()
3604+
.as_usize())
3605+
}
3606+
3607+
/// The bitmap is pruning-only: never built when no dynamic filter will read
3608+
/// it, and dropped rather than fatal when the pool cannot fit it.
3609+
#[tokio::test]
3610+
async fn pruning_bitmap_is_optional() -> Result<()> {
3611+
assert!(build_mem_used(1_000_000, false).await? < 100_000);
3612+
assert!(build_mem_used(1_000_000, true).await? > 100_000);
3613+
build_mem_used(100_000, true).await?;
3614+
Ok(())
3615+
}
3616+
35223617
#[derive(Debug)]
35233618
struct PartitionedTestExec {
35243619
cache: Arc<PlanProperties>,

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

Lines changed: 10 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -785,7 +785,9 @@ async fn prepared_inlist_shares_accounted_build_buffers() -> Result<()> {
785785
assert_eq!(counter.count_batch(&membership_batch), 0);
786786
drop(membership_batch);
787787

788-
// Disabling IN-list membership changes no retained key buffers.
788+
// Disabling IN-list membership shares the same key buffers; a
789+
// pruning bitmap, when the sparse two-key range earns one, adds
790+
// its own bytes on top.
789791
let mut config = ConfigOptions::default();
790792
config.optimizer.hash_join_inlist_pushdown_max_size = 0;
791793
let map = base
@@ -795,9 +797,12 @@ async fn prepared_inlist_shares_accounted_build_buffers() -> Result<()> {
795797
Arc::new(config),
796798
)
797799
.await?;
798-
assert!(matches!(map.build.membership, PushdownStrategy::Map(_)));
799-
assert_eq!(map.reserved_bytes(), bytes);
800-
assert_eq!(pool.reserved(), 2 * bytes);
800+
let PushdownStrategy::Map(_, bitmap) = &map.build.membership else {
801+
panic!("expected hash-map membership");
802+
};
803+
let bitmap_bytes = bitmap.as_ref().map_or(0, |bitmap| bitmap.size());
804+
assert_eq!(map.reserved_bytes(), bytes + bitmap_bytes);
805+
assert_eq!(pool.reserved(), 2 * bytes + bitmap_bytes);
801806
drop(map);
802807
let lease = Arc::clone(&prepared);
803808
drop(prepared);
@@ -888,7 +893,7 @@ async fn prepared_byte_keys_use_hash_membership() -> Result<()> {
888893
assert!(prepared.build.bounds.is_none());
889894
assert!(matches!(
890895
&prepared.build.membership,
891-
PushdownStrategy::Map(_)
896+
PushdownStrategy::Map(_, _)
892897
));
893898
let task = with_probe_filter(base)?
894899
.builder()

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

Lines changed: 60 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -34,6 +34,7 @@ use datafusion_expr_common::dyn_eq::DynHash;
3434
use datafusion_physical_expr_common::physical_expr::{PhysicalExpr, PhysicalExprRef};
3535

3636
use crate::joins::Map;
37+
use crate::joins::key_range_bitmap::KeyRangeBitmap;
3738

3839
/// RandomState wrapper that preserves the seed used to create it.
3940
///
@@ -284,6 +285,8 @@ pub struct HashTableLookupExpr {
284285
map: Arc<Map>,
285286
/// Description for display
286287
description: String,
288+
/// Shared pruning-only view of the build side's key range
289+
pruning_bitmap: Option<Arc<KeyRangeBitmap>>,
287290
}
288291
impl HashTableLookupExpr {
289292
/// Create a new HashTableLookupExpr
@@ -293,6 +296,7 @@ impl HashTableLookupExpr {
293296
/// * `random_state` - SeededRandomState for hashing
294297
/// * `map` - Map to check membership (hash table or array map)
295298
/// * `description` - Description for debugging
299+
/// * `pruning_bitmap` - key-range summary for pruning only, or `None`
296300
///
297301
/// # Public Only for Internal Use:
298302
/// `datafusion-proto` tests require this constructor, but it is not part of
@@ -303,14 +307,21 @@ impl HashTableLookupExpr {
303307
random_state: SeededRandomState,
304308
map: Arc<Map>,
305309
description: String,
310+
pruning_bitmap: Option<Arc<KeyRangeBitmap>>,
306311
) -> Self {
307312
Self {
308313
on_columns,
309314
random_state,
310315
map,
311316
description,
317+
pruning_bitmap,
312318
}
313319
}
320+
321+
/// Which parts of this build side's key range hold keys, for container pruning.
322+
pub fn pruning_bitmap(&self) -> Option<&Arc<KeyRangeBitmap>> {
323+
self.pruning_bitmap.as_ref()
324+
}
314325
}
315326
impl std::fmt::Debug for HashTableLookupExpr {
316327
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
@@ -363,12 +374,13 @@ impl PhysicalExpr for HashTableLookupExpr {
363374
self: Arc<Self>,
364375
children: Vec<Arc<dyn PhysicalExpr>>,
365376
) -> Result<Arc<dyn PhysicalExpr>> {
366-
Ok(Arc::new(HashTableLookupExpr::new(
367-
children,
368-
self.random_state.clone(),
369-
Arc::clone(&self.map),
370-
self.description.clone(),
371-
)))
377+
Ok(Arc::new(HashTableLookupExpr {
378+
on_columns: children,
379+
random_state: self.random_state.clone(),
380+
map: Arc::clone(&self.map),
381+
description: self.description.clone(),
382+
pruning_bitmap: self.pruning_bitmap.clone(),
383+
}))
372384
}
373385

374386
fn data_type(&self, _input_schema: &Schema) -> Result<DataType> {
@@ -414,6 +426,7 @@ impl PhysicalExpr for HashTableLookupExpr {
414426
random_state: _,
415427
map: _,
416428
description: _,
429+
pruning_bitmap: _,
417430
} = self;
418431

419432
// HashTableLookupExpr holds a runtime Arc<Map> (the build-side hash
@@ -460,6 +473,7 @@ fn evaluate_columns(
460473
mod tests {
461474
use super::*;
462475
use crate::joins::join_hash_map::JoinHashMapU32;
476+
use datafusion_common::ScalarValue;
463477
use datafusion_physical_expr::expressions::Column;
464478
use std::collections::hash_map::DefaultHasher;
465479
use std::hash::Hasher;
@@ -470,6 +484,36 @@ mod tests {
470484
hasher.finish()
471485
}
472486

487+
/// The pruning bitmap must survive `with_new_children`, which a scan calls
488+
/// once per file.
489+
#[test]
490+
fn test_pruning_bitmap_shared_with_derived_children() {
491+
let keys: ArrayRef = Arc::new(arrow::array::Int64Array::from(vec![0, 1_000_000]));
492+
let bitmap = Arc::new(
493+
KeyRangeBitmap::try_new(
494+
&keys,
495+
&ScalarValue::Int64(Some(0)),
496+
&ScalarValue::Int64(Some(1_000_000)),
497+
2,
498+
)
499+
.expect("two keys a million apart leave prunable gaps"),
500+
);
501+
let expr = Arc::new(HashTableLookupExpr::new(
502+
vec![Arc::new(Column::new("a", 0))],
503+
SeededRandomState::with_seed(1),
504+
Arc::new(Map::HashMap(Box::new(JoinHashMapU32::with_capacity(10)))),
505+
"hash_lookup".to_string(),
506+
Some(Arc::clone(&bitmap)),
507+
));
508+
509+
let derived = expr
510+
.with_new_children(vec![Arc::new(Column::new("a", 7))])
511+
.unwrap();
512+
let derived = derived.downcast_ref::<HashTableLookupExpr>().unwrap();
513+
assert_eq!(derived.children()[0].to_string(), "a@7");
514+
assert!(Arc::ptr_eq(&bitmap, derived.pruning_bitmap().unwrap()));
515+
}
516+
473517
#[test]
474518
fn test_hash_expr_eq_same() {
475519
let col_a: PhysicalExprRef = Arc::new(Column::new("a", 0));
@@ -748,13 +792,15 @@ mod tests {
748792
SeededRandomState::with_seed(1),
749793
Arc::clone(&hash_map),
750794
"lookup".to_string(),
795+
None,
751796
);
752797

753798
let expr2 = HashTableLookupExpr::new(
754799
vec![Arc::clone(&col_a)],
755800
SeededRandomState::with_seed(1),
756801
Arc::clone(&hash_map),
757802
"lookup".to_string(),
803+
None,
758804
);
759805

760806
assert_eq!(expr1, expr2);
@@ -773,13 +819,15 @@ mod tests {
773819
SeededRandomState::with_seed(1),
774820
Arc::clone(&hash_map),
775821
"lookup".to_string(),
822+
None,
776823
);
777824

778825
let expr2 = HashTableLookupExpr::new(
779826
vec![Arc::clone(&col_b)],
780827
SeededRandomState::with_seed(1),
781828
Arc::clone(&hash_map),
782829
"lookup".to_string(),
830+
None,
783831
);
784832

785833
assert_ne!(expr1, expr2);
@@ -796,13 +844,15 @@ mod tests {
796844
SeededRandomState::with_seed(1),
797845
Arc::clone(&hash_map),
798846
"lookup_one".to_string(),
847+
None,
799848
);
800849

801850
let expr2 = HashTableLookupExpr::new(
802851
vec![Arc::clone(&col_a)],
803852
SeededRandomState::with_seed(1),
804853
Arc::clone(&hash_map),
805854
"lookup_two".to_string(),
855+
None,
806856
);
807857

808858
assert_ne!(expr1, expr2);
@@ -822,13 +872,15 @@ mod tests {
822872
SeededRandomState::with_seed(1),
823873
hash_map1,
824874
"lookup".to_string(),
875+
None,
825876
);
826877

827878
let expr2 = HashTableLookupExpr::new(
828879
vec![Arc::clone(&col_a)],
829880
SeededRandomState::with_seed(1),
830881
hash_map2,
831882
"lookup".to_string(),
883+
None,
832884
);
833885

834886
// Different Arc pointers means not equal (uses Arc::ptr_eq)
@@ -846,13 +898,15 @@ mod tests {
846898
SeededRandomState::with_seed(1),
847899
Arc::clone(&hash_map),
848900
"lookup".to_string(),
901+
None,
849902
);
850903

851904
let expr2 = HashTableLookupExpr::new(
852905
vec![Arc::clone(&col_a)],
853906
SeededRandomState::with_seed(1),
854907
Arc::clone(&hash_map),
855908
"lookup".to_string(),
909+
None,
856910
);
857911

858912
// Equal expressions should have equal hashes

0 commit comments

Comments
 (0)