You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by gi...@apache.org on 2026/07/15 09:36:42 UTC
(datafusion) branch gh-readonly-queue/main/pr-23355-bc6e058a96ddf4ac1f5247ec25a8ef1fe1d4fab3 created (now e123e6fc7b)
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a change to branch gh-readonly-queue/main/pr-23355-bc6e058a96ddf4ac1f5247ec25a8ef1fe1d4fab3
in repository https://gitbox.apache.org/repos/asf/datafusion.git
at e123e6fc7b Allow Range partitioned inputs to PartitionedTopK (#23355)
This branch includes the following new commits:
new e123e6fc7b Allow Range partitioned inputs to PartitionedTopK (#23355)
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org
(datafusion) 01/01: Allow Range partitioned inputs to PartitionedTopK (#23355)
Posted by gi...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-23355-bc6e058a96ddf4ac1f5247ec25a8ef1fe1d4fab3
in repository https://gitbox.apache.org/repos/asf/datafusion.git
commit e123e6fc7b04de1261dcb14e8343062f1fa9107e
Author: Stu Hood <st...@gmail.com>
AuthorDate: Wed Jul 15 02:36:20 2026 -0700
Allow Range partitioned inputs to PartitionedTopK (#23355)
## Which issue does this PR close?
- Closes #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.
---
datafusion/physical-optimizer/src/window_topn.rs | 76 +++++-----
.../physical-plan/src/sorts/partitioned_topk.rs | 1 +
.../sqllogictest/test_files/range_partitioning.slt | 157 +++++++++++++++++++++
datafusion/sqllogictest/test_files/window_topn.slt | 45 ++++++
4 files changed, 239 insertions(+), 40 deletions(-)
diff --git a/datafusion/physical-optimizer/src/window_topn.rs b/datafusion/physical-optimizer/src/window_topn.rs
index 3f88e86c67..c668608ca2 100644
--- a/datafusion/physical-optimizer/src/window_topn.rs
+++ b/datafusion/physical-optimizer/src/window_topn.rs
@@ -61,6 +61,7 @@ use datafusion_physical_expr::window::StandardWindowExpr;
use datafusion_physical_plan::ExecutionPlan;
use datafusion_physical_plan::filter::FilterExec;
use datafusion_physical_plan::projection::ProjectionExec;
+use datafusion_physical_plan::repartition::RepartitionExec;
use datafusion_physical_plan::sorts::partitioned_topk::{
PartitionedTopKExec, WindowFnKind,
};
@@ -140,24 +141,25 @@ impl WindowTopN {
// Step 2: Extract limit from predicate (rn <= K, rn < K, etc.)
let (col_idx, limit_n) = extract_window_limit(filter.predicate())?;
- // Step 3: Walk through optional ProjectionExec to find BoundedWindowAggExec
+ // Step 3: Walk through optional ProjectionExec and RepartitionExec to find BoundedWindowAggExec
let child = filter.input();
- let (window_exec, proj_between) = find_window_below(child)?;
+ let (window_exec, intermediates) = find_window_below(child)?;
// Step 4: Verify col_idx references a supported window function output column
- let input_field_count = window_exec.input().schema().fields().len();
+ let window_exec_typed = window_exec.downcast_ref::<BoundedWindowAggExec>()?;
+ let sort_exec = window_exec_typed.input().downcast_ref::<SortExec>()?;
+ let input_field_count = window_exec_typed.input().schema().fields().len();
if col_idx < input_field_count {
return None; // Filter is on an input column, not a window column
}
let window_expr_idx = col_idx - input_field_count;
- let window_exprs = window_exec.window_expr();
+ let window_exprs = window_exec_typed.window_expr();
if window_expr_idx >= window_exprs.len() {
return None;
}
let fn_kind = supported_window_fn(&window_exprs[window_expr_idx])?;
- // Step 5: Verify child of window is SortExec
- let sort_exec = window_exec.input().downcast_ref::<SortExec>()?;
+ // Step 5: child of window is SortExec (verified above)
let sort_child = sort_exec.input();
// Step 6: Determine partition_prefix_len from the window expression
@@ -190,28 +192,19 @@ impl WindowTopN {
.ok()?;
// Step 8: Rebuild window with new child
- let new_window = Arc::clone(&child_as_arc(window_exec))
+ let mut result = window_exec
.with_new_children(vec![Arc::new(partitioned_topk)])
.ok()?;
- // Step 9: If ProjectionExec was between Filter and Window, rebuild it
- let result = match proj_between {
- Some(proj) => Arc::clone(&child_as_arc(proj))
- .with_new_children(vec![new_window])
- .ok()?,
- None => new_window,
- };
+ // Step 9: Rebuild intermediate nodes (ProjectionExec/RepartitionExec)
+ for node in intermediates.into_iter().rev() {
+ result = node.with_new_children(vec![result]).ok()?;
+ }
Some(result)
}
}
-/// Helper to get an `Arc<dyn ExecutionPlan>` from a reference.
-/// We need this because `with_new_children` takes `Arc<Self>`.
-fn child_as_arc<T: ExecutionPlan + Clone + 'static>(plan: &T) -> Arc<dyn ExecutionPlan> {
- Arc::new(plan.clone())
-}
-
impl PhysicalOptimizerRule for WindowTopN {
fn optimize(
&self,
@@ -336,29 +329,32 @@ fn supported_window_fn(
}
}
+type PlanAndIntermediates = (Arc<dyn ExecutionPlan>, Vec<Arc<dyn ExecutionPlan>>);
+
/// Walk below a plan node looking for a [`BoundedWindowAggExec`].
///
-/// Handles two cases:
-/// - Direct child: `FilterExec → BoundedWindowAggExec`
-/// - With projection: `FilterExec → ProjectionExec → BoundedWindowAggExec`
+/// Handles sequences of `ProjectionExec` and `RepartitionExec`.
+/// This is safe because `PartitionedTopKExec` can be pushed below them:
+/// projections only provide aliases, and pushing the limit below repartitions
+/// is safe because the limit is computed per-partition.
///
-/// Returns the window exec and an optional `ProjectionExec` in between,
-/// or `None` if no `BoundedWindowAggExec` is found within one or two levels.
-fn find_window_below(
- plan: &Arc<dyn ExecutionPlan>,
-) -> Option<(&BoundedWindowAggExec, Option<&ProjectionExec>)> {
- // Direct child is BoundedWindowAggExec
- if let Some(window) = plan.downcast_ref::<BoundedWindowAggExec>() {
- return Some((window, None));
- }
-
- // Child is ProjectionExec with BoundedWindowAggExec below
- if let Some(proj) = plan.downcast_ref::<ProjectionExec>() {
- let proj_child = proj.input();
- if let Some(window) = proj_child.downcast_ref::<BoundedWindowAggExec>() {
- return Some((window, Some(proj)));
+/// Returns the window exec and a list of intermediate nodes to rebuild,
+/// or `None` if no `BoundedWindowAggExec` is found.
+fn find_window_below(plan: &Arc<dyn ExecutionPlan>) -> Option<PlanAndIntermediates> {
+ let mut current = Arc::clone(plan);
+ let mut intermediates = Vec::new();
+
+ loop {
+ if current.downcast_ref::<BoundedWindowAggExec>().is_some() {
+ return Some((current, intermediates));
+ } else if current.downcast_ref::<ProjectionExec>().is_some()
+ || current.downcast_ref::<RepartitionExec>().is_some()
+ {
+ let next = Arc::clone(current.children().first()?);
+ intermediates.push(current);
+ current = next;
+ } else {
+ return None;
}
}
-
- None
}
diff --git a/datafusion/physical-plan/src/sorts/partitioned_topk.rs b/datafusion/physical-plan/src/sorts/partitioned_topk.rs
index 730440a429..c250130341 100644
--- a/datafusion/physical-plan/src/sorts/partitioned_topk.rs
+++ b/datafusion/physical-plan/src/sorts/partitioned_topk.rs
@@ -355,6 +355,7 @@ impl ExecutionPlan for PartitionedTopKExec {
crate::InputDistributionRequirements::new(vec![Distribution::KeyPartitioned(
partition_exprs,
)])
+ .allow_range_satisfaction_for_key_partitioning()
}
fn maintains_input_order(&self) -> Vec<bool> {
diff --git a/datafusion/sqllogictest/test_files/range_partitioning.slt b/datafusion/sqllogictest/test_files/range_partitioning.slt
index 2cf3b87e3c..6c456fe363 100644
--- a/datafusion/sqllogictest/test_files/range_partitioning.slt
+++ b/datafusion/sqllogictest/test_files/range_partitioning.slt
@@ -907,5 +907,162 @@ SELECT range_key, SUM(value) OVER (ORDER BY value) FROM range_partitioned ORDER
30 1060
35 1410
+
+
+##########
+# TEST 26: PartitionedTopK on Range Partition Column
+# Exact Range([range_key]) satisfies the TopK partition key and avoids repartitioning.
+##########
+
+statement ok
+set datafusion.optimizer.enable_window_topn = true;
+
+statement ok
+set datafusion.optimizer.subset_repartition_threshold = 4;
+
+statement ok
+set datafusion.optimizer.preserve_file_partitions = 0;
+
+query TT
+EXPLAIN SELECT * FROM (
+ SELECT range_key, value, ROW_NUMBER() OVER (PARTITION BY range_key ORDER BY value DESC) as rn
+ FROM range_partitioned
+) WHERE rn <= 1;
+----
+physical_plan
+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]
+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]
+03)----PartitionedTopKExec: fn=row_number, fetch=1, partition=[range_key@0], order=[value@1 DESC]
+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
+
+query III
+SELECT * FROM (
+ SELECT range_key, value, ROW_NUMBER() OVER (PARTITION BY range_key ORDER BY value DESC) as rn
+ FROM range_partitioned
+) WHERE rn <= 1
+ORDER BY range_key;
+----
+1 10 1
+5 50 1
+10 100 1
+15 150 1
+20 200 1
+25 250 1
+30 300 1
+35 350 1
+
+
+##########
+# TEST 27: PartitionedTopK on Non-Range Column
+# Partitioning on a non-range key cannot reuse Range([range_key]) and
+# requires hash repartitioning.
+##########
+
+statement ok
+set datafusion.optimizer.subset_repartition_threshold = 4;
+
+statement ok
+set datafusion.optimizer.preserve_file_partitions = 0;
+
+query TT
+EXPLAIN SELECT * FROM (
+ SELECT non_range_key, value, ROW_NUMBER() OVER (PARTITION BY non_range_key ORDER BY value DESC) as rn
+ FROM range_partitioned
+) WHERE rn <= 1;
+----
+physical_plan
+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]
+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]
+03)----PartitionedTopKExec: fn=row_number, fetch=1, partition=[non_range_key@0], order=[value@1 DESC]
+04)------RepartitionExec: partitioning=Hash([non_range_key@0], 4), input_partitions=4
+05)--------DataSourceExec: file_groups=<slt:ignore>, projection=[non_range_key, value], output_partitioning=UnknownPartitioning(4), file_type=csv, has_header=false
+
+query III
+SELECT * FROM (
+ SELECT non_range_key, value, ROW_NUMBER() OVER (PARTITION BY non_range_key ORDER BY value DESC) as rn
+ FROM range_partitioned
+) WHERE rn <= 1
+ORDER BY non_range_key;
+----
+1 300 1
+2 350 1
+
+
+##########
+# TEST 28: PartitionedTopK Reuses Range Subset Partitioning
+# With subset threshold met and preserve-file disabled, Range([range_key])
+# satisfies partitioning by (range_key, non_range_key).
+##########
+
+statement ok
+set datafusion.optimizer.subset_repartition_threshold = 4;
+
+statement ok
+set datafusion.optimizer.preserve_file_partitions = 0;
+
+query TT
+EXPLAIN SELECT * FROM (
+ SELECT range_key, non_range_key, value, ROW_NUMBER() OVER (PARTITION BY range_key, non_range_key ORDER BY value DESC) as rn
+ FROM range_partitioned
+) WHERE rn <= 1;
+----
+physical_plan
+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]
+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 [...]
+03)----PartitionedTopKExec: fn=row_number, fetch=1, partition=[range_key@0, non_range_key@1], order=[value@2 DESC]
+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
+
+query IIII
+SELECT * FROM (
+ SELECT range_key, non_range_key, value, ROW_NUMBER() OVER (PARTITION BY range_key, non_range_key ORDER BY value DESC) as rn
+ FROM range_partitioned
+) WHERE rn <= 1
+ORDER BY range_key, non_range_key;
+----
+1 1 10 1
+5 2 50 1
+10 1 100 1
+15 2 150 1
+20 1 200 1
+25 2 250 1
+30 1 300 1
+35 2 350 1
+
+
+##########
+# TEST 29: Range Subset PartitionedTopK Rehashes Below Subset Threshold
+# Range([range_key]) is only a subset of PARTITION BY (range_key, non_range_key),
+# so it should not satisfy the TopK partition key when subset satisfaction is
+# disabled.
+##########
+
+statement ok
+set datafusion.execution.target_partitions = 4;
+
+statement ok
+set datafusion.optimizer.subset_repartition_threshold = 5;
+
+statement ok
+set datafusion.optimizer.preserve_file_partitions = 0;
+
+query TT
+EXPLAIN SELECT * FROM (
+ SELECT range_key, non_range_key, value, ROW_NUMBER() OVER (PARTITION BY range_key, non_range_key ORDER BY value DESC) as rn
+ FROM range_partitioned
+) WHERE rn <= 1;
+----
+physical_plan
+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]
+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 [...]
+03)----PartitionedTopKExec: fn=row_number, fetch=1, partition=[range_key@0, non_range_key@1], order=[value@2 DESC]
+04)------RepartitionExec: partitioning=Hash([range_key@0, non_range_key@1], 4), input_partitions=4
+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
+
+statement ok
+reset datafusion.optimizer.subset_repartition_threshold;
+
statement ok
reset datafusion.explain.physical_plan_only;
+
+statement ok
+reset datafusion.optimizer.enable_window_topn;
diff --git a/datafusion/sqllogictest/test_files/window_topn.slt b/datafusion/sqllogictest/test_files/window_topn.slt
index 2eb72f519b..4dff4a779b 100644
--- a/datafusion/sqllogictest/test_files/window_topn.slt
+++ b/datafusion/sqllogictest/test_files/window_topn.slt
@@ -1044,3 +1044,48 @@ DROP TABLE window_topn_rank_null_t;
# Reset config to default (false)
statement ok
SET datafusion.optimizer.enable_window_topn = false;
+
+statement ok
+create table t(c1 int, c2 int) as values (1, 2), (3, 4);
+
+statement ok
+set datafusion.execution.target_partitions = 5;
+
+statement ok
+set datafusion.optimizer.repartition_windows = false;
+
+statement ok
+set datafusion.execution.batch_size = 1;
+
+statement ok
+set datafusion.optimizer.enable_window_topn = true;
+
+query TT
+EXPLAIN SELECT * FROM (
+ SELECT c1, c2, ROW_NUMBER() OVER (PARTITION BY c1 ORDER BY c2 DESC) as rn
+ FROM t
+) WHERE rn <= 1;
+----
+logical_plan
+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
+02)--Filter: row_number() PARTITION BY [t.c1] ORDER BY [t.c2 DESC NULLS FIRST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW <= UInt64(1)
+03)----WindowAggr: windowExpr=[[row_number() PARTITION BY [t.c1] ORDER BY [t.c2 DESC NULLS FIRST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW]]
+04)------TableScan: t projection=[c1, c2]
+physical_plan
+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]
+02)--RepartitionExec: partitioning=RoundRobinBatch(5), input_partitions=1, maintains_sort_order=true
+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]
+04)------PartitionedTopKExec: fn=row_number, fetch=1, partition=[c1@0], order=[c2@1 DESC]
+05)--------DataSourceExec: partitions=1, partition_sizes=[1]
+
+statement ok
+set datafusion.execution.target_partitions = 4;
+
+statement ok
+set datafusion.optimizer.repartition_windows = true;
+
+statement ok
+set datafusion.execution.batch_size = 8192;
+
+statement ok
+set datafusion.optimizer.enable_window_topn = false;
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org