2626//! ) WHERE rn <= K;
2727//! ```
2828//!
29- //! or with `RANK()` in place of `ROW_NUMBER()`:
29+ //! or with `RANK()` / `DENSE_RANK()` in place of `ROW_NUMBER()`:
3030//!
3131//! ```sql
3232//! SELECT * FROM (
4040//! `FilterExec` and inserting `PartitionedTopKExec` under the window.
4141//!
4242//! The appropriate [`WindowFnKind`] is forwarded to `PartitionedTopKExec`.
43- //! RANK requires a non-empty `ORDER BY` clause (otherwise all rows tie at
44- //! rank 1 and the optimization is degenerate).
43+ //! ` RANK` and `DENSE_RANK` require a non-empty `ORDER BY` clause (otherwise
44+ //! all rows tie at rank 1 and the optimization is degenerate).
4545//!
4646//! See [`PartitionedTopKExec`] for details on the replacement operator.
4747//!
@@ -69,9 +69,9 @@ use datafusion_physical_plan::sorts::partitioned_topk::{
6969} ;
7070use datafusion_physical_plan:: windows:: { BoundedWindowAggExec , WindowUDFExpr } ;
7171
72- /// Physical optimizer rule that converts per-partition `ROW_NUMBER` and
73- /// `RANK` top-K queries into a more efficient plan using
74- /// [`PartitionedTopKExec`].
72+ /// Physical optimizer rule that converts per-partition `ROW_NUMBER`,
73+ /// `RANK`, and `DENSE_RANK` top-K queries into a more efficient plan
74+ /// using [`PartitionedTopKExec`].
7575///
7676/// # Pattern Detected
7777///
@@ -86,12 +86,14 @@ use datafusion_physical_plan::windows::{BoundedWindowAggExec, WindowUDFExpr};
8686/// ```text
8787/// [optional ProjectionExec]
8888/// BoundedWindowAggExec(<ranking fn> PARTITION BY ... ORDER BY ...)
89- /// PartitionedTopKExec(fn=<row_number|rank>, partition_keys, order_keys, fetch=K)
89+ /// PartitionedTopKExec(fn=<row_number|rank|dense_rank >, partition_keys, order_keys, fetch=K)
9090/// ```
9191///
9292/// The `FilterExec` is removed entirely. The child of `BoundedWindowAggExec` is now
93- /// `PartitionedTopKExec`, which maintains a per-partition top-K heap (and,
94- /// for `RANK`, a sibling ties `Vec`) instead of sorting the whole dataset.
93+ /// `PartitionedTopKExec`, which maintains per-partition top-K state (a
94+ /// heap for `ROW_NUMBER`, a heap plus boundary ties for `RANK`, a
95+ /// K-bounded distinct-ob map for `DENSE_RANK`) instead of sorting the
96+ /// whole dataset.
9597///
9698/// # Supported Predicates
9799///
@@ -105,12 +107,19 @@ use datafusion_physical_plan::windows::{BoundedWindowAggExec, WindowUDFExpr};
105107/// All of the following must be true:
106108/// - Config flag `enable_window_topn` is `true`
107109/// - The plan matches `FilterExec → [ProjectionExec] → BoundedWindowAggExec`
108- /// - The window function is `ROW_NUMBER` or `RANK` (not `DENSE_RANK`)
110+ /// - The window function is `ROW_NUMBER`, `RANK`, or `DENSE_RANK`
111+ /// - Every window expression in the `BoundedWindowAggExec` is `ROW_NUMBER`,
112+ /// `RANK`, or `DENSE_RANK` over the same `PARTITION BY` / `ORDER BY`. A
113+ /// sibling that reads pruned rows (e.g. `LEAD`, or an aggregate whose
114+ /// frame is not strictly backward-looking) would be computed over the
115+ /// pruned input and give wrong results.
109116/// - The window function has a `PARTITION BY` clause (global top-K is
110117/// already handled by `SortExec` with `fetch`)
111- /// - For `RANK`: a non-empty `ORDER BY` clause (otherwise all rows tie
112- /// at rank 1 — the optimization is useless and the boundary-tie storage
113- /// would be unbounded)
118+ /// - At least one `ORDER BY` key survives past the `PARTITION BY` prefix
119+ /// (so the operator has a non-empty ORDER BY). This rejects both a
120+ /// missing `ORDER BY` and one fully covered by the partition prefix
121+ /// such as `PARTITION BY pk ORDER BY pk`; for `RANK` / `DENSE_RANK`
122+ /// such orderings also make every row tie at rank 1 (degenerate).
114123/// - The filter predicate compares the window output column to an integer
115124/// literal using `<=`, `<`, `>=`, or `>`
116125///
@@ -142,10 +151,10 @@ impl WindowTopN {
142151 let ( col_idx, limit_n) = extract_window_limit ( filter. predicate ( ) ) ?;
143152
144153 // A predicate such as `rn < 1` (or the flipped `1 > rn`) yields a fetch of
145- // 0. `ROW_NUMBER`/`RANK` are always >= 1, so no row can satisfy it and the
146- // correct result is empty. `PartitionedTopKExec` requires `k > 0` and would
147- // panic on `k = 0`, so bail out here and let the regular `FilterExec` produce
148- // the (empty) result instead of rewriting.
154+ // 0. `ROW_NUMBER`/`RANK`/`DENSE_RANK` are always >= 1, so no row can satisfy
155+ // it and the correct result is empty. `PartitionedTopKExec` requires `k > 0`
156+ // and would panic on `k = 0`, so bail out here and let the regular
157+ // `FilterExec` produce the (empty) result instead of rewriting.
149158 if limit_n == 0 {
150159 return None ;
151160 }
@@ -167,6 +176,28 @@ impl WindowTopN {
167176 }
168177 let fn_kind = supported_window_fn ( & window_exprs[ window_expr_idx] ) ?;
169178
179+ // Tail-pruning drops the rows that rank after the retained top-K,
180+ // and every window expression in this `BoundedWindowAggExec` is
181+ // then evaluated over the *pruned* input. The rewrite is only valid
182+ // if each expression's value for a *retained* row is unaffected by
183+ // the dropped rows. ROW_NUMBER / RANK / DENSE_RANK over the same
184+ // PARTITION BY / ORDER BY satisfy this — each depends only on rows
185+ // at or before the current row in that order, all of which are
186+ // retained. A sibling like `LEAD(x)` reads following (pruned) rows,
187+ // so at the retained boundary it would resolve to a dropped row and
188+ // give a wrong result. Bail out unless every window expression is a
189+ // supported ranking function sharing the matched expression's
190+ // partition/order keys.
191+ let matched_expr = & window_exprs[ window_expr_idx] ;
192+ let all_prune_safe = window_exprs. iter ( ) . all ( |e| {
193+ supported_window_fn ( e) . is_some ( )
194+ && e. partition_by ( ) == matched_expr. partition_by ( )
195+ && e. order_by ( ) == matched_expr. order_by ( )
196+ } ) ;
197+ if !all_prune_safe {
198+ return None ;
199+ }
200+
170201 // Step 5: Validate PARTITION BY / ORDER BY and collect sort keys from the window expr
171202 let partition_by = window_exprs[ window_expr_idx] . partition_by ( ) ;
172203 let partition_prefix_len = partition_by. len ( ) ;
@@ -177,21 +208,31 @@ impl WindowTopN {
177208 return None ;
178209 }
179210
180- // For RANK: an empty ORDER BY makes every row tie at rank 1 —
181- // the optimization is degenerate (we'd retain the entire input)
182- // and tie storage would be unbounded.
183- let order_by = window_exprs[ window_expr_idx] . order_by ( ) ;
184- if matches ! ( fn_kind, WindowFnKind :: Rank ) && order_by. is_empty ( ) {
185- return None ;
186- }
187-
188211 // Step 6: Build PartitionedTopKExec from the window's partition/order keys
212+ let order_by = window_exprs[ window_expr_idx] . order_by ( ) ;
189213 let expr_iterator = partition_by
190214 . iter ( )
191215 . map ( |e| PhysicalSortExpr :: new_default ( Arc :: clone ( e) ) )
192216 . chain ( order_by. iter ( ) . cloned ( ) ) ;
193217 let expr = LexOrdering :: new ( expr_iterator) ?;
194218
219+ // `PartitionedTopKExec` derives its ORDER BY keys from the ordering
220+ // *beyond* the partition prefix (`expr[partition_prefix_len..]`).
221+ // That slice is empty in two cases:
222+ // * no ORDER BY at all (e.g. `ROW_NUMBER() OVER (PARTITION BY pk)`);
223+ // * ORDER BY keys fully covered by the partition prefix (e.g.
224+ // `DENSE_RANK() OVER (PARTITION BY pk ORDER BY pk)`, whose
225+ // deduplicated ordering is just `[pk]`).
226+ // With zero order keys the operator panics on execution (it
227+ // requires at least one), and for RANK / DENSE_RANK every row
228+ // would tie at rank 1 (a degenerate, unbounded retained set).
229+ // `order_by()` alone does not catch the second case — it reports
230+ // `[pk]` even though no order key survives past the partition
231+ // prefix — so guard on the effective order-key count instead.
232+ if expr. len ( ) <= partition_prefix_len {
233+ return None ;
234+ }
235+
195236 let partitioned_topk = PartitionedTopKExec :: try_new (
196237 Arc :: clone ( window_exec_typed. input ( ) ) ,
197238 expr,
@@ -325,7 +366,8 @@ fn scalar_to_usize(value: &ScalarValue) -> Option<usize> {
325366/// the UDF name. Returns:
326367/// - `Some(WindowFnKind::RowNumber)` for `"row_number"`
327368/// - `Some(WindowFnKind::Rank)` for `"rank"`
328- /// - `None` for everything else (e.g. `dense_rank`)
369+ /// - `Some(WindowFnKind::DenseRank)` for `"dense_rank"`
370+ /// - `None` for everything else
329371fn supported_window_fn (
330372 expr : & Arc < dyn datafusion_physical_expr:: window:: WindowExpr > ,
331373) -> Option < WindowFnKind > {
@@ -335,6 +377,7 @@ fn supported_window_fn(
335377 match udf. fun ( ) . name ( ) {
336378 "row_number" => Some ( WindowFnKind :: RowNumber ) ,
337379 "rank" => Some ( WindowFnKind :: Rank ) ,
380+ "dense_rank" => Some ( WindowFnKind :: DenseRank ) ,
338381 _ => None ,
339382 }
340383}
0 commit comments