You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Commit eebba16
Browse filesBrowse the repository at this point in the historyBrowse files
fix: add stacked windows' lookaheads instead of taking the max
`grow_limit` folded each window's lookahead into the chain's with
`max_lookahead`, but a window reads ahead of every row the windows above it
need, so the lookaheads of stacked windows add. Taking the max leaves the sort
below short of the rows the inner window needs, and the last rows of the
result are computed over a truncated frame. Expressions within one window do
share a lookahead, and `WindowLookahead` has already taken the maximum over
those.
`window_limits.slt` gets a case for each of the two shapes this reaches.
SELECT empno, sum(s1) OVER (ORDER BY empno ROWS BETWEEN CURRENT ROW AND 1 FOLLOWING) AS s2
FROM (SELECT empno, sum(salary) OVER (ORDER BY empno ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING) AS s1 FROM employees)
ORDER BY empno LIMIT 3;
Two windows on one chain above a single sort. The sort needs 3 + 1 + 2 rows
and got 3 + max(1, 2), so the third row's `s2` came back 11103612124 instead
of 15119054465. `main` gets this shape wrong as well: its early stop kept the
walk out of the subtree below a sort it had already given a fetch to, never out
of a second window on the same chain.
The other shape puts an `ORDER BY ... LIMIT` between the two levels, so the
outer limit is spent on a sort and the walk starts a new chain at the inner
limit. That one is reachable only once applying a fetch stops ending the walk,
which is `fix: push a limit past every window in a plan, not just the first`
in this series. @jayzhan211 found it in review; the fix here is their patch.
Five `EXPLAIN`s in `window.slt` raise their fetch by 1 to 5 rows. Adding is a
safe upper bound but an over-estimate when the outer window does not read the
inner window's output, and all five are that shape: both windows in each of
them read `c9`. Telling the two apart needs the columns each window reads
traced through the projections between them, which is a separate change.
Co-Authored-By: Claude Opus 5 <[email protected]>
Copy file name to clipboardExpand all lines: datafusion/sqllogictest/test_files/window.slt
+5-5Lines changed: 5 additions & 5 deletions
Original file line number
Diff line number
Diff line change
@@ -1331,7 +1331,7 @@ physical_plan
1331
1331
02)--GlobalLimitExec: skip=0, fetch=5
1332
1332
03)----BoundedWindowAggExec: wdw=[sum(aggregate_test_100.c9) ORDER BY [aggregate_test_100.c9 ASC NULLS LAST] ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING: Field { "sum(aggregate_test_100.c9) ORDER BY [aggregate_test_100.c9 ASC NULLS LAST] ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING": nullable UInt64 }, frame: ROWS BETWEEN 5 PRECEDING AND 1 FOLLOWING], mode=[Sorted]
1333
1333
04)------BoundedWindowAggExec: wdw=[sum(aggregate_test_100.c9) ORDER BY [aggregate_test_100.c9 DESC NULLS FIRST] ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING: Field { "sum(aggregate_test_100.c9) ORDER BY [aggregate_test_100.c9 DESC NULLS FIRST] ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING": nullable UInt64 }, frame: ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING], mode=[Sorted]
03)----BoundedWindowAggExec: wdw=[sum(aggregate_test_100.c9) ORDER BY [aggregate_test_100.c9 ASC NULLS LAST] ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING: Field { "sum(aggregate_test_100.c9) ORDER BY [aggregate_test_100.c9 ASC NULLS LAST] ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING": nullable UInt64 }, frame: ROWS BETWEEN 5 PRECEDING AND 1 FOLLOWING], mode=[Sorted]
1376
1376
04)------BoundedWindowAggExec: wdw=[sum(aggregate_test_100.c9) ORDER BY [aggregate_test_100.c9 DESC NULLS FIRST] ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING: Field { "sum(aggregate_test_100.c9) ORDER BY [aggregate_test_100.c9 DESC NULLS FIRST] ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING": nullable UInt64 }, frame: ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING], mode=[Sorted]
# ensure limit pushdown can handle bigger preceding instead of following
@@ -1434,7 +1434,7 @@ physical_plan
1434
1434
02)--GlobalLimitExec: skip=5, fetch=5
1435
1435
03)----BoundedWindowAggExec: wdw=[sum(aggregate_test_100.c9) ORDER BY [aggregate_test_100.c9 ASC NULLS LAST] ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING: Field { "sum(aggregate_test_100.c9) ORDER BY [aggregate_test_100.c9 ASC NULLS LAST] ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING": nullable UInt64 }, frame: ROWS BETWEEN 5 PRECEDING AND 1 FOLLOWING], mode=[Sorted]
1436
1436
04)------BoundedWindowAggExec: wdw=[sum(aggregate_test_100.c9) ORDER BY [aggregate_test_100.c9 DESC NULLS FIRST] ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING: Field { "sum(aggregate_test_100.c9) ORDER BY [aggregate_test_100.c9 DESC NULLS FIRST] ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING": nullable UInt64 }, frame: ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING], mode=[Sorted]
03)----BoundedWindowAggExec: wdw=[sum(aggregate_test_100.c9) PARTITION BY [aggregate_test_100.c1] ORDER BY [aggregate_test_100.c9 DESC NULLS FIRST] ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING: Field { "sum(aggregate_test_100.c9) PARTITION BY [aggregate_test_100.c1] ORDER BY [aggregate_test_100.c9 DESC NULLS FIRST] ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING": nullable UInt64 }, frame: ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING], mode=[Sorted]
1731
1731
04)------BoundedWindowAggExec: wdw=[sum(aggregate_test_100.c9) ORDER BY [aggregate_test_100.c1 ASC NULLS LAST, aggregate_test_100.c9 DESC NULLS FIRST] ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING: Field { "sum(aggregate_test_100.c9) ORDER BY [aggregate_test_100.c1 ASC NULLS LAST, aggregate_test_100.c9 DESC NULLS FIRST] ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING": nullable UInt64 }, frame: ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING], mode=[Sorted]
1732
-
05)--------SortExec: TopK(fetch=10), expr=[c1@0 ASC NULLS LAST, c9@1 DESC], preserve_partitioning=[false]
1732
+
05)--------SortExec: TopK(fetch=15), expr=[c1@0 ASC NULLS LAST, c9@1 DESC], preserve_partitioning=[false]
03)----BoundedWindowAggExec: wdw=[sum(aggregate_test_100.c9) PARTITION BY [aggregate_test_100.c1] ORDER BY [aggregate_test_100.c9 ASC NULLS LAST] ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING: Field { "sum(aggregate_test_100.c9) PARTITION BY [aggregate_test_100.c1] ORDER BY [aggregate_test_100.c9 ASC NULLS LAST] ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING": nullable UInt64 }, frame: ROWS BETWEEN 5 PRECEDING AND 1 FOLLOWING], mode=[Sorted]
1775
1775
04)------BoundedWindowAggExec: wdw=[sum(aggregate_test_100.c9) PARTITION BY [aggregate_test_100.c1] ORDER BY [aggregate_test_100.c9 DESC NULLS FIRST] ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING: Field { "sum(aggregate_test_100.c9) PARTITION BY [aggregate_test_100.c1] ORDER BY [aggregate_test_100.c9 DESC NULLS FIRST] ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING": nullable UInt64 }, frame: ROWS BETWEEN 1 PRECEDING AND 5 FOLLOWING], mode=[Sorted]
1776
-
05)--------SortExec: TopK(fetch=10), expr=[c1@0 ASC NULLS LAST, c9@1 DESC], preserve_partitioning=[false]
1776
+
05)--------SortExec: TopK(fetch=11), expr=[c1@0 ASC NULLS LAST, c9@1 DESC], preserve_partitioning=[false]
Copy file name to clipboardExpand all lines: datafusion/sqllogictest/test_files/window_limits.slt
+130Lines changed: 130 additions & 0 deletions
Original file line number
Diff line number
Diff line change
@@ -1178,3 +1178,133 @@ physical_plan
1178
1178
06)----------BoundedWindowAggExec: wdw=[sum(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "sum(employees.salary) 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]
# Stacked windows add their lookaheads, they do not take the max. An outer window
1183
+
# reads the inner window's output column, so every row the outer window reads
1184
+
# ahead is a row the inner window must have computed correctly -- which needs the
1185
+
# inner window's own lookahead on top. Taking the max leaves the inner sort a row
1186
+
# short and the last row of the result is computed over a truncated frame.
1187
+
#
1188
+
# The outer `LIMIT 3` here is spent on the SortExec that orders by `salary`, and
1189
+
# the walk then starts a new chain at the inner `LIMIT 3`. That makes this shape
1190
+
# reachable only once applying a fetch stops ending the walk, which is the first
1191
+
# commit in this PR. Three properties are load-bearing: `s2` must read `s1`, or
1192
+
# the max is enough and the case does not fail; the two frames must end at
1193
+
# different offsets (1 and 2), or the max and the sum agree; and the outer
1194
+
# window's frame must end at the current row so it adds no lookahead of its own.
1195
+
1196
+
statement ok
1197
+
set datafusion.optimizer.enable_window_limits = false;
1198
+
1199
+
query IIII
1200
+
SELECT empno, salary, s2, sum(empno) OVER (ORDER BY salary ROWS UNBOUNDED PRECEDING) AS s3
1201
+
FROM (
1202
+
SELECT empno, salary, sum(s1) OVER (ORDER BY empno ROWS BETWEEN CURRENT ROW AND 1 FOLLOWING) AS s2
1203
+
FROM (SELECT empno, salary, sum(salary) OVER (ORDER BY empno ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING) AS s1 FROM employees)
1204
+
ORDER BY empno LIMIT 3
1205
+
)
1206
+
ORDER BY salary LIMIT 3;
1207
+
----
1208
+
299 28774375 8936059064 299
1209
+
363 1865307672 15119054465 662
1210
+
102 3276123488 7621804701 764
1211
+
1212
+
statement ok
1213
+
set datafusion.optimizer.enable_window_limits = true;
1214
+
1215
+
query IIII
1216
+
SELECT empno, salary, s2, sum(empno) OVER (ORDER BY salary ROWS UNBOUNDED PRECEDING) AS s3
1217
+
FROM (
1218
+
SELECT empno, salary, sum(s1) OVER (ORDER BY empno ROWS BETWEEN CURRENT ROW AND 1 FOLLOWING) AS s2
1219
+
FROM (SELECT empno, salary, sum(salary) OVER (ORDER BY empno ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING) AS s1 FROM employees)
1220
+
ORDER BY empno LIMIT 3
1221
+
)
1222
+
ORDER BY salary LIMIT 3;
1223
+
----
1224
+
299 28774375 8936059064 299
1225
+
363 1865307672 15119054465 662
1226
+
102 3276123488 7621804701 764
1227
+
1228
+
query TT
1229
+
EXPLAIN
1230
+
SELECT empno, salary, s2, sum(empno) OVER (ORDER BY salary ROWS UNBOUNDED PRECEDING) AS s3
1231
+
FROM (
1232
+
SELECT empno, salary, sum(s1) OVER (ORDER BY empno ROWS BETWEEN CURRENT ROW AND 1 FOLLOWING) AS s2
1233
+
FROM (SELECT empno, salary, sum(salary) OVER (ORDER BY empno ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING) AS s1 FROM employees)
1234
+
ORDER BY empno LIMIT 3
1235
+
)
1236
+
ORDER BY salary LIMIT 3;
1237
+
----
1238
+
logical_plan
1239
+
01)Sort: employees.salary ASC NULLS LAST, fetch=3
1240
+
02)--Projection: employees.empno, employees.salary, s2, sum(employees.empno) ORDER BY [employees.salary ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW AS s3
1241
+
03)----WindowAggr: windowExpr=[[sum(CAST(employees.empno AS Int64)) ORDER BY [employees.salary ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW]]
1242
+
04)------Sort: employees.empno ASC NULLS LAST, fetch=3
1243
+
05)--------Projection: employees.empno, employees.salary, sum(s1) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN CURRENT ROW AND 1 FOLLOWING AS s2
1244
+
06)----------WindowAggr: windowExpr=[[sum(s1) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN CURRENT ROW AND 1 FOLLOWING]]
1245
+
07)------------Projection: employees.empno, employees.salary, sum(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING AS s1
1246
+
08)--------------WindowAggr: windowExpr=[[sum(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING]]
01)ProjectionExec: expr=[empno@0 as empno, salary@1 as salary, s2@2 as s2, sum(employees.empno) ORDER BY [employees.salary ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@3 as s3]
1250
+
02)--GlobalLimitExec: skip=0, fetch=3
1251
+
03)----BoundedWindowAggExec: wdw=[sum(employees.empno) ORDER BY [employees.salary ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "sum(employees.empno) ORDER BY [employees.salary ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": nullable Int64 }, frame: ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
05)--------ProjectionExec: expr=[empno@0 as empno, salary@1 as salary, sum(s1) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN CURRENT ROW AND 1 FOLLOWING@3 as s2]
1254
+
06)----------GlobalLimitExec: skip=0, fetch=3
1255
+
07)------------BoundedWindowAggExec: wdw=[sum(s1) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN CURRENT ROW AND 1 FOLLOWING: Field { "sum(s1) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN CURRENT ROW AND 1 FOLLOWING": nullable UInt64 }, frame: ROWS BETWEEN CURRENT ROW AND 1 FOLLOWING], mode=[Sorted]
1256
+
08)--------------ProjectionExec: expr=[empno@0 as empno, salary@1 as salary, sum(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING@2 as s1]
1257
+
09)----------------BoundedWindowAggExec: wdw=[sum(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING: Field { "sum(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING": nullable UInt64 }, frame: ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING], mode=[Sorted]
01)ProjectionExec: expr=[empno@0 as empno, sum(s1) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN CURRENT ROW AND 1 FOLLOWING@2 as s2]
1305
+
02)--GlobalLimitExec: skip=0, fetch=3
1306
+
03)----BoundedWindowAggExec: wdw=[sum(s1) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN CURRENT ROW AND 1 FOLLOWING: Field { "sum(s1) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN CURRENT ROW AND 1 FOLLOWING": nullable UInt64 }, frame: ROWS BETWEEN CURRENT ROW AND 1 FOLLOWING], mode=[Sorted]
1307
+
04)------ProjectionExec: expr=[empno@0 as empno, sum(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING@2 as s1]
1308
+
05)--------BoundedWindowAggExec: wdw=[sum(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING: Field { "sum(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING": nullable UInt64 }, frame: ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING], mode=[Sorted]
0 commit comments