Skip to content

Commit bed9dcd

Browse files
authored
feat: Support null aware hash mark-joins (apache#21585)
## Which issue does this PR close? - Closes apache#21309. ## Rationale for this change This change is about correctness/sql completeness, but is also a step towards better subquery de-correlation. Before this change, mark joins only produced boolean `true` / `false` results, so queries such as `(id NOT IN (...)) IS NULL` could return incorrect results, especially for correlated scalar subqueries. ## What changes are included in this PR? 1. Adds support for null-aware mark joins. 2. Make sure queries that joins that require null awareness go through a join implementation that supports that. 3. Extends decorrelation so scalar `NOT IN` mark joins use null-aware semantics when the predicate can be represented as hash join keys. I pulled tests from existing tests, a DuckDB issue I ran into, the [Story of Joins (in HyPer)](https://www.cs.cmu.edu/~15721-f24/papers/Story_of_Joins.pdf) paper and some AI generated cases. ## Are these changes tested? 1. Existing SLT tests that explicitly showed bad results. 2. New dedicated SLT tests. 5. New unit tests. ## Are there any user-facing changes? This PR changes planning behavior and introduces more public API around hash joins, the only new functionality is public function I could find is the new helper function `build_join_schema_with_null_aware` ## AI Usage *AI was used in the process of developing this PR, mostly around testing and planning* --------- Signed-off-by: Adam Gutglick <[email protected]>
1 parent 2215238 commit bed9dcd

13 files changed

Lines changed: 1584 additions & 105 deletions

File tree

‎datafusion/common/src/join_type.rs‎

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -61,9 +61,10 @@ pub enum JoinType {
6161
/// [1]. This join type is used to decorrelate EXISTS subqueries used inside disjunctive
6262
/// predicates.
6363
///
64-
/// Note: This we currently do not implement the full null semantics for the mark join described
65-
/// in [1] which will be needed if we and ANY subqueries. In our version the mark column will
66-
/// only be true for had a match and false when no match was found, never null.
64+
/// For scalar `NOT IN`, DataFusion can plan a null-aware hash mark join where the
65+
/// mark column is nullable: TRUE for a match, NULL for SQL UNKNOWN, and FALSE
66+
/// otherwise. Row-valued multi-column `NOT IN` and non-hash residual predicate
67+
/// null-aware mark semantics are not implemented.
6768
///
6869
/// [1]: http://btw2017.informatik.uni-stuttgart.de/slidesandpapers/F1-10-37/paper_web.pdf
6970
LeftMark,

‎datafusion/core/src/physical_planner.rs‎

Lines changed: 72 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -1592,6 +1592,12 @@ impl DefaultPhysicalPlanner {
15921592

15931593
let prefer_hash_join =
15941594
session_state.config_options().optimizer.prefer_hash_join;
1595+
// Null-aware joins are pinned to CollectLeft hash joins (see
1596+
// `HashJoinExec::null_aware`): never repartition them, and
1597+
// never route them to the sort-merge path below.
1598+
let can_repartition_join = session_state.config().target_partitions() > 1
1599+
&& session_state.config().repartition_joins()
1600+
&& !*null_aware;
15951601

15961602
// TODO: Allow PWMJ to deal with residual equijoin conditions
15971603
let join: Arc<dyn ExecutionPlan> = if join_on.is_empty() {
@@ -1744,32 +1750,23 @@ impl DefaultPhysicalPlanner {
17441750
vec![SortOptions::default(); join_on_len],
17451751
*null_equality,
17461752
)?)
1747-
} else if session_state.config().target_partitions() > 1
1748-
&& session_state.config().repartition_joins()
1749-
&& prefer_hash_join
1750-
&& !*null_aware
1751-
// Null-aware joins must use CollectLeft
1752-
{
1753-
Arc::new(HashJoinExec::try_new(
1754-
physical_left,
1755-
physical_right,
1756-
join_on,
1757-
join_filter,
1758-
join_type,
1759-
None,
1760-
PartitionMode::Auto,
1761-
*null_equality,
1762-
*null_aware,
1763-
)?)
17641753
} else {
1754+
// Null-aware joins need global probe-side state, so keep
1755+
// them in CollectLeft mode.
1756+
let partition_mode = if can_repartition_join {
1757+
PartitionMode::Auto
1758+
} else {
1759+
PartitionMode::CollectLeft
1760+
};
1761+
17651762
Arc::new(HashJoinExec::try_new(
17661763
physical_left,
17671764
physical_right,
17681765
join_on,
17691766
join_filter,
17701767
join_type,
17711768
None,
1772-
PartitionMode::CollectLeft,
1769+
partition_mode,
17731770
*null_equality,
17741771
*null_aware,
17751772
)?)
@@ -3991,6 +3988,63 @@ mod tests {
39913988
Ok(())
39923989
}
39933990

3991+
#[tokio::test]
3992+
async fn correlated_not_in_is_null_uses_null_aware_hash_mark_join() -> Result<()> {
3993+
let query = "
3994+
SELECT value
3995+
FROM (
3996+
VALUES
3997+
(1, 1, 'a'),
3998+
(3, 1, 'b'),
3999+
(1, 2, 'c'),
4000+
(NULL, 1, 'd'),
4001+
(5, 3, 'e'),
4002+
(2, 1, 'f'),
4003+
(NULL, 2, 'g')
4004+
) AS outer_corr_table(id, grp, value)
4005+
WHERE (id NOT IN (
4006+
SELECT id
4007+
FROM (
4008+
VALUES
4009+
(2, 1),
4010+
(NULL, 1),
4011+
(1, 2)
4012+
) AS inner_corr_table(id, grp)
4013+
WHERE inner_corr_table.grp = outer_corr_table.grp
4014+
)) IS NULL
4015+
ORDER BY value";
4016+
4017+
let config = SessionConfig::new()
4018+
.with_target_partitions(4)
4019+
.set_bool("datafusion.optimizer.prefer_hash_join", false);
4020+
let ctx = SessionContext::new_with_config(config);
4021+
4022+
let plan = ctx.sql(query).await?.create_physical_plan().await?;
4023+
let formatted = displayable(plan.as_ref()).indent(true).to_string();
4024+
assert_contains!(
4025+
&formatted,
4026+
"HashJoinExec: mode=CollectLeft, join_type=LeftMark"
4027+
);
4028+
assert!(!formatted.contains("SortMergeJoinExec"), "{formatted}");
4029+
4030+
let batches = ctx.sql(query).await?.collect().await?;
4031+
assert_batches_eq!(
4032+
&[
4033+
"+-------+",
4034+
"| value |",
4035+
"+-------+",
4036+
"| a |",
4037+
"| b |",
4038+
"| d |",
4039+
"| g |",
4040+
"+-------+",
4041+
],
4042+
&batches
4043+
);
4044+
4045+
Ok(())
4046+
}
4047+
39944048
#[tokio::test]
39954049
async fn scalar_subquery_in_projection_and_filter_plans() -> Result<()> {
39964050
let plan = plan_sql(

‎datafusion/expr/src/logical_plan/builder.rs‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1666,7 +1666,9 @@ fn mark_field(schema: &DFSchema) -> (Option<TableReference>, Arc<Field>) {
16661666

16671667
(
16681668
table_reference,
1669-
Arc::new(Field::new("mark", DataType::Boolean, false)),
1669+
// Nullable: null-aware `LeftMark` joins use NULL to represent SQL
1670+
// UNKNOWN for `NOT IN`. Other mark joins simply never produce a NULL.
1671+
Arc::new(Field::new("mark", DataType::Boolean, true)),
16701672
)
16711673
}
16721674

‎datafusion/expr/src/logical_plan/plan.rs‎

Lines changed: 9 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -4333,13 +4333,13 @@ pub struct Join {
43334333
pub schema: DFSchemaRef,
43344334
/// Defines the null equality for the join.
43354335
pub null_equality: NullEquality,
4336-
/// Whether this is a null-aware anti join (for NOT IN semantics).
4336+
/// Whether this join needs null-aware NOT IN semantics.
43374337
///
4338-
/// Only applies to LeftAnti joins. When true, implements SQL NOT IN semantics where:
4339-
/// - If the right side (subquery) contains any NULL in join keys, no rows are output
4340-
/// - Left side rows with NULL in join keys are not output
4338+
/// For `LeftAnti`, if the right side contains any NULL in join keys, no rows are output and
4339+
/// left rows with NULL join keys are also excluded.
43414340
///
4342-
/// This is required for correct NOT IN subquery behavior with three-valued logic.
4341+
/// For `LeftMark`, the generated `mark` column becomes nullable so unmatched rows can produce
4342+
/// `NULL` rather than `false` when SQL three-valued logic requires it.
43434343
pub null_aware: bool,
43444344
}
43454345

@@ -4358,7 +4358,7 @@ impl Join {
43584358
/// * `join_type` - Type of join (Inner, Left, Right, etc.)
43594359
/// * `join_constraint` - Join constraint (On, Using)
43604360
/// * `null_equality` - How to handle nulls in join comparisons
4361-
/// * `null_aware` - Whether this is a null-aware anti join (for NOT IN semantics)
4361+
/// * `null_aware` - Whether this join needs null-aware NOT IN semantics
43624362
///
43634363
/// # Returns
43644364
///
@@ -6637,7 +6637,9 @@ mod tests {
66376637

66386638
assert!(!fields[0].is_nullable());
66396639
assert!(!fields[1].is_nullable());
6640-
assert!(!fields[2].is_nullable());
6640+
// The mark column is always nullable: null-aware `LeftMark`
6641+
// joins use NULL to represent SQL UNKNOWN for `NOT IN`.
6642+
assert!(fields[2].is_nullable());
66416643
}
66426644
_ => {
66436645
assert_eq!(join.schema.fields().len(), 4);

‎datafusion/optimizer/src/decorrelate_predicate_subquery.rs‎

Lines changed: 129 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,7 @@ use std::ops::Deref;
2121
use std::sync::Arc;
2222

2323
use crate::decorrelate::PullUpCorrelatedExpr;
24+
use crate::extract_equijoin_predicate::split_eq_and_noneq_join_predicate;
2425
use crate::optimizer::ApplyOrder;
2526
use crate::utils::replace_qualified_name;
2627
use crate::{OptimizerConfig, OptimizerRule};
@@ -448,9 +449,40 @@ fn build_join(
448449
sub_query_alias.clone()
449450
};
450451

451-
// Mark joins don't use null-aware semantics (they use three-valued logic with mark column)
452+
let mark_filter_is_hashable_only =
453+
if join_type == JoinType::LeftMark && in_predicate_opt.is_some() {
454+
let (_, residual_filter) = split_eq_and_noneq_join_predicate(
455+
join_filter.clone(),
456+
left.schema(),
457+
right_projected.schema(),
458+
)?;
459+
residual_filter.is_none()
460+
} else {
461+
false
462+
};
463+
464+
// For scalar NOT IN mark joins, propagate null-aware semantics into the
465+
// nullable mark column when the predicate can be implemented by hash keys.
466+
// Non-equality correlated filters stay on the legacy path because hash join
467+
// execution cannot mark UNKNOWN candidates for residual predicates.
468+
let null_aware = join_type == JoinType::LeftMark
469+
&& in_predicate_opt.is_some()
470+
&& mark_filter_is_hashable_only
471+
&& join_keys_may_be_null(
472+
&join_filter,
473+
left.schema(),
474+
right_projected.schema(),
475+
)?;
476+
452477
let new_plan = LogicalPlanBuilder::from(left.clone())
453-
.join_on(right_projected, join_type, Some(join_filter))?
478+
.join_detailed_with_options(
479+
right_projected,
480+
join_type,
481+
(Vec::<Column>::new(), Vec::<Column>::new()),
482+
Some(join_filter),
483+
NullEquality::NullEqualsNothing,
484+
null_aware,
485+
)?
454486
.build()?;
455487

456488
debug!(
@@ -571,6 +603,43 @@ mod tests {
571603
))
572604
}
573605

606+
fn nullable_scalar_mark_scan(name: &str) -> Result<LogicalPlan> {
607+
let schema = Schema::new(vec![
608+
Field::new("id", DataType::Int32, true),
609+
Field::new("grp", DataType::Int32, true),
610+
]);
611+
table_scan(Some(name), &schema, None)?.build()
612+
}
613+
614+
fn has_null_aware_left_mark_join(plan: &LogicalPlan) -> bool {
615+
if let LogicalPlan::Join(join) = plan
616+
&& join.join_type == JoinType::LeftMark
617+
{
618+
return join.null_aware;
619+
}
620+
621+
plan.inputs().into_iter().any(has_null_aware_left_mark_join)
622+
}
623+
624+
fn has_non_null_aware_left_mark_join(plan: &LogicalPlan) -> bool {
625+
if let LogicalPlan::Join(join) = plan
626+
&& join.join_type == JoinType::LeftMark
627+
{
628+
return !join.null_aware;
629+
}
630+
631+
plan.inputs()
632+
.into_iter()
633+
.any(has_non_null_aware_left_mark_join)
634+
}
635+
636+
fn optimize_with_decorrelate(plan: LogicalPlan) -> Result<LogicalPlan> {
637+
let optimizer = crate::Optimizer::with_rules(vec![Arc::new(
638+
DecorrelatePredicateSubquery::new(),
639+
)]);
640+
optimizer.optimize(plan, &crate::OptimizerContext::new(), |_, _| {})
641+
}
642+
574643
/// Test for several IN subquery expressions
575644
#[test]
576645
fn in_subquery_multiple() -> Result<()> {
@@ -1201,6 +1270,62 @@ mod tests {
12011270
)
12021271
}
12031272

1273+
#[test]
1274+
fn correlated_not_in_mark_join_is_null_aware_for_hashable_filter() -> Result<()> {
1275+
let outer_scan = nullable_scalar_mark_scan("outer_t")?;
1276+
let inner_scan = nullable_scalar_mark_scan("inner_t")?;
1277+
1278+
let subquery = Arc::new(
1279+
LogicalPlanBuilder::from(inner_scan)
1280+
.filter(
1281+
out_ref_col(DataType::Int32, "outer_t.grp").eq(col("inner_t.grp")),
1282+
)?
1283+
.project(vec![col("inner_t.id")])?
1284+
.build()?,
1285+
);
1286+
1287+
let plan = LogicalPlanBuilder::from(outer_scan)
1288+
.filter(not_in_subquery(col("outer_t.id"), subquery).is_null())?
1289+
.build()?;
1290+
1291+
let optimized = optimize_with_decorrelate(plan)?;
1292+
assert!(
1293+
has_null_aware_left_mark_join(&optimized),
1294+
"{}",
1295+
optimized.display_indent_schema()
1296+
);
1297+
1298+
Ok(())
1299+
}
1300+
1301+
#[test]
1302+
fn correlated_not_in_mark_join_is_not_null_aware_for_residual_filter() -> Result<()> {
1303+
let outer_scan = nullable_scalar_mark_scan("outer_t")?;
1304+
let inner_scan = nullable_scalar_mark_scan("inner_t")?;
1305+
1306+
let subquery = Arc::new(
1307+
LogicalPlanBuilder::from(inner_scan)
1308+
.filter(
1309+
out_ref_col(DataType::Int32, "outer_t.grp").lt(col("inner_t.grp")),
1310+
)?
1311+
.project(vec![col("inner_t.id")])?
1312+
.build()?,
1313+
);
1314+
1315+
let plan = LogicalPlanBuilder::from(outer_scan)
1316+
.filter(not_in_subquery(col("outer_t.id"), subquery).is_null())?
1317+
.build()?;
1318+
1319+
let optimized = optimize_with_decorrelate(plan)?;
1320+
assert!(
1321+
has_non_null_aware_left_mark_join(&optimized),
1322+
"{}",
1323+
optimized.display_indent_schema()
1324+
);
1325+
1326+
Ok(())
1327+
}
1328+
12041329
#[test]
12051330
fn in_subquery_both_side_expr() -> Result<()> {
12061331
let table_scan = test_table_scan()?;
@@ -1745,8 +1870,8 @@ mod tests {
17451870
@r"
17461871
Projection: customer.c_custkey [c_custkey:Int64]
17471872
Projection: customer.c_custkey, customer.c_name [c_custkey:Int64, c_name:Utf8]
1748-
Filter: __correlated_sq_1.mark OR customer.c_custkey = Int32(1) [c_custkey:Int64, c_name:Utf8, mark:Boolean]
1749-
LeftMark Join: Filter: Boolean(true) [c_custkey:Int64, c_name:Utf8, mark:Boolean]
1873+
Filter: __correlated_sq_1.mark OR customer.c_custkey = Int32(1) [c_custkey:Int64, c_name:Utf8, mark:Boolean;N]
1874+
LeftMark Join: Filter: Boolean(true) [c_custkey:Int64, c_name:Utf8, mark:Boolean;N]
17501875
TableScan: customer [c_custkey:Int64, c_name:Utf8]
17511876
SubqueryAlias: __correlated_sq_1 [o_custkey:Int64]
17521877
Projection: orders.o_custkey [o_custkey:Int64]

‎datafusion/optimizer/src/extract_equijoin_predicate.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -174,7 +174,7 @@ impl OptimizerRule for ExtractEquijoinPredicate {
174174
///
175175
/// According to the above rule, `expr1` is the equijoin predicate, while `expr2` and `expr3` are not.
176176
/// The function returns Ok(\[expr1\], Some(expr2 AND expr3))
177-
fn split_eq_and_noneq_join_predicate(
177+
pub(crate) fn split_eq_and_noneq_join_predicate(
178178
filter: Expr,
179179
left_schema: &DFSchema,
180180
right_schema: &DFSchema,

0 commit comments

Comments
 (0)