Skip to content

Commit 75125ad

Browse files
committed
Skipped the probe-NULL widening when the build has no NULL keys.
A probe NULL can only null-match an actual build NULL. Arrow tracks null counts per array, so detecting one costs no data scan. A canceled partition's content is unknown, so it counts as holding one.
1 parent d090cf5 commit 75125ad

2 files changed

Lines changed: 112 additions & 18 deletions

File tree

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

Lines changed: 100 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -282,10 +282,12 @@ pub(crate) enum PartitionBuildData {
282282
partition_id: usize,
283283
pushdown: PushdownStrategy,
284284
bounds: PartitionBounds,
285+
keys_have_null: bool,
285286
},
286287
CollectLeft {
287288
pushdown: PushdownStrategy,
288289
bounds: PartitionBounds,
290+
keys_have_null: bool,
289291
},
290292
}
291293

@@ -294,6 +296,9 @@ pub(crate) enum PartitionBuildData {
294296
struct PartitionData {
295297
bounds: PartitionBounds,
296298
pushdown: PushdownStrategy,
299+
/// Whether any build key of this partition is NULL. Decides whether the pushed
300+
/// filter must keep probe-side NULL rows for a null-equal join to match them.
301+
keys_have_null: bool,
297302
}
298303

299304
/// Build-side data organized by partition mode
@@ -469,6 +474,7 @@ impl SharedBuildAccumulator {
469474
partition_id,
470475
pushdown,
471476
bounds,
477+
keys_have_null,
472478
},
473479
AccumulatedBuildData::Partitioned {
474480
partitions,
@@ -478,19 +484,30 @@ impl SharedBuildAccumulator {
478484
if matches!(partitions[partition_id], PartitionStatus::Pending) {
479485
*completed_partitions += 1;
480486
}
481-
partitions[partition_id] =
482-
PartitionStatus::Reported(PartitionData { pushdown, bounds });
487+
partitions[partition_id] = PartitionStatus::Reported(PartitionData {
488+
pushdown,
489+
bounds,
490+
keys_have_null,
491+
});
483492
}
484493
(
485-
PartitionBuildData::CollectLeft { pushdown, bounds },
494+
PartitionBuildData::CollectLeft {
495+
pushdown,
496+
bounds,
497+
keys_have_null,
498+
},
486499
AccumulatedBuildData::CollectLeft {
487500
data,
488501
reported_count,
489502
..
490503
},
491504
) => {
492505
if matches!(data, PartitionStatus::Pending) {
493-
*data = PartitionStatus::Reported(PartitionData { pushdown, bounds });
506+
*data = PartitionStatus::Reported(PartitionData {
507+
pushdown,
508+
bounds,
509+
keys_have_null,
510+
});
494511
}
495512
*reported_count += 1;
496513
}
@@ -592,8 +609,10 @@ impl SharedBuildAccumulator {
592609
if let Some(filter_expr) =
593610
combine_membership_and_bounds(membership_expr, bounds_expr)
594611
{
595-
self.dynamic_filter
596-
.update(self.preserve_probe_nulls(filter_expr)?)?;
612+
self.dynamic_filter.update(self.preserve_probe_nulls(
613+
filter_expr,
614+
partition_data.keys_have_null,
615+
)?)?;
597616
}
598617
}
599618
PartitionStatus::Pending => {
@@ -624,6 +643,7 @@ impl SharedBuildAccumulator {
624643
let mut real_branches = Vec::new();
625644
let mut empty_partition_ids = Vec::new();
626645
let mut has_canceled_unknown = false;
646+
let mut keys_have_null = false;
627647

628648
for (partition_id, partition) in partitions.iter().enumerate() {
629649
match partition {
@@ -633,6 +653,7 @@ impl SharedBuildAccumulator {
633653
empty_partition_ids.push(partition_id);
634654
}
635655
PartitionStatus::Reported(partition) => {
656+
keys_have_null |= partition.keys_have_null;
636657
let membership_expr = create_membership_predicate(
637658
&self.on_right,
638659
partition.pushdown.clone(),
@@ -655,6 +676,9 @@ impl SharedBuildAccumulator {
655676
}
656677
PartitionStatus::CanceledUnknown => {
657678
has_canceled_unknown = true;
679+
// A canceled partition's build content is unknown, so it
680+
// may hold a NULL key.
681+
keys_have_null = true;
658682
}
659683
PartitionStatus::Pending => {
660684
return datafusion_common::internal_err!(
@@ -700,7 +724,7 @@ impl SharedBuildAccumulator {
700724
};
701725

702726
self.dynamic_filter
703-
.update(self.preserve_probe_nulls(filter_expr)?)?;
727+
.update(self.preserve_probe_nulls(filter_expr, keys_have_null)?)?;
704728
}
705729
}
706730

@@ -717,8 +741,16 @@ impl SharedBuildAccumulator {
717741
fn preserve_probe_nulls(
718742
&self,
719743
filter_expr: Arc<dyn PhysicalExpr>,
744+
build_keys_have_null: bool,
720745
) -> Result<Arc<dyn PhysicalExpr>> {
721-
if self.null_equality != NullEquality::NullEqualsNull && !self.null_aware {
746+
// A null-aware anti join needs every probe NULL no matter what the build holds: one
747+
// probe NULL makes `NOT IN` unknown for every build row. A null-equal join needs probe
748+
// NULLs only to match an actual build-side NULL, so a NULL-free build keeps the filter
749+
// at full selectivity.
750+
let needs_probe_nulls = self.null_aware
751+
|| (self.null_equality == NullEquality::NullEqualsNull
752+
&& build_keys_have_null);
753+
if !needs_probe_nulls {
722754
return Ok(filter_expr);
723755
}
724756
// Only a key that can actually be NULL needs the disjunct; a NOT NULL key never widens.
@@ -879,7 +911,11 @@ mod tests {
879911
}
880912

881913
fn reported(pushdown: PushdownStrategy, bounds: PartitionBounds) -> PartitionStatus {
882-
PartitionStatus::Reported(PartitionData { pushdown, bounds })
914+
PartitionStatus::Reported(PartitionData {
915+
pushdown,
916+
bounds,
917+
keys_have_null: false,
918+
})
883919
}
884920

885921
fn current_expr(acc: &SharedBuildAccumulator) -> PhysicalExprRef {
@@ -1060,6 +1096,7 @@ mod tests {
10601096
partition_id: 0,
10611097
pushdown: PushdownStrategy::Empty,
10621098
bounds: PartitionBounds::new(vec![]),
1099+
keys_have_null: false,
10631100
},
10641101
)
10651102
.unwrap();
@@ -1097,9 +1134,11 @@ mod tests {
10971134
assert_eq!(completed, 1);
10981135
}
10991136

1100-
fn null_equal_accumulator(
1137+
fn null_semantics_accumulator(
11011138
probe_schema: Arc<Schema>,
11021139
on_right: Vec<PhysicalExprRef>,
1140+
null_equality: NullEquality,
1141+
null_aware: bool,
11031142
) -> SharedBuildAccumulator {
11041143
SharedBuildAccumulator {
11051144
inner: Mutex::new(AccumulatorState {
@@ -1114,11 +1153,23 @@ mod tests {
11141153
on_right,
11151154
repartition_random_state: SeededRandomState::with_seed(1),
11161155
probe_schema,
1117-
null_equality: NullEquality::NullEqualsNull,
1118-
null_aware: false,
1156+
null_equality,
1157+
null_aware,
11191158
}
11201159
}
11211160

1161+
fn null_equal_accumulator(
1162+
probe_schema: Arc<Schema>,
1163+
on_right: Vec<PhysicalExprRef>,
1164+
) -> SharedBuildAccumulator {
1165+
null_semantics_accumulator(
1166+
probe_schema,
1167+
on_right,
1168+
NullEquality::NullEqualsNull,
1169+
false,
1170+
)
1171+
}
1172+
11221173
#[test]
11231174
fn preserve_probe_nulls_only_widens_nullable_keys() {
11241175
let probe_schema = Arc::new(Schema::new(vec![
@@ -1132,7 +1183,7 @@ mod tests {
11321183
let acc = null_equal_accumulator(probe_schema, on_right);
11331184

11341185
// Only the nullable key earns an IS NULL disjunct; the NOT NULL key is left out.
1135-
let widened = acc.preserve_probe_nulls(lit(true)).unwrap();
1186+
let widened = acc.preserve_probe_nulls(lit(true), true).unwrap();
11361187
assert_eq!(format!("{widened}").matches("IS NULL").count(), 1);
11371188
}
11381189

@@ -1148,7 +1199,7 @@ mod tests {
11481199

11491200
// Every key is NOT NULL, so there is nothing to OR in and the filter is returned as-is.
11501201
let filter = lit(true);
1151-
let result = acc.preserve_probe_nulls(Arc::clone(&filter)).unwrap();
1202+
let result = acc.preserve_probe_nulls(Arc::clone(&filter), true).unwrap();
11521203
assert_eq!(format!("{result}"), format!("{filter}"));
11531204
}
11541205

@@ -1161,6 +1212,40 @@ mod tests {
11611212
let on_right: Vec<PhysicalExprRef> = vec![Arc::new(Column::new("b", 1))];
11621213
let acc = null_equal_accumulator(probe_schema, on_right);
11631214

1164-
assert!(acc.preserve_probe_nulls(lit(true)).is_err());
1215+
assert!(acc.preserve_probe_nulls(lit(true), true).is_err());
1216+
}
1217+
1218+
#[test]
1219+
fn preserve_probe_nulls_skips_wrap_when_build_has_no_nulls() {
1220+
let probe_schema =
1221+
Arc::new(Schema::new(vec![Field::new("a", DataType::Int32, true)]));
1222+
let on_right: Vec<PhysicalExprRef> = vec![Arc::new(Column::new("a", 0))];
1223+
let acc = null_equal_accumulator(probe_schema, on_right);
1224+
1225+
// A NULL-free build has nothing for a probe NULL to null-match, so the
1226+
// filter keeps its full selectivity.
1227+
let filter = lit(true);
1228+
let result = acc
1229+
.preserve_probe_nulls(Arc::clone(&filter), false)
1230+
.unwrap();
1231+
assert_eq!(format!("{result}"), format!("{filter}"));
1232+
}
1233+
1234+
#[test]
1235+
fn preserve_probe_nulls_wraps_null_aware_regardless_of_build() {
1236+
let probe_schema =
1237+
Arc::new(Schema::new(vec![Field::new("a", DataType::Int32, true)]));
1238+
let on_right: Vec<PhysicalExprRef> = vec![Arc::new(Column::new("a", 0))];
1239+
let acc = null_semantics_accumulator(
1240+
probe_schema,
1241+
on_right,
1242+
NullEquality::NullEqualsNothing,
1243+
true,
1244+
);
1245+
1246+
// One probe NULL collapses `NOT IN` for every build row, so the wrap must not
1247+
// depend on the build content.
1248+
let widened = acc.preserve_probe_nulls(lit(true), false).unwrap();
1249+
assert_eq!(format!("{widened}").matches("IS NULL").count(), 1);
11651250
}
11661251
}

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

Lines changed: 12 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -559,16 +559,24 @@ impl HashJoinStream {
559559
.bounds
560560
.clone()
561561
.unwrap_or_else(|| PartitionBounds::new(vec![]));
562+
// Arrow tracks null counts per array, so this costs no data scan.
563+
let keys_have_null = left_data
564+
.values()
565+
.iter()
566+
.any(|array| array.null_count() > 0);
562567

563568
let build_data = match self.mode {
564569
PartitionMode::Partitioned => PartitionBuildData::Partitioned {
565570
partition_id: self.partition,
566571
pushdown,
567572
bounds,
573+
keys_have_null,
574+
},
575+
PartitionMode::CollectLeft => PartitionBuildData::CollectLeft {
576+
pushdown,
577+
bounds,
578+
keys_have_null,
568579
},
569-
PartitionMode::CollectLeft => {
570-
PartitionBuildData::CollectLeft { pushdown, bounds }
571-
}
572580
PartitionMode::Auto => unreachable!(
573581
"PartitionMode::Auto should not be present at execution time. This is a bug in DataFusion, please report it!"
574582
),
@@ -1075,6 +1083,7 @@ mod tests {
10751083
partition_id,
10761084
pushdown: PushdownStrategy::Empty,
10771085
bounds: PartitionBounds::new(vec![]),
1086+
keys_have_null: false,
10781087
}
10791088
}
10801089

0 commit comments

Comments
 (0)