Skip to content

Commit 36f3935

Browse files
fix: WindowTopN resolves the filter column through intermediate proje… (apache#26417)
## Which issue does this PR close? - Closes apache#26416 - Part of apache#24608. ## Rationale for this change With `datafusion.optimizer.enable_window_topn = true`, some top-K window queries return wrong results: SELECT pk, id, rn, rk FROM ( SELECT pk, v, id, row_number() OVER (PARTITION BY pk ORDER BY v) AS rn, rank() OVER (PARTITION BY pk ORDER BY v) AS rk FROM t) WHERE rk <= 1; returns only one row per partition and drops the rows tied at `rk = 1`. With the two functions swapped and `WHERE rn <= 1`, it returns rows with `rn = 2`. `WindowTopN` reads the filter's column index from the predicate, which indexes the projection between the filter and the window, and used it as if it indexed the window's output. When that projection drops a column (here `v`, which the outer query doesn't select), every later index shifts down by one. With two ranking functions the rule then builds `PartitionedTopKExec` from the wrong one, and since it also removes the `FilterExec`, nothing corrects the result. With a single ranking function, the same shifted index made the rule decline instead. So queries such as `row_number() OVER (PARTITION BY pk ORDER BY v, s)` with `s` unused afterwards never got the optimization. ## What changes are included in this PR? - New `column_index_below`, which maps the filter's column index down through the nodes `find_window_below` walks: a `ProjectionExec` must pass the column through as a bare `Column`, and the index follows it; a `RepartitionExec` leaves it unchanged; a column the projection computes (e.g. `rk + 1`) makes the rule decline. - `try_transform` resolves the index before checking that it names a window column. Everything after that already reads the resolved window expression. - The rule's doc comment lists the new condition. ## What is the testing strategy for this PR? `window_topn.slt`, each case checking both the rows (identical to `enable_window_topn = false`) and the `fn=` in `EXPLAIN`: - the two wrong-result queries above (`fn=rank`, `fn=row_number`), and a `dense_rank()` variant; - `row_number() OVER (PARTITION BY pk ORDER BY v, id)` with `v` dropped by the outer query, which is now rewritten; - `rank() OVER (...) + 1 AS x ... WHERE x <= 2`, which is still not rewritten: filter pushdown moves the expression into the predicate. `core/tests/physical_optimizer/window_topn.rs`, with hand-built plans for shapes the default optimizer pipeline doesn't produce but the rule accepts: - two stacked projections, which only resolve correctly top-down; - a projection over a `RepartitionExec` (the rule runs before `EnsureRequirements` inserts any); - a column the projection computes, e.g. `rk + 1`: unchanged plan. ## Are there any user-facing changes? With `enable_window_topn = true`, the affected queries now return correct results, and more query shapes are rewritten to `PartitionedTopKExec`. That includes `dense_rank()`, whose memory use is tracked in #. No API changes. The option is off by default.
1 parent 6aef019 commit 36f3935

3 files changed

Lines changed: 346 additions & 5 deletions

File tree

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

Lines changed: 148 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -46,10 +46,13 @@ use datafusion_physical_plan::filter::FilterExec;
4646
use datafusion_physical_plan::metrics::MetricValue;
4747
use datafusion_physical_plan::placeholder_row::PlaceholderRowExec;
4848
use datafusion_physical_plan::projection::ProjectionExec;
49-
use datafusion_physical_plan::sorts::partitioned_topk::PartitionedTopKExec;
49+
use datafusion_physical_plan::repartition::RepartitionExec;
50+
use datafusion_physical_plan::sorts::partitioned_topk::{
51+
PartitionedTopKExec, WindowFnKind,
52+
};
5053
use datafusion_physical_plan::sorts::sort::SortExec;
5154
use datafusion_physical_plan::windows::{BoundedWindowAggExec, create_udwf_window_expr};
52-
use datafusion_physical_plan::{ExecutionPlan, InputOrderMode};
55+
use datafusion_physical_plan::{ExecutionPlan, InputOrderMode, Partitioning};
5356
use insta::assert_snapshot;
5457

5558
fn schema() -> Arc<Schema> {
@@ -458,6 +461,149 @@ fn two_window_exprs_keep_the_window_node() -> Result<()> {
458461
Ok(())
459462
}
460463

464+
/// `ROW_NUMBER() AS rn, RANK() AS rk` over `PARTITION BY pk ORDER BY val`.
465+
/// Output: `[pk@0, val@1, rn@2, rk@3]`.
466+
fn build_rn_rk_window() -> Result<Arc<dyn ExecutionPlan>> {
467+
let s = schema();
468+
let input: Arc<dyn ExecutionPlan> = Arc::new(PlaceholderRowExec::new(Arc::clone(&s)));
469+
let partition_by = vec![col("pk", &s)?];
470+
let order_by = vec![PhysicalSortExpr::new_default(col("val", &s)?).asc()];
471+
let window_expr = |udwf: Arc<datafusion_expr::WindowUDF>, name: &str| {
472+
Ok::<_, datafusion_common::DataFusionError>(Arc::new(StandardWindowExpr::new(
473+
create_udwf_window_expr(&udwf, &[], &s, name.to_string(), false)?,
474+
&partition_by,
475+
&order_by,
476+
Arc::new(WindowFrame::new_bounds(
477+
WindowFrameUnits::Rows,
478+
WindowFrameBound::Preceding(ScalarValue::UInt64(None)),
479+
WindowFrameBound::CurrentRow,
480+
)),
481+
)))
482+
};
483+
Ok(Arc::new(BoundedWindowAggExec::try_new(
484+
vec![
485+
window_expr(row_number_udwf(), "rn")?,
486+
window_expr(rank_udwf(), "rk")?,
487+
],
488+
input,
489+
InputOrderMode::Sorted,
490+
true,
491+
)?))
492+
}
493+
494+
/// A `ProjectionExec` passing through `input`'s columns at `indices`.
495+
fn project(
496+
input: Arc<dyn ExecutionPlan>,
497+
indices: &[usize],
498+
) -> Result<Arc<dyn ExecutionPlan>> {
499+
let schema = input.schema();
500+
let exprs: Vec<(Arc<dyn datafusion_physical_expr::PhysicalExpr>, String)> = indices
501+
.iter()
502+
.map(|&i| {
503+
let name = schema.field(i).name();
504+
(
505+
Arc::new(Column::new(name, i))
506+
as Arc<dyn datafusion_physical_expr::PhysicalExpr>,
507+
name.to_string(),
508+
)
509+
})
510+
.collect();
511+
Ok(Arc::new(ProjectionExec::try_new(exprs, input)?))
512+
}
513+
514+
/// `FilterExec(<column idx of input> <= 3)`, with the literal in the column's type.
515+
fn filter_lteq_3(
516+
input: Arc<dyn ExecutionPlan>,
517+
idx: usize,
518+
) -> Result<Arc<dyn ExecutionPlan>> {
519+
let schema = input.schema();
520+
let field = schema.field(idx);
521+
let predicate = Arc::new(BinaryExpr::new(
522+
Arc::new(Column::new(field.name(), idx)),
523+
Operator::LtEq,
524+
lit(ScalarValue::UInt64(Some(3)).cast_to(field.data_type())?),
525+
));
526+
Ok(Arc::new(FilterExec::try_new(predicate, input)?))
527+
}
528+
529+
/// The ranking function the rewrite chose, or `None` if it did not fire.
530+
fn rewritten_fn(plan: Arc<dyn ExecutionPlan>) -> Result<Option<WindowFnKind>> {
531+
let optimized = optimize(plan)?;
532+
Ok(find_partitioned_topk(&optimized).map(|p| {
533+
p.downcast_ref::<PartitionedTopKExec>()
534+
.expect("find_partitioned_topk returns a PartitionedTopKExec")
535+
.fn_kind()
536+
}))
537+
}
538+
539+
/// Stacked projections are resolved top-down: each one maps an index into its
540+
/// output to one into its input. Bottom-up, `rk@0` would follow `pk@0` and then
541+
/// `rk@2` to `rn` in the window's output.
542+
#[test]
543+
fn stacked_projections_resolve_top_down() -> Result<()> {
544+
let lower = project(build_rn_rk_window()?, &[0, 2, 3])?; // [pk, rn, rk]
545+
let upper = project(lower, &[2, 0])?; // [rk, pk]
546+
assert_eq!(
547+
rewritten_fn(filter_lteq_3(upper, 0)?)?,
548+
Some(WindowFnKind::Rank)
549+
);
550+
Ok(())
551+
}
552+
553+
/// A `RepartitionExec` keeps its input's schema, so the index passes through it.
554+
#[test]
555+
fn repartition_between_passes_the_index_through() -> Result<()> {
556+
let repartition: Arc<dyn ExecutionPlan> = Arc::new(RepartitionExec::try_new(
557+
build_rn_rk_window()?,
558+
Partitioning::RoundRobinBatch(4),
559+
)?);
560+
let projection = project(repartition, &[0, 3])?; // [pk, rk]
561+
assert_eq!(
562+
rewritten_fn(filter_lteq_3(projection, 1)?)?,
563+
Some(WindowFnKind::Rank)
564+
);
565+
Ok(())
566+
}
567+
568+
/// A projection that reorders the window's columns: the filter's `pk@2` maps
569+
/// back to `pk@0`, an input column, so the rule leaves the plan alone. Read as
570+
/// an index into the window's output, it would be `rn`.
571+
#[test]
572+
fn reordered_projection_input_column_no_change() -> Result<()> {
573+
let projection = project(build_rn_rk_window()?, &[2, 3, 0])?; // [rn, rk, pk]
574+
let plan = filter_lteq_3(projection, 2)?;
575+
let before = plan_str(plan.as_ref());
576+
assert_eq!(plan_str(optimize(plan)?.as_ref()), before);
577+
Ok(())
578+
}
579+
580+
/// A column the projection computes has no single window column behind it,
581+
/// so the rule leaves the plan alone. `x` sits at index 2 so that treating it
582+
/// as a pass-through would land on `rn` rather than be rejected as an input
583+
/// column.
584+
#[test]
585+
fn computed_projection_column_no_change() -> Result<()> {
586+
let window = build_rn_rk_window()?;
587+
let rk_plus_one: Arc<dyn datafusion_physical_expr::PhysicalExpr> =
588+
Arc::new(BinaryExpr::new(
589+
Arc::new(Column::new("rk", 3)),
590+
Operator::Plus,
591+
lit(ScalarValue::UInt64(Some(1))),
592+
));
593+
let projection: Arc<dyn ExecutionPlan> = Arc::new(ProjectionExec::try_new(
594+
vec![
595+
(Arc::new(Column::new("pk", 0)) as _, "pk".to_string()),
596+
(Arc::new(Column::new("val", 1)) as _, "val".to_string()),
597+
(rk_plus_one, "x".to_string()),
598+
],
599+
window,
600+
)?);
601+
let plan = filter_lteq_3(projection, 2)?;
602+
let before = plan_str(plan.as_ref());
603+
assert_eq!(plan_str(optimize(plan)?.as_ref()), before);
604+
Ok(())
605+
}
606+
461607
// ----------------------------------------------------------------------
462608
// RANK rule tests
463609
// ----------------------------------------------------------------------

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

Lines changed: 36 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -122,6 +122,9 @@ use datafusion_physical_plan::windows::{BoundedWindowAggExec, WindowUDFExpr};
122122
/// All of the following must be true:
123123
/// - Config flag `enable_window_topn` is `true`
124124
/// - The plan matches `FilterExec → [ProjectionExec] → BoundedWindowAggExec`
125+
/// - Every `ProjectionExec` between the filter and the window passes the
126+
/// filtered column through as a bare column, possibly at another position
127+
/// (as when a column the query no longer needs is dropped)
125128
/// - The window function is `ROW_NUMBER`, `RANK`, or `DENSE_RANK`
126129
/// - Every window expression in the `BoundedWindowAggExec` is `ROW_NUMBER`,
127130
/// `RANK`, or `DENSE_RANK` over the same `PARTITION BY` / `ORDER BY`. A
@@ -193,7 +196,10 @@ impl WindowTopN {
193196
let child = filter.input();
194197
let (window_exec, intermediates) = find_window_below(child)?;
195198

196-
// Step 4: Verify col_idx references a supported window function output column
199+
// Step 4: Verify col_idx references a supported window function output column.
200+
// `col_idx` indexes the filter's input; resolve it to the window's output
201+
// first, since a projection in between can drop or reorder columns.
202+
let col_idx = column_index_below(col_idx, &intermediates)?;
197203
let window_exec_typed = window_exec.downcast_ref::<BoundedWindowAggExec>()?;
198204
let input_field_count = window_exec_typed.input().schema().fields().len();
199205
if col_idx < input_field_count {
@@ -455,8 +461,10 @@ type PlanAndIntermediates = (Arc<dyn ExecutionPlan>, Vec<Arc<dyn ExecutionPlan>>
455461
///
456462
/// Handles sequences of `ProjectionExec` and `RepartitionExec`.
457463
/// This is safe because `PartitionedTopKExec` can be pushed below them:
458-
/// projections only provide aliases, and pushing the limit below repartitions
459-
/// is safe because the limit is computed per-partition.
464+
/// projections only rename, drop, reorder or compute over the window's
465+
/// columns (the filter's column is mapped back through them by
466+
/// [`column_index_below`]), and pushing the limit below repartitions is safe
467+
/// because the limit is computed per-partition.
460468
///
461469
/// Returns the window exec and a list of intermediate nodes to rebuild,
462470
/// or `None` if no `BoundedWindowAggExec` is found.
@@ -478,3 +486,28 @@ fn find_window_below(plan: &Arc<dyn ExecutionPlan>) -> Option<PlanAndIntermediat
478486
}
479487
}
480488
}
489+
490+
/// Maps `col_idx`, an index into the output of `intermediates[0]` (the
491+
/// filter's input), to the index of the same column in the output of the
492+
/// node below the last intermediate (the window).
493+
///
494+
/// `intermediates` is top-down, as [`find_window_below`] returns it, so each
495+
/// step reads an index into the node's output and yields one into its input.
496+
/// A `RepartitionExec` keeps its input's schema. A `ProjectionExec` must pass
497+
/// the column through as a bare [`Column`]: one it computes (e.g. `rn + 1`)
498+
/// has no single input column to follow, so this returns `None`.
499+
fn column_index_below(
500+
col_idx: usize,
501+
intermediates: &[Arc<dyn ExecutionPlan>],
502+
) -> Option<usize> {
503+
intermediates.iter().try_fold(col_idx, |idx, node| {
504+
if let Some(projection) = node.downcast_ref::<ProjectionExec>() {
505+
let expr = &projection.expr().get(idx)?.expr;
506+
Some(expr.downcast_ref::<Column>()?.index())
507+
} else if node.downcast_ref::<RepartitionExec>().is_some() {
508+
Some(idx)
509+
} else {
510+
None
511+
}
512+
})
513+
}

0 commit comments

Comments
 (0)