Skip to content

Commit cd3a218

Browse files
EdsonPetryGene Bordegaray
authored andcommitted
fix: preserve range partitioning through joins (apache#23584)
- Closes apache#23450. partitioned inner joins without hash repartitioning. However, join output still downgraded `Partitioning::Range` to `UnknownPartitioning`, so downstream joins and aggregates could not reuse the preserved range layout and inserted avoidable hash repartitions. - Preserve `Partitioning::Range` in `adjust_right_output_partitioning`. - Shift right-side range-ordering column indexes into the joined schema while retaining split points and sort options. - Add unit coverage for compound range keys and non-default sort options. - Update SQL logic test plans for nested range joins and a range join feeding an aggregate. Yes. - `./dev/rust_lint.sh` - `cargo clippy --all-targets --all-features -- -D warnings` - `cargo test -p datafusion-physical-plan test_adjust_right_output_partitioning_preserves_range` - `cargo test --profile=ci --test sqllogictests -- range_partitioning.slt` - `ulimit -n 10240 && RUST_BACKTRACE=1 cargo test --profile ci --exclude datafusion-examples --exclude datafusion-benchmarks --exclude datafusion-cli --workspace --lib --tests --bins --features avro,json,backtrace,extended_tests,recursive_protection,parquet_encryption` Yes. Physical plans can preserve proven range partitioning through joins, allowing compatible downstream joins and aggregates to avoid unnecessary hash repartitioning. There are no public API changes.
1 parent e98fb60 commit cd3a218

2 files changed

Lines changed: 76 additions & 24 deletions

File tree

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

Lines changed: 64 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -33,7 +33,8 @@ use crate::metrics::{
3333
};
3434
use crate::projection::{ProjectionExec, ProjectionExpr};
3535
use crate::{
36-
ColumnStatistics, ExecutionPlan, ExecutionPlanProperties, Partitioning, Statistics,
36+
ColumnStatistics, ExecutionPlan, ExecutionPlanProperties, Partitioning,
37+
RangePartitioning, Statistics,
3738
};
3839
// compatibility
3940
pub use super::join_filter::JoinFilter;
@@ -67,7 +68,7 @@ use datafusion_common::hash_utils::create_hashes;
6768
use datafusion_common::stats::Precision;
6869
use datafusion_common::{
6970
DataFusionError, JoinSide, JoinType, NullEquality, Result, SharedResult,
70-
not_impl_err, plan_err,
71+
internal_datafusion_err, not_impl_err, plan_err,
7172
};
7273
use datafusion_expr::Operator;
7374
use datafusion_expr::interval_arithmetic::Interval;
@@ -145,9 +146,19 @@ pub fn adjust_right_output_partitioning(
145146
Partitioning::Hash(new_exprs, *size)
146147
}
147148
Partitioning::Range(range) => {
148-
// Range partitioning optimizer propagation is tracked in
149-
// https://github.com/apache/datafusion/issues/22395
150-
Partitioning::UnknownPartitioning(range.partition_count())
149+
let ordering = add_offset_to_physical_sort_exprs(
150+
range.ordering().iter().cloned(),
151+
left_columns_len as _,
152+
)?;
153+
let ordering = LexOrdering::new(ordering).ok_or_else(|| {
154+
internal_datafusion_err!(
155+
"Offsetting range partitioning produced an empty ordering"
156+
)
157+
})?;
158+
Partitioning::Range(RangePartitioning::new(
159+
ordering,
160+
range.split_points().to_vec(),
161+
))
151162
}
152163
result => result.clone(),
153164
};
@@ -2149,7 +2160,7 @@ mod tests {
21492160
use arrow::datatypes::{DataType, Fields};
21502161
use arrow::error::{ArrowError, Result as ArrowResult};
21512162
use datafusion_common::stats::Precision::{Absent, Exact, Inexact};
2152-
use datafusion_common::{ScalarValue, arrow_datafusion_err, arrow_err};
2163+
use datafusion_common::{ScalarValue, SplitPoint, arrow_datafusion_err, arrow_err};
21532164
use datafusion_physical_expr::PhysicalSortExpr;
21542165

21552166
use rstest::rstest;
@@ -3244,6 +3255,53 @@ mod tests {
32443255
Ok(())
32453256
}
32463257

3258+
#[test]
3259+
fn test_adjust_right_output_partitioning_preserves_range() -> Result<()> {
3260+
let split_points = vec![
3261+
SplitPoint::new(vec![
3262+
ScalarValue::Int32(Some(10)),
3263+
ScalarValue::Int32(Some(100)),
3264+
]),
3265+
SplitPoint::new(vec![
3266+
ScalarValue::Int32(Some(20)),
3267+
ScalarValue::Int32(Some(50)),
3268+
]),
3269+
];
3270+
let range = RangePartitioning::try_new(
3271+
LexOrdering::new([
3272+
PhysicalSortExpr::new(
3273+
Arc::new(Column::new("a", 0)),
3274+
SortOptions::new(false, true),
3275+
),
3276+
PhysicalSortExpr::new(
3277+
Arc::new(Column::new("b", 2)),
3278+
SortOptions::new(true, false),
3279+
),
3280+
])
3281+
.unwrap(),
3282+
split_points.clone(),
3283+
)?;
3284+
3285+
let adjusted = adjust_right_output_partitioning(&Partitioning::Range(range), 3)?;
3286+
let expected = Partitioning::Range(RangePartitioning::new(
3287+
LexOrdering::new([
3288+
PhysicalSortExpr::new(
3289+
Arc::new(Column::new("a", 3)),
3290+
SortOptions::new(false, true),
3291+
),
3292+
PhysicalSortExpr::new(
3293+
Arc::new(Column::new("b", 5)),
3294+
SortOptions::new(true, false),
3295+
),
3296+
])
3297+
.unwrap(),
3298+
split_points,
3299+
));
3300+
3301+
assert_eq!(adjusted, expected);
3302+
Ok(())
3303+
}
3304+
32473305
#[test]
32483306
fn test_calculate_join_output_ordering() -> Result<()> {
32493307
let left_ordering = LexOrdering::new(vec![

‎datafusion/sqllogictest/test_files/range_partitioning.slt‎

Lines changed: 12 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -496,9 +496,8 @@ set datafusion.optimizer.preserve_file_partitions = 0;
496496

497497
##########
498498
# TEST 15: Nested Range Joins
499-
# Compatible Range partitioning satisfies the lower join inputs. The upper join
500-
# still repairs the intermediate join output with Hash repartitioning because
501-
# HashJoinExec does not currently expose Range output partitioning.
499+
# Compatible Range partitioning is preserved through the lower join, allowing
500+
# the upper join to consume it without Hash repartitioning either input.
502501
##########
503502

504503
query TT
@@ -509,12 +508,10 @@ JOIN range_partitioned s ON r.range_key = s.range_key;
509508
----
510509
physical_plan
511510
01)HashJoinExec: mode=Partitioned, join_type=Inner, on=[(range_key@2, range_key@0)], projection=[range_key@0, value@1, value@3, value@5]
512-
02)--RepartitionExec: partitioning=Hash([range_key@2], 4), input_partitions=4
513-
03)----HashJoinExec: mode=Partitioned, join_type=Inner, on=[(range_key@0, range_key@0)]
514-
04)------DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(10), (20), (30)], 4), file_type=csv, has_header=false
515-
05)------DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(10), (20), (30)], 4), file_type=csv, has_header=false
516-
06)--RepartitionExec: partitioning=Hash([range_key@0], 4), input_partitions=4
517-
07)----DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(10), (20), (30)], 4), file_type=csv, has_header=false
511+
02)--HashJoinExec: mode=Partitioned, join_type=Inner, on=[(range_key@0, range_key@0)]
512+
03)----DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(10), (20), (30)], 4), file_type=csv, has_header=false
513+
04)----DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(10), (20), (30)], 4), file_type=csv, has_header=false
514+
05)--DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(10), (20), (30)], 4), file_type=csv, has_header=false
518515

519516
query IIII
520517
SELECT l.range_key, l.value, r.value, s.value
@@ -589,9 +586,8 @@ ORDER BY l.range_key;
589586

590587
##########
591588
# TEST 17: Range Join Feeds Aggregate
592-
# The join inputs avoid Hash repartitioning, but the aggregate above the join
593-
# still repartitions because HashJoinExec does not currently expose Range
594-
# output partitioning.
589+
# The join preserves compatible Range partitioning on range_key, allowing the
590+
# aggregate above it to avoid Hash repartitioning.
595591
##########
596592

597593
query TT
@@ -601,12 +597,10 @@ JOIN range_partitioned r ON l.range_key = r.range_key
601597
GROUP BY l.range_key;
602598
----
603599
physical_plan
604-
01)AggregateExec: mode=FinalPartitioned, gby=[range_key@0 as range_key], aggr=[sum(l.value + r.value)]
605-
02)--RepartitionExec: partitioning=Hash([range_key@0], 4), input_partitions=4
606-
03)----AggregateExec: mode=Partial, gby=[range_key@0 as range_key], aggr=[sum(l.value + r.value)]
607-
04)------HashJoinExec: mode=Partitioned, join_type=Inner, on=[(range_key@0, range_key@0)], projection=[range_key@0, value@1, value@3]
608-
05)--------DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(10), (20), (30)], 4), file_type=csv, has_header=false
609-
06)--------DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(10), (20), (30)], 4), file_type=csv, has_header=false
600+
01)AggregateExec: mode=SinglePartitioned, gby=[range_key@0 as range_key], aggr=[sum(l.value + r.value)]
601+
02)--HashJoinExec: mode=Partitioned, join_type=Inner, on=[(range_key@0, range_key@0)], projection=[range_key@0, value@1, value@3]
602+
03)----DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(10), (20), (30)], 4), file_type=csv, has_header=false
603+
04)----DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(10), (20), (30)], 4), file_type=csv, has_header=false
610604

611605
query II
612606
SELECT l.range_key, SUM(l.value + r.value)

0 commit comments

Comments
 (0)