Skip to content

Commit 13c2969

Browse files
committed
account for null equality and computed keys in join ordering proofs
1 parent 0a4a474 commit 13c2969

8 files changed

Lines changed: 200 additions & 31 deletions

File tree

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

Lines changed: 116 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -3495,17 +3495,22 @@ async fn test_passthrough_wrapper_projection_keeps_ordering() -> Result<()> {
34953495

34963496
#[tokio::test]
34973497
async fn test_unique_build_hash_join_unbounded_limit() -> Result<()> {
3498-
check_unique_build_join_unbounded_limit(JoinType::Inner).await
3498+
check_unique_build_join_unbounded_limit(JoinType::Inner, false).await
34993499
}
35003500

35013501
#[tokio::test]
35023502
async fn test_unique_build_right_join_unbounded_limit() -> Result<()> {
3503-
check_unique_build_join_unbounded_limit(JoinType::Right).await
3503+
check_unique_build_join_unbounded_limit(JoinType::Right, false).await
35043504
}
35053505

35063506
#[tokio::test]
35073507
async fn test_unique_build_left_sort_merge_join_unbounded_limit() -> Result<()> {
3508-
check_unique_build_join_unbounded_limit(JoinType::Left).await
3508+
check_unique_build_join_unbounded_limit(JoinType::Left, false).await
3509+
}
3510+
3511+
#[tokio::test]
3512+
async fn test_unique_build_computed_key_join_unbounded_limit() -> Result<()> {
3513+
check_unique_build_join_unbounded_limit(JoinType::Inner, true).await
35093514
}
35103515

35113516
fn unique_join_build() -> Result<Arc<DataSourceExec>> {
@@ -3531,7 +3536,10 @@ fn unique_join_build() -> Result<Arc<DataSourceExec>> {
35313536
/// With no extra ON filter, equal probe keys match the same unique build row.
35323537
/// LIMIT must return even if the probe-key group never finishes, including when
35333538
/// the join preserves unmatched probe rows.
3534-
async fn check_unique_build_join_unbounded_limit(join_type: JoinType) -> Result<()> {
3539+
async fn check_unique_build_join_unbounded_limit(
3540+
join_type: JoinType,
3541+
computed_key: bool,
3542+
) -> Result<()> {
35353543
#[derive(Debug)]
35363544
struct PendingPartition(RecordBatch);
35373545

@@ -3560,15 +3568,22 @@ async fn check_unique_build_join_unbounded_limit(join_type: JoinType) -> Result<
35603568
true,
35613569
None,
35623570
)?);
3571+
let probe_key: Arc<dyn PhysicalExpr> = Arc::new(Column::new("probe_k", 0));
3572+
let probe_key = if computed_key {
3573+
Arc::new(BinaryExpr::new(
3574+
probe_key,
3575+
Operator::Plus,
3576+
datafusion_physical_expr::expressions::lit(1_i32),
3577+
)) as Arc<dyn PhysicalExpr>
3578+
} else {
3579+
probe_key
3580+
};
35633581
// HashJoin probes the right side. Use SMJ to exercise a left probe.
35643582
let join: Arc<dyn ExecutionPlan> = if join_type == JoinType::Left {
35653583
Arc::new(SortMergeJoinExec::try_new(
35663584
probe,
35673585
build,
3568-
vec![(
3569-
Arc::new(Column::new("probe_k", 0)),
3570-
Arc::new(Column::new("build_k", 0)),
3571-
)],
3586+
vec![(probe_key, Arc::new(Column::new("build_k", 0)))],
35723587
None,
35733588
join_type,
35743589
vec![SortOptions::default()],
@@ -3579,10 +3594,7 @@ async fn check_unique_build_join_unbounded_limit(join_type: JoinType) -> Result<
35793594
HashJoinExecBuilder::new(
35803595
build,
35813596
probe,
3582-
vec![(
3583-
Arc::new(Column::new("build_k", 0)),
3584-
Arc::new(Column::new("probe_k", 0)),
3585-
)],
3597+
vec![(Arc::new(Column::new("build_k", 0)), probe_key)],
35863598
join_type,
35873599
)
35883600
.with_partition_mode(PartitionMode::CollectLeft)
@@ -3639,7 +3651,11 @@ async fn check_unique_build_join_unbounded_limit(join_type: JoinType) -> Result<
36393651
"+---------+---------+---------+",
36403652
"| build_k | build_v | probe_k |",
36413653
"+---------+---------+---------+",
3642-
"| 1 | 100 | 1 |",
3654+
if computed_key {
3655+
"| 2 | 200 | 1 |"
3656+
} else {
3657+
"| 1 | 100 | 1 |"
3658+
},
36433659
"+---------+---------+---------+",
36443660
],
36453661
&batches
@@ -3792,3 +3808,90 @@ async fn test_projected_constraints_join_limit() -> Result<()> {
37923808
);
37933809
Ok(())
37943810
}
3811+
3812+
#[tokio::test]
3813+
async fn test_nullable_unique_build_null_equals_null_requires_sort() -> Result<()> {
3814+
let build_batch = record_batch!(
3815+
("build_k", Int32, [None, None]),
3816+
("build_v", Int32, [10, 20])
3817+
)?;
3818+
let build_schema = build_batch.schema();
3819+
assert!(build_schema.field(0).is_nullable());
3820+
let build_ordering = LexOrdering::new([
3821+
sort_expr("build_k", &build_schema),
3822+
sort_expr("build_v", &build_schema),
3823+
])
3824+
.unwrap();
3825+
let build = Arc::new(
3826+
DataSourceExec::new(Arc::new(
3827+
MemorySourceConfig::try_new(&[vec![build_batch]], build_schema, None)?
3828+
.try_with_sort_information(vec![build_ordering])?,
3829+
))
3830+
.with_constraints(Constraints::new_unverified(vec![
3831+
Constraint::Unique(vec![0]),
3832+
])),
3833+
);
3834+
let probe_batch = record_batch!(("probe_k", Int32, [None, None]))?;
3835+
let probe_schema = probe_batch.schema();
3836+
let probe_ordering = LexOrdering::new([sort_expr("probe_k", &probe_schema)]).unwrap();
3837+
let probe = DataSourceExec::from_data_source(
3838+
MemorySourceConfig::try_new(&[vec![probe_batch]], probe_schema, None)?
3839+
.try_with_sort_information(vec![probe_ordering])?,
3840+
);
3841+
let join = HashJoinExecBuilder::new(
3842+
build,
3843+
probe,
3844+
vec![(
3845+
Arc::new(Column::new("build_k", 0)),
3846+
Arc::new(Column::new("probe_k", 0)),
3847+
)],
3848+
JoinType::Inner,
3849+
)
3850+
.with_partition_mode(PartitionMode::CollectLeft)
3851+
.with_null_equality(NullEquality::NullEqualsNothing)
3852+
.build()?;
3853+
let required = LexOrdering::new([
3854+
sort_expr("probe_k", &join.schema()),
3855+
sort_expr("build_v", &join.schema()),
3856+
])
3857+
.unwrap();
3858+
// NULLs cannot match under ordinary equality, so nullable UNIQUE is sufficient.
3859+
assert!(
3860+
join.properties()
3861+
.equivalence_properties()
3862+
.ordering_satisfy(required.clone())?
3863+
);
3864+
3865+
// Rebuilding must invalidate the cached ordering proof when NULLs can match.
3866+
let join = join
3867+
.builder()
3868+
.with_null_equality(NullEquality::NullEqualsNull)
3869+
.build()?;
3870+
assert!(
3871+
!join
3872+
.properties()
3873+
.equivalence_properties()
3874+
.ordering_satisfy(required.clone())?
3875+
);
3876+
let mut plan: Arc<dyn ExecutionPlan> =
3877+
Arc::new(SortExec::new(required, Arc::new(join)).with_fetch(Some(2)));
3878+
let ctx =
3879+
SessionContext::new_with_config(SessionConfig::new().with_target_partitions(1));
3880+
let state = ctx.state();
3881+
for optimizer in state.physical_optimizers() {
3882+
plan = optimizer.optimize(plan, state.config_options())?;
3883+
}
3884+
let batches = datafusion_physical_plan::collect(plan, ctx.task_ctx()).await?;
3885+
assert_batches_eq!(
3886+
[
3887+
"+---------+---------+---------+",
3888+
"| build_k | build_v | probe_k |",
3889+
"+---------+---------+---------+",
3890+
"| | 10 | |",
3891+
"| | 10 | |",
3892+
"+---------+---------+---------+",
3893+
],
3894+
&batches
3895+
);
3896+
Ok(())
3897+
}

‎datafusion/physical-expr/src/equivalence/properties/joins.rs‎

Lines changed: 66 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -19,10 +19,11 @@ use std::sync::Arc;
1919

2020
use super::EquivalenceProperties;
2121
use crate::expressions::Column;
22-
use crate::{PhysicalExprRef, equivalence::OrderingEquivalenceClass};
22+
use crate::{ConstExpr, PhysicalExprRef, equivalence::OrderingEquivalenceClass};
2323

2424
use arrow::datatypes::SchemaRef;
25-
use datafusion_common::{Constraint, JoinSide, JoinType, Result};
25+
use datafusion_common::{Constraint, JoinSide, JoinType, NullEquality, Result};
26+
use datafusion_physical_expr_common::physical_expr::is_volatile;
2627

2728
/// Calculate ordering equivalence properties for the given join operation.
2829
#[expect(clippy::too_many_arguments)]
@@ -35,6 +36,7 @@ pub fn join_equivalence_properties(
3536
probe_side: Option<JoinSide>,
3637
on: &[(PhysicalExprRef, PhysicalExprRef)],
3738
has_filter: bool,
39+
null_equality: NullEquality,
3840
) -> Result<EquivalenceProperties> {
3941
let left_size = left.schema.fields.len();
4042
let mut result = EquivalenceProperties::new(join_schema);
@@ -59,6 +61,7 @@ pub fn join_equivalence_properties(
5961
on,
6062
JoinSide::Left,
6163
*join_type != JoinType::Inner,
64+
null_equality,
6265
)?);
6366
}
6467
result.add_orderings(left.oeq_class);
@@ -74,6 +77,7 @@ pub fn join_equivalence_properties(
7477
on,
7578
JoinSide::Right,
7679
*join_type != JoinType::Inner,
80+
null_equality,
7781
)?);
7882
}
7983
let mut right_oeq_class = right.oeq_class;
@@ -102,6 +106,7 @@ fn unique_build_join_orderings(
102106
on: &[(PhysicalExprRef, PhysicalExprRef)],
103107
probe_side: JoinSide,
104108
preserves_unmatched_probe: bool,
109+
null_equality: NullEquality,
105110
) -> Result<OrderingEquivalenceClass> {
106111
if build.constraints().is_empty() || build.oeq_class().is_empty() {
107112
return Ok(OrderingEquivalenceClass::default());
@@ -122,20 +127,31 @@ fn unique_build_join_orderings(
122127
.collect::<Vec<_>>();
123128
let mut valid_orderings = Vec::new();
124129
for ordering in probe.oeq_class().iter() {
125-
let probe_exprs = ordering
126-
.iter()
127-
.map(|sort| probe.eq_group().normalize_expr(Arc::clone(&sort.expr)))
128-
.collect::<Vec<_>>();
130+
// Within a group of equal ordering values, these expressions are
131+
// constant. Keep this assumption local to the ordering proof.
132+
let mut group = probe.eq_group().clone();
133+
for sort in ordering {
134+
let expr = probe.eq_group().normalize_expr(Arc::clone(&sort.expr));
135+
group.add_constant(ConstExpr::from(expr));
136+
}
137+
let probe_key_is_fixed = |key: &PhysicalExprRef| {
138+
!is_volatile(key) && group.is_expr_constant(key).is_some()
139+
};
129140

130141
// Outer joins must have the same match status throughout the group.
131142
if preserves_unmatched_probe
132143
&& !on
133144
.iter()
134-
.all(|(probe_key, _)| probe_exprs.contains(probe_key))
145+
.all(|(probe_key, _)| probe_key_is_fixed(probe_key))
135146
{
136147
continue;
137148
}
138-
if !ordering_covers_unique_build_key(build, &on, &probe_exprs) {
149+
if !ordering_covers_unique_build_key(
150+
build,
151+
&on,
152+
probe_key_is_fixed,
153+
null_equality,
154+
) {
139155
continue;
140156
}
141157
valid_orderings.push(ordering.clone());
@@ -154,11 +170,12 @@ fn unique_build_join_orderings(
154170
}
155171

156172
/// Check whether the probe ordering determines a unique build key.
157-
/// Join keys and probe ordering expressions must already be normalized.
173+
/// Join keys must already be normalized against their input equivalence groups.
158174
fn ordering_covers_unique_build_key(
159175
build: &EquivalenceProperties,
160176
on: &[(PhysicalExprRef, PhysicalExprRef)],
161-
probe_exprs: &[PhysicalExprRef],
177+
probe_key_is_fixed: impl Fn(&PhysicalExprRef) -> bool,
178+
null_equality: NullEquality,
162179
) -> bool {
163180
build.constraints().iter().any(|constraint| {
164181
let (Constraint::PrimaryKey(indices) | Constraint::Unique(indices)) = constraint;
@@ -167,15 +184,18 @@ fn ordering_covers_unique_build_key(
167184
let Some(field) = build.schema.fields().get(index) else {
168185
return false;
169186
};
170-
// UNIQUE can contain repeated NULLs. Without null-equality
171-
// information, only non-null UNIQUE columns prove uniqueness.
172-
if matches!(constraint, Constraint::Unique(_)) && field.is_nullable() {
187+
// UNIQUE permits repeated NULLs, which only invalidate the
188+
// uniqueness proof when NULL join keys can match each other.
189+
if matches!(constraint, Constraint::Unique(_))
190+
&& field.is_nullable()
191+
&& null_equality == NullEquality::NullEqualsNull
192+
{
173193
return false;
174194
}
175195
let column: PhysicalExprRef = Arc::new(Column::new(field.name(), index));
176196
let column = build.eq_group().normalize_expr(column);
177197
on.iter().any(|(probe_key, build_key)| {
178-
build_key.eq(&column) && probe_exprs.contains(probe_key)
198+
build_key.eq(&column) && probe_key_is_fixed(probe_key)
179199
})
180200
})
181201
})
@@ -209,9 +229,10 @@ mod tests {
209229
use super::*;
210230
use crate::equivalence::convert_to_orderings;
211231
use crate::equivalence::tests::create_test_schema;
212-
use crate::expressions::{Column, col};
232+
use crate::expressions::{BinaryExpr, Column, col, lit};
213233
use crate::{LexOrdering, PhysicalSortExpr};
214234
use datafusion_common::{Constraint, Constraints};
235+
use datafusion_expr::Operator;
215236

216237
use arrow::compute::SortOptions;
217238
use arrow::datatypes::{DataType, Field, Fields, Schema};
@@ -273,6 +294,7 @@ mod tests {
273294
Some(JoinSide::Left),
274295
&[],
275296
false,
297+
NullEquality::NullEqualsNothing,
276298
)?;
277299
let err_msg =
278300
format!("expected: {:?}, actual:{:?}", expected, join_eq.oeq_class);
@@ -326,6 +348,7 @@ mod tests {
326348
Some(JoinSide::Left),
327349
on,
328350
false,
351+
NullEquality::NullEqualsNothing,
329352
)
330353
};
331354
let required = |prefix| {
@@ -348,7 +371,34 @@ mod tests {
348371
let inner = join_properties(JoinType::Inner, &on)?;
349372
let outer = join_properties(JoinType::Left, &on)?;
350373
assert!(inner.ordering_satisfy(required(Arc::clone(&a)))?);
351-
assert!(!outer.ordering_satisfy(required(a))?);
374+
assert!(!outer.ordering_satisfy(required(Arc::clone(&a)))?);
375+
376+
let plus_one = |expr| -> PhysicalExprRef {
377+
Arc::new(BinaryExpr::new(expr, Operator::Plus, lit(1_i32)))
378+
};
379+
let a_plus_one = plus_one(Arc::clone(&a));
380+
let b_plus_one = plus_one(Arc::clone(&b));
381+
// Record the ordering before adding equivalence, so the proof must
382+
// normalize both the ordering expression and the join key consistently.
383+
let mut probe = EquivalenceProperties::new_with_orderings(
384+
Arc::clone(&schema),
385+
[ordering(Arc::clone(&b_plus_one))],
386+
);
387+
probe.add_equal_conditions(Arc::clone(&a), b)?;
388+
for join_type in [JoinType::Inner, JoinType::Left] {
389+
let output = join_equivalence_properties(
390+
probe.clone(),
391+
build.clone(),
392+
&join_type,
393+
Arc::clone(&output_schema),
394+
&[true, false],
395+
Some(JoinSide::Left),
396+
&[(Arc::clone(&a_plus_one), Arc::clone(&a))],
397+
false,
398+
NullEquality::NullEqualsNothing,
399+
)?;
400+
assert!(output.ordering_satisfy(required(Arc::clone(&b_plus_one)))?);
401+
}
352402
Ok(())
353403
}
354404

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

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -45,7 +45,8 @@ use arrow::datatypes::{Fields, Schema, SchemaRef};
4545
use datafusion_common::stats::Precision;
4646
use datafusion_common::tree_node::TreeNodeRecursion;
4747
use datafusion_common::{
48-
DataFusionError, JoinType, Result, ScalarValue, assert_eq_or_internal_err,
48+
DataFusionError, JoinType, NullEquality, Result, ScalarValue,
49+
assert_eq_or_internal_err,
4950
};
5051
use datafusion_execution::memory_pool::{MemoryConsumer, MemoryReservation};
5152
use datafusion_execution::{TaskContext, TryEmitter, async_try_stream};
@@ -161,6 +162,7 @@ impl CrossJoinExec {
161162
None,
162163
&[],
163164
false,
165+
NullEquality::NullEqualsNothing,
164166
)?;
165167

166168
// Get output partitioning:

0 commit comments

Comments
 (0)