Skip to content

Commit 32bd81f

Browse files
fix: preserve window inputs when replacing TopK sorts (apache#26719)
## Which issue does this PR close? Closes apache#26617. ## Rationale for this change With multiple execution partitions, replacing an outer TopK sort with an ordered merge can push its limit below a window that needs all input rows. The reproducer returns `count(*) OVER () = 1` instead of 3. ## What changes are included in this PR? - Only propagate fetch through operators that support limit pushdown. - Retain the original limit above the replacement plan when removing the sort. - Add SQL regressions for `LIMIT 1` and `LIMIT 1 OFFSET 1` with four target partitions. ## What is the testing strategy for this PR? The new cases in `window_limits.slt` expect `(3, 1)` and `(3, 2)`. Before the fix, they return `(1, 1)` and `(2, 2)`. ## Are there any user-facing changes? None other than user gets correct window results when an outer TopK sort is replaced with an ordered merge.
1 parent 8b88a86 commit 32bd81f

3 files changed

Lines changed: 101 additions & 2 deletions

File tree

‎datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/replace_with_order_preserving_variants.rs‎

Lines changed: 11 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,8 @@
88
99
use std::sync::Arc;
1010

11+
use super::sort_pushdown::can_push_fetch_through;
12+
use crate::row_bound::{RowBound, limit_node};
1113
use crate::utils::{
1214
is_coalesce_partitions, is_repartition, is_sort, is_sort_preserving_merge,
1315
};
@@ -97,6 +99,7 @@ pub fn plan_with_order_preserving_variants(
9799
sort_input.data = false;
98100
return Ok(sort_input);
99101
}
102+
let child_fetch = fetch.filter(|_| can_push_fetch_through(&sort_input.plan));
100103
sort_input.children = sort_input
101104
.children
102105
.into_iter()
@@ -107,7 +110,7 @@ pub fn plan_with_order_preserving_variants(
107110
node,
108111
is_spr_better,
109112
is_spm_better,
110-
fetch,
113+
child_fetch,
111114
)
112115
} else {
113116
Ok(node)
@@ -272,5 +275,12 @@ pub fn replace_with_order_preserving_variants(
272275
for child in alternate_plan.children.iter_mut() {
273276
child.data = false;
274277
}
278+
if let Some(fetch) = requirements.plan.fetch() {
279+
let plan = limit_node(
280+
Arc::clone(&alternate_plan.plan),
281+
RowBound::fetch(Some(fetch)),
282+
);
283+
alternate_plan = PlanContext::new(plan, false, vec![alternate_plan]);
284+
}
275285
Ok(Transformed::yes(alternate_plan))
276286
}

‎datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/sort_pushdown.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -132,7 +132,7 @@ fn min_fetch(f1: Option<usize>, f2: Option<usize>) -> Option<usize> {
132132
}
133133

134134
/// Returns whether a fetch on `plan` can move to its input.
135-
fn can_push_fetch_through(plan: &Arc<dyn ExecutionPlan>) -> bool {
135+
pub(crate) fn can_push_fetch_through(plan: &Arc<dyn ExecutionPlan>) -> bool {
136136
match plan.limit_behavior() {
137137
LimitBehavior::MoveToInput => true,
138138
LimitBehavior::Merge => plan.fetch().is_none(),

‎datafusion/sqllogictest/test_files/window_limits.slt‎

Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -898,6 +898,47 @@ physical_plan
898898
statement ok
899899
DROP TABLE huge_frame_t;
900900

901+
# Regression for #26617: count all rows before applying LIMIT.
902+
statement ok
903+
SET datafusion.execution.target_partitions = 4;
904+
905+
query II
906+
SELECT count(*) OVER () AS n,
907+
row_number() OVER (PARTITION BY length('x') ORDER BY a) AS r
908+
FROM (SELECT 1 AS a UNION ALL SELECT 2 UNION ALL SELECT 3)
909+
ORDER BY r LIMIT 1;
910+
----
911+
3 1
912+
913+
query II
914+
SELECT count(*) OVER () AS n,
915+
row_number() OVER (PARTITION BY length('x') ORDER BY a) AS r
916+
FROM (SELECT 1 AS a UNION ALL SELECT 2 UNION ALL SELECT 3)
917+
ORDER BY r LIMIT 1 OFFSET 1;
918+
----
919+
3 2
920+
921+
# When replacing the outer TopK is safe, LimitPushdown must absorb the
922+
# redundant GlobalLimitExec into SortPreservingMergeExec.
923+
query TT
924+
EXPLAIN
925+
SELECT depname, row_number() OVER (PARTITION BY depname ORDER BY empno) AS r
926+
FROM employees
927+
ORDER BY depname LIMIT 1;
928+
----
929+
logical_plan
930+
01)Sort: employees.depname ASC NULLS LAST, fetch=1
931+
02)--Projection: employees.depname, row_number() PARTITION BY [employees.depname] ORDER BY [employees.empno ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW AS r
932+
03)----WindowAggr: windowExpr=[[row_number() PARTITION BY [employees.depname] ORDER BY [employees.empno ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW]]
933+
04)------TableScan: employees projection=[depname, empno]
934+
physical_plan
935+
01)SortPreservingMergeExec: [depname@0 ASC NULLS LAST], fetch=1
936+
02)--ProjectionExec: expr=[depname@0 as depname, row_number() PARTITION BY [employees.depname] ORDER BY [employees.empno ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@2 as r]
937+
03)----BoundedWindowAggExec: wdw=[row_number() PARTITION BY [employees.depname] ORDER BY [employees.empno ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "row_number() PARTITION BY [employees.depname] ORDER BY [employees.empno ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": UInt64 }, frame: RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
938+
04)------SortExec: expr=[depname@0 ASC NULLS LAST, empno@1 ASC NULLS LAST], preserve_partitioning=[true]
939+
05)--------RepartitionExec: partitioning=Hash([depname@0], 4), input_partitions=1
940+
06)----------DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/testing/data/csv/aggregate_test_100_with_dates.csv]]}, projection=[depname, empno], file_type=csv, has_header=true
941+
901942
# Every window in a plan should get the limit pushed past it, not just the first
902943
# one. See https://github.com/apache/datafusion/issues/26659
903944
#
@@ -1482,3 +1523,51 @@ physical_plan
14821523
07)------------RepartitionExec: partitioning=Hash([depname@0], 4), input_partitions=1, maintains_sort_order=true
14831524
08)--------------SortExec: TopK(fetch=6), expr=[depname@0 ASC NULLS LAST, empno@1 ASC NULLS LAST], preserve_partitioning=[true]
14841525
09)----------------DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/testing/data/csv/aggregate_test_100_with_dates.csv]]}, projection=[depname, empno, salary], file_type=csv, has_header=true
1526+
1527+
# A fetch above an OFFSET must not truncate the OFFSET input.
1528+
statement ok
1529+
SET datafusion.execution.target_partitions = 4;
1530+
1531+
query I
1532+
COPY (SELECT * FROM (VALUES (1), (3), (5), (7)) AS t(a))
1533+
TO 'test_files/scratch/window_limits/sorted_offset/first.csv'
1534+
STORED AS CSV OPTIONS ('format.has_header' 'false');
1535+
----
1536+
4
1537+
1538+
query I
1539+
COPY (SELECT * FROM (VALUES (2), (4), (6), (8)) AS t(a))
1540+
TO 'test_files/scratch/window_limits/sorted_offset/second.csv'
1541+
STORED AS CSV OPTIONS ('format.has_header' 'false');
1542+
----
1543+
4
1544+
1545+
statement ok
1546+
CREATE EXTERNAL TABLE sorted_offset_t (a INT NOT NULL)
1547+
STORED AS CSV
1548+
WITH ORDER (a ASC)
1549+
LOCATION 'test_files/scratch/window_limits/sorted_offset/'
1550+
OPTIONS ('format.has_header' 'false');
1551+
1552+
query I
1553+
SELECT count(*) FROM (SELECT * FROM (SELECT a FROM sorted_offset_t LIMIT 3 OFFSET 2) ORDER BY a LIMIT 1);
1554+
----
1555+
1
1556+
1557+
query TT
1558+
EXPLAIN SELECT * FROM (SELECT a FROM sorted_offset_t LIMIT 3 OFFSET 2) ORDER BY a LIMIT 1;
1559+
----
1560+
logical_plan
1561+
01)Sort: sorted_offset_t.a ASC NULLS LAST, fetch=1
1562+
02)--Limit: skip=0, fetch=3
1563+
03)----TableScan: sorted_offset_t projection=[a], fetch=3, skip=2
1564+
physical_plan
1565+
01)GlobalLimitExec: skip=2, fetch=1
1566+
02)--SortPreservingMergeExec: [a@0 ASC NULLS LAST], fetch=3
1567+
03)----DataSourceExec: file_groups={4 groups: [[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/window_limits/sorted_offset/first.csv:0..4], [WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/window_limits/sorted_offset/second.csv:0..4], [WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/window_limits/sorted_offset/first.csv:4..8], [WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/window_limits/sorted_offset/second.csv:4..8]]}, projection=[a], limit=3, output_ordering=[a@0 ASC NULLS LAST], file_type=csv, has_header=false
1568+
1569+
# Also cover the OFFSET-only shape from #26690.
1570+
query I
1571+
SELECT count(*) FROM (SELECT * FROM (SELECT a FROM sorted_offset_t OFFSET 2) ORDER BY a LIMIT 3);
1572+
----
1573+
3

0 commit comments

Comments
 (0)