Skip to content

Commit a1ba7f8

Browse files
saadtajwarkosiew
authored andcommitted
feat: complete range repartition physical planning (apache#23617)
## Which issue does this PR close? - Closes apache#23230 ## Rationale for this change After apache#23231 was merged in for supporting physical execution of the range repartitioning scheme, we still had a few methods on physical planning unimplemented, specifically `try_swapping_with_projection`, `try_pushdown_sort`, `repartitioned` - this PR finishes the implementation of those methods ## What changes are included in this PR? - `try_swapping_with_projection`: similar to the `Hash` scheme, for `Range` we call `update_expr` for each of the range key expressions to attempt rewriting based on the projection expressions - `try_pushdown_sort`: same as other variants, we delegate to the child and wrap with a new `RepartitionExec` - `repartitioned`: unable to support for Range, left comment in codebase with explanation ## Are these changes tested? Yes ## Are there any user-facing changes? No
1 parent 3a6883f commit a1ba7f8

1 file changed

Lines changed: 329 additions & 17 deletions

File tree

  • datafusion/physical-plan/src/repartition

‎datafusion/physical-plan/src/repartition/mod.rs‎

Lines changed: 329 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -1607,10 +1607,29 @@ impl ExecutionPlan for RepartitionExec {
16071607
}
16081608
Partitioning::Hash(new_partitions, *size)
16091609
}
1610-
Partitioning::Range(_) => {
1611-
// Range partitioning optimizer propagation is tracked in
1612-
// https://github.com/apache/datafusion/issues/23230
1613-
return Ok(None);
1610+
Partitioning::Range(range_partitioning) => {
1611+
// Rewrite range key expressions through the projection.
1612+
let mut sort_exprs =
1613+
Vec::with_capacity(range_partitioning.ordering().len());
1614+
for sort_expr in range_partitioning.ordering() {
1615+
let Some(new_expr) =
1616+
update_expr(&sort_expr.expr, projection.expr(), false)?
1617+
else {
1618+
return Ok(None);
1619+
};
1620+
sort_exprs.push(PhysicalSortExpr::new(new_expr, sort_expr.options));
1621+
}
1622+
1623+
let Some(ordering) = LexOrdering::new(sort_exprs) else {
1624+
return internal_err!(
1625+
"failed to create LexOrdering for range partitioning"
1626+
);
1627+
};
1628+
1629+
Partitioning::Range(RangePartitioning::try_new(
1630+
ordering,
1631+
range_partitioning.split_points().to_vec(),
1632+
)?)
16141633
}
16151634
others => others.clone(),
16161635
};
@@ -1648,16 +1667,6 @@ impl ExecutionPlan for RepartitionExec {
16481667
if !self.maintains_input_order()[0] {
16491668
return Ok(SortOrderPushdownResult::Unsupported);
16501669
}
1651-
match self.partitioning() {
1652-
Partitioning::Range(_) => {
1653-
// Range partitioning optimizer propagation is tracked in
1654-
// https://github.com/apache/datafusion/issues/23230
1655-
return Ok(SortOrderPushdownResult::Unsupported);
1656-
}
1657-
Partitioning::RoundRobinBatch(_)
1658-
| Partitioning::Hash(_, _)
1659-
| Partitioning::UnknownPartitioning(_) => {}
1660-
}
16611670

16621671
// Delegate to the child and wrap with a new RepartitionExec
16631672
self.input.try_pushdown_sort(order)?.try_map(|new_input| {
@@ -1680,12 +1689,11 @@ impl ExecutionPlan for RepartitionExec {
16801689
new_properties.partitioning = match new_properties.partitioning {
16811690
RoundRobinBatch(_) => RoundRobinBatch(target_partitions),
16821691
Hash(hash, _) => Hash(hash, target_partitions),
1683-
UnknownPartitioning(_) => UnknownPartitioning(target_partitions),
16841692
Range(_) => {
1685-
// Range repartition optimizations are tracked in
1686-
// https://github.com/apache/datafusion/issues/23230
1693+
// Number of partitions is constrained by the split points and cannot be changed
16871694
return Ok(None);
16881695
}
1696+
UnknownPartitioning(_) => UnknownPartitioning(target_partitions),
16891697
};
16901698
Ok(Some(Arc::new(Self {
16911699
input: Arc::clone(&self.input),
@@ -2144,6 +2152,8 @@ mod tests {
21442152
use std::collections::HashSet;
21452153

21462154
use super::*;
2155+
use crate::empty::EmptyExec;
2156+
use crate::projection::ProjectionExpr;
21472157
use crate::test::TestMemoryExec;
21482158
use crate::{
21492159
test::{
@@ -2604,6 +2614,281 @@ mod tests {
26042614
Ok(())
26052615
}
26062616

2617+
#[test]
2618+
fn range_repartition_swaps_with_projection_rewrites_key_index() -> Result<()> {
2619+
// Three columns so the projection both narrows the schema (required for
2620+
// swap) and moves the range key from @0 to @1.
2621+
let schema = Arc::new(Schema::new(vec![
2622+
Field::new("id", DataType::UInt32, false),
2623+
Field::new("region", DataType::Utf8, false),
2624+
Field::new("payload", DataType::UInt32, false),
2625+
]));
2626+
let repartition = Arc::new(RepartitionExec::try_new(
2627+
Arc::new(EmptyExec::new(Arc::clone(&schema))),
2628+
range_partitioning_on_columns(&schema, &["id"], vec![vec![10]])?,
2629+
)?);
2630+
2631+
let projection =
2632+
projection_on_columns(&(Arc::clone(&repartition) as _), &["payload", "id"])?;
2633+
2634+
let swapped = repartition
2635+
.try_swapping_with_projection(&projection)?
2636+
.expect("swap should succeed when projection keeps the range key");
2637+
let swapped_repartition = swapped
2638+
.downcast_ref::<RepartitionExec>()
2639+
.expect("top node should be RepartitionExec");
2640+
2641+
assert!(swapped_repartition.input().is::<ProjectionExec>());
2642+
let range = expect_range_partitioning(swapped_repartition.partitioning());
2643+
assert_eq!(range.ordering()[0].to_string(), "id@1 ASC");
2644+
assert_eq!(
2645+
range.split_points(),
2646+
&[SplitPoint::new(vec![ScalarValue::UInt32(Some(10))])]
2647+
);
2648+
2649+
Ok(())
2650+
}
2651+
2652+
#[test]
2653+
fn range_repartition_does_not_swap_when_projection_drops_key() -> Result<()> {
2654+
// Drop a simple range key.
2655+
let schema = Arc::new(Schema::new(vec![
2656+
Field::new("id", DataType::UInt32, false),
2657+
Field::new("payload", DataType::UInt32, false),
2658+
]));
2659+
let repartition = Arc::new(RepartitionExec::try_new(
2660+
Arc::new(EmptyExec::new(Arc::clone(&schema))),
2661+
range_partitioning_on_columns(&schema, &["id"], vec![vec![10]])?,
2662+
)?);
2663+
let projection =
2664+
projection_on_columns(&(Arc::clone(&repartition) as _), &["payload"])?;
2665+
assert!(
2666+
repartition
2667+
.try_swapping_with_projection(&projection)?
2668+
.is_none()
2669+
);
2670+
2671+
// Drop part of a compound range key.
2672+
let schema = Arc::new(Schema::new(vec![
2673+
Field::new("a", DataType::UInt32, false),
2674+
Field::new("b", DataType::UInt32, false),
2675+
Field::new("c", DataType::UInt32, false),
2676+
]));
2677+
let repartition = Arc::new(RepartitionExec::try_new(
2678+
Arc::new(EmptyExec::new(Arc::clone(&schema))),
2679+
range_partitioning_on_columns(&schema, &["a", "b"], vec![vec![10, 1]])?,
2680+
)?);
2681+
let projection =
2682+
projection_on_columns(&(Arc::clone(&repartition) as _), &["a", "c"])?;
2683+
assert!(
2684+
repartition
2685+
.try_swapping_with_projection(&projection)?
2686+
.is_none()
2687+
);
2688+
2689+
Ok(())
2690+
}
2691+
2692+
#[test]
2693+
fn range_repartition_try_pushdown_sort_when_maintains_order() -> Result<()> {
2694+
let schema =
2695+
Arc::new(Schema::new(vec![Field::new("id", DataType::UInt32, false)]));
2696+
let ordering = LexOrdering::new([PhysicalSortExpr::new(
2697+
col("id", &schema)?,
2698+
SortOptions::default(),
2699+
)])
2700+
.expect("ordering must not be empty");
2701+
2702+
// Multi-partition source with preserve_order: Range maintains input order.
2703+
let source = Arc::new(ExactSortPushdownExec::new(
2704+
Arc::clone(&schema),
2705+
2,
2706+
ordering.clone(),
2707+
));
2708+
let repartition = Arc::new(
2709+
RepartitionExec::try_new(
2710+
source,
2711+
range_partitioning_on_columns(&schema, &["id"], vec![vec![10]])?,
2712+
)?
2713+
.with_preserve_order(),
2714+
);
2715+
assert!(repartition.maintains_input_order()[0]);
2716+
2717+
match repartition.try_pushdown_sort(ordering.as_ref())? {
2718+
SortOrderPushdownResult::Exact { inner } => {
2719+
let pushed = inner
2720+
.downcast_ref::<RepartitionExec>()
2721+
.expect("pushdown should keep RepartitionExec");
2722+
2723+
assert!(pushed.preserve_order());
2724+
assert!(pushed.maintains_input_order()[0]);
2725+
2726+
let range = expect_range_partitioning(pushed.partitioning());
2727+
assert_eq!(range.ordering()[0].to_string(), "id@0 ASC");
2728+
assert_eq!(
2729+
inner.properties().output_ordering().map(|o| o.to_string()),
2730+
Some(ordering.to_string()),
2731+
"pushed repartition output ordering should match the requested sort"
2732+
);
2733+
}
2734+
other => panic!("expected Exact sort pushdown, got {other:?}"),
2735+
}
2736+
2737+
Ok(())
2738+
}
2739+
2740+
#[test]
2741+
fn range_repartition_try_pushdown_sort_unsupported_without_order_maintenance()
2742+
-> Result<()> {
2743+
let schema =
2744+
Arc::new(Schema::new(vec![Field::new("id", DataType::UInt32, false)]));
2745+
let ordering = LexOrdering::new([PhysicalSortExpr::new(
2746+
col("id", &schema)?,
2747+
SortOptions::default(),
2748+
)])
2749+
.expect("ordering must not be empty");
2750+
2751+
// Multi-partition source without preserve_order: Range does not maintain order.
2752+
let source = Arc::new(ExactSortPushdownExec::new(
2753+
Arc::clone(&schema),
2754+
2,
2755+
ordering.clone(),
2756+
));
2757+
let repartition = Arc::new(RepartitionExec::try_new(
2758+
source,
2759+
range_partitioning_on_columns(&schema, &["id"], vec![vec![10]])?,
2760+
)?);
2761+
assert!(!repartition.maintains_input_order()[0]);
2762+
2763+
assert!(matches!(
2764+
repartition.try_pushdown_sort(ordering.as_ref())?,
2765+
SortOrderPushdownResult::Unsupported
2766+
));
2767+
2768+
Ok(())
2769+
}
2770+
2771+
fn range_partitioning_on_columns(
2772+
schema: &SchemaRef,
2773+
key_columns: &[&str],
2774+
split_points: Vec<Vec<u32>>,
2775+
) -> Result<Partitioning> {
2776+
let Some(ordering) = LexOrdering::new(
2777+
key_columns
2778+
.iter()
2779+
.map(|name| {
2780+
Ok(PhysicalSortExpr::new(
2781+
col(name, schema)?,
2782+
SortOptions::default(),
2783+
))
2784+
})
2785+
.collect::<Result<Vec<_>>>()?,
2786+
) else {
2787+
return exec_err!("range ordering must not be empty");
2788+
};
2789+
Ok(Partitioning::Range(RangePartitioning::try_new(
2790+
ordering,
2791+
split_points
2792+
.into_iter()
2793+
.map(|values| {
2794+
SplitPoint::new(
2795+
values
2796+
.into_iter()
2797+
.map(|value| ScalarValue::UInt32(Some(value)))
2798+
.collect(),
2799+
)
2800+
})
2801+
.collect(),
2802+
)?))
2803+
}
2804+
2805+
fn projection_on_columns(
2806+
input: &Arc<dyn ExecutionPlan>,
2807+
names: &[&str],
2808+
) -> Result<ProjectionExec> {
2809+
let exprs = names
2810+
.iter()
2811+
.map(|name| {
2812+
Ok(ProjectionExpr {
2813+
expr: col(name, &input.schema())?,
2814+
alias: (*name).to_string(),
2815+
})
2816+
})
2817+
.collect::<Result<Vec<_>>>()?;
2818+
ProjectionExec::try_new(exprs, Arc::clone(input))
2819+
}
2820+
2821+
fn expect_range_partitioning(partitioning: &Partitioning) -> &RangePartitioning {
2822+
match partitioning {
2823+
Partitioning::Range(range) => range,
2824+
other => panic!("expected Range partitioning, got {other:?}"),
2825+
}
2826+
}
2827+
2828+
/// Test source that claims Exact support for any sort pushdown request.
2829+
#[derive(Debug, Clone)]
2830+
struct ExactSortPushdownExec {
2831+
cache: Arc<PlanProperties>,
2832+
}
2833+
2834+
impl ExactSortPushdownExec {
2835+
fn new(schema: SchemaRef, num_partitions: usize, ordering: LexOrdering) -> Self {
2836+
use crate::execution_plan::{Boundedness, EmissionType};
2837+
Self {
2838+
cache: Arc::new(PlanProperties::new(
2839+
EquivalenceProperties::new_with_orderings(schema, [ordering]),
2840+
Partitioning::UnknownPartitioning(num_partitions),
2841+
EmissionType::Incremental,
2842+
Boundedness::Bounded,
2843+
)),
2844+
}
2845+
}
2846+
}
2847+
2848+
impl DisplayAs for ExactSortPushdownExec {
2849+
fn fmt_as(&self, _t: DisplayFormatType, f: &mut Formatter) -> std::fmt::Result {
2850+
write!(f, "ExactSortPushdownExec")
2851+
}
2852+
}
2853+
2854+
impl ExecutionPlan for ExactSortPushdownExec {
2855+
fn name(&self) -> &str {
2856+
"ExactSortPushdownExec"
2857+
}
2858+
2859+
fn properties(&self) -> &Arc<PlanProperties> {
2860+
&self.cache
2861+
}
2862+
2863+
fn children(&self) -> Vec<&Arc<dyn ExecutionPlan>> {
2864+
vec![]
2865+
}
2866+
2867+
fn with_new_children(
2868+
self: Arc<Self>,
2869+
_: Vec<Arc<dyn ExecutionPlan>>,
2870+
) -> Result<Arc<dyn ExecutionPlan>> {
2871+
Ok(self)
2872+
}
2873+
2874+
fn execute(
2875+
&self,
2876+
_partition: usize,
2877+
_context: Arc<TaskContext>,
2878+
) -> Result<SendableRecordBatchStream> {
2879+
Ok(Box::pin(EmptyRecordBatchStream::new(self.schema())))
2880+
}
2881+
2882+
fn try_pushdown_sort(
2883+
&self,
2884+
_order: &[PhysicalSortExpr],
2885+
) -> Result<SortOrderPushdownResult<Arc<dyn ExecutionPlan>>> {
2886+
Ok(SortOrderPushdownResult::Exact {
2887+
inner: Arc::new(self.clone()),
2888+
})
2889+
}
2890+
}
2891+
26072892
#[tokio::test]
26082893
async fn test_repartition_with_coalescing() -> Result<()> {
26092894
let schema = test_schema(false);
@@ -3796,6 +4081,33 @@ mod test {
37964081
Ok(())
37974082
}
37984083

4084+
#[test]
4085+
fn test_range_repartitioned_returns_none() -> Result<()> {
4086+
let schema = test_schema();
4087+
let source = memory_exec(&schema);
4088+
let partitioning = Partitioning::Range(RangePartitioning::try_new(
4089+
[PhysicalSortExpr::new(
4090+
col("c0", &schema)?,
4091+
SortOptions::default(),
4092+
)]
4093+
.into(),
4094+
vec![
4095+
SplitPoint::new(vec![ScalarValue::UInt32(Some(10))]),
4096+
SplitPoint::new(vec![ScalarValue::UInt32(Some(20))]),
4097+
],
4098+
)?);
4099+
let exec = RepartitionExec::try_new(source, partitioning)?;
4100+
4101+
// Range partition count is fixed by split points, so repartitioned()
4102+
// cannot change it to an arbitrary target.
4103+
let result = exec.repartitioned(10, &Default::default())?;
4104+
assert!(
4105+
result.is_none(),
4106+
"range repartitioning should not support changing partition count"
4107+
);
4108+
Ok(())
4109+
}
4110+
37994111
fn test_schema() -> Arc<Schema> {
38004112
Arc::new(Schema::new(vec![Field::new("c0", DataType::UInt32, false)]))
38014113
}

0 commit comments

Comments
 (0)