Skip to content

Commit 4b68de6

Browse files
authored
feat: allow Partitioning::Range to satisfy window Distribution::KeyPartitioned requirements (apache#23416)
## Which issue does this PR close? - Closes apache#23289. Rebased on main now that apache#23184 has merged. Overlaps with apache#23355, which also opts the window execs into range satisfaction as part of its PartitionedTopK work — happy to rebase whichever lands second. ## What changes are included in this PR? In one commit: * Opt `WindowAggExec` and `BoundedWindowAggExec` with partition keys into range satisfaction via `InputDistributionRequirements::allow_range_satisfaction_for_key_partitioning`, mirroring `AggregateExec`. Compatible range-partitioned inputs then satisfy the window key requirement without a hash repartition; subset satisfaction and the hash fallback for incompatible keys come from the existing satisfaction machinery. Windows without `PARTITION BY` keep requiring a single partition. ## Are these changes tested? Yes: new `slt` tests in `range_partitioning.slt` (exact and subset reuse, rehash on incompatible keys, `subset_repartition_threshold` / `preserve_file_partitions` / `target_partitions` behavior, `WindowAggExec` via an unbounded frame, and no-`PARTITION BY`), plus plan-shape tests in `enforce_distribution.rs` and acceptance/rejection tests in `sanity_checker.rs`. ## Are there any user-facing changes? No: only plan changes.
1 parent d1e6d45 commit 4b68de6

6 files changed

Lines changed: 403 additions & 20 deletions

File tree

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

Lines changed: 65 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -20,8 +20,8 @@ use std::ops::Deref;
2020
use std::sync::Arc;
2121

2222
use crate::physical_optimizer::test_utils::{
23-
check_integrity, coalesce_partitions_exec, parquet_exec_with_sort,
24-
parquet_exec_with_stats, repartition_exec, schema, sort_exec,
23+
bounded_window_exec_with_can_repartition, check_integrity, coalesce_partitions_exec,
24+
parquet_exec_with_sort, parquet_exec_with_stats, repartition_exec, schema, sort_exec,
2525
sort_exec_with_preserve_partitioning, sort_merge_join_exec,
2626
sort_preserving_merge_exec, union_exec,
2727
};
@@ -870,6 +870,69 @@ fn range_inner_hash_join_rehashes_incompatible_range_partitioning() -> Result<()
870870
Ok(())
871871
}
872872

873+
#[test]
874+
fn range_window_reuses_range_partitioning() -> Result<()> {
875+
let input = parquet_exec_with_output_partitioning(range_partitioning(
876+
"a",
877+
[10, 20, 30],
878+
SortOptions::default(),
879+
)?);
880+
let window = bounded_window_exec_with_can_repartition(
881+
"a",
882+
vec![],
883+
&[col("a", &schema())?],
884+
input,
885+
true,
886+
);
887+
888+
let plan = TestConfig::default()
889+
.with_query_execution_partitions(4)
890+
.to_plan(window, &DISTRIB_DISTRIB_SORT);
891+
892+
assert_plan!(
893+
plan,
894+
@r#"
895+
BoundedWindowAggExec: wdw=[count: Field { "count": Int64 }, frame: RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
896+
SortExec: expr=[a@0 ASC NULLS LAST], preserve_partitioning=[true]
897+
DataSourceExec: file_groups={4 groups: [[p0], [p1], [p2], [p3]]}, projection=[a, b, c, d, e], output_partitioning=Range([a@0 ASC], [(10), (20), (30)], 4), file_type=parquet
898+
"#
899+
);
900+
901+
Ok(())
902+
}
903+
904+
#[test]
905+
fn range_window_rehashes_incompatible_range_partitioning() -> Result<()> {
906+
let input = parquet_exec_with_output_partitioning(range_partitioning(
907+
"a",
908+
[10, 20, 30],
909+
SortOptions::default(),
910+
)?);
911+
let window = bounded_window_exec_with_can_repartition(
912+
"b",
913+
vec![],
914+
&[col("b", &schema())?],
915+
input,
916+
true,
917+
);
918+
919+
let plan = TestConfig::default()
920+
.with_query_execution_partitions(4)
921+
.to_plan(window, &DISTRIB_DISTRIB_SORT);
922+
923+
assert_plan!(
924+
plan,
925+
@r#"
926+
BoundedWindowAggExec: wdw=[count: Field { "count": Int64 }, frame: RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
927+
SortExec: expr=[b@1 ASC NULLS LAST], preserve_partitioning=[true]
928+
RepartitionExec: partitioning=Hash([b@1], 4), input_partitions=4
929+
DataSourceExec: file_groups={4 groups: [[p0], [p1], [p2], [p3]]}, projection=[a, b, c, d, e], output_partitioning=Range([a@0 ASC], [(10), (20), (30)], 4), file_type=parquet
930+
"#
931+
);
932+
933+
Ok(())
934+
}
935+
873936
#[test]
874937
fn multi_hash_joins() -> Result<()> {
875938
let left = parquet_exec();

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

Lines changed: 74 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -19,9 +19,10 @@ use insta::assert_snapshot;
1919
use std::sync::Arc;
2020

2121
use crate::physical_optimizer::test_utils::{
22-
bounded_window_exec, global_limit_exec, hash_join_exec, local_limit_exec,
23-
memory_exec, projection_exec, repartition_exec, sort_exec, sort_expr,
24-
sort_expr_options, sort_merge_join_exec, sort_preserving_merge_exec, union_exec,
22+
bounded_window_exec, bounded_window_exec_with_can_repartition, global_limit_exec,
23+
hash_join_exec, local_limit_exec, memory_exec, projection_exec, repartition_exec,
24+
sort_exec, sort_exec_with_preserve_partitioning, sort_expr, sort_expr_options,
25+
sort_merge_join_exec, sort_preserving_merge_exec, union_exec,
2526
};
2627

2728
use arrow::compute::SortOptions;
@@ -501,6 +502,76 @@ async fn test_bounded_window_agg_no_sort_requirement() -> Result<()> {
501502
Ok(())
502503
}
503504

505+
#[tokio::test]
506+
/// Tests that a window over a compatible range-partitioned input satisfies
507+
/// the window's key distribution requirement without a hash repartition.
508+
async fn test_bounded_window_agg_range_partitioning() -> Result<()> {
509+
let schema = create_test_schema2();
510+
let source = range_partitioned_exec(&schema, "a", [10, 20, 30])?;
511+
let ordering: LexOrdering = [sort_expr_options(
512+
"a",
513+
&schema,
514+
SortOptions {
515+
descending: false,
516+
nulls_first: false,
517+
},
518+
)]
519+
.into();
520+
let partition_by = vec![col("a", &schema)?];
521+
let sort = sort_exec_with_preserve_partitioning(ordering, source);
522+
let bw =
523+
bounded_window_exec_with_can_repartition("a", vec![], &partition_by, sort, true);
524+
let plan_str = displayable(bw.as_ref()).indent(true).to_string();
525+
let actual = plan_str.trim();
526+
assert_snapshot!(
527+
actual,
528+
@r#"
529+
BoundedWindowAggExec: wdw=[count: Field { "count": Int64 }, frame: RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
530+
SortExec: expr=[a@0 ASC NULLS LAST], preserve_partitioning=[true]
531+
RepartitionExec: partitioning=Range([a@0 ASC], [(10), (20), (30)], 4), input_partitions=1
532+
DataSourceExec: partitions=1, partition_sizes=[0]
533+
"#
534+
);
535+
assert_sanity_check(&bw, true);
536+
Ok(())
537+
}
538+
539+
#[tokio::test]
540+
/// Tests that a window over an incompatible range-partitioned input fails
541+
/// the window's key distribution requirement.
542+
async fn test_bounded_window_agg_incompatible_range_partitioning() -> Result<()> {
543+
let schema = create_test_schema2();
544+
let source = range_partitioned_exec(&schema, "a", [10, 20, 30])?;
545+
let ordering: LexOrdering = [sort_expr_options(
546+
"b",
547+
&schema,
548+
SortOptions {
549+
descending: false,
550+
nulls_first: false,
551+
},
552+
)]
553+
.into();
554+
let partition_by = vec![col("b", &schema)?];
555+
let sort = sort_exec_with_preserve_partitioning(ordering, source);
556+
let bw =
557+
bounded_window_exec_with_can_repartition("b", vec![], &partition_by, sort, true);
558+
let plan_str = displayable(bw.as_ref()).indent(true).to_string();
559+
let actual = plan_str.trim();
560+
assert_snapshot!(
561+
actual,
562+
@r#"
563+
BoundedWindowAggExec: wdw=[count: Field { "count": Int64 }, frame: RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
564+
SortExec: expr=[b@1 ASC NULLS LAST], preserve_partitioning=[true]
565+
RepartitionExec: partitioning=Range([a@0 ASC], [(10), (20), (30)], 4), input_partitions=1
566+
DataSourceExec: partitions=1, partition_sizes=[0]
567+
"#
568+
);
569+
// Range([a]) does not colocate `b` values, so the window's key
570+
// distribution requirement is not satisfied.
571+
assert_sanity_check(&bw, false);
572+
Ok(())
573+
}
574+
504575
#[tokio::test]
505576
/// A valid when a single partition requirement
506577
/// is satisfied.

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

Lines changed: 17 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -274,6 +274,22 @@ pub fn bounded_window_exec_with_partition(
274274
sort_exprs: impl IntoIterator<Item = PhysicalSortExpr>,
275275
partition_by: &[Arc<dyn PhysicalExpr>],
276276
input: Arc<dyn ExecutionPlan>,
277+
) -> Arc<dyn ExecutionPlan> {
278+
bounded_window_exec_with_can_repartition(
279+
col_name,
280+
sort_exprs,
281+
partition_by,
282+
input,
283+
false,
284+
)
285+
}
286+
287+
pub fn bounded_window_exec_with_can_repartition(
288+
col_name: &str,
289+
sort_exprs: impl IntoIterator<Item = PhysicalSortExpr>,
290+
partition_by: &[Arc<dyn PhysicalExpr>],
291+
input: Arc<dyn ExecutionPlan>,
292+
can_repartition: bool,
277293
) -> Arc<dyn ExecutionPlan> {
278294
let sort_exprs = sort_exprs.into_iter().collect::<Vec<_>>();
279295
let schema = input.schema();
@@ -296,7 +312,7 @@ pub fn bounded_window_exec_with_partition(
296312
vec![window_expr],
297313
Arc::clone(&input),
298314
InputOrderMode::Sorted,
299-
false,
315+
can_repartition,
300316
)
301317
.unwrap(),
302318
)

‎datafusion/physical-plan/src/windows/bounded_window_agg_exec.rs‎

Lines changed: 11 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -36,8 +36,9 @@ use crate::windows::{
3636
};
3737
use crate::{
3838
ColumnStatistics, DisplayAs, DisplayFormatType, Distribution, ExecutionPlan,
39-
ExecutionPlanProperties, InputOrderMode, PlanProperties, RecordBatchStream,
40-
SendableRecordBatchStream, Statistics, WindowExpr, check_if_same_properties,
39+
ExecutionPlanProperties, InputDistributionRequirements, InputOrderMode,
40+
PlanProperties, RecordBatchStream, SendableRecordBatchStream, Statistics, WindowExpr,
41+
check_if_same_properties,
4142
};
4243

4344
use arrow::compute::take_record_batch;
@@ -324,13 +325,16 @@ impl ExecutionPlan for BoundedWindowAggExec {
324325
self.input_distribution_requirements().into_per_child()
325326
}
326327

327-
fn input_distribution_requirements(&self) -> crate::InputDistributionRequirements {
328-
crate::InputDistributionRequirements::new(if self.partition_keys().is_empty() {
328+
fn input_distribution_requirements(&self) -> InputDistributionRequirements {
329+
if self.partition_keys().is_empty() {
329330
debug!("No partition defined for BoundedWindowAggExec!!!");
330-
vec![Distribution::SinglePartition]
331+
InputDistributionRequirements::new(vec![Distribution::SinglePartition])
331332
} else {
332-
vec![Distribution::KeyPartitioned(self.partition_keys().clone())]
333-
})
333+
InputDistributionRequirements::new(vec![Distribution::KeyPartitioned(
334+
self.partition_keys(),
335+
)])
336+
.allow_range_satisfaction_for_key_partitioning()
337+
}
334338
}
335339

336340
fn maintains_input_order(&self) -> Vec<bool> {

‎datafusion/physical-plan/src/windows/window_agg_exec.rs‎

Lines changed: 11 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -32,8 +32,9 @@ use crate::windows::{
3232
};
3333
use crate::{
3434
ColumnStatistics, DisplayAs, DisplayFormatType, Distribution, ExecutionPlan,
35-
ExecutionPlanProperties, PhysicalExpr, PlanProperties, RecordBatchStream,
36-
SendableRecordBatchStream, Statistics, WindowExpr, check_if_same_properties,
35+
ExecutionPlanProperties, InputDistributionRequirements, PhysicalExpr, PlanProperties,
36+
RecordBatchStream, SendableRecordBatchStream, Statistics, WindowExpr,
37+
check_if_same_properties,
3738
};
3839

3940
use arrow::array::ArrayRef;
@@ -233,12 +234,15 @@ impl ExecutionPlan for WindowAggExec {
233234
self.input_distribution_requirements().into_per_child()
234235
}
235236

236-
fn input_distribution_requirements(&self) -> crate::InputDistributionRequirements {
237-
crate::InputDistributionRequirements::new(if self.partition_keys().is_empty() {
238-
vec![Distribution::SinglePartition]
237+
fn input_distribution_requirements(&self) -> InputDistributionRequirements {
238+
if self.partition_keys().is_empty() {
239+
InputDistributionRequirements::new(vec![Distribution::SinglePartition])
239240
} else {
240-
vec![Distribution::KeyPartitioned(self.partition_keys())]
241-
})
241+
InputDistributionRequirements::new(vec![Distribution::KeyPartitioned(
242+
self.partition_keys(),
243+
)])
244+
.allow_range_satisfaction_for_key_partitioning()
245+
}
242246
}
243247

244248
fn with_new_children(

0 commit comments

Comments
 (0)