Skip to content

Commit 3470bd0

Browse files
kita-renjiclaude
andauthored
fix: wait for the whole NULL peer group before emitting RANGE N PRECEDING window results (apache#25860)
## Which issue does this PR close? - Closes apache#25859. ## Rationale for this change Window aggregates over a `RANGE ... N PRECEDING` frame return results that depend on how the input is split into batches when the ORDER BY value is NULL. For a NULL row the frame is its group of NULL peers, and when that group spans batches the row is computed before the rest of the group arrives. At default settings a query over 20,000 rows with 10,000 NULL keys returns a count of 6384 instead of 10000 for 6,384 of the NULL rows. Details and repros are in the issue. ## What changes are included in this PR? - `WindowFrame::new_bounds`: a `RANGE` frame is causal only when it ends at `UNBOUNDED PRECEDING`. With an offset end bound, the frame of a NULL or NaN row ends at its last peer, which can be a later row. `GROUPS` keeps the current rule, since NULL peers form an ordinary group there. - `is_end_bound_safe_for_range`: a `PRECEDING` end bound is handled like `CURRENT ROW`, so the row waits until an input row past its peer group arrives (`is_row_ahead`) or the partition ends. An `N PRECEDING` frame only reaches the end of the buffer when the row's frame ends at its last peer, so the check only holds back NULL and NaN rows. Rows with other ORDER BY values behave as before: their `N PRECEDING` frame ends before the current row, so it never reaches the end of the buffer and results are still produced as the input streams. RANGE frames planned from SQL were already non-causal (their bounds are strings until type coercion), so their plans don't change; the second change is what fixes them. The first change fixes frames built from typed bounds (reversed frames, the DataFrame API, proto), where built-in window functions such as `nth_value` were affected too. ## What is the testing strategy for this PR? New cases at the end of `window.slt`, with `batch_size = 2` so the peers span batches: `sum`/`count`/`max` over `5 PRECEDING AND 1 PRECEDING` and `UNBOUNDED PRECEDING AND 1 PRECEDING`, NULLS FIRST and DESC orderings, a `FOLLOWING` frame that the planner reverses to reuse another window's sort (covering `nth_value`), and a group of NaN keys. Expected values match DuckDB 1.5.5 and Postgres 17, and all four queries fail without the fix. I also ran a randomized check outside the test suite: random tables with NULL keys, random RANGE/GROUPS/ROWS frames and functions whose result doesn't depend on tie order, compared across batch sizes 1, 2, 3, 7 and 8192 and against DuckDB. Main had 31 batch-dependent results in the first 1,000 queries; this branch had none in 7,500, and none in variants with NaN keys and with an unbounded ordered source (Linear mode, PARTITION BY). The whole sqllogictest suite and the window fuzz tests (`--features extended_tests`) pass. ## Are there any user-facing changes? Queries with NULL or NaN values in the ORDER BY column of a `RANGE ... N PRECEDING` window now return the same results regardless of batch size. `WindowFrame::is_causal()` now returns false for RANGE frames with an offset end bound. For frames built from typed bounds this can drop an ordering that a set-monotonic aggregate used to add to the window output, so a plan may need an extra sort; SQL-planned frames were already non-causal, and no sqllogictest plan changed. 🤖 Generated with [Claude Code](https://claude.com/claude-code) Co-authored-by: Claude Opus 5.5 (1M context) <[email protected]>
1 parent 5b5edc7 commit 3470bd0

3 files changed

Lines changed: 88 additions & 10 deletions

File tree

‎datafusion/expr/src/window_frame.rs‎

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -224,7 +224,13 @@ impl WindowFrame {
224224
}
225225
_ => true,
226226
},
227-
WindowFrameUnits::Range | WindowFrameUnits::Groups => match &end_bound {
227+
// For a row whose ORDER BY value is NULL or NaN, an offset bound
228+
// ends the RANGE frame at its last peer, which may be a later row.
229+
WindowFrameUnits::Range => matches!(
230+
&end_bound,
231+
WindowFrameBound::Preceding(value) if value.is_null()
232+
),
233+
WindowFrameUnits::Groups => match &end_bound {
228234
WindowFrameBound::Preceding(value) => {
229235
if value.is_null() {
230236
// Unbounded preceding

‎datafusion/physical-expr/src/window/window_expr.rs‎

Lines changed: 4 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -507,15 +507,10 @@ fn is_end_bound_safe_for_range(
507507
idx: usize,
508508
) -> Result<bool> {
509509
match end_bound {
510-
WindowFrameBound::Preceding(value) => {
511-
let zero = ScalarValue::new_zero(&value.data_type())?;
512-
if value.eq(&zero) {
513-
is_row_ahead(orderby_col, most_recent_ob_col, sort_options)
514-
} else {
515-
Ok(true)
516-
}
517-
}
518-
WindowFrameBound::CurrentRow => {
510+
// A frame ending in `N PRECEDING` can only reach the end of the buffer
511+
// when the current row's frame ends at its last peer, as for a NULL or
512+
// NaN ORDER BY value, so it is safe once a row past its peers arrives.
513+
WindowFrameBound::Preceding(_) | WindowFrameBound::CurrentRow => {
519514
is_row_ahead(orderby_col, most_recent_ob_col, sort_options)
520515
}
521516
WindowFrameBound::Following(delta) => {

‎datafusion/sqllogictest/test_files/window.slt‎

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7345,3 +7345,80 @@ SELECT a FROM window_in_filter_t LIMIT count(*);
73457345

73467346
statement ok
73477347
DROP TABLE window_in_filter_t;
7348+
7349+
# RANGE frames ending in `N PRECEDING`: for a row whose ORDER BY value is NULL
7350+
# the frame is its NULL peer group, so the result must not depend on how the
7351+
# NULL peers are split across input batches.
7352+
statement ok
7353+
CREATE TABLE range_null_peers(id INT, x INT, v INT) AS VALUES
7354+
(1, 1, 10), (2, 2, 20), (3, NULL, 30), (4, NULL, 40), (5, NULL, 50);
7355+
7356+
statement ok
7357+
set datafusion.execution.batch_size = 2;
7358+
7359+
query IIIII
7360+
SELECT id,
7361+
sum(v) OVER (ORDER BY x RANGE BETWEEN 5 PRECEDING AND 1 PRECEDING),
7362+
count(*) OVER (ORDER BY x RANGE BETWEEN 5 PRECEDING AND 1 PRECEDING),
7363+
max(v) OVER (ORDER BY x RANGE BETWEEN 5 PRECEDING AND 1 PRECEDING),
7364+
sum(v) OVER (ORDER BY x RANGE BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING)
7365+
FROM range_null_peers ORDER BY id;
7366+
----
7367+
1 NULL 0 NULL NULL
7368+
2 10 1 10 10
7369+
3 120 3 50 150
7370+
4 120 3 50 150
7371+
5 120 3 50 150
7372+
7373+
query III
7374+
SELECT id,
7375+
sum(v) OVER (ORDER BY x NULLS FIRST RANGE BETWEEN 5 PRECEDING AND 1 PRECEDING),
7376+
sum(v) OVER (ORDER BY x DESC RANGE BETWEEN 5 PRECEDING AND 1 PRECEDING)
7377+
FROM range_null_peers ORDER BY id;
7378+
----
7379+
1 NULL 20
7380+
2 10 NULL
7381+
3 120 120
7382+
4 120 120
7383+
5 120 120
7384+
7385+
# The FOLLOWING frames are reversed to `5 PRECEDING AND 1 PRECEDING` so they can
7386+
# reuse the sort of the first window
7387+
query IIII
7388+
SELECT id,
7389+
count(*) OVER (ORDER BY x DESC NULLS LAST, id),
7390+
sum(v) OVER (ORDER BY x ASC NULLS FIRST RANGE BETWEEN 1 FOLLOWING AND 5 FOLLOWING),
7391+
nth_value(1, 3) OVER (ORDER BY x ASC NULLS FIRST RANGE BETWEEN 1 FOLLOWING AND 5 FOLLOWING)
7392+
FROM range_null_peers ORDER BY id;
7393+
----
7394+
1 2 20 NULL
7395+
2 1 NULL NULL
7396+
3 3 120 1
7397+
4 4 120 1
7398+
5 5 120 1
7399+
7400+
# NaN sorts as a single peer group too, and `NaN - 1` is NaN
7401+
statement ok
7402+
CREATE TABLE range_nan_peers(id INT, x DOUBLE) AS VALUES
7403+
(1, 1.0), (2, 'NaN'), (3, 'NaN'), (4, 'NaN'), (5, 2.0);
7404+
7405+
query III
7406+
SELECT id,
7407+
count(*) OVER (ORDER BY x RANGE BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING),
7408+
count(*) OVER (ORDER BY x DESC RANGE BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING)
7409+
FROM range_nan_peers ORDER BY id;
7410+
----
7411+
1 0 4
7412+
2 5 3
7413+
3 5 3
7414+
4 5 3
7415+
5 1 3
7416+
7417+
statement ok
7418+
reset datafusion.execution.batch_size;
7419+
7420+
statement ok
7421+
DROP TABLE range_null_peers;
7422+
7423+
statement ok
7424+
DROP TABLE range_nan_peers;

0 commit comments

Comments
 (0)