Skip to content

Commit e95b7a2

Browse files
saadtajwarGene Bordegaray
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 34149d9 commit e95b7a2

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
@@ -1548,10 +1548,29 @@ impl ExecutionPlan for RepartitionExec {
15481548
}
15491549
Partitioning::Hash(new_partitions, *size)
15501550
}
1551-
Partitioning::Range(_) => {
1552-
// Range partitioning optimizer propagation is tracked in
1553-
// https://github.com/apache/datafusion/issues/23230
1554-
return Ok(None);
1551+
Partitioning::Range(range_partitioning) => {
1552+
// Rewrite range key expressions through the projection.
1553+
let mut sort_exprs =
1554+
Vec::with_capacity(range_partitioning.ordering().len());
1555+
for sort_expr in range_partitioning.ordering() {
1556+
let Some(new_expr) =
1557+
update_expr(&sort_expr.expr, projection.expr(), false)?
1558+
else {
1559+
return Ok(None);
1560+
};
1561+
sort_exprs.push(PhysicalSortExpr::new(new_expr, sort_expr.options));
1562+
}
1563+
1564+
let Some(ordering) = LexOrdering::new(sort_exprs) else {
1565+
return internal_err!(
1566+
"failed to create LexOrdering for range partitioning"
1567+
);
1568+
};
1569+
1570+
Partitioning::Range(RangePartitioning::try_new(
1571+
ordering,
1572+
range_partitioning.split_points().to_vec(),
1573+
)?)
15551574
}
15561575
others => others.clone(),
15571576
};
@@ -1589,16 +1608,6 @@ impl ExecutionPlan for RepartitionExec {
15891608
if !self.maintains_input_order()[0] {
15901609
return Ok(SortOrderPushdownResult::Unsupported);
15911610
}
1592-
match self.partitioning() {
1593-
Partitioning::Range(_) => {
1594-
// Range partitioning optimizer propagation is tracked in
1595-
// https://github.com/apache/datafusion/issues/23230
1596-
return Ok(SortOrderPushdownResult::Unsupported);
1597-
}
1598-
Partitioning::RoundRobinBatch(_)
1599-
| Partitioning::Hash(_, _)
1600-
| Partitioning::UnknownPartitioning(_) => {}
1601-
}
16021611

16031612
// Delegate to the child and wrap with a new RepartitionExec
16041613
self.input.try_pushdown_sort(order)?.try_map(|new_input| {
@@ -1621,12 +1630,11 @@ impl ExecutionPlan for RepartitionExec {
16211630
new_properties.partitioning = match new_properties.partitioning {
16221631
RoundRobinBatch(_) => RoundRobinBatch(target_partitions),
16231632
Hash(hash, _) => Hash(hash, target_partitions),
1624-
UnknownPartitioning(_) => UnknownPartitioning(target_partitions),
16251633
Range(_) => {
1626-
// Range repartition optimizations are tracked in
1627-
// https://github.com/apache/datafusion/issues/23230
1634+
// Number of partitions is constrained by the split points and cannot be changed
16281635
return Ok(None);
16291636
}
1637+
UnknownPartitioning(_) => UnknownPartitioning(target_partitions),
16301638
};
16311639
Ok(Some(Arc::new(Self {
16321640
input: Arc::clone(&self.input),
@@ -2078,6 +2086,8 @@ mod tests {
20782086
use std::collections::HashSet;
20792087

20802088
use super::*;
2089+
use crate::empty::EmptyExec;
2090+
use crate::projection::ProjectionExpr;
20812091
use crate::test::TestMemoryExec;
20822092
use crate::{
20832093
test::{
@@ -2538,6 +2548,281 @@ mod tests {
25382548
Ok(())
25392549
}
25402550

2551+
#[test]
2552+
fn range_repartition_swaps_with_projection_rewrites_key_index() -> Result<()> {
2553+
// Three columns so the projection both narrows the schema (required for
2554+
// swap) and moves the range key from @0 to @1.
2555+
let schema = Arc::new(Schema::new(vec![
2556+
Field::new("id", DataType::UInt32, false),
2557+
Field::new("region", DataType::Utf8, false),
2558+
Field::new("payload", DataType::UInt32, false),
2559+
]));
2560+
let repartition = Arc::new(RepartitionExec::try_new(
2561+
Arc::new(EmptyExec::new(Arc::clone(&schema))),
2562+
range_partitioning_on_columns(&schema, &["id"], vec![vec![10]])?,
2563+
)?);
2564+
2565+
let projection =
2566+
projection_on_columns(&(Arc::clone(&repartition) as _), &["payload", "id"])?;
2567+
2568+
let swapped = repartition
2569+
.try_swapping_with_projection(&projection)?
2570+
.expect("swap should succeed when projection keeps the range key");
2571+
let swapped_repartition = swapped
2572+
.downcast_ref::<RepartitionExec>()
2573+
.expect("top node should be RepartitionExec");
2574+
2575+
assert!(swapped_repartition.input().is::<ProjectionExec>());
2576+
let range = expect_range_partitioning(swapped_repartition.partitioning());
2577+
assert_eq!(range.ordering()[0].to_string(), "id@1 ASC");
2578+
assert_eq!(
2579+
range.split_points(),
2580+
&[SplitPoint::new(vec![ScalarValue::UInt32(Some(10))])]
2581+
);
2582+
2583+
Ok(())
2584+
}
2585+
2586+
#[test]
2587+
fn range_repartition_does_not_swap_when_projection_drops_key() -> Result<()> {
2588+
// Drop a simple range key.
2589+
let schema = Arc::new(Schema::new(vec![
2590+
Field::new("id", DataType::UInt32, false),
2591+
Field::new("payload", DataType::UInt32, false),
2592+
]));
2593+
let repartition = Arc::new(RepartitionExec::try_new(
2594+
Arc::new(EmptyExec::new(Arc::clone(&schema))),
2595+
range_partitioning_on_columns(&schema, &["id"], vec![vec![10]])?,
2596+
)?);
2597+
let projection =
2598+
projection_on_columns(&(Arc::clone(&repartition) as _), &["payload"])?;
2599+
assert!(
2600+
repartition
2601+
.try_swapping_with_projection(&projection)?
2602+
.is_none()
2603+
);
2604+
2605+
// Drop part of a compound range key.
2606+
let schema = Arc::new(Schema::new(vec![
2607+
Field::new("a", DataType::UInt32, false),
2608+
Field::new("b", DataType::UInt32, false),
2609+
Field::new("c", DataType::UInt32, false),
2610+
]));
2611+
let repartition = Arc::new(RepartitionExec::try_new(
2612+
Arc::new(EmptyExec::new(Arc::clone(&schema))),
2613+
range_partitioning_on_columns(&schema, &["a", "b"], vec![vec![10, 1]])?,
2614+
)?);
2615+
let projection =
2616+
projection_on_columns(&(Arc::clone(&repartition) as _), &["a", "c"])?;
2617+
assert!(
2618+
repartition
2619+
.try_swapping_with_projection(&projection)?
2620+
.is_none()
2621+
);
2622+
2623+
Ok(())
2624+
}
2625+
2626+
#[test]
2627+
fn range_repartition_try_pushdown_sort_when_maintains_order() -> Result<()> {
2628+
let schema =
2629+
Arc::new(Schema::new(vec![Field::new("id", DataType::UInt32, false)]));
2630+
let ordering = LexOrdering::new([PhysicalSortExpr::new(
2631+
col("id", &schema)?,
2632+
SortOptions::default(),
2633+
)])
2634+
.expect("ordering must not be empty");
2635+
2636+
// Multi-partition source with preserve_order: Range maintains input order.
2637+
let source = Arc::new(ExactSortPushdownExec::new(
2638+
Arc::clone(&schema),
2639+
2,
2640+
ordering.clone(),
2641+
));
2642+
let repartition = Arc::new(
2643+
RepartitionExec::try_new(
2644+
source,
2645+
range_partitioning_on_columns(&schema, &["id"], vec![vec![10]])?,
2646+
)?
2647+
.with_preserve_order(),
2648+
);
2649+
assert!(repartition.maintains_input_order()[0]);
2650+
2651+
match repartition.try_pushdown_sort(ordering.as_ref())? {
2652+
SortOrderPushdownResult::Exact { inner } => {
2653+
let pushed = inner
2654+
.downcast_ref::<RepartitionExec>()
2655+
.expect("pushdown should keep RepartitionExec");
2656+
2657+
assert!(pushed.preserve_order());
2658+
assert!(pushed.maintains_input_order()[0]);
2659+
2660+
let range = expect_range_partitioning(pushed.partitioning());
2661+
assert_eq!(range.ordering()[0].to_string(), "id@0 ASC");
2662+
assert_eq!(
2663+
inner.properties().output_ordering().map(|o| o.to_string()),
2664+
Some(ordering.to_string()),
2665+
"pushed repartition output ordering should match the requested sort"
2666+
);
2667+
}
2668+
other => panic!("expected Exact sort pushdown, got {other:?}"),
2669+
}
2670+
2671+
Ok(())
2672+
}
2673+
2674+
#[test]
2675+
fn range_repartition_try_pushdown_sort_unsupported_without_order_maintenance()
2676+
-> Result<()> {
2677+
let schema =
2678+
Arc::new(Schema::new(vec![Field::new("id", DataType::UInt32, false)]));
2679+
let ordering = LexOrdering::new([PhysicalSortExpr::new(
2680+
col("id", &schema)?,
2681+
SortOptions::default(),
2682+
)])
2683+
.expect("ordering must not be empty");
2684+
2685+
// Multi-partition source without preserve_order: Range does not maintain order.
2686+
let source = Arc::new(ExactSortPushdownExec::new(
2687+
Arc::clone(&schema),
2688+
2,
2689+
ordering.clone(),
2690+
));
2691+
let repartition = Arc::new(RepartitionExec::try_new(
2692+
source,
2693+
range_partitioning_on_columns(&schema, &["id"], vec![vec![10]])?,
2694+
)?);
2695+
assert!(!repartition.maintains_input_order()[0]);
2696+
2697+
assert!(matches!(
2698+
repartition.try_pushdown_sort(ordering.as_ref())?,
2699+
SortOrderPushdownResult::Unsupported
2700+
));
2701+
2702+
Ok(())
2703+
}
2704+
2705+
fn range_partitioning_on_columns(
2706+
schema: &SchemaRef,
2707+
key_columns: &[&str],
2708+
split_points: Vec<Vec<u32>>,
2709+
) -> Result<Partitioning> {
2710+
let Some(ordering) = LexOrdering::new(
2711+
key_columns
2712+
.iter()
2713+
.map(|name| {
2714+
Ok(PhysicalSortExpr::new(
2715+
col(name, schema)?,
2716+
SortOptions::default(),
2717+
))
2718+
})
2719+
.collect::<Result<Vec<_>>>()?,
2720+
) else {
2721+
return exec_err!("range ordering must not be empty");
2722+
};
2723+
Ok(Partitioning::Range(RangePartitioning::try_new(
2724+
ordering,
2725+
split_points
2726+
.into_iter()
2727+
.map(|values| {
2728+
SplitPoint::new(
2729+
values
2730+
.into_iter()
2731+
.map(|value| ScalarValue::UInt32(Some(value)))
2732+
.collect(),
2733+
)
2734+
})
2735+
.collect(),
2736+
)?))
2737+
}
2738+
2739+
fn projection_on_columns(
2740+
input: &Arc<dyn ExecutionPlan>,
2741+
names: &[&str],
2742+
) -> Result<ProjectionExec> {
2743+
let exprs = names
2744+
.iter()
2745+
.map(|name| {
2746+
Ok(ProjectionExpr {
2747+
expr: col(name, &input.schema())?,
2748+
alias: (*name).to_string(),
2749+
})
2750+
})
2751+
.collect::<Result<Vec<_>>>()?;
2752+
ProjectionExec::try_new(exprs, Arc::clone(input))
2753+
}
2754+
2755+
fn expect_range_partitioning(partitioning: &Partitioning) -> &RangePartitioning {
2756+
match partitioning {
2757+
Partitioning::Range(range) => range,
2758+
other => panic!("expected Range partitioning, got {other:?}"),
2759+
}
2760+
}
2761+
2762+
/// Test source that claims Exact support for any sort pushdown request.
2763+
#[derive(Debug, Clone)]
2764+
struct ExactSortPushdownExec {
2765+
cache: Arc<PlanProperties>,
2766+
}
2767+
2768+
impl ExactSortPushdownExec {
2769+
fn new(schema: SchemaRef, num_partitions: usize, ordering: LexOrdering) -> Self {
2770+
use crate::execution_plan::{Boundedness, EmissionType};
2771+
Self {
2772+
cache: Arc::new(PlanProperties::new(
2773+
EquivalenceProperties::new_with_orderings(schema, [ordering]),
2774+
Partitioning::UnknownPartitioning(num_partitions),
2775+
EmissionType::Incremental,
2776+
Boundedness::Bounded,
2777+
)),
2778+
}
2779+
}
2780+
}
2781+
2782+
impl DisplayAs for ExactSortPushdownExec {
2783+
fn fmt_as(&self, _t: DisplayFormatType, f: &mut Formatter) -> std::fmt::Result {
2784+
write!(f, "ExactSortPushdownExec")
2785+
}
2786+
}
2787+
2788+
impl ExecutionPlan for ExactSortPushdownExec {
2789+
fn name(&self) -> &str {
2790+
"ExactSortPushdownExec"
2791+
}
2792+
2793+
fn properties(&self) -> &Arc<PlanProperties> {
2794+
&self.cache
2795+
}
2796+
2797+
fn children(&self) -> Vec<&Arc<dyn ExecutionPlan>> {
2798+
vec![]
2799+
}
2800+
2801+
fn with_new_children(
2802+
self: Arc<Self>,
2803+
_: Vec<Arc<dyn ExecutionPlan>>,
2804+
) -> Result<Arc<dyn ExecutionPlan>> {
2805+
Ok(self)
2806+
}
2807+
2808+
fn execute(
2809+
&self,
2810+
_partition: usize,
2811+
_context: Arc<TaskContext>,
2812+
) -> Result<SendableRecordBatchStream> {
2813+
Ok(Box::pin(EmptyRecordBatchStream::new(self.schema())))
2814+
}
2815+
2816+
fn try_pushdown_sort(
2817+
&self,
2818+
_order: &[PhysicalSortExpr],
2819+
) -> Result<SortOrderPushdownResult<Arc<dyn ExecutionPlan>>> {
2820+
Ok(SortOrderPushdownResult::Exact {
2821+
inner: Arc::new(self.clone()),
2822+
})
2823+
}
2824+
}
2825+
25412826
#[tokio::test]
25422827
async fn test_repartition_with_coalescing() -> Result<()> {
25432828
let schema = test_schema(false);
@@ -3666,6 +3951,33 @@ mod test {
36663951
Ok(())
36673952
}
36683953

3954+
#[test]
3955+
fn test_range_repartitioned_returns_none() -> Result<()> {
3956+
let schema = test_schema();
3957+
let source = memory_exec(&schema);
3958+
let partitioning = Partitioning::Range(RangePartitioning::try_new(
3959+
[PhysicalSortExpr::new(
3960+
col("c0", &schema)?,
3961+
SortOptions::default(),
3962+
)]
3963+
.into(),
3964+
vec![
3965+
SplitPoint::new(vec![ScalarValue::UInt32(Some(10))]),
3966+
SplitPoint::new(vec![ScalarValue::UInt32(Some(20))]),
3967+
],
3968+
)?);
3969+
let exec = RepartitionExec::try_new(source, partitioning)?;
3970+
3971+
// Range partition count is fixed by split points, so repartitioned()
3972+
// cannot change it to an arbitrary target.
3973+
let result = exec.repartitioned(10, &Default::default())?;
3974+
assert!(
3975+
result.is_none(),
3976+
"range repartitioning should not support changing partition count"
3977+
);
3978+
Ok(())
3979+
}
3980+
36693981
fn test_schema() -> Arc<Schema> {
36703982
Arc::new(Schema::new(vec![Field::new("c0", DataType::UInt32, false)]))
36713983
}

0 commit comments

Comments
 (0)