Skip to content

Commit 9b71f36

Browse files
gruuyadiscord9
authored andcommitted
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]> Backport provenance: - Upstream PR: apache#25602 - Upstream commit: 4bb9f8d - Upstream additions/removals and self-tests retained; fork codec/import context is resolved separately. Signed-off-by: discord9 <[email protected]> (cherry picked from commit d787bc3)
1 parent 7cf6172 commit 9b71f36

14 files changed

Lines changed: 876 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, reorder_output_after_swap,
4546
swap_join_projection, update_hash,
@@ -2615,7 +2616,10 @@ async fn collect_left_input(
26152616

26162617
let map = Arc::new(join_hash_map);
26172618

2618-
let membership = if num_rows == 0 {
2619+
// For an ordinary build, nothing reads the strategy unless this join's own
2620+
// dynamic filter accumulator exists. A prepared build is shared with joins
2621+
// decided later, so it must always be ready to serve one.
2622+
let membership = if num_rows == 0 || (!prepared && !should_compute_dynamic_filters) {
26192623
PushdownStrategy::Empty
26202624
} else {
26212625
// If the build side is small enough we can use IN list pushdown.
@@ -2625,19 +2629,45 @@ async fn collect_left_input(
26252629
.iter()
26262630
.map(|arr| arr.get_array_memory_size())
26272631
.sum::<usize>();
2628-
if left_values.is_empty()
2629-
|| left_values[0].is_empty()
2630-
|| estimated_size > config.optimizer.hash_join_inlist_pushdown_max_size
2631-
|| map.num_of_distinct_key()
2632-
> config
2632+
2633+
let pushdown_inlist = !left_values.is_empty()
2634+
&& !left_values[0].is_empty()
2635+
&& estimated_size <= config.optimizer.hash_join_inlist_pushdown_max_size
2636+
&& map.num_of_distinct_key()
2637+
<= config
26332638
.optimizer
2634-
.hash_join_inlist_pushdown_max_distinct_values
2639+
.hash_join_inlist_pushdown_max_distinct_values;
2640+
2641+
if pushdown_inlist
2642+
&& let Some(in_list_values) = build_struct_inlist_values(&left_values)?
26352643
{
2636-
PushdownStrategy::Map(Arc::clone(&map))
2637-
} else if let Some(in_list_values) = build_struct_inlist_values(&left_values)? {
26382644
PushdownStrategy::InList(in_list_values)
26392645
} else {
2640-
PushdownStrategy::Map(Arc::clone(&map))
2646+
// Past the InList threshold use a bucket bitmap for container pruning.
2647+
let pruning_bitmap = match (left_values.as_slice(), bounds.as_ref()) {
2648+
([keys], Some(bounds)) if !keys.is_empty() => bounds
2649+
.get_column_bounds(0)
2650+
.and_then(|b| {
2651+
KeyRangeBitmap::try_new(
2652+
keys,
2653+
&b.min,
2654+
&b.max,
2655+
map.num_of_distinct_key(),
2656+
)
2657+
})
2658+
.map(Arc::new),
2659+
_ => None,
2660+
};
2661+
// Held for the join's lifetime, so charge it like the maps; it is
2662+
// optional, so skip it rather than fail when the pool is full.
2663+
let pruning_bitmap = pruning_bitmap.filter(|bitmap| {
2664+
let ok = reservation.try_grow(bitmap.size()).is_ok();
2665+
if ok {
2666+
metrics.build_mem_used.add(bitmap.size());
2667+
}
2668+
ok
2669+
});
2670+
PushdownStrategy::Map(Arc::clone(&map), pruning_bitmap)
26412671
}
26422672
};
26432673

@@ -2785,6 +2815,71 @@ mod tests {
27852815
Ok(())
27862816
}
27872817

2818+
/// Runs a join whose 200 keys spread over 2M would size a pruning bitmap
2819+
/// at the 128 KiB cap, and reports the bytes the build side reserved.
2820+
///
2821+
/// Forces the IN-list threshold off: under `force_hash_collisions` every
2822+
/// key hashes to the same bucket, so `num_of_distinct_key()` no longer
2823+
/// reflects the real 200 distinct keys and would otherwise take the
2824+
/// IN-list branch instead of the one under test.
2825+
async fn build_mem_used(limit: usize, dynamic_filters: bool) -> Result<usize> {
2826+
let schema = Arc::new(Schema::new(vec![Field::new("k", DataType::Int64, false)]));
2827+
let batch = |keys: Vec<i64>| {
2828+
let column = Arc::new(Int64Array::from(keys)) as ArrayRef;
2829+
let batch = RecordBatch::try_new(Arc::clone(&schema), vec![column])?;
2830+
TestMemoryExec::try_new_exec(&[vec![batch]], Arc::clone(&schema), None)
2831+
};
2832+
let on = vec![(
2833+
Arc::new(Column::new_with_schema("k", &schema)?) as _,
2834+
Arc::new(Column::new_with_schema("k", &schema)?) as _,
2835+
)];
2836+
let build = batch((0..200).map(|i| i * 10_000).collect())?;
2837+
let probe = batch(vec![0, 500_000, 1_500_000])?;
2838+
let join = if dynamic_filters {
2839+
hash_join_with_dynamic_filter(build, probe, on, JoinType::Inner)?.0
2840+
} else {
2841+
join(
2842+
build,
2843+
probe,
2844+
on,
2845+
&JoinType::Inner,
2846+
NullEquality::NullEqualsNothing,
2847+
)?
2848+
};
2849+
2850+
let runtime = RuntimeEnvBuilder::new()
2851+
.with_memory_limit(limit, 1.0)
2852+
.build_arc()?;
2853+
let mut config = SessionConfig::new();
2854+
config
2855+
.options_mut()
2856+
.optimizer
2857+
.hash_join_inlist_pushdown_max_size = 0;
2858+
let task_ctx = Arc::new(
2859+
TaskContext::default()
2860+
.with_runtime(runtime)
2861+
.with_session_config(config),
2862+
);
2863+
let batches = common::collect(join.execute(0, task_ctx)?).await?;
2864+
assert_eq!(batches.iter().map(|b| b.num_rows()).sum::<usize>(), 3);
2865+
Ok(join
2866+
.metrics()
2867+
.unwrap()
2868+
.sum_by_name("build_mem_used")
2869+
.unwrap()
2870+
.as_usize())
2871+
}
2872+
2873+
/// The bitmap is pruning-only: never built when no dynamic filter will read
2874+
/// it, and dropped rather than fatal when the pool cannot fit it.
2875+
#[tokio::test]
2876+
async fn pruning_bitmap_is_optional() -> Result<()> {
2877+
assert!(build_mem_used(1_000_000, false).await? < 100_000);
2878+
assert!(build_mem_used(1_000_000, true).await? > 100_000);
2879+
build_mem_used(100_000, true).await?;
2880+
Ok(())
2881+
}
2882+
27882883
#[derive(Debug)]
27892884
struct PartitionedTestExec {
27902885
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: 59 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -35,6 +35,7 @@ use datafusion_physical_expr_common::physical_expr::{
3535
};
3636

3737
use crate::joins::Map;
38+
use crate::joins::key_range_bitmap::KeyRangeBitmap;
3839

3940
/// RandomState wrapper that preserves the seed used to create it.
4041
///
@@ -265,6 +266,8 @@ pub struct HashTableLookupExpr {
265266
map: Arc<Map>,
266267
/// Description for display
267268
description: String,
269+
/// Shared pruning-only view of the build side's key range
270+
pruning_bitmap: Option<Arc<KeyRangeBitmap>>,
268271
}
269272
impl HashTableLookupExpr {
270273
/// Create a new HashTableLookupExpr
@@ -274,6 +277,7 @@ impl HashTableLookupExpr {
274277
/// * `random_state` - SeededRandomState for hashing
275278
/// * `map` - Map to check membership (hash table or array map)
276279
/// * `description` - Description for debugging
280+
/// * `pruning_bitmap` - key-range summary for pruning only, or `None`
277281
/// # Note
278282
/// This is public for internal testing purposes only and is not
279283
/// guaranteed to be stable across versions.
@@ -282,14 +286,21 @@ impl HashTableLookupExpr {
282286
random_state: SeededRandomState,
283287
map: Arc<Map>,
284288
description: String,
289+
pruning_bitmap: Option<Arc<KeyRangeBitmap>>,
285290
) -> Self {
286291
Self {
287292
on_columns,
288293
random_state,
289294
map,
290295
description,
296+
pruning_bitmap,
291297
}
292298
}
299+
300+
/// Which parts of this build side's key range hold keys, for container pruning.
301+
pub fn pruning_bitmap(&self) -> Option<&Arc<KeyRangeBitmap>> {
302+
self.pruning_bitmap.as_ref()
303+
}
293304
}
294305
impl std::fmt::Debug for HashTableLookupExpr {
295306
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
@@ -342,12 +353,13 @@ impl PhysicalExpr for HashTableLookupExpr {
342353
self: Arc<Self>,
343354
children: Vec<Arc<dyn PhysicalExpr>>,
344355
) -> Result<Arc<dyn PhysicalExpr>> {
345-
Ok(Arc::new(HashTableLookupExpr::new(
346-
children,
347-
self.random_state.clone(),
348-
Arc::clone(&self.map),
349-
self.description.clone(),
350-
)))
356+
Ok(Arc::new(HashTableLookupExpr {
357+
on_columns: children,
358+
random_state: self.random_state.clone(),
359+
map: Arc::clone(&self.map),
360+
description: self.description.clone(),
361+
pruning_bitmap: self.pruning_bitmap.clone(),
362+
}))
351363
}
352364

353365
fn data_type(&self, _input_schema: &Schema) -> Result<DataType> {
@@ -427,6 +439,7 @@ fn evaluate_columns(
427439
mod tests {
428440
use super::*;
429441
use crate::joins::join_hash_map::JoinHashMapU32;
442+
use datafusion_common::ScalarValue;
430443
use datafusion_physical_expr::expressions::Column;
431444
use std::collections::hash_map::DefaultHasher;
432445
use std::hash::Hasher;
@@ -437,6 +450,36 @@ mod tests {
437450
hasher.finish()
438451
}
439452

453+
/// The pruning bitmap must survive `with_new_children`, which a scan calls
454+
/// once per file.
455+
#[test]
456+
fn test_pruning_bitmap_shared_with_derived_children() {
457+
let keys: ArrayRef = Arc::new(arrow::array::Int64Array::from(vec![0, 1_000_000]));
458+
let bitmap = Arc::new(
459+
KeyRangeBitmap::try_new(
460+
&keys,
461+
&ScalarValue::Int64(Some(0)),
462+
&ScalarValue::Int64(Some(1_000_000)),
463+
2,
464+
)
465+
.expect("two keys a million apart leave prunable gaps"),
466+
);
467+
let expr = Arc::new(HashTableLookupExpr::new(
468+
vec![Arc::new(Column::new("a", 0))],
469+
SeededRandomState::with_seed(1),
470+
Arc::new(Map::HashMap(Box::new(JoinHashMapU32::with_capacity(10)))),
471+
"hash_lookup".to_string(),
472+
Some(Arc::clone(&bitmap)),
473+
));
474+
475+
let derived = expr
476+
.with_new_children(vec![Arc::new(Column::new("a", 7))])
477+
.unwrap();
478+
let derived = derived.downcast_ref::<HashTableLookupExpr>().unwrap();
479+
assert_eq!(derived.children()[0].to_string(), "a@7");
480+
assert!(Arc::ptr_eq(&bitmap, derived.pruning_bitmap().unwrap()));
481+
}
482+
440483
#[test]
441484
fn test_hash_expr_eq_same() {
442485
let col_a: PhysicalExprRef = Arc::new(Column::new("a", 0));
@@ -715,13 +758,15 @@ mod tests {
715758
SeededRandomState::with_seed(1),
716759
Arc::clone(&hash_map),
717760
"lookup".to_string(),
761+
None,
718762
);
719763

720764
let expr2 = HashTableLookupExpr::new(
721765
vec![Arc::clone(&col_a)],
722766
SeededRandomState::with_seed(1),
723767
Arc::clone(&hash_map),
724768
"lookup".to_string(),
769+
None,
725770
);
726771

727772
assert_eq!(expr1, expr2);
@@ -740,13 +785,15 @@ mod tests {
740785
SeededRandomState::with_seed(1),
741786
Arc::clone(&hash_map),
742787
"lookup".to_string(),
788+
None,
743789
);
744790

745791
let expr2 = HashTableLookupExpr::new(
746792
vec![Arc::clone(&col_b)],
747793
SeededRandomState::with_seed(1),
748794
Arc::clone(&hash_map),
749795
"lookup".to_string(),
796+
None,
750797
);
751798

752799
assert_ne!(expr1, expr2);
@@ -763,13 +810,15 @@ mod tests {
763810
SeededRandomState::with_seed(1),
764811
Arc::clone(&hash_map),
765812
"lookup_one".to_string(),
813+
None,
766814
);
767815

768816
let expr2 = HashTableLookupExpr::new(
769817
vec![Arc::clone(&col_a)],
770818
SeededRandomState::with_seed(1),
771819
Arc::clone(&hash_map),
772820
"lookup_two".to_string(),
821+
None,
773822
);
774823

775824
assert_ne!(expr1, expr2);
@@ -789,13 +838,15 @@ mod tests {
789838
SeededRandomState::with_seed(1),
790839
hash_map1,
791840
"lookup".to_string(),
841+
None,
792842
);
793843

794844
let expr2 = HashTableLookupExpr::new(
795845
vec![Arc::clone(&col_a)],
796846
SeededRandomState::with_seed(1),
797847
hash_map2,
798848
"lookup".to_string(),
849+
None,
799850
);
800851

801852
// Different Arc pointers means not equal (uses Arc::ptr_eq)
@@ -813,13 +864,15 @@ mod tests {
813864
SeededRandomState::with_seed(1),
814865
Arc::clone(&hash_map),
815866
"lookup".to_string(),
867+
None,
816868
);
817869

818870
let expr2 = HashTableLookupExpr::new(
819871
vec![Arc::clone(&col_a)],
820872
SeededRandomState::with_seed(1),
821873
Arc::clone(&hash_map),
822874
"lookup".to_string(),
875+
None,
823876
);
824877

825878
// Equal expressions should have equal hashes

0 commit comments

Comments
 (0)