Skip to content

Commit e123e6f

Browse files
authored
Allow Range partitioned inputs to PartitionedTopK (apache#23355)
## Which issue does this PR close? - Closes apache#23290. ## What changes are included in this PR? In two commits: * Improve the robustness of `WindowTopN` to intermediate `RepartitionExec` nodes, to ensure that `PartitionedTopK` can still be used when `target_partitions` mismatches physical partitions. * Use `required_input_distributions` to declare required partitioning for `PartitionedTopKExec`, `BoundedWindowAggExec`, and `WindowAggExec`. ## Are these changes tested? Yes, new `slt` tests are added for both the `WindowTopN` robustness fix, and for the use of `required_input_distributions` in `PartitionedTopK`. ## Are there any user-facing changes? No: only plan changes.
1 parent bc6e058 commit e123e6f

4 files changed

Lines changed: 239 additions & 40 deletions

File tree

‎datafusion/physical-optimizer/src/window_topn.rs‎

Lines changed: 36 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -61,6 +61,7 @@ use datafusion_physical_expr::window::StandardWindowExpr;
6161
use datafusion_physical_plan::ExecutionPlan;
6262
use datafusion_physical_plan::filter::FilterExec;
6363
use datafusion_physical_plan::projection::ProjectionExec;
64+
use datafusion_physical_plan::repartition::RepartitionExec;
6465
use datafusion_physical_plan::sorts::partitioned_topk::{
6566
PartitionedTopKExec, WindowFnKind,
6667
};
@@ -140,24 +141,25 @@ impl WindowTopN {
140141
// Step 2: Extract limit from predicate (rn <= K, rn < K, etc.)
141142
let (col_idx, limit_n) = extract_window_limit(filter.predicate())?;
142143

143-
// Step 3: Walk through optional ProjectionExec to find BoundedWindowAggExec
144+
// Step 3: Walk through optional ProjectionExec and RepartitionExec to find BoundedWindowAggExec
144145
let child = filter.input();
145-
let (window_exec, proj_between) = find_window_below(child)?;
146+
let (window_exec, intermediates) = find_window_below(child)?;
146147

147148
// Step 4: Verify col_idx references a supported window function output column
148-
let input_field_count = window_exec.input().schema().fields().len();
149+
let window_exec_typed = window_exec.downcast_ref::<BoundedWindowAggExec>()?;
150+
let sort_exec = window_exec_typed.input().downcast_ref::<SortExec>()?;
151+
let input_field_count = window_exec_typed.input().schema().fields().len();
149152
if col_idx < input_field_count {
150153
return None; // Filter is on an input column, not a window column
151154
}
152155
let window_expr_idx = col_idx - input_field_count;
153-
let window_exprs = window_exec.window_expr();
156+
let window_exprs = window_exec_typed.window_expr();
154157
if window_expr_idx >= window_exprs.len() {
155158
return None;
156159
}
157160
let fn_kind = supported_window_fn(&window_exprs[window_expr_idx])?;
158161

159-
// Step 5: Verify child of window is SortExec
160-
let sort_exec = window_exec.input().downcast_ref::<SortExec>()?;
162+
// Step 5: child of window is SortExec (verified above)
161163
let sort_child = sort_exec.input();
162164

163165
// Step 6: Determine partition_prefix_len from the window expression
@@ -190,28 +192,19 @@ impl WindowTopN {
190192
.ok()?;
191193

192194
// Step 8: Rebuild window with new child
193-
let new_window = Arc::clone(&child_as_arc(window_exec))
195+
let mut result = window_exec
194196
.with_new_children(vec![Arc::new(partitioned_topk)])
195197
.ok()?;
196198

197-
// Step 9: If ProjectionExec was between Filter and Window, rebuild it
198-
let result = match proj_between {
199-
Some(proj) => Arc::clone(&child_as_arc(proj))
200-
.with_new_children(vec![new_window])
201-
.ok()?,
202-
None => new_window,
203-
};
199+
// Step 9: Rebuild intermediate nodes (ProjectionExec/RepartitionExec)
200+
for node in intermediates.into_iter().rev() {
201+
result = node.with_new_children(vec![result]).ok()?;
202+
}
204203

205204
Some(result)
206205
}
207206
}
208207

209-
/// Helper to get an `Arc<dyn ExecutionPlan>` from a reference.
210-
/// We need this because `with_new_children` takes `Arc<Self>`.
211-
fn child_as_arc<T: ExecutionPlan + Clone + 'static>(plan: &T) -> Arc<dyn ExecutionPlan> {
212-
Arc::new(plan.clone())
213-
}
214-
215208
impl PhysicalOptimizerRule for WindowTopN {
216209
fn optimize(
217210
&self,
@@ -336,29 +329,32 @@ fn supported_window_fn(
336329
}
337330
}
338331

332+
type PlanAndIntermediates = (Arc<dyn ExecutionPlan>, Vec<Arc<dyn ExecutionPlan>>);
333+
339334
/// Walk below a plan node looking for a [`BoundedWindowAggExec`].
340335
///
341-
/// Handles two cases:
342-
/// - Direct child: `FilterExec → BoundedWindowAggExec`
343-
/// - With projection: `FilterExec → ProjectionExec → BoundedWindowAggExec`
336+
/// Handles sequences of `ProjectionExec` and `RepartitionExec`.
337+
/// This is safe because `PartitionedTopKExec` can be pushed below them:
338+
/// projections only provide aliases, and pushing the limit below repartitions
339+
/// is safe because the limit is computed per-partition.
344340
///
345-
/// Returns the window exec and an optional `ProjectionExec` in between,
346-
/// or `None` if no `BoundedWindowAggExec` is found within one or two levels.
347-
fn find_window_below(
348-
plan: &Arc<dyn ExecutionPlan>,
349-
) -> Option<(&BoundedWindowAggExec, Option<&ProjectionExec>)> {
350-
// Direct child is BoundedWindowAggExec
351-
if let Some(window) = plan.downcast_ref::<BoundedWindowAggExec>() {
352-
return Some((window, None));
353-
}
354-
355-
// Child is ProjectionExec with BoundedWindowAggExec below
356-
if let Some(proj) = plan.downcast_ref::<ProjectionExec>() {
357-
let proj_child = proj.input();
358-
if let Some(window) = proj_child.downcast_ref::<BoundedWindowAggExec>() {
359-
return Some((window, Some(proj)));
341+
/// Returns the window exec and a list of intermediate nodes to rebuild,
342+
/// or `None` if no `BoundedWindowAggExec` is found.
343+
fn find_window_below(plan: &Arc<dyn ExecutionPlan>) -> Option<PlanAndIntermediates> {
344+
let mut current = Arc::clone(plan);
345+
let mut intermediates = Vec::new();
346+
347+
loop {
348+
if current.downcast_ref::<BoundedWindowAggExec>().is_some() {
349+
return Some((current, intermediates));
350+
} else if current.downcast_ref::<ProjectionExec>().is_some()
351+
|| current.downcast_ref::<RepartitionExec>().is_some()
352+
{
353+
let next = Arc::clone(current.children().first()?);
354+
intermediates.push(current);
355+
current = next;
356+
} else {
357+
return None;
360358
}
361359
}
362-
363-
None
364360
}

‎datafusion/physical-plan/src/sorts/partitioned_topk.rs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -355,6 +355,7 @@ impl ExecutionPlan for PartitionedTopKExec {
355355
crate::InputDistributionRequirements::new(vec![Distribution::KeyPartitioned(
356356
partition_exprs,
357357
)])
358+
.allow_range_satisfaction_for_key_partitioning()
358359
}
359360

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

‎datafusion/sqllogictest/test_files/range_partitioning.slt‎

Lines changed: 157 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -907,5 +907,162 @@ SELECT range_key, SUM(value) OVER (ORDER BY value) FROM range_partitioned ORDER
907907
30 1060
908908
35 1410
909909

910+
911+
912+
##########
913+
# TEST 26: PartitionedTopK on Range Partition Column
914+
# Exact Range([range_key]) satisfies the TopK partition key and avoids repartitioning.
915+
##########
916+
917+
statement ok
918+
set datafusion.optimizer.enable_window_topn = true;
919+
920+
statement ok
921+
set datafusion.optimizer.subset_repartition_threshold = 4;
922+
923+
statement ok
924+
set datafusion.optimizer.preserve_file_partitions = 0;
925+
926+
query TT
927+
EXPLAIN SELECT * FROM (
928+
SELECT range_key, value, ROW_NUMBER() OVER (PARTITION BY range_key ORDER BY value DESC) as rn
929+
FROM range_partitioned
930+
) WHERE rn <= 1;
931+
----
932+
physical_plan
933+
01)ProjectionExec: expr=[range_key@0 as range_key, value@1 as value, row_number() PARTITION BY [range_partitioned.range_key] ORDER BY [range_partitioned.value DESC NULLS FIRST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@2 as rn]
934+
02)--BoundedWindowAggExec: wdw=[row_number() PARTITION BY [range_partitioned.range_key] ORDER BY [range_partitioned.value DESC NULLS FIRST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "row_number() PARTITION BY [range_partitioned.range_key] ORDER BY [range_partitioned.value DESC NULLS FIRST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": UInt64 }, frame: RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
935+
03)----PartitionedTopKExec: fn=row_number, fetch=1, partition=[range_key@0], order=[value@1 DESC]
936+
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
937+
938+
query III
939+
SELECT * FROM (
940+
SELECT range_key, value, ROW_NUMBER() OVER (PARTITION BY range_key ORDER BY value DESC) as rn
941+
FROM range_partitioned
942+
) WHERE rn <= 1
943+
ORDER BY range_key;
944+
----
945+
1 10 1
946+
5 50 1
947+
10 100 1
948+
15 150 1
949+
20 200 1
950+
25 250 1
951+
30 300 1
952+
35 350 1
953+
954+
955+
##########
956+
# TEST 27: PartitionedTopK on Non-Range Column
957+
# Partitioning on a non-range key cannot reuse Range([range_key]) and
958+
# requires hash repartitioning.
959+
##########
960+
961+
statement ok
962+
set datafusion.optimizer.subset_repartition_threshold = 4;
963+
964+
statement ok
965+
set datafusion.optimizer.preserve_file_partitions = 0;
966+
967+
query TT
968+
EXPLAIN SELECT * FROM (
969+
SELECT non_range_key, value, ROW_NUMBER() OVER (PARTITION BY non_range_key ORDER BY value DESC) as rn
970+
FROM range_partitioned
971+
) WHERE rn <= 1;
972+
----
973+
physical_plan
974+
01)ProjectionExec: expr=[non_range_key@0 as non_range_key, value@1 as value, row_number() PARTITION BY [range_partitioned.non_range_key] ORDER BY [range_partitioned.value DESC NULLS FIRST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@2 as rn]
975+
02)--BoundedWindowAggExec: wdw=[row_number() PARTITION BY [range_partitioned.non_range_key] ORDER BY [range_partitioned.value DESC NULLS FIRST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "row_number() PARTITION BY [range_partitioned.non_range_key] ORDER BY [range_partitioned.value DESC NULLS FIRST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": UInt64 }, frame: RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
976+
03)----PartitionedTopKExec: fn=row_number, fetch=1, partition=[non_range_key@0], order=[value@1 DESC]
977+
04)------RepartitionExec: partitioning=Hash([non_range_key@0], 4), input_partitions=4
978+
05)--------DataSourceExec: file_groups=<slt:ignore>, projection=[non_range_key, value], output_partitioning=UnknownPartitioning(4), file_type=csv, has_header=false
979+
980+
query III
981+
SELECT * FROM (
982+
SELECT non_range_key, value, ROW_NUMBER() OVER (PARTITION BY non_range_key ORDER BY value DESC) as rn
983+
FROM range_partitioned
984+
) WHERE rn <= 1
985+
ORDER BY non_range_key;
986+
----
987+
1 300 1
988+
2 350 1
989+
990+
991+
##########
992+
# TEST 28: PartitionedTopK Reuses Range Subset Partitioning
993+
# With subset threshold met and preserve-file disabled, Range([range_key])
994+
# satisfies partitioning by (range_key, non_range_key).
995+
##########
996+
997+
statement ok
998+
set datafusion.optimizer.subset_repartition_threshold = 4;
999+
1000+
statement ok
1001+
set datafusion.optimizer.preserve_file_partitions = 0;
1002+
1003+
query TT
1004+
EXPLAIN SELECT * FROM (
1005+
SELECT range_key, non_range_key, value, ROW_NUMBER() OVER (PARTITION BY range_key, non_range_key ORDER BY value DESC) as rn
1006+
FROM range_partitioned
1007+
) WHERE rn <= 1;
1008+
----
1009+
physical_plan
1010+
01)ProjectionExec: expr=[range_key@0 as range_key, non_range_key@1 as non_range_key, value@2 as value, row_number() PARTITION BY [range_partitioned.range_key, range_partitioned.non_range_key] ORDER BY [range_partitioned.value DESC NULLS FIRST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@3 as rn]
1011+
02)--BoundedWindowAggExec: wdw=[row_number() PARTITION BY [range_partitioned.range_key, range_partitioned.non_range_key] ORDER BY [range_partitioned.value DESC NULLS FIRST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "row_number() PARTITION BY [range_partitioned.range_key, range_partitioned.non_range_key] ORDER BY [range_partitioned.value DESC NULLS FIRST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": UInt64 }, frame: RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
1012+
03)----PartitionedTopKExec: fn=row_number, fetch=1, partition=[range_key@0, non_range_key@1], order=[value@2 DESC]
1013+
04)------DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, non_range_key, value], output_partitioning=Range([range_key@0 ASC], [(10), (20), (30)], 4), file_type=csv, has_header=false
1014+
1015+
query IIII
1016+
SELECT * FROM (
1017+
SELECT range_key, non_range_key, value, ROW_NUMBER() OVER (PARTITION BY range_key, non_range_key ORDER BY value DESC) as rn
1018+
FROM range_partitioned
1019+
) WHERE rn <= 1
1020+
ORDER BY range_key, non_range_key;
1021+
----
1022+
1 1 10 1
1023+
5 2 50 1
1024+
10 1 100 1
1025+
15 2 150 1
1026+
20 1 200 1
1027+
25 2 250 1
1028+
30 1 300 1
1029+
35 2 350 1
1030+
1031+
1032+
##########
1033+
# TEST 29: Range Subset PartitionedTopK Rehashes Below Subset Threshold
1034+
# Range([range_key]) is only a subset of PARTITION BY (range_key, non_range_key),
1035+
# so it should not satisfy the TopK partition key when subset satisfaction is
1036+
# disabled.
1037+
##########
1038+
1039+
statement ok
1040+
set datafusion.execution.target_partitions = 4;
1041+
1042+
statement ok
1043+
set datafusion.optimizer.subset_repartition_threshold = 5;
1044+
1045+
statement ok
1046+
set datafusion.optimizer.preserve_file_partitions = 0;
1047+
1048+
query TT
1049+
EXPLAIN SELECT * FROM (
1050+
SELECT range_key, non_range_key, value, ROW_NUMBER() OVER (PARTITION BY range_key, non_range_key ORDER BY value DESC) as rn
1051+
FROM range_partitioned
1052+
) WHERE rn <= 1;
1053+
----
1054+
physical_plan
1055+
01)ProjectionExec: expr=[range_key@0 as range_key, non_range_key@1 as non_range_key, value@2 as value, row_number() PARTITION BY [range_partitioned.range_key, range_partitioned.non_range_key] ORDER BY [range_partitioned.value DESC NULLS FIRST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@3 as rn]
1056+
02)--BoundedWindowAggExec: wdw=[row_number() PARTITION BY [range_partitioned.range_key, range_partitioned.non_range_key] ORDER BY [range_partitioned.value DESC NULLS FIRST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "row_number() PARTITION BY [range_partitioned.range_key, range_partitioned.non_range_key] ORDER BY [range_partitioned.value DESC NULLS FIRST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": UInt64 }, frame: RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
1057+
03)----PartitionedTopKExec: fn=row_number, fetch=1, partition=[range_key@0, non_range_key@1], order=[value@2 DESC]
1058+
04)------RepartitionExec: partitioning=Hash([range_key@0, non_range_key@1], 4), input_partitions=4
1059+
05)--------DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, non_range_key, value], output_partitioning=Range([range_key@0 ASC], [(10), (20), (30)], 4), file_type=csv, has_header=false
1060+
1061+
statement ok
1062+
reset datafusion.optimizer.subset_repartition_threshold;
1063+
9101064
statement ok
9111065
reset datafusion.explain.physical_plan_only;
1066+
1067+
statement ok
1068+
reset datafusion.optimizer.enable_window_topn;

‎datafusion/sqllogictest/test_files/window_topn.slt‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1044,3 +1044,48 @@ DROP TABLE window_topn_rank_null_t;
10441044
# Reset config to default (false)
10451045
statement ok
10461046
SET datafusion.optimizer.enable_window_topn = false;
1047+
1048+
statement ok
1049+
create table t(c1 int, c2 int) as values (1, 2), (3, 4);
1050+
1051+
statement ok
1052+
set datafusion.execution.target_partitions = 5;
1053+
1054+
statement ok
1055+
set datafusion.optimizer.repartition_windows = false;
1056+
1057+
statement ok
1058+
set datafusion.execution.batch_size = 1;
1059+
1060+
statement ok
1061+
set datafusion.optimizer.enable_window_topn = true;
1062+
1063+
query TT
1064+
EXPLAIN SELECT * FROM (
1065+
SELECT c1, c2, ROW_NUMBER() OVER (PARTITION BY c1 ORDER BY c2 DESC) as rn
1066+
FROM t
1067+
) WHERE rn <= 1;
1068+
----
1069+
logical_plan
1070+
01)Projection: t.c1, t.c2, row_number() PARTITION BY [t.c1] ORDER BY [t.c2 DESC NULLS FIRST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW AS rn
1071+
02)--Filter: row_number() PARTITION BY [t.c1] ORDER BY [t.c2 DESC NULLS FIRST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW <= UInt64(1)
1072+
03)----WindowAggr: windowExpr=[[row_number() PARTITION BY [t.c1] ORDER BY [t.c2 DESC NULLS FIRST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW]]
1073+
04)------TableScan: t projection=[c1, c2]
1074+
physical_plan
1075+
01)ProjectionExec: expr=[c1@0 as c1, c2@1 as c2, row_number() PARTITION BY [t.c1] ORDER BY [t.c2 DESC NULLS FIRST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@2 as rn]
1076+
02)--RepartitionExec: partitioning=RoundRobinBatch(5), input_partitions=1, maintains_sort_order=true
1077+
03)----BoundedWindowAggExec: wdw=[row_number() PARTITION BY [t.c1] ORDER BY [t.c2 DESC NULLS FIRST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "row_number() PARTITION BY [t.c1] ORDER BY [t.c2 DESC NULLS FIRST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": UInt64 }, frame: RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
1078+
04)------PartitionedTopKExec: fn=row_number, fetch=1, partition=[c1@0], order=[c2@1 DESC]
1079+
05)--------DataSourceExec: partitions=1, partition_sizes=[1]
1080+
1081+
statement ok
1082+
set datafusion.execution.target_partitions = 4;
1083+
1084+
statement ok
1085+
set datafusion.optimizer.repartition_windows = true;
1086+
1087+
statement ok
1088+
set datafusion.execution.batch_size = 8192;
1089+
1090+
statement ok
1091+
set datafusion.optimizer.enable_window_topn = false;

0 commit comments

Comments
 (0)