Skip to content

Commit 85cdf20

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 c163461 commit 85cdf20

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
@@ -203,7 +203,11 @@ fn apply_limit(
203203
None => fetch,
204204
Some(existing) => cmp::min(existing, fetch),
205205
};
206-
Some(Transformed::complete(node.with_fetch(Some(fetch)).unwrap()))
206+
// Carry on past this sort rather than stopping. `ctx` was reset above, so it
207+
// now holds exactly what it held at the start of the traversal, which makes
208+
// walking the subtree below equivalent to running the rule on it afresh --
209+
// and that subtree may hold another independent limit over another window.
210+
Some(Transformed::yes(node.with_fetch(Some(fetch)).unwrap()))
207211
}
208212

209213
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
@@ -897,3 +897,119 @@ physical_plan
897897

898898
statement ok
899899
DROP TABLE huge_frame_t;
900+
901+
# Every window in a plan should get the limit pushed past it, not just the first
902+
# one. See https://github.com/apache/datafusion/issues/26659
903+
#
904+
# Both branches of this union have their own window and their own limit, so both
905+
# SortExecs should become a TopK. `rowsort` is required here: UnionExec yields
906+
# its branches in a nondeterministic order.
907+
statement ok
908+
set datafusion.optimizer.enable_window_limits = false;
909+
910+
query II rowsort
911+
SELECT * FROM (SELECT empno, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) s FROM employees ORDER BY empno LIMIT 2)
912+
UNION ALL
913+
SELECT * FROM (SELECT empno, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) s FROM employees ORDER BY empno LIMIT 3);
914+
----
915+
102 3276123488
916+
102 3276123488
917+
299 3304897863
918+
299 3304897863
919+
363 5170205535
920+
921+
statement ok
922+
set datafusion.optimizer.enable_window_limits = true;
923+
924+
query II rowsort
925+
SELECT * FROM (SELECT empno, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) s FROM employees ORDER BY empno LIMIT 2)
926+
UNION ALL
927+
SELECT * FROM (SELECT empno, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) s FROM employees ORDER BY empno LIMIT 3);
928+
----
929+
102 3276123488
930+
102 3276123488
931+
299 3304897863
932+
299 3304897863
933+
363 5170205535
934+
935+
query TT
936+
EXPLAIN
937+
SELECT * FROM (SELECT empno, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) s FROM employees ORDER BY empno LIMIT 2)
938+
UNION ALL
939+
SELECT * FROM (SELECT empno, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) s FROM employees ORDER BY empno LIMIT 3);
940+
----
941+
logical_plan
942+
01)Union
943+
02)--Sort: employees.empno ASC NULLS LAST, fetch=2
944+
03)----Projection: employees.empno, sum(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW AS s
945+
04)------WindowAggr: windowExpr=[[sum(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW]]
946+
05)--------TableScan: employees projection=[empno, salary]
947+
06)--Sort: employees.empno ASC NULLS LAST, fetch=3
948+
07)----Projection: employees.empno, sum(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW AS s
949+
08)------WindowAggr: windowExpr=[[sum(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW]]
950+
09)--------TableScan: employees projection=[empno, salary]
951+
physical_plan
952+
01)UnionExec
953+
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]
954+
03)----GlobalLimitExec: skip=0, fetch=2
955+
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]
956+
05)--------SortExec: TopK(fetch=2), expr=[empno@0 ASC NULLS LAST], preserve_partitioning=[false]
957+
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
958+
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]
959+
08)----GlobalLimitExec: skip=0, fetch=3
960+
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]
961+
10)--------SortExec: TopK(fetch=3), expr=[empno@0 ASC NULLS LAST], preserve_partitioning=[false]
962+
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
963+
964+
# A second, independent window+limit further down the same chain should get a
965+
# TopK too. Three things about this query are load bearing, so do not simplify
966+
# it: the two levels must order by different columns (otherwise EnforceSorting
967+
# drops the inner SortExec), the outer SELECT must reference `s1` (otherwise
968+
# projection pushdown removes the inner window), and both levels need their own
969+
# LIMIT.
970+
statement ok
971+
set datafusion.optimizer.enable_window_limits = false;
972+
973+
query IIII
974+
SELECT empno, salary, s1, sum(empno) OVER (ORDER BY salary ROWS UNBOUNDED PRECEDING) AS s2
975+
FROM (SELECT empno, salary, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) AS s1 FROM employees ORDER BY empno LIMIT 5)
976+
ORDER BY salary LIMIT 2;
977+
----
978+
299 28774375 3304897863 299
979+
417 557517119 5727722654 716
980+
981+
statement ok
982+
set datafusion.optimizer.enable_window_limits = true;
983+
984+
query IIII
985+
SELECT empno, salary, s1, sum(empno) OVER (ORDER BY salary ROWS UNBOUNDED PRECEDING) AS s2
986+
FROM (SELECT empno, salary, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) AS s1 FROM employees ORDER BY empno LIMIT 5)
987+
ORDER BY salary LIMIT 2;
988+
----
989+
299 28774375 3304897863 299
990+
417 557517119 5727722654 716
991+
992+
query TT
993+
EXPLAIN
994+
SELECT empno, salary, s1, sum(empno) OVER (ORDER BY salary ROWS UNBOUNDED PRECEDING) AS s2
995+
FROM (SELECT empno, salary, sum(salary) OVER (ORDER BY empno ROWS UNBOUNDED PRECEDING) AS s1 FROM employees ORDER BY empno LIMIT 5)
996+
ORDER BY salary LIMIT 2;
997+
----
998+
logical_plan
999+
01)Sort: employees.salary ASC NULLS LAST, fetch=2
1000+
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
1001+
03)----WindowAggr: windowExpr=[[sum(CAST(employees.empno AS Int64)) ORDER BY [employees.salary ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW]]
1002+
04)------Sort: employees.empno ASC NULLS LAST, fetch=5
1003+
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
1004+
06)----------WindowAggr: windowExpr=[[sum(employees.salary) ORDER BY [employees.empno ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW]]
1005+
07)------------TableScan: employees projection=[empno, salary]
1006+
physical_plan
1007+
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]
1008+
02)--GlobalLimitExec: skip=0, fetch=2
1009+
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]
1010+
04)------SortExec: TopK(fetch=2), expr=[salary@1 ASC NULLS LAST], preserve_partitioning=[false]
1011+
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]
1012+
06)----------GlobalLimitExec: skip=0, fetch=5
1013+
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]
1014+
08)--------------SortExec: TopK(fetch=5), expr=[empno@0 ASC NULLS LAST], preserve_partitioning=[false]
1015+
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)