Skip to content

Commit 20a4629

Browse files
perf: Partitioned topk emit row number (apache#26133)
## Which issue does this PR close? - Part of [apache#24608](apache#24608) ## Rationale for this change With `enable_window_topn`, `WindowTopN` rewrites `Filter(rn <= K) → BoundedWindowAggExec → SortExec` into: ```text BoundedWindowAggExec: row_number() PARTITION BY [pk] ORDER BY [val], mode=Sorted PartitionedTopKExec: fn=row_number, fetch=2, partition=[pk], order=[val ASC] ``` The window node stays only to produce `rn`, but the operator already knows every retained row's rank when it emits it: rows leave in `(partition keys, order keys)` order, and the retained set is exactly the rows with rank ≤ K. The node's cost scales with the operator's output (K × partitions) and never amortizes, because every batch it sees is dense in partition boundaries. ## What changes are included in this PR? - `PartitionedTopKExec::try_new` takes `ranking_field: Option<FieldRef>`. When set, the operator appends a `UInt64` column with each row's rank, and `WindowTopN` drops the window node: ```text PartitionedTopKExec: fn=row_number, fetch=2, partition=[pk], order=[val ASC], emit=[rn] ``` - Each policy derives the rank from what it already holds. `ROW_NUMBER`: position in the partition's drain. `RANK`: position of the first row with the same key; boundary ties take the boundary key's. `DENSE_RANK`: index of the distinct-key group. All three rely on the retained set being a complete order-prefix of its partition. - Applied only when the window node has exactly one expression, since the operator appends one column. Otherwise the node is kept, as today. The output schema is the node's (input fields plus that field), so column indices above are unchanged and `schema_check()` holds. - `compute_properties` declares the ordering the removed node published, `[partition keys..., rank ASC NULLS LAST]`, so `ORDER BY pk, rn` stays sort-free. ## Are these changes tested? - `topk/mod.rs`: the rank column for each policy, including boundary ties, an eviction that moves a row to the tie list, a `DENSE_RANK` group gathered from several input batches, and output spanning several `batch_size` chunks. - `sorts/partitioned_topk.rs`: the widened schema, and the `[pk, rn]` ordering (but not `[rn]` alone). - `core/tests/physical_optimizer/window_topn.rs`: the node is removed for one expression and kept for two; `ORDER BY pk, rn` plans no `SortExec` for all three functions; end to end, the emitted column equals the flag-off result (ties, 4 partitions, batch size 4). - `window_topn.slt` and `range_partitioning.slt`: EXPLAIN output updated, query results unchanged. ## Benchmark h2o `window.sql` k=2 sweeps on `J1_1e7_1e7_NA.parquet` (10 M rows, 14 partitions), `enable_window_topn = true` in both arms. | partitions | `ROW_NUMBER` | `RANK` | `DENSE_RANK` | |---|---|---|---| | 100 | 0.037 → 0.035 s (1.06×) | 0.036 → 0.037 s (0.97×) | 0.037 → 0.037 s (1.00×) | | 1 K | 0.036 → 0.035 s (1.03×) | 0.038 → 0.039 s (0.97×) | 0.040 → 0.040 s (1.00×) | | 10 K | 0.041 → 0.038 s (1.08×) | 0.034 → 0.032 s (1.06×) | 0.047 → 0.044 s (1.07×) | | 100 K | **0.075 → 0.050 s (1.50×)** | **0.092 → 0.060 s (1.53×)** | **0.147 → 0.118 s (1.25×)** | ## Are there any user-facing changes? Only with enable_window_topn (default false): EXPLAIN no longer shows the window node for single-expression ranking queries, and PartitionedTopKExec shows emit=[...]. Results for the built-in functions are unchanged. A user-defined window function registered as row_number, rank or dense_rank is no longer rewritten. WindowTopN used to match these functions by name; it now compares the WindowUDF with the built-in (row_number_udwf(), rank_udwf(), dense_rank_udwf()). Without this, the operator's column would replace the custom evaluator's output, or the query would fail at execution if the return type isn't UInt64. On main, such a function already had its input pruned. datafusion-functions-window becomes a regular dependency of datafusion-physical-optimizer. No breaking API change: PartitionedTopKExec::try_new keeps its signature. with_ranking_field() and ranking_field() are new public methods.
1 parent d5f5ad4 commit 20a4629

8 files changed

Lines changed: 1499 additions & 338 deletions

File tree

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

Lines changed: 479 additions & 39 deletions
Large diffs are not rendered by default.

‎datafusion/physical-optimizer/Cargo.toml‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -46,6 +46,7 @@ datafusion-common = { workspace = true }
4646
datafusion-execution = { workspace = true }
4747
datafusion-expr = { workspace = true }
4848
datafusion-expr-common = { workspace = true, default-features = true }
49+
datafusion-functions-window = { workspace = true }
4950
datafusion-physical-expr = { workspace = true }
5051
datafusion-physical-expr-common = { workspace = true }
5152
datafusion-physical-plan = { workspace = true }
@@ -57,6 +58,5 @@ recursive = { workspace = true, optional = true }
5758
[dev-dependencies]
5859
datafusion-expr = { workspace = true }
5960
datafusion-functions = { workspace = true }
60-
datafusion-functions-window = { workspace = true }
6161
insta = { workspace = true }
6262
tokio = { workspace = true }

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

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -124,8 +124,10 @@ impl PhysicalOptimizer {
124124
// those are handled by the later `FilterPushdown` rule.
125125
// See `FilterPushdownPhase` for more details.
126126
Arc::new(FilterPushdown::new()),
127-
// WindowTopN: replaces Filter(rn<=K) → Window(ROW_NUMBER)
128-
// with Window(ROW_NUMBER) → PartitionedTopKExec(fetch=K).
127+
// WindowTopN: replaces Filter(rn<=K) → Window(ROW_NUMBER) with
128+
// PartitionedTopKExec(fetch=K), which emits `rn` itself; the
129+
// window node is kept above it only when it has other window
130+
// expressions to compute.
129131
// Must run before EnsureRequirements (so it can rewrite against the
130132
// window's declared ordering without pattern-matching a SortExec)
131133
// and before ProjectionPushdown (which embeds projections into FilterExec).

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

Lines changed: 75 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -36,8 +36,10 @@
3636
//! ```
3737
//!
3838
//! And replaces the `FilterExec → BoundedWindowAggExec` pipeline with
39-
//! `BoundedWindowAggExec → PartitionedTopKExec(fetch=K)`, removing the
40-
//! `FilterExec` and inserting `PartitionedTopKExec` under the window.
39+
//! `PartitionedTopKExec(fetch=K)`, removing the `FilterExec`. When the window
40+
//! node holds a single ranking expression the operator emits that expression's
41+
//! column itself and the `BoundedWindowAggExec` is removed too; with two or
42+
//! more it is kept above the operator to compute its columns.
4143
//!
4244
//! The appropriate [`WindowFnKind`] is forwarded to `PartitionedTopKExec`.
4345
//! `RANK` and `DENSE_RANK` require a non-empty `ORDER BY` clause (otherwise
@@ -56,6 +58,8 @@ use datafusion_common::config::ConfigOptions;
5658
use datafusion_common::tree_node::{Transformed, TransformedResult, TreeNode};
5759
use datafusion_common::{Result, ScalarValue};
5860
use datafusion_expr::Operator;
61+
use datafusion_functions_window::rank::{dense_rank_udwf, rank_udwf};
62+
use datafusion_functions_window::row_number::row_number_udwf;
5963
use datafusion_physical_expr::expressions::{BinaryExpr, Column, Literal};
6064
use datafusion_physical_expr::window::StandardWindowExpr;
6165
use datafusion_physical_expr::{LexOrdering, PhysicalSortExpr};
@@ -85,15 +89,26 @@ use datafusion_physical_plan::windows::{BoundedWindowAggExec, WindowUDFExpr};
8589
///
8690
/// ```text
8791
/// [optional ProjectionExec]
88-
/// BoundedWindowAggExec(<ranking fn> PARTITION BY ... ORDER BY ...)
92+
/// PartitionedTopKExec(fn=<row_number|rank|dense_rank>, partition_keys, order_keys, fetch=K, emit=[<ranking fn> PARTITION BY ... ORDER BY ...])
93+
/// ```
94+
///
95+
/// or, when the window node holds two or more window expressions and so still
96+
/// has columns to compute:
97+
///
98+
/// ```text
99+
/// [optional ProjectionExec]
100+
/// BoundedWindowAggExec(<ranking fns> PARTITION BY ... ORDER BY ...)
89101
/// PartitionedTopKExec(fn=<row_number|rank|dense_rank>, partition_keys, order_keys, fetch=K)
90102
/// ```
91103
///
92-
/// The `FilterExec` is removed entirely. The child of `BoundedWindowAggExec` is now
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.
104+
/// The `FilterExec` is removed entirely, and `PartitionedTopKExec` maintains
105+
/// per-partition top-K state (a heap for `ROW_NUMBER`, a heap plus boundary
106+
/// ties for `RANK`, a K-bounded distinct-ob map for `DENSE_RANK`) instead of
107+
/// sorting the whole dataset. In the first shape it also appends the ranking
108+
/// column, which it can derive from the retained rows as it emits them, so
109+
/// nothing is left for the window node to do and it is removed as well. The
110+
/// column keeps the window expression's name, not the query's alias (`rn`):
111+
/// the alias is applied by the `ProjectionExec` above.
97112
///
98113
/// # Supported Predicates
99114
///
@@ -233,19 +248,47 @@ impl WindowTopN {
233248
return None;
234249
}
235250

236-
let partitioned_topk = PartitionedTopKExec::try_new(
251+
// The operator can emit the ranking column itself, which makes the
252+
// `BoundedWindowAggExec` above it redundant — see step 7. All three
253+
// ranking functions are derivable from the retained set as it is
254+
// emitted (`PartitionedTopKExec` documents how per policy), so the only
255+
// condition is that there is exactly one window expression: the
256+
// operator appends a single column, and it has to reproduce the whole
257+
// of the window node's output schema. With two or more the window node
258+
// stays and computes them as before.
259+
let ranking_field = if window_exprs.len() == 1 {
260+
Some(matched_expr.field().ok()?)
261+
} else {
262+
None
263+
};
264+
265+
let mut partitioned_topk = PartitionedTopKExec::try_new(
237266
Arc::clone(window_exec_typed.input()),
238267
expr,
239268
partition_prefix_len,
240269
limit_n,
241270
fn_kind,
242271
)
243272
.ok()?;
244-
245-
// Step 7: Rebuild window with PartitionedTopKExec as its child
246-
let mut result =
247-
replace_children_if_necessary(window_exec, vec![Arc::new(partitioned_topk)])
273+
if let Some(field) = &ranking_field {
274+
partitioned_topk = partitioned_topk
275+
.with_ranking_field(Arc::clone(field))
248276
.ok()?;
277+
}
278+
279+
// Step 7: Rebuild the pipeline above the operator.
280+
//
281+
// When the operator emits the ranking column itself, the
282+
// `BoundedWindowAggExec` has nothing left to compute: it would
283+
// re-derive, over the retained rows, exactly the values already in
284+
// that column. Its output schema is the input's fields followed by
285+
// its window expressions' fields, which is what the operator now
286+
// produces, so the nodes above it keep referencing the same column
287+
// indices. Drop it.
288+
let mut result: Arc<dyn ExecutionPlan> = Arc::new(partitioned_topk);
289+
if ranking_field.is_none() {
290+
result = replace_children_if_necessary(window_exec, vec![result]).ok()?;
291+
}
249292

250293
// Step 8: Rebuild intermediate nodes (ProjectionExec/RepartitionExec)
251294
for node in intermediates.into_iter().rev() {
@@ -362,23 +405,32 @@ fn scalar_to_usize(value: &ScalarValue) -> Option<usize> {
362405

363406
/// Identify which supported ranking window function `expr` is.
364407
///
365-
/// Downcasts through `StandardWindowExpr` → `WindowUDFExpr` and checks
366-
/// the UDF name. Returns:
367-
/// - `Some(WindowFnKind::RowNumber)` for `"row_number"`
368-
/// - `Some(WindowFnKind::Rank)` for `"rank"`
369-
/// - `Some(WindowFnKind::DenseRank)` for `"dense_rank"`
408+
/// Downcasts through `StandardWindowExpr` → `WindowUDFExpr` and compares
409+
/// the UDF with the built-in one. Returns:
410+
/// - `Some(WindowFnKind::RowNumber)` for the built-in `row_number`
411+
/// - `Some(WindowFnKind::Rank)` for the built-in `rank`
412+
/// - `Some(WindowFnKind::DenseRank)` for the built-in `dense_rank`
370413
/// - `None` for everything else
414+
///
415+
/// The comparison is `WindowUDF` equality rather than the name: a user-defined
416+
/// function registered as `row_number` (say) can compute anything, and the
417+
/// rewrite both prunes its input and, with a single window expression, drops
418+
/// its evaluator.
371419
fn supported_window_fn(
372420
expr: &Arc<dyn datafusion_physical_expr::window::WindowExpr>,
373421
) -> Option<WindowFnKind> {
374422
let swe = expr.as_any().downcast_ref::<StandardWindowExpr>()?;
375423
let swfe = swe.get_standard_func_expr();
376424
let udf = swfe.as_any().downcast_ref::<WindowUDFExpr>()?;
377-
match udf.fun().name() {
378-
"row_number" => Some(WindowFnKind::RowNumber),
379-
"rank" => Some(WindowFnKind::Rank),
380-
"dense_rank" => Some(WindowFnKind::DenseRank),
381-
_ => None,
425+
let fun = udf.fun();
426+
if fun == &row_number_udwf() {
427+
Some(WindowFnKind::RowNumber)
428+
} else if fun == &rank_udwf() {
429+
Some(WindowFnKind::Rank)
430+
} else if fun == &dense_rank_udwf() {
431+
Some(WindowFnKind::DenseRank)
432+
} else {
433+
None
382434
}
383435
}
384436

0 commit comments

Comments
 (0)