Skip to content

Commit 32f39b4

Browse files
authored
fix(physical-plan): report Final emission for LeftSemi hash and neste… (apache#24976)
## Which issue does this PR close? - apache#24962 ## Rationale for this change `HashJoinExec` and `NestedLoopJoinExec` report `LeftSemi` joins as emitting incrementally, but they only emit matched build-side rows after the probe side is exhausted. Reporting `EmissionType::Final` reflects their actual behavior and allows `SanityCheckPlan` to reject pipelines with an unbounded probe side that cannot produce output. ## What changes are included in this PR? - Classify `LeftSemi` joins as `EmissionType::Final` in both operators, regardless of the probe input's emission type. - Added unit tests verifying the emission type of LeftSemi joins in both `HashJoinExec` and `NestedLoopJoinExec`. - Add an integration test covering input swapping for an unbounded left input, rejection of an unbounded probe input, and successful planning when both inputs are bounded. ## Are these changes tested? Added unit tests verifying the emission type of LeftSemi joins in both `HashJoinExec` and `NestedLoopJoinExec`. Added an integration test covering: - Unbounded left and bounded right: planning succeeds after swapping to RightSemi. - Bounded left and unbounded right: planning is rejected. - Both inputs bounded: planning succeeds. Following test commands have been executed and passed - `cargo test -p datafusion` - `cargo test --profile=ci --test sqllogictests` - `cargo test -p datafusion` - `cargo test -p datafusion-cli` ## Are there any user-facing changes? Yes. `LeftSemi` hash and nested loop joins now report Final emission. Plans with a bounded build side and an unbounded probe side are rejected instead of being accepted despite being unable to produce output. Results for bounded inputs are unchanged.
1 parent a01dc70 commit 32f39b4

3 files changed

Lines changed: 116 additions & 34 deletions

File tree

‎datafusion/core/tests/physical_optimizer/sanity_checker.rs‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -186,6 +186,45 @@ async fn test_hash_left_join_swap() -> Result<()> {
186186
Ok(())
187187
}
188188

189+
#[tokio::test]
190+
async fn test_hash_left_semi_join() -> Result<()> {
191+
// LeftSemi hash joins emit matched build-side rows only after probing
192+
// completes, so their emission type is Final.
193+
194+
let test1 = BinaryTestCase {
195+
// The optimizer swaps the inputs and changes LeftSemi to RightSemi.
196+
// The bounded right table becomes the build side, allowing matched
197+
// rows from the unbounded left table to be emitted incrementally.
198+
source_types: (SourceType::Unbounded, SourceType::Bounded),
199+
expect_fail: false,
200+
};
201+
202+
let test2 = BinaryTestCase {
203+
// LeftSemi waits for the unbounded probe side to finish before
204+
// emitting matched build-side rows. SanityCheckPlan must reject
205+
// this pipeline because it cannot produce output.
206+
source_types: (SourceType::Bounded, SourceType::Unbounded),
207+
expect_fail: true,
208+
};
209+
210+
let test3 = BinaryTestCase {
211+
// Both inputs are bounded, so probing can finish and final output
212+
// can be emitted.
213+
source_types: (SourceType::Bounded, SourceType::Bounded),
214+
expect_fail: false,
215+
};
216+
217+
let case = QueryCase {
218+
sql: "SELECT l.c1 FROM left AS l LEFT SEMI JOIN right AS r ON l.c1 = r.c1"
219+
.to_string(),
220+
cases: vec![Arc::new(test1), Arc::new(test2), Arc::new(test3)],
221+
error_operator: "operator: HashJoinExec".to_string(),
222+
};
223+
224+
case.run().await?;
225+
Ok(())
226+
}
227+
189228
#[tokio::test]
190229
async fn test_hash_right_join_swap() -> Result<()> {
191230
let test1 = BinaryTestCase {

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

Lines changed: 40 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1218,19 +1218,22 @@ impl HashJoinExec {
12181218
}
12191219
};
12201220

1221-
let emission_type = if left.boundedness().is_unbounded() {
1222-
EmissionType::Final
1223-
} else if right.pipeline_behavior() == EmissionType::Incremental {
1224-
// Unmatched build-side rows can only be emitted once the probe side
1225-
// is exhausted; everything else is emitted incrementally.
1226-
if emits_unmatched_left_rows(join_type) {
1227-
EmissionType::Both
1221+
let emission_type =
1222+
// LeftSemi does not emit rows during probing. It records matching build-side
1223+
// rows in a bitmap and can only emit them after the probe side is exhausted.
1224+
if left.boundedness().is_unbounded() || join_type == JoinType::LeftSemi {
1225+
EmissionType::Final
1226+
} else if right.pipeline_behavior() == EmissionType::Incremental {
1227+
// Unmatched build-side rows can only be emitted once the probe side
1228+
// is exhausted; everything else is emitted incrementally.
1229+
if emits_unmatched_left_rows(join_type) {
1230+
EmissionType::Both
1231+
} else {
1232+
EmissionType::Incremental
1233+
}
12281234
} else {
1229-
EmissionType::Incremental
1230-
}
1231-
} else {
1232-
right.pipeline_behavior()
1233-
};
1235+
right.pipeline_behavior()
1236+
};
12341237

12351238
// If contains projection, update the PlanProperties.
12361239
if let Some(projection) = projection {
@@ -4732,6 +4735,31 @@ mod tests {
47324735
)
47334736
}
47344737

4738+
#[tokio::test]
4739+
async fn test_semi_left_join_reports_final_emission() -> Result<()> {
4740+
let (left_schema, right_schema, on) = build_schema_and_on()?;
4741+
4742+
let left = TestMemoryExec::try_new_exec(&[vec![]], left_schema, None)?;
4743+
4744+
let right = TestMemoryExec::try_new_exec(&[vec![]], right_schema, None)?;
4745+
4746+
let join = HashJoinExec::try_new(
4747+
left,
4748+
right,
4749+
on,
4750+
None,
4751+
&JoinType::LeftSemi,
4752+
None,
4753+
PartitionMode::CollectLeft,
4754+
NullEquality::NullEqualsNothing,
4755+
false,
4756+
)?;
4757+
4758+
assert_eq!(join.properties().emission_type, EmissionType::Final);
4759+
4760+
Ok(())
4761+
}
4762+
47354763
#[apply(hash_join_exec_configs)]
47364764
#[tokio::test]
47374765
async fn join_left_semi(

‎datafusion/physical-plan/src/joins/nested_loop_join.rs‎

Lines changed: 37 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -390,28 +390,31 @@ impl NestedLoopJoinExec {
390390
let mut output_partitioning =
391391
asymmetric_join_output_partitioning(left, right, &join_type)?;
392392

393-
let emission_type = if left.boundedness().is_unbounded() {
394-
EmissionType::Final
395-
} else if right.pipeline_behavior() == EmissionType::Incremental {
396-
match join_type {
397-
// If we only need to generate matched rows from the probe side,
398-
// we can emit rows incrementally.
399-
JoinType::Inner
400-
| JoinType::LeftSemi
401-
| JoinType::RightSemi
402-
| JoinType::Right
403-
| JoinType::RightAnti
404-
| JoinType::RightMark => EmissionType::Incremental,
405-
// If we need to generate unmatched rows from the *build side*,
406-
// we need to emit them at the end.
407-
JoinType::Left
408-
| JoinType::LeftAnti
409-
| JoinType::LeftMark
410-
| JoinType::Full => EmissionType::Both,
411-
}
412-
} else {
413-
right.pipeline_behavior()
414-
};
393+
let emission_type =
394+
// LeftSemi does not emit rows during probing. It records matching build-side
395+
// rows in a bitmap and can only emit them after the probe side is exhausted.
396+
if left.boundedness().is_unbounded() || join_type == JoinType::LeftSemi {
397+
EmissionType::Final
398+
} else if right.pipeline_behavior() == EmissionType::Incremental {
399+
match join_type {
400+
// If we only need to generate matched rows from the probe side,
401+
// we can emit rows incrementally.
402+
JoinType::Inner
403+
| JoinType::LeftSemi
404+
| JoinType::RightSemi
405+
| JoinType::Right
406+
| JoinType::RightAnti
407+
| JoinType::RightMark => EmissionType::Incremental,
408+
// If we need to generate unmatched rows from the *build side*,
409+
// we need to emit them at the end.
410+
JoinType::Left
411+
| JoinType::LeftAnti
412+
| JoinType::LeftMark
413+
| JoinType::Full => EmissionType::Both,
414+
}
415+
} else {
416+
right.pipeline_behavior()
417+
};
415418

416419
if let Some(projection) = projection {
417420
// construct a map from the input expressions to the output expression of the Projection
@@ -4954,6 +4957,18 @@ pub(crate) mod tests {
49544957
Ok(())
49554958
}
49564959

4960+
#[tokio::test]
4961+
async fn test_left_semi_join_reports_final_emission() -> Result<()> {
4962+
let left = build_left_table();
4963+
let right = build_right_table();
4964+
let join =
4965+
NestedLoopJoinExec::try_new(left, right, None, &JoinType::LeftSemi, None)?;
4966+
4967+
assert_eq!(join.properties().emission_type, EmissionType::Final);
4968+
4969+
Ok(())
4970+
}
4971+
49574972
#[rstest]
49584973
#[tokio::test]
49594974
async fn join_left_semi_with_filter(

0 commit comments

Comments
 (0)