Skip to content

Commit 84acf49

Browse files
authored
fix: correct LEAD/LAG IGNORE NULLS evaluation and limit pushdown (#25472)
## Which issue does this PR close? <!-- We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123. --> - Closes #25471. ## Rationale for this change <!-- Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed. Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes. Please explain the problem you are trying to solve in terms of the user-visible behavior, rather than the implementation. For example, "The code in `foo.rs` doesn't handle nulls" is a symptom of the implementation. "COUNT(DISTINCT) returns wrong results when the column contains nulls" is the user-visible problem. --> LEAD and negative-offset LAG with IGNORE NULLS can return NULL or a default value even when the requested non-null row exists. This happens when stateful evaluation fails to refill a partially populated lookahead cache, or when window LIMIT pushdown truncates input before the target row. ## What changes are included in this PR? <!-- There is no need to duplicate the description in the issue here, but it is sometimes worth providing a summary of the individual changes in this PR. --> - Resume scanning after the last cached non-null row until enough candidates are available or the range ends. - Return `LimitEffect::Unknown` for IGNORE NULLS window UDF expressions, since non-null offsets cannot bound the number of required input rows. ## What is the testing strategy for this PR? <!-- We typically require tests for all PRs in order to: 1. Prevent the code from being accidentally broken by subsequent changes 2. Serve as another way to document the expected behavior of the code Briefly describe how this PR is tested, and point to the specific tests you added. For example: 'This new feature is covered by the `sqllogictest` cases added in `foo.slt`'. If this PR does not add tests, explain why. For example, if the change is already covered by existing tests, please mention it. You should also check the `codecov` bot reply on this PR to confirm the changed code is exercised. --> Added regression tests in `window.slt` for LEAD/LAG IGNORE NULLS across NULL gaps and batch boundaries, and in `window_limits.slt` for LIMIT pushdown correctness. ## Are there any user-facing changes? <!-- If there are user-facing changes then we may require documentation to be updated before approving the PR. If there are any breaking changes to public APIs, please add the `api change` label. --> Affected IGNORE NULLS window queries now return the correct results. No public API changes.
1 parent b172f73 commit 84acf49

4 files changed

Lines changed: 183 additions & 35 deletions

File tree

‎datafusion/functions-window/src/lead_lag.rs‎

Lines changed: 20 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -311,21 +311,24 @@ impl WindowUDFImpl for WindowShift {
311311
}
312312

313313
fn limit_effect(&self, args: &[Arc<dyn PhysicalExpr>]) -> LimitEffect {
314-
if self.kind == WindowShiftKind::Lag {
315-
return LimitEffect::None;
316-
}
317-
match args {
314+
let amount = match args {
318315
[_, expr, ..] => {
319316
let Some(lit) = expr.downcast_ref::<expressions::Literal>() else {
320317
return LimitEffect::Unknown;
321318
};
322319
let ScalarValue::Int64(Some(amount)) = lit.value() else {
323320
return LimitEffect::Unknown; // we should only get int64 from the parser
324321
};
325-
LimitEffect::Relative((*amount).max(0) as usize)
322+
*amount
326323
}
327-
[_] => LimitEffect::Relative(1), // default value
328-
_ => LimitEffect::Unknown, // invalid arguments
324+
[_] => 1, // default value
325+
_ => return LimitEffect::Unknown, // invalid arguments
326+
};
327+
let shift_offset = self.kind.shift_offset(Some(amount));
328+
if shift_offset < 0 {
329+
LimitEffect::Relative(offset_magnitude(shift_offset))
330+
} else {
331+
LimitEffect::None
329332
}
330333
}
331334
}
@@ -655,39 +658,22 @@ impl PartitionEvaluator for WindowShiftEvaluator {
655658
// Stores the necessary non-null entry number further than the current row.
656659
let non_null_row_count = offset_magnitude(self.shift_offset);
657660

658-
if self.non_null_offsets.is_empty() {
659-
// When empty, fill non_null offsets with the data further than the current row.
660-
let mut offset_val = 1;
661-
for idx in range.start + 1..range.end {
662-
if array.is_valid(idx) {
663-
self.non_null_offsets.push_back(offset_val);
664-
offset_val = 1;
665-
} else {
666-
offset_val += 1;
667-
}
668-
// It is enough to keep track of `non_null_row_count + 1` non-null offset.
669-
// further data is unnecessary for the result.
670-
if self.non_null_offsets.len() == non_null_row_count.saturating_add(1)
671-
{
672-
break;
673-
}
661+
// Resume after the last cached non-null row, even when the cache is
662+
// non-empty but does not yet contain enough rows for this offset.
663+
let mut total_offset: usize = self.non_null_offsets.iter().sum();
664+
for next_idx in range.start + total_offset + 1..range.end {
665+
if self.non_null_offsets.len() == non_null_row_count {
666+
break;
674667
}
675-
} else if range.end < len && array.is_valid(range.end) {
676-
// Update `non_null_offsets` with the new end data.
677-
if array.is_valid(range.end) {
678-
// When non-null, append a new offset.
679-
self.non_null_offsets.push_back(1);
680-
} else {
681-
// When null, increment offset count of the last entry
682-
let last_idx = self.non_null_offsets.len() - 1;
683-
self.non_null_offsets[last_idx] += 1;
668+
if array.is_valid(next_idx) {
669+
let next_offset = next_idx - range.start;
670+
self.non_null_offsets.push_back(next_offset - total_offset);
671+
total_offset = next_offset;
684672
}
685673
}
686674

687675
// Find the nonNULL row index that shifted by offset comparing to current row index
688676
idx = if self.non_null_offsets.len() >= non_null_row_count {
689-
let total_offset: usize =
690-
self.non_null_offsets.iter().take(non_null_row_count).sum();
691677
Some(range.start + total_offset)
692678
} else {
693679
None

‎datafusion/physical-plan/src/windows/mod.rs‎

Lines changed: 8 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -295,7 +295,14 @@ impl StandardWindowFunctionExpr for WindowUDFExpr {
295295
}
296296

297297
fn limit_effect(&self) -> LimitEffect {
298-
self.fun.inner().limit_effect(self.args.as_slice())
298+
match self.fun.inner().limit_effect(self.args.as_slice()) {
299+
// The function's offset counts non-null values, so it cannot bound
300+
// the number of input rows needed when NULLs are skipped.
301+
LimitEffect::Relative(_) | LimitEffect::Absolute(_) if self.ignore_nulls => {
302+
LimitEffect::Unknown
303+
}
304+
effect => effect,
305+
}
299306
}
300307
}
301308

‎datafusion/sqllogictest/test_files/window.slt‎

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4482,6 +4482,63 @@ NULL 19
44824482
statement ok
44834483
set datafusion.execution.batch_size = 100;
44844484

4485+
statement ok
4486+
CREATE TABLE shifts AS VALUES
4487+
(1, 10), (2, 20), (3, 30), (4, 40),
4488+
(5, NULL), (6, NULL), (7, 70), (8, 80), (9, NULL);
4489+
4490+
# A partially populated lookahead cache must scan past NULLs to find
4491+
# the requested non-null row. Negative offsets reverse the direction.
4492+
query IIIIII
4493+
SELECT column1, column2,
4494+
LEAD(column2, 2) IGNORE NULLS OVER w,
4495+
LAG(column2, -2, -1) IGNORE NULLS OVER w,
4496+
LAG(column2, 2) IGNORE NULLS OVER w,
4497+
LEAD(column2, -2) IGNORE NULLS OVER w
4498+
FROM shifts
4499+
WINDOW w AS (ORDER BY column1)
4500+
ORDER BY column1;
4501+
----
4502+
1 10 30 30 NULL NULL
4503+
2 20 40 40 NULL NULL
4504+
3 30 70 70 10 10
4505+
4 40 80 80 20 20
4506+
5 NULL 80 80 30 30
4507+
6 NULL 80 80 30 30
4508+
7 70 NULL -1 30 30
4509+
8 80 NULL -1 40 40
4510+
9 NULL NULL -1 70 70
4511+
4512+
# The result must be the same when input arrives in separate batches.
4513+
statement ok
4514+
SET datafusion.execution.batch_size = 1;
4515+
4516+
query IIIIII
4517+
SELECT column1, column2,
4518+
LEAD(column2, 2) IGNORE NULLS OVER w,
4519+
LAG(column2, -2, -1) IGNORE NULLS OVER w,
4520+
LAG(column2, 2) IGNORE NULLS OVER w,
4521+
LEAD(column2, -2) IGNORE NULLS OVER w
4522+
FROM shifts
4523+
WINDOW w AS (ORDER BY column1)
4524+
ORDER BY column1;
4525+
----
4526+
1 10 30 30 NULL NULL
4527+
2 20 40 40 NULL NULL
4528+
3 30 70 70 10 10
4529+
4 40 80 80 20 20
4530+
5 NULL 80 80 30 30
4531+
6 NULL 80 80 30 30
4532+
7 70 NULL -1 30 30
4533+
8 80 NULL -1 40 40
4534+
9 NULL NULL -1 70 70
4535+
4536+
statement ok
4537+
SET datafusion.execution.batch_size = 100;
4538+
4539+
statement ok
4540+
DROP TABLE shifts;
4541+
44854542
# Tests schema and data are in sync for mixed nulls and not nulls values for builtin window function
44864543
query T
44874544
select lag(a) over (order by a ASC NULLS FIRST) as x1

‎datafusion/sqllogictest/test_files/window_limits.slt‎

Lines changed: 98 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -112,6 +112,104 @@ physical_plan
112112
04)------SortExec: TopK(fetch=5), expr=[empno@0 ASC NULLS LAST], preserve_partitioning=[false]
113113
05)--------DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/testing/data/csv/aggregate_test_100_with_dates.csv]]}, projection=[empno], file_type=csv, has_header=true
114114

115+
# Non-null offsets cannot be used as physical row counts for LIMIT pushdown.
116+
statement ok
117+
SET datafusion.optimizer.enable_window_limits = false;
118+
119+
query III
120+
SELECT id,
121+
LEAD(v) IGNORE NULLS OVER w,
122+
LAG(v, -1, -1) IGNORE NULLS OVER w
123+
FROM (VALUES (1, 10), (2, NULL), (3, NULL), (4, 40)) AS t(id, v)
124+
WINDOW w AS (ORDER BY id ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)
125+
ORDER BY id
126+
LIMIT 1;
127+
----
128+
1 40 40
129+
130+
statement ok
131+
SET datafusion.optimizer.enable_window_limits = true;
132+
133+
query III
134+
SELECT id,
135+
LEAD(v) IGNORE NULLS OVER w,
136+
LAG(v, -1, -1) IGNORE NULLS OVER w
137+
FROM (VALUES (1, 10), (2, NULL), (3, NULL), (4, 40)) AS t(id, v)
138+
WINDOW w AS (ORDER BY id ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)
139+
ORDER BY id
140+
LIMIT 1;
141+
----
142+
1 40 40
143+
144+
# Negative-offset LAG must also block pushdown when no LEAD is present.
145+
query II
146+
SELECT id, LAG(v, -1) IGNORE NULLS OVER (
147+
ORDER BY id ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
148+
)
149+
FROM (VALUES (1, 10), (2, NULL), (3, NULL), (4, 40)) AS t(id, v)
150+
ORDER BY id
151+
LIMIT 1;
152+
----
153+
1 40
154+
155+
# Negative-offset LAG needs lookahead even without IGNORE NULLS.
156+
query II
157+
SELECT id, LAG(v, -1) OVER (
158+
ORDER BY id ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
159+
)
160+
FROM (VALUES (1, 10), (2, 20), (3, 30), (4, 40)) AS t(id, v)
161+
ORDER BY id
162+
LIMIT 1;
163+
----
164+
1 20
165+
166+
# Causal IGNORE NULLS functions should retain TopK below the window.
167+
query IIIIIII
168+
SELECT id,
169+
LAG(v) IGNORE NULLS OVER w,
170+
LEAD(v, -1) IGNORE NULLS OVER w,
171+
LEAD(v, 0) IGNORE NULLS OVER w,
172+
FIRST_VALUE(v) IGNORE NULLS OVER w,
173+
LAST_VALUE(v) IGNORE NULLS OVER w,
174+
NTH_VALUE(v, 2) IGNORE NULLS OVER w
175+
FROM (VALUES (1, 10), (2, NULL), (3, 30), (4, 40)) AS t(id, v)
176+
WINDOW w AS (ORDER BY id ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)
177+
ORDER BY id
178+
LIMIT 3;
179+
----
180+
1 NULL NULL 10 10 10 NULL
181+
2 10 10 NULL 10 10 NULL
182+
3 10 10 30 10 30 30
183+
184+
query TT
185+
EXPLAIN
186+
SELECT id,
187+
LAG(v) IGNORE NULLS OVER w,
188+
LEAD(v, -1) IGNORE NULLS OVER w,
189+
LEAD(v, 0) IGNORE NULLS OVER w,
190+
FIRST_VALUE(v) IGNORE NULLS OVER w,
191+
LAST_VALUE(v) IGNORE NULLS OVER w,
192+
NTH_VALUE(v, 2) IGNORE NULLS OVER w
193+
FROM (VALUES (1, 10), (2, NULL), (3, 30), (4, 40)) AS t(id, v)
194+
WINDOW w AS (ORDER BY id ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)
195+
ORDER BY id
196+
LIMIT 3;
197+
----
198+
logical_plan
199+
01)Sort: t.id ASC NULLS LAST, fetch=3
200+
02)--Projection: t.id, lag(t.v) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, lead(t.v,Int64(-1)) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, lead(t.v,Int64(0)) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, first_value(t.v) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, last_value(t.v) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, nth_value(t.v,Int64(2)) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
201+
03)----WindowAggr: windowExpr=[[lag(t.v)IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, lead(t.v, Int64(-1))IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, lead(t.v, Int64(0))IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, first_value(t.v)IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, last_value(t.v)IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, nth_value(t.v, Int64(2))IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW]]
202+
04)------SubqueryAlias: t
203+
05)--------Projection: column1 AS id, column2 AS v
204+
06)----------Values: (Int64(1), Int64(10)), (Int64(2), Int64(NULL)), (Int64(3), Int64(30)), (Int64(4), Int64(40))
205+
physical_plan
206+
01)ProjectionExec: expr=[id@0 as id, lag(t.v) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@2 as lag(t.v) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, lead(t.v,Int64(-1)) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@3 as lead(t.v,Int64(-1)) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, lead(t.v,Int64(0)) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@4 as lead(t.v,Int64(0)) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, first_value(t.v) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@5 as first_value(t.v) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, last_value(t.v) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@6 as last_value(t.v) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, nth_value(t.v,Int64(2)) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@7 as nth_value(t.v,Int64(2)) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW]
207+
02)--GlobalLimitExec: skip=0, fetch=3
208+
03)----BoundedWindowAggExec: wdw=[lag(t.v) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "lag(t.v) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": nullable Int64 }, frame: ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, lead(t.v,Int64(-1)) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "lead(t.v,Int64(-1)) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": nullable Int64 }, frame: ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, lead(t.v,Int64(0)) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "lead(t.v,Int64(0)) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": nullable Int64 }, frame: ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, first_value(t.v) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "first_value(t.v) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": nullable Int64 }, frame: ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, last_value(t.v) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "last_value(t.v) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": nullable Int64 }, frame: ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, nth_value(t.v,Int64(2)) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "nth_value(t.v,Int64(2)) IGNORE NULLS ORDER BY [t.id ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": nullable Int64 }, frame: ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
209+
04)------ProjectionExec: expr=[column1@0 as id, column2@1 as v]
210+
05)--------SortExec: TopK(fetch=3), expr=[column1@0 ASC NULLS LAST], preserve_partitioning=[false]
211+
06)----------DataSourceExec: partitions=1, partition_sizes=[1]
212+
115213
# Should use the max of leads
116214
statement ok
117215
set datafusion.optimizer.enable_window_limits = false;

0 commit comments

Comments
 (0)