Skip to content

Commit a218140

Browse files
saadtajwarkosiew
authored andcommitted
refactor: moving WindowTopN before EnsureRequirements (apache#24191)
## Which issue does this PR close? - Closes apache#21594 ## Rationale for this change The WindowTopN physical optimizer rule currently runs after EnsureRequirements, which means it must pattern-match through SortExec nodes that EnsureRequirements inserts: ``` FilterExec(rn <= K) [optional ProjectionExec] BoundedWindowAggExec(ROW_NUMBER PARTITION BY ... ORDER BY ...) SortExec(partition_keys, order_keys) ← inserted by EnforceSorting ``` By moving WindowTopN to run before EnsureRequirements, we can simplify the logic to avoid pattern-matching through `SortExec` node and instead use the `ORDER BY` and `PARTITION BY` on the `BoundedWindowAggExec` ## What changes are included in this PR? Moved `WindowTopN` to run before `EnsureRequirements`, and updated its logic to not expect a `SortExec` and instead use the `ORDER BY` and `PARTITION BY` on the `BoundedWindowAggExec` ## Are these changes tested? Yes ## Are there any user-facing changes? These are just optimizer changes (order of optimizations and internal logic of `WindowTopN`), no API changes
1 parent 8abc2fa commit a218140

6 files changed

Lines changed: 123 additions & 129 deletions

File tree

‎datafusion/core/src/optimizer_rule_reference.md‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -75,10 +75,10 @@ in multiple phases.
7575
| 3 | `join_selection` | - | Chooses join implementation, build side, and partition mode from statistics and stream properties. |
7676
| 4 | `LimitedDistinctAggregation` | - | Pushes limit hints into grouped distinct-style aggregations when only a small result is needed. |
7777
| 5 | `FilterPushdown` | pre-optimization phase | Pushes supported physical filters down toward data sources before distribution and sorting are enforced. |
78-
| 6 | `EnsureRequirements` | - | Enforces both distribution and sorting requirements in a single idempotent rule. |
79-
| 7 | `CombinePartialFinalAggregate` | - | Collapses adjacent partial and final aggregates when the distributed shape makes them redundant. |
80-
| 8 | `OptimizeAggregateOrder` | - | Updates aggregate expressions to use the best ordering once sort requirements are known. |
81-
| 9 | `WindowTopN` | - | Replaces eligible row-number window and filter patterns with per-partition TopK execution. |
78+
| 6 | `WindowTopN` | - | Replaces eligible row-number window and filter patterns with per-partition TopK execution. |
79+
| 7 | `EnsureRequirements` | - | Enforces both distribution and sorting requirements in a single idempotent rule. |
80+
| 8 | `CombinePartialFinalAggregate` | - | Collapses adjacent partial and final aggregates when the distributed shape makes them redundant. |
81+
| 9 | `OptimizeAggregateOrder` | - | Updates aggregate expressions to use the best ordering once sort requirements are known. |
8282
| 10 | `ProjectionPushdown` | early pass | Pushes projections toward inputs before later physical rewrites add more limit and TopK structure. |
8383
| 11 | `OutputRequirements` | remove phase | Removes the temporary output-requirement helper nodes after requirement-sensitive planning is done. |
8484
| 12 | `LimitAggregation` | - | Passes a limit hint into eligible aggregations so they can keep fewer accumulator buckets. |

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

Lines changed: 10 additions & 44 deletions
Original file line numberDiff line numberDiff line change
@@ -64,24 +64,16 @@ fn optimize_disabled(plan: Arc<dyn ExecutionPlan>) -> Result<Arc<dyn ExecutionPl
6464
WindowTopN::new().optimize(plan, &config)
6565
}
6666

67-
/// Build: FilterExec(rn <= limit) → BoundedWindowAggExec(ROW_NUMBER PBY pk OBY val) → SortExec(pk, val)
67+
/// Build: FilterExec(rn <= limit) → BoundedWindowAggExec(ROW_NUMBER PBY pk OBY val)
68+
///
69+
/// Matches the pre-`EnsureRequirements` plan shape (no `SortExec` under the window).
6870
fn build_window_topn_plan(
6971
limit_value: i64,
7072
op: Operator,
7173
) -> Result<Arc<dyn ExecutionPlan>> {
7274
let s = schema();
7375
let input: Arc<dyn ExecutionPlan> = Arc::new(PlaceholderRowExec::new(Arc::clone(&s)));
7476

75-
// Sort by pk ASC, val ASC
76-
let ordering = LexOrdering::new(vec![
77-
PhysicalSortExpr::new_default(col("pk", &s)?).asc(),
78-
PhysicalSortExpr::new_default(col("val", &s)?).asc(),
79-
])
80-
.unwrap();
81-
82-
let sort: Arc<dyn ExecutionPlan> =
83-
Arc::new(SortExec::new(ordering.clone(), input).with_preserve_partitioning(true));
84-
8577
// ROW_NUMBER() OVER (PARTITION BY pk ORDER BY val)
8678
let partition_by = vec![col("pk", &s)?];
8779
let order_by = vec![PhysicalSortExpr::new_default(col("val", &s)?).asc()];
@@ -105,7 +97,7 @@ fn build_window_topn_plan(
10597

10698
let window: Arc<dyn ExecutionPlan> = Arc::new(BoundedWindowAggExec::try_new(
10799
vec![window_expr],
108-
sort,
100+
input,
109101
InputOrderMode::Sorted,
110102
true,
111103
)?);
@@ -252,16 +244,6 @@ fn flipped_3_gteq_rn() -> Result<()> {
252244
let input: Arc<dyn ExecutionPlan> =
253245
Arc::new(PlaceholderRowExec::new(Arc::clone(&s)));
254246

255-
let ordering = LexOrdering::new(vec![
256-
PhysicalSortExpr::new_default(col("pk", &s)?).asc(),
257-
PhysicalSortExpr::new_default(col("val", &s)?).asc(),
258-
])
259-
.unwrap();
260-
261-
let sort: Arc<dyn ExecutionPlan> = Arc::new(
262-
SortExec::new(ordering.clone(), input).with_preserve_partitioning(true),
263-
);
264-
265247
let partition_by = vec![col("pk", &s)?];
266248
let order_by = vec![PhysicalSortExpr::new_default(col("val", &s)?).asc()];
267249

@@ -284,7 +266,7 @@ fn flipped_3_gteq_rn() -> Result<()> {
284266

285267
let window: Arc<dyn ExecutionPlan> = Arc::new(BoundedWindowAggExec::try_new(
286268
vec![window_expr],
287-
sort,
269+
input,
288270
InputOrderMode::Sorted,
289271
true,
290272
)?);
@@ -353,15 +335,6 @@ fn with_projection_between() -> Result<()> {
353335
let s = schema();
354336
let input: Arc<dyn ExecutionPlan> = Arc::new(PlaceholderRowExec::new(Arc::clone(&s)));
355337

356-
let ordering = LexOrdering::new(vec![
357-
PhysicalSortExpr::new_default(col("pk", &s)?).asc(),
358-
PhysicalSortExpr::new_default(col("val", &s)?).asc(),
359-
])
360-
.unwrap();
361-
362-
let sort: Arc<dyn ExecutionPlan> =
363-
Arc::new(SortExec::new(ordering.clone(), input).with_preserve_partitioning(true));
364-
365338
let partition_by = vec![col("pk", &s)?];
366339
let order_by = vec![PhysicalSortExpr::new_default(col("val", &s)?).asc()];
367340

@@ -384,7 +357,7 @@ fn with_projection_between() -> Result<()> {
384357

385358
let window: Arc<dyn ExecutionPlan> = Arc::new(BoundedWindowAggExec::try_new(
386359
vec![window_expr],
387-
sort,
360+
input,
388361
InputOrderMode::Sorted,
389362
true,
390363
)?);
@@ -429,7 +402,9 @@ fn with_projection_between() -> Result<()> {
429402
// RANK rule tests
430403
// ----------------------------------------------------------------------
431404

432-
/// Build: FilterExec(rk op limit) → BoundedWindowAggExec(<udwf> PBY pk OBY val) → SortExec(pk, val)
405+
/// Build: FilterExec(rk op limit) → BoundedWindowAggExec(<udwf> PBY pk OBY val)
406+
///
407+
/// Matches the pre-`EnsureRequirements` plan shape (no `SortExec` under the window).
433408
///
434409
/// `udwf_factory` selects the window UDWF (rank, dense_rank, ...) and
435410
/// `udwf_name` is the column name produced by that UDWF (matters because
@@ -444,15 +419,6 @@ fn build_ranking_topn_plan(
444419
let s = schema();
445420
let input: Arc<dyn ExecutionPlan> = Arc::new(PlaceholderRowExec::new(Arc::clone(&s)));
446421

447-
let ordering = LexOrdering::new(vec![
448-
PhysicalSortExpr::new_default(col("pk", &s)?).asc(),
449-
PhysicalSortExpr::new_default(col("val", &s)?).asc(),
450-
])
451-
.unwrap();
452-
453-
let sort: Arc<dyn ExecutionPlan> =
454-
Arc::new(SortExec::new(ordering.clone(), input).with_preserve_partitioning(true));
455-
456422
let partition_by = vec![col("pk", &s)?];
457423
let order_by = vec![PhysicalSortExpr::new_default(col("val", &s)?).asc()];
458424

@@ -469,7 +435,7 @@ fn build_ranking_topn_plan(
469435

470436
let window: Arc<dyn ExecutionPlan> = Arc::new(BoundedWindowAggExec::try_new(
471437
vec![window_expr],
472-
sort,
438+
input,
473439
InputOrderMode::Sorted,
474440
true,
475441
)?);

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

Lines changed: 6 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -109,6 +109,12 @@ impl PhysicalOptimizer {
109109
// those are handled by the later `FilterPushdown` rule.
110110
// See `FilterPushdownPhase` for more details.
111111
Arc::new(FilterPushdown::new()),
112+
// WindowTopN: replaces Filter(rn<=K) → Window(ROW_NUMBER)
113+
// with Window(ROW_NUMBER) → PartitionedTopKExec(fetch=K).
114+
// Must run before EnsureRequirements (so it can rewrite against the
115+
// window's declared ordering without pattern-matching a SortExec)
116+
// and before ProjectionPushdown (which embeds projections into FilterExec).
117+
Arc::new(WindowTopN::new()),
112118
// Ensures each input plan satisfies the distribution and ordering
113119
// requirements declared by `ExecutionPlan::required_input_distribution`
114120
// and `ExecutionPlan::required_input_ordering`.
@@ -132,11 +138,6 @@ impl PhysicalOptimizer {
132138
Arc::new(CombinePartialFinalAggregate::new()),
133139
// Run once after the local sorting requirement is changed
134140
Arc::new(OptimizeAggregateOrder::new()),
135-
// WindowTopN: replaces Filter(rn<=K) → Window(ROW_NUMBER) → Sort
136-
// with Window(ROW_NUMBER) → PartitionedTopKExec(fetch=K).
137-
// Must run after EnsureRequirements (which inserts SortExec) and before
138-
// ProjectionPushdown (which embeds projections into FilterExec).
139-
Arc::new(WindowTopN::new()),
140141
// TODO: `try_embed_to_hash_join` in the ProjectionPushdown rule would be block by the CoalesceBatches, so add it before CoalesceBatches. Maybe optimize it in the future.
141142
Arc::new(ProjectionPushdown::new()),
142143
// Remove the ancillary output requirement operator since we are done with the planning

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

Lines changed: 21 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -35,9 +35,9 @@
3535
//! ) WHERE rk <= K;
3636
//! ```
3737
//!
38-
//! And replaces the `FilterExec → BoundedWindowAggExec → SortExec` pipeline
39-
//! with `BoundedWindowAggExec → PartitionedTopKExec(fetch=K)`, removing both
40-
//! the `FilterExec` and `SortExec`.
38+
//! And replaces the `FilterExec → BoundedWindowAggExec` pipeline with
39+
//! `BoundedWindowAggExec → PartitionedTopKExec(fetch=K)`, removing the
40+
//! `FilterExec` and inserting `PartitionedTopKExec` under the window.
4141
//!
4242
//! The appropriate [`WindowFnKind`] is forwarded to `PartitionedTopKExec`.
4343
//! RANK requires a non-empty `ORDER BY` clause (otherwise all rows tie at
@@ -58,14 +58,14 @@ use datafusion_common::{Result, ScalarValue};
5858
use datafusion_expr::Operator;
5959
use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
6060
use datafusion_physical_expr::window::StandardWindowExpr;
61+
use datafusion_physical_expr::{LexOrdering, PhysicalSortExpr};
6162
use datafusion_physical_plan::ExecutionPlan;
6263
use datafusion_physical_plan::filter::FilterExec;
6364
use datafusion_physical_plan::projection::ProjectionExec;
6465
use datafusion_physical_plan::repartition::RepartitionExec;
6566
use datafusion_physical_plan::sorts::partitioned_topk::{
6667
PartitionedTopKExec, WindowFnKind,
6768
};
68-
use datafusion_physical_plan::sorts::sort::SortExec;
6969
use datafusion_physical_plan::windows::{BoundedWindowAggExec, WindowUDFExpr};
7070

7171
/// Physical optimizer rule that converts per-partition `ROW_NUMBER` and
@@ -78,7 +78,6 @@ use datafusion_physical_plan::windows::{BoundedWindowAggExec, WindowUDFExpr};
7878
/// FilterExec(<ranking fn output> <= K)
7979
/// [optional ProjectionExec]
8080
/// BoundedWindowAggExec(<ranking fn> PARTITION BY ... ORDER BY ...)
81-
/// SortExec(partition_keys, order_keys)
8281
/// ```
8382
///
8483
/// # Replacement
@@ -89,7 +88,7 @@ use datafusion_physical_plan::windows::{BoundedWindowAggExec, WindowUDFExpr};
8988
/// PartitionedTopKExec(fn=<row_number|rank>, partition_keys, order_keys, fetch=K)
9089
/// ```
9190
///
92-
/// The `FilterExec` is removed entirely. The `SortExec` is replaced by
91+
/// The `FilterExec` is removed entirely. The child of `BoundedWindowAggExec` is now
9392
/// `PartitionedTopKExec`, which maintains a per-partition top-K heap (and,
9493
/// for `RANK`, a sibling ties `Vec`) instead of sorting the whole dataset.
9594
///
@@ -104,7 +103,7 @@ use datafusion_physical_plan::windows::{BoundedWindowAggExec, WindowUDFExpr};
104103
///
105104
/// All of the following must be true:
106105
/// - Config flag `enable_window_topn` is `true`
107-
/// - The plan matches `FilterExec → [ProjectionExec] → BoundedWindowAggExec → SortExec`
106+
/// - The plan matches `FilterExec → [ProjectionExec] → BoundedWindowAggExec`
108107
/// - The window function is `ROW_NUMBER` or `RANK` (not `DENSE_RANK`)
109108
/// - The window function has a `PARTITION BY` clause (global top-K is
110109
/// already handled by `SortExec` with `fetch`)
@@ -126,7 +125,7 @@ impl WindowTopN {
126125
/// Attempt to transform a single plan node.
127126
///
128127
/// Returns `Some(new_plan)` if the node matches the
129-
/// `FilterExec → [ProjectionExec] → BoundedWindowAggExec → SortExec`
128+
/// `FilterExec → [ProjectionExec] → BoundedWindowAggExec`
130129
/// pattern and can be rewritten, or `None` if the node should be
131130
/// left unchanged.
132131
fn try_transform(plan: &Arc<dyn ExecutionPlan>) -> Option<Arc<dyn ExecutionPlan>> {
@@ -147,7 +146,6 @@ impl WindowTopN {
147146

148147
// Step 4: Verify col_idx references a supported window function output column
149148
let window_exec_typed = window_exec.downcast_ref::<BoundedWindowAggExec>()?;
150-
let sort_exec = window_exec_typed.input().downcast_ref::<SortExec>()?;
151149
let input_field_count = window_exec_typed.input().schema().fields().len();
152150
if col_idx < input_field_count {
153151
return None; // Filter is on an input column, not a window column
@@ -159,10 +157,7 @@ impl WindowTopN {
159157
}
160158
let fn_kind = supported_window_fn(&window_exprs[window_expr_idx])?;
161159

162-
// Step 5: child of window is SortExec (verified above)
163-
let sort_child = sort_exec.input();
164-
165-
// Step 6: Determine partition_prefix_len from the window expression
160+
// Step 5: Validate PARTITION BY / ORDER BY and collect sort keys from the window expr
166161
let partition_by = window_exprs[window_expr_idx].partition_by();
167162
let partition_prefix_len = partition_by.len();
168163

@@ -175,28 +170,33 @@ impl WindowTopN {
175170
// For RANK: an empty ORDER BY makes every row tie at rank 1 —
176171
// the optimization is degenerate (we'd retain the entire input)
177172
// and tie storage would be unbounded.
178-
if matches!(fn_kind, WindowFnKind::Rank)
179-
&& window_exprs[window_expr_idx].order_by().is_empty()
180-
{
173+
let order_by = window_exprs[window_expr_idx].order_by();
174+
if matches!(fn_kind, WindowFnKind::Rank) && order_by.is_empty() {
181175
return None;
182176
}
183177

184-
// Step 7: Build PartitionedTopKExec using SortExec's expressions
178+
// Step 6: Build PartitionedTopKExec from the window's partition/order keys
179+
let expr_iterator = partition_by
180+
.iter()
181+
.map(|e| PhysicalSortExpr::new_default(Arc::clone(e)))
182+
.chain(order_by.iter().cloned());
183+
let expr = LexOrdering::new(expr_iterator)?;
184+
185185
let partitioned_topk = PartitionedTopKExec::try_new(
186-
Arc::clone(sort_child),
187-
sort_exec.expr().clone(),
186+
Arc::clone(window_exec_typed.input()),
187+
expr,
188188
partition_prefix_len,
189189
limit_n,
190190
fn_kind,
191191
)
192192
.ok()?;
193193

194-
// Step 8: Rebuild window with new child
194+
// Step 7: Rebuild window with PartitionedTopKExec as its child
195195
let mut result = window_exec
196196
.with_new_children(vec![Arc::new(partitioned_topk)])
197197
.ok()?;
198198

199-
// Step 9: Rebuild intermediate nodes (ProjectionExec/RepartitionExec)
199+
// Step 8: Rebuild intermediate nodes (ProjectionExec/RepartitionExec)
200200
for node in intermediates.into_iter().rev() {
201201
result = node.with_new_children(vec![result]).ok()?;
202202
}

‎datafusion/sqllogictest/test_files/explain.slt‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -237,10 +237,10 @@ physical_plan after aggregate_statistics SAME TEXT AS ABOVE
237237
physical_plan after join_selection SAME TEXT AS ABOVE
238238
physical_plan after LimitedDistinctAggregation SAME TEXT AS ABOVE
239239
physical_plan after FilterPushdown SAME TEXT AS ABOVE
240+
physical_plan after WindowTopN SAME TEXT AS ABOVE
240241
physical_plan after EnsureRequirements SAME TEXT AS ABOVE
241242
physical_plan after CombinePartialFinalAggregate SAME TEXT AS ABOVE
242243
physical_plan after OptimizeAggregateOrder SAME TEXT AS ABOVE
243-
physical_plan after WindowTopN SAME TEXT AS ABOVE
244244
physical_plan after ProjectionPushdown SAME TEXT AS ABOVE
245245
physical_plan after OutputRequirements DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/core/tests/data/example.csv]]}, projection=[a, b, c], file_type=csv, has_header=true
246246
physical_plan after LimitAggregation SAME TEXT AS ABOVE
@@ -317,10 +317,10 @@ physical_plan after aggregate_statistics SAME TEXT AS ABOVE
317317
physical_plan after join_selection SAME TEXT AS ABOVE
318318
physical_plan after LimitedDistinctAggregation SAME TEXT AS ABOVE
319319
physical_plan after FilterPushdown SAME TEXT AS ABOVE
320+
physical_plan after WindowTopN SAME TEXT AS ABOVE
320321
physical_plan after EnsureRequirements SAME TEXT AS ABOVE
321322
physical_plan after CombinePartialFinalAggregate SAME TEXT AS ABOVE
322323
physical_plan after OptimizeAggregateOrder SAME TEXT AS ABOVE
323-
physical_plan after WindowTopN SAME TEXT AS ABOVE
324324
physical_plan after ProjectionPushdown SAME TEXT AS ABOVE
325325
physical_plan after OutputRequirements
326326
01)GlobalLimitExec: skip=0, fetch=10, statistics=[Rows=Exact(8), Bytes=Absent, [(Col[0]: ScanBytes=Exact(32)),(Col[1]: ScanBytes=Inexact(24)),(Col[2]: ScanBytes=Exact(32)),(Col[3]: ScanBytes=Exact(32)),(Col[4]: ScanBytes=Exact(32)),(Col[5]: ScanBytes=Exact(64)),(Col[6]: ScanBytes=Exact(32)),(Col[7]: ScanBytes=Exact(64)),(Col[8]: ScanBytes=Inexact(88)),(Col[9]: ScanBytes=Inexact(49)),(Col[10]: ScanBytes=Exact(64))]]
@@ -363,10 +363,10 @@ physical_plan after aggregate_statistics SAME TEXT AS ABOVE
363363
physical_plan after join_selection SAME TEXT AS ABOVE
364364
physical_plan after LimitedDistinctAggregation SAME TEXT AS ABOVE
365365
physical_plan after FilterPushdown SAME TEXT AS ABOVE
366+
physical_plan after WindowTopN SAME TEXT AS ABOVE
366367
physical_plan after EnsureRequirements SAME TEXT AS ABOVE
367368
physical_plan after CombinePartialFinalAggregate SAME TEXT AS ABOVE
368369
physical_plan after OptimizeAggregateOrder SAME TEXT AS ABOVE
369-
physical_plan after WindowTopN SAME TEXT AS ABOVE
370370
physical_plan after ProjectionPushdown SAME TEXT AS ABOVE
371371
physical_plan after OutputRequirements
372372
01)GlobalLimitExec: skip=0, fetch=10
@@ -616,10 +616,10 @@ physical_plan after aggregate_statistics SAME TEXT AS ABOVE
616616
physical_plan after join_selection SAME TEXT AS ABOVE
617617
physical_plan after LimitedDistinctAggregation SAME TEXT AS ABOVE
618618
physical_plan after FilterPushdown SAME TEXT AS ABOVE
619+
physical_plan after WindowTopN SAME TEXT AS ABOVE
619620
physical_plan after EnsureRequirements SAME TEXT AS ABOVE
620621
physical_plan after CombinePartialFinalAggregate SAME TEXT AS ABOVE
621622
physical_plan after OptimizeAggregateOrder SAME TEXT AS ABOVE
622-
physical_plan after WindowTopN SAME TEXT AS ABOVE
623623
physical_plan after ProjectionPushdown SAME TEXT AS ABOVE
624624
physical_plan after OutputRequirements DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/core/tests/data/example.csv]]}, projection=[a, b, c], file_type=csv, has_header=true
625625
physical_plan after LimitAggregation SAME TEXT AS ABOVE

0 commit comments

Comments
 (0)