Skip to content

Commit 8768c31

Browse files
adriangbclaude
andcommitted
Collapse an all-InList partitioned membership check into one InList
When every non-empty build partition pushes an `InList`, the routing `CASE` is redundant. Routing is a deterministic function of the key columns, so every build row holding key `K` lands in the same partition a probe row holding `K` routes to; testing `K` against the union of all the lists therefore accepts and rejects *precisely* what the `CASE` does. This is an equality, not the relaxation the bounds merge is. Collapsing drops the routing hash from the probe path entirely and leaves an `InListExpr`, which unlike a `CASE` is a shape `datafusion/pruning` understands (up to `max_in_list_size`). The union is capped at 1 MiB: each partition's list is independently limited by `hash_join_inlist_pushdown_max_size`, so the concatenation grows with the partition count, and past some size the routed `CASE` — where a probe row only ever probes one list — is the cheaper shape. Partitions that push a hash map, and builds where a canceled partition makes the union incomplete, keep the `CASE`. Co-Authored-By: Claude Opus 5 <[email protected]>
1 parent 2020202 commit 8768c31

1 file changed

Lines changed: 105 additions & 0 deletions

File tree

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

Lines changed: 105 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -34,6 +34,7 @@ use crate::joins::hash_join::partitioned_hash_eval::{
3434
HashExpr, HashTableLookupExpr, SeededRandomState,
3535
};
3636
use arrow::array::ArrayRef;
37+
use arrow::compute::concat;
3738
use arrow::datatypes::{DataType, Field, Schema};
3839
use datafusion_common::config::ConfigOptions;
3940
use datafusion_common::{
@@ -284,6 +285,15 @@ pub(crate) struct SharedBuildAccumulator {
284285
null_aware: bool,
285286
}
286287

288+
/// Ceiling on the combined size of the per-partition `InList` arrays that
289+
/// [`SharedBuildAccumulator::union_inlist_membership`] will concatenate.
290+
///
291+
/// Each partition's list is independently capped by
292+
/// `hash_join_inlist_pushdown_max_size`, so without a combined cap the union
293+
/// grows with the partition count. Past this size, keeping the routed `CASE` —
294+
/// where each probe row only ever probes one list — is the cheaper shape.
295+
const MAX_UNIONED_INLIST_BYTES: usize = 1024 * 1024;
296+
287297
/// Strategy for filter pushdown (decided at collection time)
288298
#[derive(Clone)]
289299
pub(crate) enum PushdownStrategy {
@@ -767,6 +777,13 @@ impl SharedBuildAccumulator {
767777
has_canceled_unknown: bool,
768778
include_bounds: bool,
769779
) -> Result<Arc<dyn PhysicalExpr>> {
780+
if !has_canceled_unknown
781+
&& !include_bounds
782+
&& let Some(union) = self.union_inlist_membership(real_partitions)?
783+
{
784+
return Ok(union);
785+
}
786+
770787
let mut real_branches = Vec::with_capacity(real_partitions.len());
771788
for (partition_id, partition) in real_partitions {
772789
let membership_expr = create_membership_predicate(
@@ -833,6 +850,60 @@ impl SharedBuildAccumulator {
833850
}
834851
}
835852

853+
/// Collapses an all-`InList` partitioned membership check into one `InList`
854+
/// over the union of the per-partition lists.
855+
///
856+
/// This is **exact**, not a relaxation: routing is a deterministic function
857+
/// of the key columns, so every build row holding key `K` lands in the same
858+
/// partition a probe row holding `K` routes to. Testing `K` against the
859+
/// union therefore accepts and rejects precisely what the `CASE` does, and
860+
/// the result no longer needs the routing hash at all — nor is it opaque to
861+
/// pruning the way a `CASE` is.
862+
///
863+
/// Returns `None` when the collapse does not apply (some partition pushes a
864+
/// hash map instead of a list, the lists disagree on type, or the union
865+
/// would be too large to be worth materializing).
866+
fn union_inlist_membership(
867+
&self,
868+
real_partitions: &[(usize, &PartitionData)],
869+
) -> Result<Option<Arc<dyn PhysicalExpr>>> {
870+
if real_partitions.is_empty() {
871+
return Ok(None);
872+
}
873+
874+
let mut arrays = Vec::with_capacity(real_partitions.len());
875+
let mut total_bytes = 0;
876+
for (_, partition) in real_partitions {
877+
let PushdownStrategy::InList(values) = &partition.pushdown else {
878+
return Ok(None);
879+
};
880+
total_bytes += values.get_array_memory_size();
881+
if total_bytes > MAX_UNIONED_INLIST_BYTES {
882+
return Ok(None);
883+
}
884+
if arrays
885+
.first()
886+
.is_some_and(|first: &&ArrayRef| first.data_type() != values.data_type())
887+
{
888+
return Ok(None);
889+
}
890+
arrays.push(values);
891+
}
892+
893+
let union: ArrayRef = if arrays.len() == 1 {
894+
Arc::clone(arrays[0])
895+
} else {
896+
concat(&arrays.iter().map(|a| a.as_ref()).collect::<Vec<_>>())?
897+
};
898+
899+
create_membership_predicate(
900+
&self.on_right,
901+
PushdownStrategy::InList(union),
902+
&HASH_JOIN_SEED,
903+
self.probe_schema.as_ref(),
904+
)
905+
}
906+
836907
/// Keeps probe rows with a NULL key when the join semantics need them.
837908
///
838909
/// The build-side predicate drops probe rows whose key is NULL. A null-aware anti join
@@ -1251,6 +1322,40 @@ mod tests {
12511322
);
12521323
}
12531324

1325+
#[test]
1326+
fn partitioned_all_inlist_collapses_to_a_single_union_inlist() {
1327+
let acc = make_split_partitioned_accumulator_for_test(3);
1328+
1329+
acc.build_filter(FinalizeInput::Partitioned(vec![
1330+
reported(in_list(&[1, 4]), bounds(1, 4)),
1331+
reported(in_list(&[2, 5]), bounds(2, 5)),
1332+
reported(PushdownStrategy::Empty, no_bounds()),
1333+
]))
1334+
.unwrap();
1335+
1336+
// Routing is a function of the key, so a probe key only ever matches
1337+
// the list of the partition it routes to: the union is exact and the
1338+
// `CASE` (and its routing hash) disappears entirely.
1339+
let membership_expr = current_expr(&acc);
1340+
assert!(membership_expr.downcast_ref::<CaseExpr>().is_none());
1341+
assert_in_list_column_values(&membership_expr, "probe_key", 0, &[1, 4, 2, 5]);
1342+
}
1343+
1344+
#[test]
1345+
fn partitioned_mixed_strategies_keep_the_routing_case() {
1346+
let acc = make_split_partitioned_accumulator_for_test(2);
1347+
1348+
acc.build_filter(FinalizeInput::Partitioned(vec![
1349+
reported(in_list(&[1, 2]), bounds(1, 2)),
1350+
reported(map_pushdown(), bounds(3, 4)),
1351+
]))
1352+
.unwrap();
1353+
1354+
// One partition still needs a hash-table lookup, so routing is required.
1355+
let membership_expr = current_expr(&acc);
1356+
assert_eq!(case_expr(&membership_expr).when_then_expr().len(), 2);
1357+
}
1358+
12541359
#[test]
12551360
fn partitioned_split_leaves_bounds_in_the_case_when_a_partition_is_canceled() {
12561361
let acc = make_split_partitioned_accumulator_for_test(2);

0 commit comments

Comments
 (0)