Skip to content

Commit 6eaca8b

Browse files
perf: Extend WindowTopN to dense_rank (apache#23869)
## Which issue does this PR close? - Related to apache#6899. Completes the ROW_NUMBER + RANK + DENSE_RANK trio requested by the issue (ROW_NUMBER shipped in apache#21479; RANK is in flight as PR A). ## Rationale for this change Naive plan for `Filter(dr <= K) → BoundedWindowAggExec(DENSE_RANK) → SortExec(pk, ob) → input` sorts the full input even though only rows at the K distinct-smallest ob values per partition are needed. DENSE_RANK is stable under tail-pruning, so the rewrite preserves ranks for every retained row. ## What changes are included in this PR? ## Are these changes tested? Yes **h2o bench** — Q24–Q29 added; top-2 on 10M-row `large`, 3-iter avg vs `enable_window_topn=false`: | # | Cardinality | OFF (ms) | ON (ms) | Δ | |-----|------------------|---------:|--------:|:-------------| | Q24 | ~100 parts | 308.19 | 114.45 | 2.20× faster | | Q25 | ~1K, low ties | 261.24 | 113.85 | 2.13× faster | | Q26 | ~1K, heavy ties | 296.54 | 124.42 | 2.09× faster | | Q27 | ~10K, low ties | 250.83 | 131.85 | 1.70× faster | | Q28 | ~10K, heavy ties | 281.00 | 149.00 | 1.76× faster | | Q29 | ~100K parts | 264.32 | 304.37 | 1.40× slower | ## Are there any user-facing changes? No breaking changes. Rule fires on DENSE_RANK when `datafusion.optimizer.enable_window_topn = true`; flag stays `false` by default
1 parent 708ee7e commit 6eaca8b

5 files changed

Lines changed: 1828 additions & 56 deletions

File tree

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

Lines changed: 94 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -454,8 +454,12 @@ fn build_ranking_topn_plan(
454454
Ok(filter)
455455
}
456456

457-
/// Build a RANK plan with NO ORDER BY: every row ties at rank 1 — degenerate.
458-
fn build_rank_no_order_by_plan(limit_value: i64) -> Result<Arc<dyn ExecutionPlan>> {
457+
/// Build a RANK / DENSE_RANK plan with NO ORDER BY: every row ties at rank 1 — degenerate.
458+
fn build_no_order_by_plan(
459+
udwf_factory: fn() -> Arc<datafusion_expr::WindowUDF>,
460+
udwf_name: &str,
461+
limit_value: i64,
462+
) -> Result<Arc<dyn ExecutionPlan>> {
459463
let s = schema();
460464
let input: Arc<dyn ExecutionPlan> = Arc::new(PlaceholderRowExec::new(Arc::clone(&s)));
461465

@@ -469,7 +473,7 @@ fn build_rank_no_order_by_plan(limit_value: i64) -> Result<Arc<dyn ExecutionPlan
469473
let partition_by = vec![col("pk", &s)?];
470474

471475
let window_expr = Arc::new(StandardWindowExpr::new(
472-
create_udwf_window_expr(&rank_udwf(), &[], &s, "rank".to_string(), false)?,
476+
create_udwf_window_expr(&udwf_factory(), &[], &s, udwf_name.to_string(), false)?,
473477
&partition_by,
474478
&[], // empty ORDER BY
475479
Arc::new(WindowFrame::new_bounds(
@@ -486,7 +490,7 @@ fn build_rank_no_order_by_plan(limit_value: i64) -> Result<Arc<dyn ExecutionPlan
486490
true,
487491
)?);
488492

489-
let rk_col = Arc::new(Column::new("rank", 2));
493+
let rk_col = Arc::new(Column::new(udwf_name, 2));
490494
let limit_lit = lit(ScalarValue::UInt64(Some(limit_value as u64)));
491495
let predicate = Arc::new(BinaryExpr::new(rk_col, Operator::LtEq, limit_lit));
492496
let filter: Arc<dyn ExecutionPlan> =
@@ -548,7 +552,7 @@ fn rank_no_order_by_no_change() -> Result<()> {
548552
// Without ORDER BY, every row ties at rank 1 — the optimization is
549553
// degenerate (entire input would be retained, ties storage unbounded).
550554
// The rule must skip.
551-
let plan = build_rank_no_order_by_plan(3)?;
555+
let plan = build_no_order_by_plan(rank_udwf, "rank", 3)?;
552556
let before = plan_str(plan.as_ref());
553557
let optimized = optimize(plan)?;
554558
let after = plan_str(optimized.as_ref());
@@ -559,17 +563,98 @@ fn rank_no_order_by_no_change() -> Result<()> {
559563
Ok(())
560564
}
561565

566+
// ----------------------------------------------------------------------
567+
// DENSE_RANK rule tests
568+
// ----------------------------------------------------------------------
569+
562570
#[test]
563-
fn dense_rank_no_change() -> Result<()> {
564-
// DENSE_RANK is not yet supported by the rule. The plan must pass
565-
// through unchanged.
571+
fn basic_dense_rank_dr_lteq_3() -> Result<()> {
566572
let plan = build_ranking_topn_plan(dense_rank_udwf, "dense_rank", 3, Operator::LtEq)?;
573+
let optimized = optimize(plan)?;
574+
assert_snapshot!(plan_str(optimized.as_ref()), @r#"
575+
BoundedWindowAggExec: wdw=[dense_rank: Field { "dense_rank": UInt64 }, frame: ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
576+
PartitionedTopKExec: fn=dense_rank, fetch=3, partition=[pk@0], order=[val@1 ASC]
577+
PlaceholderRowExec
578+
"#);
579+
Ok(())
580+
}
581+
582+
#[test]
583+
fn dense_rank_dr_lt_4_becomes_fetch_3() -> Result<()> {
584+
let plan = build_ranking_topn_plan(dense_rank_udwf, "dense_rank", 4, Operator::Lt)?;
585+
let optimized = optimize(plan)?;
586+
assert_snapshot!(plan_str(optimized.as_ref()), @r#"
587+
BoundedWindowAggExec: wdw=[dense_rank: Field { "dense_rank": UInt64 }, frame: ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
588+
PartitionedTopKExec: fn=dense_rank, fetch=3, partition=[pk@0], order=[val@1 ASC]
589+
PlaceholderRowExec
590+
"#);
591+
Ok(())
592+
}
593+
594+
#[test]
595+
fn dense_rank_flipped_3_gteq_dr() -> Result<()> {
596+
let plan = build_ranking_topn_plan(dense_rank_udwf, "dense_rank", 3, Operator::GtEq)?;
597+
let optimized = optimize(plan)?;
598+
assert_snapshot!(plan_str(optimized.as_ref()), @r#"
599+
BoundedWindowAggExec: wdw=[dense_rank: Field { "dense_rank": UInt64 }, frame: ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
600+
PartitionedTopKExec: fn=dense_rank, fetch=3, partition=[pk@0], order=[val@1 ASC]
601+
PlaceholderRowExec
602+
"#);
603+
Ok(())
604+
}
605+
606+
#[test]
607+
fn dense_rank_flipped_4_gt_dr_becomes_fetch_3() -> Result<()> {
608+
let plan = build_ranking_topn_plan(dense_rank_udwf, "dense_rank", 4, Operator::Gt)?;
609+
let optimized = optimize(plan)?;
610+
assert_snapshot!(plan_str(optimized.as_ref()), @r#"
611+
BoundedWindowAggExec: wdw=[dense_rank: Field { "dense_rank": UInt64 }, frame: ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
612+
PartitionedTopKExec: fn=dense_rank, fetch=3, partition=[pk@0], order=[val@1 ASC]
613+
PlaceholderRowExec
614+
"#);
615+
Ok(())
616+
}
617+
618+
#[test]
619+
fn dense_rank_no_order_by_no_change() -> Result<()> {
620+
// Without ORDER BY, every row ties at dense_rank 1 — the optimization
621+
// is degenerate (entire input would be retained). The rule must skip.
622+
let plan = build_no_order_by_plan(dense_rank_udwf, "dense_rank", 3)?;
567623
let before = plan_str(plan.as_ref());
568624
let optimized = optimize(plan)?;
569625
let after = plan_str(optimized.as_ref());
570626
assert_eq!(
571627
before, after,
572-
"DENSE_RANK is unsupported and must not be rewritten"
628+
"DENSE_RANK with empty ORDER BY must not be rewritten"
573629
);
574630
Ok(())
575631
}
632+
633+
// ----------------------------------------------------------------------
634+
// Shared guard: `fn < 1` keeps nothing
635+
// ----------------------------------------------------------------------
636+
637+
#[test]
638+
fn predicate_lt_1_no_change() -> Result<()> {
639+
// `fn < 1` (and the flipped `1 > fn`) yields limit_n = 0. Since
640+
// ROW_NUMBER / RANK / DENSE_RANK are always >= 1, the predicate keeps
641+
// nothing and the rule must skip — a fetch=0 PartitionedTopK* would
642+
// otherwise panic on its `k > 0` assertion at execution time.
643+
type UdwfFactory = fn() -> Arc<datafusion_expr::WindowUDF>;
644+
let cases: [(UdwfFactory, &str); 3] = [
645+
(row_number_udwf, "row_number"),
646+
(rank_udwf, "rank"),
647+
(dense_rank_udwf, "dense_rank"),
648+
];
649+
for (factory, name) in cases {
650+
let plan = build_ranking_topn_plan(factory, name, 1, Operator::Lt)?;
651+
let before = plan_str(plan.as_ref());
652+
let optimized = optimize(plan)?;
653+
let after = plan_str(optimized.as_ref());
654+
assert_eq!(
655+
before, after,
656+
"`{name} < 1` (limit 0) must not be rewritten"
657+
);
658+
}
659+
Ok(())
660+
}

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

Lines changed: 69 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -26,7 +26,7 @@
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 (
@@ -40,8 +40,8 @@
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
};
7070
use 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
329371
fn 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

Comments
 (0)