Skip to content

Commit e330b6b

Browse files
cool9850311claude
andcommitted
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. Closes apache#26659 Co-Authored-By: Claude Opus 5 <[email protected]>
1 parent 635e518 commit e330b6b

2 files changed

Lines changed: 121 additions & 1 deletion

File tree

‎datafusion/physical-optimizer/src/limit_pushdown_past_window.rs‎

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -208,7 +208,11 @@ fn apply_limit(
208208
None => fetch + lookahead,
209209
Some(existing) => cmp::min(existing, fetch + lookahead),
210210
};
211-
Some(Transformed::complete(node.with_fetch(Some(fetch)).unwrap()))
211+
// Carry on past this sort rather than stopping. `ctx` was reset above, so it
212+
// now holds exactly what it held at the start of the traversal, which makes
213+
// walking the subtree below equivalent to running the rule on it afresh --
214+
// and that subtree may hold another independent limit over another window.
215+
Some(Transformed::yes(node.with_fetch(Some(fetch)).unwrap()))
212216
}
213217

214218
fn get_limit(node: &Arc<dyn ExecutionPlan>, ctx: &mut TraverseState) -> bool {

‎datafusion/sqllogictest/test_files/window_limits.slt‎

Lines changed: 116 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -862,3 +862,119 @@ physical_plan
862862
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]
863863
04)------SortExec: TopK(fetch=5), expr=[empno@0 ASC NULLS LAST], preserve_partitioning=[false]
864864
05)--------DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/testing/data/csv/aggregate_test_100_with_dates.csv]]}, projection=[empno, salary], file_type=csv, has_header=true
865+
866+
# 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]]
911+
05)--------TableScan: employees projection=[empno, salary]
912+
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]]
915+
09)--------TableScan: employees projection=[empno, salary]
916+
physical_plan
917+
01)UnionExec
918+
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]
921+
05)--------SortExec: TopK(fetch=2), expr=[empno@0 ASC NULLS LAST], preserve_partitioning=[false]
922+
06)----------DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/testing/data/csv/aggregate_test_100_with_dates.csv]]}, projection=[empno, salary], file_type=csv, has_header=true
923+
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]
926+
10)--------SortExec: TopK(fetch=3), expr=[empno@0 ASC NULLS LAST], preserve_partitioning=[false]
927+
11)----------DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/testing/data/csv/aggregate_test_100_with_dates.csv]]}, projection=[empno, salary], file_type=csv, has_header=true
928+
929+
# 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]]
970+
07)------------TableScan: employees projection=[empno, salary]
971+
physical_plan
972+
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]
975+
04)------SortExec: TopK(fetch=2), expr=[salary@1 ASC NULLS LAST], preserve_partitioning=[false]
976+
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]
979+
08)--------------SortExec: TopK(fetch=5), expr=[empno@0 ASC NULLS LAST], preserve_partitioning=[false]
980+
09)----------------DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/testing/data/csv/aggregate_test_100_with_dates.csv]]}, projection=[empno, salary], file_type=csv, has_header=true

0 commit comments

Comments
 (0)