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 6ef0918
Browse filesBrowse the repository at this point in the historyBrowse files
fix: push a limit past every window in a plan, not just the first
`apply_limit` returned `Transformed::complete`, whose `TreeNodeRecursion`
is `Stop`. That ends the whole `transform_down`, not the walk below the
sort that just got its fetch, so only the first window a plan has was
ever optimized. Every later one -- a second `UNION ALL` branch, or a
second window further down the same chain -- kept a full sort.
Return `Transformed::yes` instead. The previous commit made `apply_limit`
take the traversal state, so by this point `ctx` holds what it held at
the start of the traversal and continuing into the subtree is equivalent
to running the rule on it afresh.
`TreeNodeRecursion::Jump` was suggested on the issue, and it does fix the
union case by pruning only the sort's subtree. It is not enough for the
nested case, though, because there the second limit and window sit
*inside* the subtree that `Jump` prunes. The second sqllogictest case
added here covers exactly that difference.
Closesapache#26659
Co-Authored-By: Claude Opus 5 <[email protected]>
Copy file name to clipboardExpand all lines: datafusion/sqllogictest/test_files/window_limits.slt
+116Lines changed: 116 additions & 0 deletions
Original file line number
Diff line number
Diff line change
@@ -967,3 +967,119 @@ physical_plan
967
967
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]
# Every window in a plan should get the limit pushed past it, not just the first
972
+
# one. See https://github.com/apache/datafusion/issues/26659
973
+
#
974
+
# Both branches of this union have their own window and their own limit, so both
975
+
# SortExecs should become a TopK. `rowsort` is required here: UnionExec yields
976
+
# its branches in a nondeterministic order.
977
+
statement ok
978
+
set datafusion.optimizer.enable_window_limits = false;
979
+
980
+
query II rowsort
981
+
SELECT * FROM (SELECT empno, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) s FROM employees ORDER BY empno LIMIT 2)
982
+
UNION ALL
983
+
SELECT * FROM (SELECT empno, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) s FROM employees ORDER BY empno LIMIT 3);
984
+
----
985
+
102 3276123488
986
+
102 3276123488
987
+
299 3304897863
988
+
299 3304897863
989
+
363 5170205535
990
+
991
+
statement ok
992
+
set datafusion.optimizer.enable_window_limits = true;
993
+
994
+
query II rowsort
995
+
SELECT * FROM (SELECT empno, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) s FROM employees ORDER BY empno LIMIT 2)
996
+
UNION ALL
997
+
SELECT * FROM (SELECT empno, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) s FROM employees ORDER BY empno LIMIT 3);
998
+
----
999
+
102 3276123488
1000
+
102 3276123488
1001
+
299 3304897863
1002
+
299 3304897863
1003
+
363 5170205535
1004
+
1005
+
query TT
1006
+
EXPLAIN
1007
+
SELECT * FROM (SELECT empno, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) s FROM employees ORDER BY empno LIMIT 2)
1008
+
UNION ALL
1009
+
SELECT * FROM (SELECT empno, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) s FROM employees ORDER BY empno LIMIT 3);
1010
+
----
1011
+
logical_plan
1012
+
01)Union
1013
+
02)--Sort: employees.empno ASC NULLS LAST, fetch=2
1014
+
03)----Projection: employees.empno, sum(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW AS s
1015
+
04)------WindowAggr: windowExpr=[[sum(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW]]
06)--Sort: employees.empno ASC NULLS LAST, fetch=3
1018
+
07)----Projection: employees.empno, sum(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW AS s
1019
+
08)------WindowAggr: windowExpr=[[sum(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW]]
02)--ProjectionExec: expr=[empno@0 as empno, sum(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@2 as s]
1024
+
03)----GlobalLimitExec: skip=0, fetch=2
1025
+
04)------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]
07)--ProjectionExec: expr=[empno@0 as empno, sum(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@2 as s]
1029
+
08)----GlobalLimitExec: skip=0, fetch=3
1030
+
09)------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]
# A second, independent window+limit further down the same chain should get a
1035
+
# TopK too. Three things about this query are load bearing, so do not simplify
1036
+
# it: the two levels must order by different columns (otherwise EnforceSorting
1037
+
# drops the inner SortExec), the outer SELECT must reference `s1` (otherwise
1038
+
# projection pushdown removes the inner window), and both levels need their own
1039
+
# LIMIT.
1040
+
statement ok
1041
+
set datafusion.optimizer.enable_window_limits = false;
1042
+
1043
+
query IIII
1044
+
SELECT empno, salary, s1, sum(empno) OVER (ORDER BY salary ROWS UNBOUNDED PRECEDING) AS s2
1045
+
FROM (SELECT empno, salary, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) AS s1 FROM employees ORDER BY empno LIMIT 5)
1046
+
ORDER BY salary LIMIT 2;
1047
+
----
1048
+
299 28774375 3304897863 299
1049
+
417 557517119 5727722654 716
1050
+
1051
+
statement ok
1052
+
set datafusion.optimizer.enable_window_limits = true;
1053
+
1054
+
query IIII
1055
+
SELECT empno, salary, s1, sum(empno) OVER (ORDER BY salary ROWS UNBOUNDED PRECEDING) AS s2
1056
+
FROM (SELECT empno, salary, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) AS s1 FROM employees ORDER BY empno LIMIT 5)
1057
+
ORDER BY salary LIMIT 2;
1058
+
----
1059
+
299 28774375 3304897863 299
1060
+
417 557517119 5727722654 716
1061
+
1062
+
query TT
1063
+
EXPLAIN
1064
+
SELECT empno, salary, s1, sum(empno) OVER (ORDER BY salary ROWS UNBOUNDED PRECEDING) AS s2
1065
+
FROM (SELECT empno, salary, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) AS s1 FROM employees ORDER BY empno LIMIT 5)
1066
+
ORDER BY salary LIMIT 2;
1067
+
----
1068
+
logical_plan
1069
+
01)Sort: employees.salary ASC NULLS LAST, fetch=2
1070
+
02)--Projection: employees.empno, employees.salary, s1, sum(employees.empno) ORDER BY [employees.salary ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW AS s2
1071
+
03)----WindowAggr: windowExpr=[[sum(CAST(employees.empno AS Int64)) ORDER BY [employees.salary ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW]]
1072
+
04)------Sort: employees.empno ASC NULLS LAST, fetch=5
1073
+
05)--------Projection: employees.empno, employees.salary, sum(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW AS s1
1074
+
06)----------WindowAggr: windowExpr=[[sum(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW]]
01)ProjectionExec: expr=[empno@0 as empno, salary@1 as salary, s1@2 as s1, sum(employees.empno) ORDER BY [employees.salary ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@3 as s2]
1078
+
02)--GlobalLimitExec: skip=0, fetch=2
1079
+
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(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@2 as s1]
1082
+
06)----------GlobalLimitExec: skip=0, fetch=5
1083
+
07)------------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]
0 commit comments