Skip to content

Commit 4877863

Browse files
cool9850311claude
andcommitted
fix: don't invent a limit from LimitEffect::Absolute
Review feedback. `LimitEffect::Absolute(n)` means the window needs at least `n` input rows whatever the limit is, so `grow_limit` raises the limit it is carrying to `n`. It did that through `ctx.limit.unwrap_or(0)`, which with no limit in hand does not raise a limit but invents one: the sort below then gets `TopK(fetch=n)` although nothing above it asked for a limit at all, and rows the query wanted are dropped. Unlike the rest of this PR that is a wrong-results bug, and it is pre-existing; this PR adds another path that reaches it, since the walk now continues below a sort it has already given a fetch to. With nothing in hand there is nothing to raise, so leave the limit alone. No in-tree window function returns `Absolute` -- `ntile`, `cume_dist` and `percent_rank` return `Unknown`, `row_number`, `nth_value`, `rank` and `dense_rank` return `None`, and `lead`/`lag` return `Relative(n)` or `Unknown` -- so the arm is unreachable from SQL and this is a unit test rather than a `.slt` case, per the testing guide. The two tests divide up as follows: the first is red without the fix, and the second is green either way and holds down the `max`, so that deleting the arm is not mistaken for a fix. Co-Authored-By: Claude Opus 5 <[email protected]>
1 parent 64c7911 commit 4877863

1 file changed

Lines changed: 112 additions & 4 deletions

File tree

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

Lines changed: 112 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -155,8 +155,12 @@ fn grow_limit(window: &BoundedWindowAggExec, ctx: &mut TraverseState) -> bool {
155155
LimitEffect::Unknown => return false,
156156
LimitEffect::Relative(rel) => max_rel = max_rel.max(rel),
157157
LimitEffect::Absolute(val) => {
158-
let cur = ctx.limit.unwrap_or(0);
159-
ctx.limit = Some(cur.max(val))
158+
// Only raise a limit we actually have. With nothing in hand there is
159+
// no limit to raise, and inventing one truncates a sort that has no
160+
// `LIMIT` above it at all.
161+
if let Some(cur) = ctx.limit {
162+
ctx.limit = Some(cur.max(val));
163+
}
160164
}
161165
}
162166

@@ -276,9 +280,12 @@ fn bound_to_usize(bound: &WindowFrameBound) -> Option<usize> {
276280
#[cfg(test)]
277281
mod tests {
278282
use super::*;
279-
use arrow::datatypes::{DataType, Field, Schema};
283+
use arrow::datatypes::{DataType, Field, FieldRef, Schema};
280284
use datafusion_expr::WindowFrame;
281-
use datafusion_functions_window::row_number::row_number_udwf;
285+
use datafusion_expr::function::{PartitionEvaluatorArgs, WindowUDFFieldArgs};
286+
use datafusion_expr::{PartitionEvaluator, Signature, WindowUDF, WindowUDFImpl};
287+
use datafusion_functions_window::row_number::{RowNumber, row_number_udwf};
288+
use datafusion_physical_expr::PhysicalExpr;
282289
use datafusion_physical_expr::expressions::col;
283290
use datafusion_physical_expr_common::sort_expr::{LexOrdering, PhysicalSortExpr};
284291
use datafusion_physical_plan::InputOrderMode;
@@ -378,4 +385,105 @@ mod tests {
378385
PlaceholderRowExec
379386
"#);
380387
}
388+
389+
/// A `row_number` wrapper that claims it always needs at least 200 input rows.
390+
/// No in-tree window function returns [`LimitEffect::Absolute`], so wrapping one
391+
/// is the only way to reach that arm of `grow_limit`.
392+
#[derive(Debug, PartialEq, Eq, Hash)]
393+
struct AtLeast200(RowNumber);
394+
395+
impl WindowUDFImpl for AtLeast200 {
396+
fn name(&self) -> &str {
397+
"at_least_200"
398+
}
399+
400+
fn signature(&self) -> &Signature {
401+
self.0.signature()
402+
}
403+
404+
fn partition_evaluator(
405+
&self,
406+
args: PartitionEvaluatorArgs,
407+
) -> datafusion_common::Result<Box<dyn PartitionEvaluator>> {
408+
self.0.partition_evaluator(args)
409+
}
410+
411+
fn field(&self, args: WindowUDFFieldArgs) -> datafusion_common::Result<FieldRef> {
412+
self.0.field(args)
413+
}
414+
415+
fn limit_effect(&self, _args: &[Arc<dyn PhysicalExpr>]) -> LimitEffect {
416+
LimitEffect::Absolute(200)
417+
}
418+
}
419+
420+
/// Build `[GlobalLimitExec(100) →] BoundedWindowAggExec(at_least_200) → SortExec
421+
/// → PlaceholderRowExec`. Without the limit there is no fetch anywhere in the plan.
422+
fn build_absolute_plan(
423+
with_limit: bool,
424+
) -> datafusion_common::Result<Arc<dyn ExecutionPlan>> {
425+
let s = schema();
426+
let input: Arc<dyn ExecutionPlan> =
427+
Arc::new(PlaceholderRowExec::new(Arc::clone(&s)));
428+
429+
let ordering =
430+
LexOrdering::new(vec![PhysicalSortExpr::new_default(col("a", &s)?).asc()])
431+
.unwrap();
432+
433+
let sort: Arc<dyn ExecutionPlan> = Arc::new(
434+
SortExec::new(ordering.clone(), input).with_preserve_partitioning(true),
435+
);
436+
437+
let udwf = Arc::new(WindowUDF::from(AtLeast200(RowNumber::new())));
438+
let window_expr = Arc::new(StandardWindowExpr::new(
439+
create_udwf_window_expr(&udwf, &[], &s, "at_least_200".to_string(), false)?,
440+
&[],
441+
ordering.as_ref(),
442+
Arc::new(WindowFrame::new_bounds(
443+
WindowFrameUnits::Rows,
444+
WindowFrameBound::Preceding(ScalarValue::UInt64(None)),
445+
WindowFrameBound::CurrentRow,
446+
)),
447+
));
448+
449+
let window: Arc<dyn ExecutionPlan> = Arc::new(BoundedWindowAggExec::try_new(
450+
vec![window_expr],
451+
sort,
452+
InputOrderMode::Sorted,
453+
true,
454+
)?);
455+
456+
Ok(if with_limit {
457+
Arc::new(GlobalLimitExec::new(window, 0, Some(100)))
458+
} else {
459+
window
460+
})
461+
}
462+
463+
/// With no limit in the plan there is nothing to raise, so the sort must stay a
464+
/// full sort. Turning it into a TopK here would drop rows the query asked for.
465+
#[test]
466+
fn absolute_limit_effect_does_not_invent_a_limit() {
467+
let plan = build_absolute_plan(false).unwrap();
468+
let optimized = optimize(plan);
469+
assert_snapshot!(plan_str(optimized.as_ref()), @r#"
470+
BoundedWindowAggExec: wdw=[at_least_200: Field { "at_least_200": UInt64 }, frame: ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
471+
SortExec: expr=[a@0 ASC], preserve_partitioning=[true]
472+
PlaceholderRowExec
473+
"#);
474+
}
475+
476+
/// A limit that is in the plan is still raised to the window's floor: 100 rows
477+
/// are asked for, the window needs 200, so the sort fetches 200.
478+
#[test]
479+
fn absolute_limit_effect_raises_an_existing_limit() {
480+
let plan = build_absolute_plan(true).unwrap();
481+
let optimized = optimize(plan);
482+
assert_snapshot!(plan_str(optimized.as_ref()), @r#"
483+
GlobalLimitExec: skip=0, fetch=100
484+
BoundedWindowAggExec: wdw=[at_least_200: Field { "at_least_200": UInt64 }, frame: ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
485+
SortExec: TopK(fetch=200), expr=[a@0 ASC], preserve_partitioning=[true]
486+
PlaceholderRowExec
487+
"#);
488+
}
381489
}

0 commit comments

Comments
 (0)