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 6e4279c
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` reset 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
@@ -862,3 +862,119 @@ physical_plan
862
862
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]
# Every window in a plan should get the limit pushed past it, not just the first
867
+
# one. See https://github.com/apache/datafusion/issues/26659
868
+
#
869
+
# Both branches of this union have their own window and their own limit, so both
870
+
# SortExecs should become a TopK. `rowsort` is required here: UnionExec yields
871
+
# its branches in a nondeterministic order.
872
+
statement ok
873
+
set datafusion.optimizer.enable_window_limits = false;
874
+
875
+
query II rowsort
876
+
SELECT * FROM (SELECT empno, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) s FROM employees ORDER BY empno LIMIT 2)
877
+
UNION ALL
878
+
SELECT * FROM (SELECT empno, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) s FROM employees ORDER BY empno LIMIT 3);
879
+
----
880
+
102 3276123488
881
+
102 3276123488
882
+
299 3304897863
883
+
299 3304897863
884
+
363 5170205535
885
+
886
+
statement ok
887
+
set datafusion.optimizer.enable_window_limits = true;
888
+
889
+
query II rowsort
890
+
SELECT * FROM (SELECT empno, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) s FROM employees ORDER BY empno LIMIT 2)
891
+
UNION ALL
892
+
SELECT * FROM (SELECT empno, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) s FROM employees ORDER BY empno LIMIT 3);
893
+
----
894
+
102 3276123488
895
+
102 3276123488
896
+
299 3304897863
897
+
299 3304897863
898
+
363 5170205535
899
+
900
+
query TT
901
+
EXPLAIN
902
+
SELECT * FROM (SELECT empno, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) s FROM employees ORDER BY empno LIMIT 2)
903
+
UNION ALL
904
+
SELECT * FROM (SELECT empno, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) s FROM employees ORDER BY empno LIMIT 3);
905
+
----
906
+
logical_plan
907
+
01)Union
908
+
02)--Sort: employees.empno ASC NULLS LAST, fetch=2
909
+
03)----Projection: employees.empno, sum(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW AS s
910
+
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
913
+
07)----Projection: employees.empno, sum(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW AS s
914
+
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]
919
+
03)----GlobalLimitExec: skip=0, fetch=2
920
+
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]
924
+
08)----GlobalLimitExec: skip=0, fetch=3
925
+
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
930
+
# TopK too. Three things about this query are load bearing, so do not simplify
931
+
# it: the two levels must order by different columns (otherwise EnforceSorting
932
+
# drops the inner SortExec), the outer SELECT must reference `s1` (otherwise
933
+
# projection pushdown removes the inner window), and both levels need their own
934
+
# LIMIT.
935
+
statement ok
936
+
set datafusion.optimizer.enable_window_limits = false;
937
+
938
+
query IIII
939
+
SELECT empno, salary, s1, sum(empno) OVER (ORDER BY salary ROWS UNBOUNDED PRECEDING) AS s2
940
+
FROM (SELECT empno, salary, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) AS s1 FROM employees ORDER BY empno LIMIT 5)
941
+
ORDER BY salary LIMIT 2;
942
+
----
943
+
299 28774375 3304897863 299
944
+
417 557517119 5727722654 716
945
+
946
+
statement ok
947
+
set datafusion.optimizer.enable_window_limits = true;
948
+
949
+
query IIII
950
+
SELECT empno, salary, s1, sum(empno) OVER (ORDER BY salary ROWS UNBOUNDED PRECEDING) AS s2
951
+
FROM (SELECT empno, salary, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) AS s1 FROM employees ORDER BY empno LIMIT 5)
952
+
ORDER BY salary LIMIT 2;
953
+
----
954
+
299 28774375 3304897863 299
955
+
417 557517119 5727722654 716
956
+
957
+
query TT
958
+
EXPLAIN
959
+
SELECT empno, salary, s1, sum(empno) OVER (ORDER BY salary ROWS UNBOUNDED PRECEDING) AS s2
960
+
FROM (SELECT empno, salary, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) AS s1 FROM employees ORDER BY empno LIMIT 5)
961
+
ORDER BY salary LIMIT 2;
962
+
----
963
+
logical_plan
964
+
01)Sort: employees.salary ASC NULLS LAST, fetch=2
965
+
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
966
+
03)----WindowAggr: windowExpr=[[sum(CAST(employees.empno AS Int64)) ORDER BY [employees.salary ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW]]
967
+
04)------Sort: employees.empno ASC NULLS LAST, fetch=5
968
+
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
969
+
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]
973
+
02)--GlobalLimitExec: skip=0, fetch=2
974
+
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]
977
+
06)----------GlobalLimitExec: skip=0, fetch=5
978
+
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