Skip to content

Commit 7e102d7

Browse files
authored
fix: Avoid pushing down sort under limits (#25408)
## Which issue does this PR close? - Closes #25378. ## Rationale for this change Currently, `ORDER BY` on top of `LIMIT/OFFSET` subquery is currently planned as a TopK sort below the limit operator, which has to consume the whole input. ## What changes are included in this PR? Keep a sort above `GlobalLimitExec/LocalLimitExec`, unless the limit is directly above a SortExec whose ordering the pushed sort refines. Also stop pushing a sort through fetch-carrying operators that have no output ordering. ## What is the testing strategy for this PR? Additional SLT tests in `limit.slt` and unit tests checking various plan shapes and inputs. ## Are there any user-facing changes? Plans for `ORDER BY` over a `LIMIT` / `OFFSET` subquery change: the sort stays above the limit, so the input can stop early and the limit keeps the first rows it sees rather than the smallest ones. No API changes. --------- Signed-off-by: Adam Gutglick <[email protected]>
1 parent 28a4a60 commit 7e102d7

3 files changed

Lines changed: 305 additions & 18 deletions

File tree

‎datafusion/core/tests/physical_optimizer/ensure_requirements.rs‎

Lines changed: 117 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1533,18 +1533,13 @@ fn test_collect_left_join_keeps_hash_partitioned_build_side_coalesce() -> Result
15331533
}
15341534

15351535
// ========================================================================
1536-
// Limits with a `skip`
1536+
// Sort pushdown through limits
15371537
// ========================================================================
15381538

1539-
/// A sort pushed below `GlobalLimitExec` with a non-zero `skip` must ask its
1540-
/// input for `skip + fetch` rows; asking for only `fetch` rows used to leave
1541-
/// `LIMIT 10 OFFSET 5` with 5 result rows.
1542-
///
1543-
/// This checks a single pass only: the sort is inserted by `pushdown_sorts`,
1544-
/// which runs after `parallelize_sorts`, so a second pass would additionally
1545-
/// parallelize it into `SortPreservingMergeExec` + partitioned `SortExec`.
1539+
/// Keep sorting above an unordered limit so its input can stop early and only
1540+
/// the rows retained after the offset need sorting.
15461541
#[test]
1547-
fn test_sort_pushed_below_limit_with_skip_keeps_skip_rows() -> Result<()> {
1542+
fn test_keep_sort_above_unordered_limit_with_skip() -> Result<()> {
15481543
let source = Arc::new(MockMultiPartitionExec::new(4));
15491544
let coalesce = Arc::new(CoalescePartitionsExec::new(source));
15501545
let limit = Arc::new(GlobalLimitExec::new(coalesce, 5, Some(10)));
@@ -1553,10 +1548,121 @@ fn test_sort_pushed_below_limit_with_skip_keeps_skip_rows() -> Result<()> {
15531548

15541549
let optimized = optimize_and_sanity_check(sort)?;
15551550
assert_snapshot!(plan_string(&optimized), @r"
1556-
GlobalLimitExec: skip=5, fetch=10
1557-
SortExec: TopK(fetch=15), expr=[a@0 DESC], preserve_partitioning=[false]
1551+
SortExec: expr=[a@0 DESC], preserve_partitioning=[false]
1552+
GlobalLimitExec: skip=5, fetch=10
1553+
CoalescePartitionsExec
1554+
MockMultiPartitionExec
1555+
");
1556+
Ok(())
1557+
}
1558+
1559+
/// Keep sorting above OFFSET so it skips rows in input order.
1560+
#[test]
1561+
fn test_keep_sort_above_limit_with_skip_only() -> Result<()> {
1562+
let source = Arc::new(MockMultiPartitionExec::new(4));
1563+
let coalesce = Arc::new(CoalescePartitionsExec::new(source));
1564+
let limit = Arc::new(GlobalLimitExec::new(coalesce, 5, None));
1565+
let sort: Arc<dyn ExecutionPlan> =
1566+
Arc::new(SortExec::new(sort_expr_on("a", 0, true, true), limit));
1567+
1568+
let optimized = optimize_and_sanity_check(sort)?;
1569+
assert_snapshot!(plan_string(&optimized), @r"
1570+
SortExec: expr=[a@0 DESC], preserve_partitioning=[false]
1571+
GlobalLimitExec: skip=5, fetch=None
15581572
CoalescePartitionsExec
15591573
MockMultiPartitionExec
15601574
");
15611575
Ok(())
15621576
}
1577+
1578+
/// Source ordering on `[a]` must not let a TopK on `[a, b]` change which
1579+
/// rows the limit selects.
1580+
#[test]
1581+
fn test_keep_sort_above_ordered_limit_with_skip() -> Result<()> {
1582+
let source = Arc::new(MockMultiPartitionExec::new(4));
1583+
let mut ordering = sort_expr_on("a", 0, false, false);
1584+
let ordered_input = Arc::new(MockReqExec::new(
1585+
source,
1586+
Distribution::SinglePartition,
1587+
Some(ordering.clone()),
1588+
));
1589+
let limit = Arc::new(GlobalLimitExec::new(ordered_input, 5, Some(10)));
1590+
ordering.extend(sort_expr_on("b", 1, false, false));
1591+
let sort: Arc<dyn ExecutionPlan> = Arc::new(SortExec::new(ordering, limit));
1592+
1593+
let optimized = optimize_and_sanity_check(sort)?;
1594+
assert_snapshot!(plan_string(&optimized), @r"
1595+
SortExec: expr=[a@0 ASC NULLS LAST, b@1 ASC NULLS LAST], preserve_partitioning=[false]
1596+
GlobalLimitExec: skip=5, fetch=10
1597+
MockReqExec
1598+
SortPreservingMergeExec: [a@0 ASC NULLS LAST]
1599+
MockMultiPartitionExec
1600+
");
1601+
Ok(())
1602+
}
1603+
1604+
/// Refine the sort below the limit, retaining `skip + fetch` rows for OFFSET.
1605+
/// Single partition: a coalesce below the sort would be parallelized into a
1606+
/// merge first, which the next test covers.
1607+
#[test]
1608+
fn test_sort_pushed_into_sort_below_limit_with_skip() -> Result<()> {
1609+
let source = Arc::new(MockMultiPartitionExec::new(1));
1610+
let mut ordering = sort_expr_on("b", 1, false, false);
1611+
let inner_sort = Arc::new(SortExec::new(ordering.clone(), source));
1612+
let limit = Arc::new(GlobalLimitExec::new(inner_sort, 5, Some(10)));
1613+
ordering.extend(sort_expr_on("a", 0, false, false));
1614+
let sort: Arc<dyn ExecutionPlan> = Arc::new(SortExec::new(ordering, limit));
1615+
1616+
let optimized = optimize_and_sanity_check(sort)?;
1617+
assert_snapshot!(plan_string(&optimized), @r"
1618+
GlobalLimitExec: skip=5, fetch=10
1619+
SortExec: TopK(fetch=15), expr=[b@1 ASC NULLS LAST, a@0 ASC NULLS LAST], preserve_partitioning=[false]
1620+
MockMultiPartitionExec
1621+
");
1622+
Ok(())
1623+
}
1624+
1625+
/// The sort below the limit is parallelized into a merge over per-partition
1626+
/// sorts before pushdown runs. The limit then sits above a merge, not a sort,
1627+
/// so the finer sort stays above it.
1628+
#[test]
1629+
fn test_keep_sort_above_limit_over_merged_sort() -> Result<()> {
1630+
let source = Arc::new(MockMultiPartitionExec::new(4));
1631+
let coalesce = Arc::new(CoalescePartitionsExec::new(source));
1632+
let mut ordering = sort_expr_on("b", 1, false, false);
1633+
let inner_sort = Arc::new(SortExec::new(ordering.clone(), coalesce));
1634+
let limit = Arc::new(GlobalLimitExec::new(inner_sort, 5, Some(10)));
1635+
ordering.extend(sort_expr_on("a", 0, false, false));
1636+
let sort: Arc<dyn ExecutionPlan> = Arc::new(SortExec::new(ordering, limit));
1637+
1638+
let optimized = optimize_and_sanity_check(sort)?;
1639+
assert_snapshot!(plan_string(&optimized), @r"
1640+
SortExec: expr=[b@1 ASC NULLS LAST, a@0 ASC NULLS LAST], preserve_partitioning=[false]
1641+
GlobalLimitExec: skip=5, fetch=10
1642+
SortPreservingMergeExec: [b@1 ASC NULLS LAST]
1643+
SortExec: expr=[b@1 ASC NULLS LAST], preserve_partitioning=[true]
1644+
MockMultiPartitionExec
1645+
");
1646+
Ok(())
1647+
}
1648+
1649+
/// Keep sorting above a per-partition limit so each partition keeps its
1650+
/// first rows.
1651+
#[test]
1652+
fn test_keep_sort_above_local_limit() -> Result<()> {
1653+
let source = Arc::new(MockMultiPartitionExec::new(4));
1654+
let limit = Arc::new(LocalLimitExec::new(source, 10));
1655+
let coalesce = Arc::new(CoalescePartitionsExec::new(limit));
1656+
let mut ordering = sort_expr_on("a", 0, false, false);
1657+
ordering.extend(sort_expr_on("b", 1, false, false));
1658+
let sort: Arc<dyn ExecutionPlan> = Arc::new(SortExec::new(ordering, coalesce));
1659+
1660+
let optimized = optimize_and_sanity_check(sort)?;
1661+
assert_snapshot!(plan_string(&optimized), @r"
1662+
SortPreservingMergeExec: [a@0 ASC NULLS LAST, b@1 ASC NULLS LAST]
1663+
SortExec: expr=[a@0 ASC NULLS LAST, b@1 ASC NULLS LAST], preserve_partitioning=[true]
1664+
LocalLimitExec: fetch=10
1665+
MockMultiPartitionExec
1666+
");
1667+
Ok(())
1668+
}

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

Lines changed: 19 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -532,6 +532,22 @@ fn pushdown_requirement_to_children(
532532
)
533533
.then(|| Ok(vec![Some(parent_required)]))
534534
.transpose()
535+
} else if plan.is::<GlobalLimitExec>() || plan.is::<LocalLimitExec>() {
536+
// Sorting below a limit changes which rows it keeps. Only refine a
537+
// SortExec directly below it, which changes how ties are broken.
538+
// Otherwise, sort the retained rows and let the input stop early.
539+
let refines_sort_below = plan.children()[0].is::<SortExec>()
540+
&& plan.output_ordering().is_some_and(|ordering| {
541+
plan.equivalence_properties().requirements_compatible(
542+
parent_required.first().clone(),
543+
ordering.clone().into(),
544+
)
545+
});
546+
if refines_sort_below {
547+
Ok(Some(vec![Some(parent_required)]))
548+
} else {
549+
Ok(None)
550+
}
535551
} else if plan.fetch().is_some()
536552
&& plan.supports_limit_pushdown()
537553
&& plan
@@ -562,8 +578,10 @@ fn pushdown_requirement_to_children(
562578
} else {
563579
parent_required.clone()
564580
};
581+
582+
// Pushing a sort below an unordered fetch changes which rows it keeps.
565583
let Some(ordering) = plan.properties().output_ordering() else {
566-
return Ok(Some(vec![Some(child_required)]));
584+
return Ok(None);
567585
};
568586
if plan.properties().eq_properties.requirements_compatible(
569587
parent_required.first().clone(),

‎datafusion/sqllogictest/test_files/limit.slt‎

Lines changed: 169 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -339,9 +339,8 @@ SELECT COUNT(*) FROM (SELECT a FROM t1 LIMIT 3 OFFSET 8);
339339
----
340340
2
341341

342-
# A sort above LIMIT ... OFFSET is pushed below the limit as a TopK. The TopK
343-
# has to keep `skip + fetch` rows (3 + 4 = 7) so that the limit can still skip
344-
# 3 rows and return 4; keeping only `fetch` rows returned a single row.
342+
# Keep the sort above an unordered LIMIT ... OFFSET so the scan can stop
343+
# after `skip + fetch` rows (3 + 4 = 7), and only the 4 selected rows are sorted.
345344
query TT
346345
EXPLAIN SELECT * FROM (SELECT a FROM t1 LIMIT 4 OFFSET 3) ORDER BY a;
347346
----
@@ -350,9 +349,9 @@ logical_plan
350349
02)--Limit: skip=3, fetch=4
351350
03)----TableScan: t1 projection=[a], fetch=7
352351
physical_plan
353-
01)GlobalLimitExec: skip=3, fetch=4
354-
02)--SortExec: TopK(fetch=7), expr=[a@0 ASC NULLS LAST], preserve_partitioning=[false]
355-
03)----DataSourceExec: partitions=1, partition_sizes=[1]
352+
01)SortExec: expr=[a@0 ASC NULLS LAST], preserve_partitioning=[false]
353+
02)--GlobalLimitExec: skip=3, fetch=4
354+
03)----DataSourceExec: partitions=1, partition_sizes=[1], fetch=7
356355

357356
query I
358357
SELECT * FROM (SELECT a FROM t1 LIMIT 4 OFFSET 3) ORDER BY a;
@@ -362,6 +361,170 @@ SELECT * FROM (SELECT a FROM t1 LIMIT 4 OFFSET 3) ORDER BY a;
362361
6
363362
7
364363

364+
# LIMIT 4 OFFSET 3 keeps input rows (1, 7, 2, 10), then sorts them.
365+
statement ok
366+
CREATE TABLE unsorted (a INT) AS VALUES (5), (3), (9), (1), (7), (2), (10), (4), (8), (6);
367+
368+
query I
369+
SELECT * FROM (SELECT a FROM unsorted LIMIT 4 OFFSET 3) ORDER BY a;
370+
----
371+
1
372+
2
373+
7
374+
10
375+
376+
# OFFSET skips the first 3 input rows (5, 3, 9) before sorting.
377+
query TT
378+
EXPLAIN SELECT * FROM (SELECT a FROM unsorted OFFSET 3) ORDER BY a;
379+
----
380+
logical_plan
381+
01)Sort: unsorted.a ASC NULLS LAST
382+
02)--Limit: skip=3, fetch=None
383+
03)----TableScan: unsorted projection=[a]
384+
physical_plan
385+
01)SortExec: expr=[a@0 ASC NULLS LAST], preserve_partitioning=[false]
386+
02)--GlobalLimitExec: skip=3, fetch=None
387+
03)----DataSourceExec: partitions=1, partition_sizes=[1]
388+
389+
query I
390+
SELECT * FROM (SELECT a FROM unsorted OFFSET 3) ORDER BY a;
391+
----
392+
1
393+
2
394+
4
395+
6
396+
7
397+
8
398+
10
399+
400+
# Even with input ordered on `a`, a TopK on `(a, b)` below the limit would
401+
# change which rows it keeps.
402+
query I
403+
COPY (SELECT column1 AS a, column2 AS b FROM (VALUES
404+
(1, 9), (1, 8), (1, 7), (1, 6), (1, 5), (1, 4), (1, 3), (1, 2), (2, 1), (3, 0)))
405+
TO 'test_files/scratch/limit/ordered_prefix.parquet' STORED AS PARQUET;
406+
----
407+
10
408+
409+
statement ok
410+
CREATE EXTERNAL TABLE ordered_prefix (a BIGINT, b BIGINT)
411+
STORED AS PARQUET
412+
WITH ORDER (a ASC)
413+
LOCATION 'test_files/scratch/limit/ordered_prefix.parquet';
414+
415+
query TT
416+
EXPLAIN SELECT * FROM (SELECT a, b FROM ordered_prefix LIMIT 4 OFFSET 3) ORDER BY a, b;
417+
----
418+
logical_plan
419+
01)Sort: ordered_prefix.a ASC NULLS LAST, ordered_prefix.b ASC NULLS LAST
420+
02)--Limit: skip=0, fetch=4
421+
03)----TableScan: ordered_prefix projection=[a, b], fetch=4, skip=3
422+
physical_plan
423+
01)SortExec: expr=[a@0 ASC NULLS LAST, b@1 ASC NULLS LAST], preserve_partitioning=[false]
424+
02)--GlobalLimitExec: skip=3, fetch=4
425+
03)----DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/limit/ordered_prefix.parquet]]}, projection=[a, b], limit=7, output_ordering=[a@0 ASC NULLS LAST], file_type=parquet
426+
427+
query II
428+
SELECT * FROM (SELECT a, b FROM ordered_prefix LIMIT 4 OFFSET 3) ORDER BY a, b;
429+
----
430+
1 3
431+
1 4
432+
1 5
433+
1 6
434+
435+
# Refine the explicit sort to `(b, a)`. TopK keeps `skip + fetch` (3 + 4 = 7)
436+
# rows so the limit still returns 4.
437+
query TT
438+
EXPLAIN SELECT * FROM (SELECT a, b FROM ordered_prefix ORDER BY b LIMIT 4 OFFSET 3) ORDER BY b, a;
439+
----
440+
logical_plan
441+
01)Sort: ordered_prefix.b ASC NULLS LAST, ordered_prefix.a ASC NULLS LAST
442+
02)--Limit: skip=3, fetch=4
443+
03)----Sort: ordered_prefix.b ASC NULLS LAST, fetch=7
444+
04)------TableScan: ordered_prefix projection=[a, b]
445+
physical_plan
446+
01)GlobalLimitExec: skip=3, fetch=4
447+
02)--SortExec: TopK(fetch=7), expr=[b@1 ASC NULLS LAST, a@0 ASC NULLS LAST], preserve_partitioning=[false]
448+
03)----DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/limit/ordered_prefix.parquet]]}, projection=[a, b], file_type=parquet, predicate=DynamicFilter [ empty ], sort_order_for_reorder=[b@1 ASC NULLS LAST, a@0 ASC NULLS LAST], dynamic_rg_pruning=eligible
449+
450+
query II
451+
SELECT * FROM (SELECT a, b FROM ordered_prefix ORDER BY b LIMIT 4 OFFSET 3) ORDER BY b, a;
452+
----
453+
1 3
454+
1 4
455+
1 5
456+
1 6
457+
458+
# OFFSET without LIMIT: the refined sort is pushed into the explicit sort with
459+
# no fetch, and the limit still skips 3 rows.
460+
query TT
461+
EXPLAIN SELECT * FROM (SELECT a, b FROM ordered_prefix ORDER BY b OFFSET 3) ORDER BY b, a;
462+
----
463+
logical_plan
464+
01)Sort: ordered_prefix.b ASC NULLS LAST, ordered_prefix.a ASC NULLS LAST
465+
02)--Limit: skip=3, fetch=None
466+
03)----Sort: ordered_prefix.b ASC NULLS LAST
467+
04)------TableScan: ordered_prefix projection=[a, b]
468+
physical_plan
469+
01)GlobalLimitExec: skip=3, fetch=None
470+
02)--SortExec: expr=[b@1 ASC NULLS LAST, a@0 ASC NULLS LAST], preserve_partitioning=[false]
471+
03)----DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/limit/ordered_prefix.parquet]]}, projection=[a, b], file_type=parquet, sort_order_for_reorder=[b@1 ASC NULLS LAST, a@0 ASC NULLS LAST]
472+
473+
query II
474+
SELECT * FROM (SELECT a, b FROM ordered_prefix ORDER BY b OFFSET 3) ORDER BY b, a;
475+
----
476+
1 3
477+
1 4
478+
1 5
479+
1 6
480+
1 7
481+
1 8
482+
1 9
483+
484+
# A sort required by a window function, reaching the limit through a projection,
485+
# also stays above LIMIT ... OFFSET so the input can stop after `skip + fetch`
486+
# rows. It used to be pushed below the limit as a TopK over the whole input
487+
# (#25378).
488+
statement ok
489+
CREATE TABLE window_over_limit (id INT, kind VARCHAR) AS VALUES
490+
(19, 'a'), (18, 'a'), (17, 'a'), (16, 'a'), (15, 'a'),
491+
(14, 'a'), (13, 'a'), (12, 'a'), (11, 'a'), (10, 'a'),
492+
(9, 'a'), (8, 'a'), (7, 'a'), (6, 'a'), (5, 'a'),
493+
(4, 'a'), (3, 'a'), (2, 'a'), (1, 'a'), (0, 'a');
494+
495+
query TT
496+
EXPLAIN SELECT row_number() OVER (ORDER BY id) AS rn, id
497+
FROM (SELECT id FROM window_over_limit WHERE kind = 'a' LIMIT 5 OFFSET 5);
498+
----
499+
logical_plan
500+
01)Projection: row_number() ORDER BY [window_over_limit.id ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW AS rn, window_over_limit.id
501+
02)--WindowAggr: windowExpr=[[row_number() ORDER BY [window_over_limit.id ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW]]
502+
03)----Projection: window_over_limit.id
503+
04)------Limit: skip=5, fetch=5
504+
05)--------Filter: window_over_limit.kind = Utf8View("a")
505+
06)----------TableScan: window_over_limit projection=[id, kind]
506+
physical_plan
507+
01)ProjectionExec: expr=[row_number() ORDER BY [window_over_limit.id ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@1 as rn, id@0 as id]
508+
02)--BoundedWindowAggExec: wdw=[row_number() ORDER BY [window_over_limit.id ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "row_number() ORDER BY [window_over_limit.id ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": UInt64 }, frame: RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
509+
03)----SortExec: expr=[id@0 ASC NULLS LAST], preserve_partitioning=[false]
510+
04)------ProjectionExec: expr=[id@0 as id]
511+
05)--------GlobalLimitExec: skip=5, fetch=5
512+
06)----------FilterExec: kind@1 = a, fetch=10
513+
07)------------DataSourceExec: partitions=1, partition_sizes=[1]
514+
515+
query II
516+
SELECT row_number() OVER (ORDER BY id) AS rn, id
517+
FROM (SELECT id FROM window_over_limit WHERE kind = 'a' LIMIT 5 OFFSET 5);
518+
----
519+
1 10
520+
2 11
521+
3 12
522+
4 13
523+
5 14
524+
525+
statement ok
526+
DROP TABLE window_over_limit;
527+
365528
# The aggregate does not need to be computed because the input statistics are exact and
366529
# an OFFSET, but no LIMIT, is specified.
367530
query TT

0 commit comments

Comments
 (0)