Skip to content

Commit 6286f5e

Browse files
authored
fix: saturate window frame lookahead instead of overflowing on huge FOLLOWING bounds (apache#26662)
## Which issue does this PR close? - Closes apache#26658. ## Rationale for this change A `ROWS` window frame with a huge `FOLLOWING` bound (for example `18446744073709551615 FOLLOWING`) combined with `ORDER BY ... LIMIT` panics with `attempt to add with overflow` in debug builds. In release builds the addition wraps, so `LimitPushPastWindows` could give the `SortExec` below the window a fetch that is far too small and drop rows the window needs. After fixing the optimizer rule, the same query panicked a second time in `WindowFrameContext::calculate_range_rows` (`window_state.rs`), which computes the frame end as `idx + n + 1` with the same unchecked bound. So both places need fixing for the query in the issue to return its result. ## What changes are included in this PR? - `limit_pushdown_past_window.rs`: use `saturating_add` when growing the limit by the window lookahead (`fetch + lookahead`, `lookahead + max_rel`) and when adding `skip` to a `GlobalLimitExec` fetch. A saturated fetch is still correct, it just means the sort keeps all rows. This matches how `input_fetch` in `sort_pushdown.rs` already handles the same kind of sum. - `window_state.rs`: use `saturating_add` for the `FOLLOWING n` start and end of a `ROWS` frame. The result is already clamped to the partition length, so saturating gives the right range. This touches the same lines in `limit_pushdown_past_window.rs` as the refactor in apache#26660, which leaves these sums to apache#26658. The change here is small, so whichever lands second should be easy to rebase. ## What is the testing strategy for this PR? - New cases in `window_limits.slt`: the query from the issue (`sum(x) OVER (... ROWS BETWEEN CURRENT ROW AND 18446744073709551615 FOLLOWING) ... LIMIT 2`), and a `lead(x, 1)` variant that adds its own lookahead on top of the huge frame bound. Without this change the first case panics at `limit_pushdown_past_window.rs:198`; with only the optimizer fix it panics at `window_state.rs:287`. - Locally: all `window*.slt` sqllogictests, `cargo test -p datafusion-expr --lib window_state`, `cargo test -p datafusion-physical-optimizer --lib limit_pushdown_past_window`, `cargo fmt --all` and `cargo clippy -p datafusion-expr -p datafusion-physical-optimizer --all-targets --all-features -- -D warnings` pass. ## Are there any user-facing changes? No API changes. Queries with very large `ROWS ... FOLLOWING` bounds now return results instead of panicking (or, in release builds, possibly returning too few rows). --- This PR was prepared with AI assistance. I reviewed the change and ran the tests listed above.
1 parent 914fc1b commit 6286f5e

3 files changed

Lines changed: 68 additions & 6 deletions

File tree

‎datafusion/expr/src/window_state.rs‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -263,8 +263,9 @@ impl WindowFrameContext {
263263
"Frame start cannot be UNBOUNDED FOLLOWING '{window_frame:?}'"
264264
);
265265
}
266+
// `n` comes from the query and can be as large as `u64::MAX`
266267
WindowFrameBound::Following(ScalarValue::UInt64(Some(n))) => {
267-
std::cmp::min(idx + n as usize, length)
268+
std::cmp::min(idx.saturating_add(n as usize), length)
268269
}
269270
// ERRONEOUS FRAMES
270271
WindowFrameBound::Preceding(_) | WindowFrameBound::Following(_) => {
@@ -289,7 +290,7 @@ impl WindowFrameContext {
289290
// UNBOUNDED FOLLOWING
290291
WindowFrameBound::Following(ScalarValue::UInt64(None)) => length,
291292
WindowFrameBound::Following(ScalarValue::UInt64(Some(n))) => {
292-
std::cmp::min(idx + n as usize + 1, length)
293+
std::cmp::min(idx.saturating_add(n as usize).saturating_add(1), length)
293294
}
294295
// ERRONEOUS FRAMES
295296
WindowFrameBound::Preceding(_) | WindowFrameBound::Following(_) => {

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

Lines changed: 17 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -177,7 +177,10 @@ fn grow_limit(window: &BoundedWindowAggExec, ctx: &mut TraverseState) -> bool {
177177
}
178178

179179
// finish grow
180-
ctx.max_lookahead(ctx.lookahead + max_rel);
180+
// Frame bounds come straight from the query and can be as large as
181+
// `u64::MAX`, so saturate instead of overflowing. A saturated lookahead
182+
// makes the `checked_add` in `apply_limit` fail, which skips the pushdown.
183+
ctx.max_lookahead(ctx.lookahead.saturating_add(max_rel));
181184
true
182185
}
183186

@@ -194,16 +197,26 @@ fn apply_limit(
194197
ctx.lookahead = 0;
195198
return Some(Transformed::no(Arc::clone(node)));
196199
};
200+
// A fetch that overflows can't drop any rows, so skip the pushdown rather
201+
// than turning the sort into a TopK that holds every row and can't spill.
202+
let Some(fetch) = fetch.checked_add(ctx.lookahead) else {
203+
ctx.lookahead = 0;
204+
return Some(Transformed::no(Arc::clone(node)));
205+
};
197206
let fetch = match node.fetch() {
198-
None => fetch + ctx.lookahead,
199-
Some(existing) => cmp::min(existing, fetch + ctx.lookahead),
207+
None => fetch,
208+
Some(existing) => cmp::min(existing, fetch),
200209
};
201210
Some(Transformed::complete(node.with_fetch(Some(fetch)).unwrap()))
202211
}
203212

204213
fn get_limit(node: &Arc<dyn ExecutionPlan>, ctx: &mut TraverseState) -> bool {
205214
if let Some(limit) = node.downcast_ref::<GlobalLimitExec>() {
206-
ctx.reset_limit(limit.fetch().map(|fetch| fetch + limit.skip()));
215+
ctx.reset_limit(
216+
limit
217+
.fetch()
218+
.map(|fetch| fetch.saturating_add(limit.skip())),
219+
);
207220
return true;
208221
}
209222
// In distributed execution, GlobalLimitExec becomes LocalLimitExec

‎datafusion/sqllogictest/test_files/window_limits.slt‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -862,3 +862,51 @@ physical_plan
862862
03)----BoundedWindowAggExec: wdw=[lead(employees.salary,Int64(2)) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "lead(employees.salary,Int64(2)) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": nullable UInt64 }, frame: ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
863863
04)------SortExec: TopK(fetch=5), expr=[empno@0 ASC NULLS LAST], preserve_partitioning=[false]
864864
05)--------DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/testing/data/csv/aggregate_test_100_with_dates.csv]]}, projection=[empno, salary], file_type=csv, has_header=true
865+
866+
# A huge FOLLOWING bound must not overflow when the limit is grown by the
867+
# window's lookahead (https://github.com/apache/datafusion/issues/26658)
868+
statement ok
869+
CREATE TABLE huge_frame_t(a INT, x INT) AS VALUES (1, 1), (2, 2), (3, 3), (4, 4), (5, 5);
870+
871+
query II
872+
SELECT a, sum(x) OVER (ORDER BY a ROWS BETWEEN CURRENT ROW AND 18446744073709551615 FOLLOWING) s
873+
FROM huge_frame_t ORDER BY a LIMIT 2;
874+
----
875+
1 15
876+
2 14
877+
878+
# Same, with a window function that adds its own lookahead on top of the frame
879+
query II
880+
SELECT a, lead(x, 1) OVER (ORDER BY a ROWS BETWEEN CURRENT ROW AND 18446744073709551615 FOLLOWING) l
881+
FROM huge_frame_t ORDER BY a LIMIT 2;
882+
----
883+
1 2
884+
2 3
885+
886+
# A huge FOLLOWING start bound must not overflow either
887+
query II
888+
SELECT a, sum(x) OVER (ORDER BY a ROWS BETWEEN 18446744073709551615 FOLLOWING AND 18446744073709551615 FOLLOWING) s
889+
FROM huge_frame_t ORDER BY a LIMIT 2;
890+
----
891+
1 NULL
892+
2 NULL
893+
894+
# The pushdown is skipped, so the sort stays a full sort instead of a TopK
895+
query TT
896+
EXPLAIN SELECT a, sum(x) OVER (ORDER BY a ROWS BETWEEN CURRENT ROW AND 18446744073709551615 FOLLOWING) s
897+
FROM huge_frame_t ORDER BY a LIMIT 2;
898+
----
899+
logical_plan
900+
01)Sort: huge_frame_t.a ASC NULLS LAST, fetch=2
901+
02)--Projection: huge_frame_t.a, sum(huge_frame_t.x) ORDER BY [huge_frame_t.a ASC NULLS LAST] ROWS BETWEEN CURRENT ROW AND 18446744073709551615 FOLLOWING AS s
902+
03)----WindowAggr: windowExpr=[[sum(CAST(huge_frame_t.x AS Int64)) ORDER BY [huge_frame_t.a ASC NULLS LAST] ROWS BETWEEN CURRENT ROW AND 18446744073709551615 FOLLOWING]]
903+
04)------TableScan: huge_frame_t projection=[a, x]
904+
physical_plan
905+
01)ProjectionExec: expr=[a@0 as a, sum(huge_frame_t.x) ORDER BY [huge_frame_t.a ASC NULLS LAST] ROWS BETWEEN CURRENT ROW AND 18446744073709551615 FOLLOWING@2 as s]
906+
02)--GlobalLimitExec: skip=0, fetch=2
907+
03)----BoundedWindowAggExec: wdw=[sum(huge_frame_t.x) ORDER BY [huge_frame_t.a ASC NULLS LAST] ROWS BETWEEN CURRENT ROW AND 18446744073709551615 FOLLOWING: Field { "sum(huge_frame_t.x) ORDER BY [huge_frame_t.a ASC NULLS LAST] ROWS BETWEEN CURRENT ROW AND 18446744073709551615 FOLLOWING": nullable Int64 }, frame: ROWS BETWEEN CURRENT ROW AND 18446744073709551615 FOLLOWING], mode=[Sorted]
908+
04)------SortExec: expr=[a@0 ASC NULLS LAST], preserve_partitioning=[false]
909+
05)--------DataSourceExec: partitions=1, partition_sizes=[1]
910+
911+
statement ok
912+
DROP TABLE huge_frame_t;

0 commit comments

Comments
 (0)