Skip to content

Commit 16ace4f

Browse files
authored
fix: sort pushed below GlobalLimitExec ignores skip, returning too few rows (apache#24958)
## Which issue does this PR close? - Closes #. ## Rationale for this change `ORDER BY` applied on top of a `LIMIT ... OFFSET` subquery returns too few rows. ```sql SELECT * FROM (SELECT a FROM t1 LIMIT 4 OFFSET 3) ORDER BY a; ``` `EnforceSorting` pushes the sort below the `GlobalLimitExec` and converts it into a TopK. The TopK's fetch was seeded from `GlobalLimitExec::fetch()`, which is the limit's *output* row count and ignores `skip`. So the TopK kept only 4 rows, the limit then skipped 3 of them, and the query returned a single row instead of 4. The same seeding happens in two places in `sort_pushdown.rs`: when a root's direct child is a `GlobalLimitExec` (`assign_initial_requirements`) and when the pushdown descends through one (`pushdown_sorts_helper`). Both had the bug. ## What changes are included in this PR? - Add an `input_fetch` helper in `sort_pushdown.rs` that returns `skip + fetch` for `GlobalLimitExec` and plain `fetch()` for every other operator. - Use it at both sites where the pushed-down fetch is derived from the plan node, so the TopK below a `GlobalLimitExec` retains enough rows for the limit to skip and still return `fetch` rows. ## What is the testing strategy for this PR? - `limit.slt`: new `EXPLAIN` + result test for `LIMIT 4 OFFSET 3` under `ORDER BY`, showing `TopK(fetch=7)` below `GlobalLimitExec: skip=3, fetch=4` and the correct 4 rows. - `ensure_requirements.rs`: two unit tests, one per code path (`test_sort_pushed_below_limit_with_skip_keeps_skip_rows` and `test_parent_ordering_over_limit_with_skip_keeps_skip_rows`), asserting the pushed sort has `fetch=15` for `skip=5, fetch=10`. ## Are there any user-facing changes? Queries with a sort above `LIMIT ... OFFSET` now return the correct number of rows. No API changes.
1 parent b987501 commit 16ace4f

3 files changed

Lines changed: 134 additions & 2 deletions

File tree

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

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1531,3 +1531,32 @@ fn test_collect_left_join_keeps_hash_partitioned_build_side_coalesce() -> Result
15311531

15321532
Ok(())
15331533
}
1534+
1535+
// ========================================================================
1536+
// Limits with a `skip`
1537+
// ========================================================================
1538+
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`.
1546+
#[test]
1547+
fn test_sort_pushed_below_limit_with_skip_keeps_skip_rows() -> Result<()> {
1548+
let source = Arc::new(MockMultiPartitionExec::new(4));
1549+
let coalesce = Arc::new(CoalescePartitionsExec::new(source));
1550+
let limit = Arc::new(GlobalLimitExec::new(coalesce, 5, Some(10)));
1551+
let sort: Arc<dyn ExecutionPlan> =
1552+
Arc::new(SortExec::new(sort_expr_on("a", 0, true, true), limit));
1553+
1554+
let optimized = optimize_and_sanity_check(sort)?;
1555+
assert_snapshot!(plan_string(&optimized), @r"
1556+
GlobalLimitExec: skip=5, fetch=10
1557+
SortExec: TopK(fetch=15), expr=[a@0 DESC], preserve_partitioning=[false]
1558+
CoalescePartitionsExec
1559+
MockMultiPartitionExec
1560+
");
1561+
Ok(())
1562+
}

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

Lines changed: 82 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -79,6 +79,38 @@ impl Default for ParentRequirements {
7979

8080
pub type SortPushDown = PlanContext<ParentRequirements>;
8181

82+
/// Number of input rows `plan` needs from its children in order to produce
83+
/// the rows its parent will consume.
84+
///
85+
/// `parent_fetch` is the fetch a parent imposes on `plan`'s *output*
86+
/// (`ParentRequirements::fetch`). It bounds `plan.fetch()` directly because
87+
/// both count output rows, so the effective output fetch is
88+
/// `min(plan.fetch(), parent_fetch)`.
89+
///
90+
/// The input fetch is that output fetch for every operator except
91+
/// [`GlobalLimitExec`], which discards `skip` rows first and therefore needs
92+
/// `skip` more input rows. `skip` must be added *after* taking the minimum:
93+
/// `min(fetch + skip, parent_fetch)` would be too small whenever the parent
94+
/// fetch is the tighter bound. Using the bare `fetch` would be wrong too, as
95+
/// it would turn `LIMIT 10 OFFSET 5` into `TopK(10)` below the limit, i.e. 5
96+
/// result rows.
97+
///
98+
/// `skip` and `fetch` are independent `usize`s, so their sum can overflow. Like
99+
/// [`combine_limit`], we saturate: `usize::MAX` input rows is never a smaller
100+
/// bound than the real one, so the pushed-down fetch stays correct.
101+
///
102+
/// [`combine_limit`]: datafusion_common::utils::combine_limit
103+
fn input_fetch(
104+
plan: &Arc<dyn ExecutionPlan>,
105+
parent_fetch: Option<usize>,
106+
) -> Option<usize> {
107+
let fetch = min_fetch(plan.fetch(), parent_fetch)?;
108+
let skip = plan
109+
.downcast_ref::<GlobalLimitExec>()
110+
.map_or(0, |limit| limit.skip());
111+
Some(fetch.saturating_add(skip))
112+
}
113+
82114
/// Assigns the ordering requirement of the root node to the its children.
83115
pub fn assign_initial_requirements(sort_push_down: &mut SortPushDown) {
84116
let reqs = sort_push_down.plan.required_input_ordering();
@@ -364,7 +396,7 @@ fn pushdown_sorts_helper(
364396
// For operators that can take a sort pushdown, continue with updated
365397
// requirements. If this node already outputs single partition (e.g. SPM),
366398
// don't push SinglePartition to children.
367-
let current_fetch = sort_push_down.plan.fetch();
399+
let current_fetch = input_fetch(&sort_push_down.plan, parent_fetch);
368400
let dists = sort_push_down
369401
.plan
370402
.input_distribution_requirements()
@@ -379,7 +411,7 @@ fn pushdown_sorts_helper(
379411
sort_push_down.children.iter_mut().zip(adjusted).enumerate()
380412
{
381413
child.data.ordering_requirement = order;
382-
child.data.fetch = min_fetch(current_fetch, parent_fetch);
414+
child.data.fetch = current_fetch;
383415
child.data.distribution_requirement = stronger_distribution(
384416
&effective_dist,
385417
dists
@@ -1204,6 +1236,7 @@ mod tests {
12041236
use datafusion_physical_expr::PhysicalExpr;
12051237
use datafusion_physical_expr::expressions::{BinaryExpr, col};
12061238
use datafusion_physical_plan::empty::EmptyExec;
1239+
use datafusion_physical_plan::limit::GlobalLimitExec;
12071240

12081241
const DESC: SortOptions = SortOptions {
12091242
descending: true,
@@ -1214,6 +1247,53 @@ mod tests {
12141247
nulls_first: true,
12151248
};
12161249

1250+
#[test]
1251+
fn input_fetch_adds_skip_for_global_limit() {
1252+
let input = Arc::new(EmptyExec::new(child_schema()));
1253+
let limit: Arc<dyn ExecutionPlan> =
1254+
Arc::new(GlobalLimitExec::new(input, 5, Some(10)));
1255+
1256+
assert_eq!(input_fetch(&limit, None), Some(15));
1257+
}
1258+
1259+
/// A parent fetch bounds the limit's *output*, so it is applied before
1260+
/// `skip` is added: `min(10, 3) + 5 = 8`, not `min(10 + 5, 3) = 3`.
1261+
#[test]
1262+
fn input_fetch_applies_parent_fetch_before_adding_skip() {
1263+
let input = Arc::new(EmptyExec::new(child_schema()));
1264+
let limit: Arc<dyn ExecutionPlan> =
1265+
Arc::new(GlobalLimitExec::new(input, 5, Some(10)));
1266+
1267+
assert_eq!(input_fetch(&limit, Some(3)), Some(8));
1268+
// A looser parent fetch changes nothing.
1269+
assert_eq!(input_fetch(&limit, Some(20)), Some(15));
1270+
}
1271+
1272+
/// `OFFSET` without `LIMIT` has no fetch of its own, but a parent fetch
1273+
/// still needs `skip` extra input rows.
1274+
#[test]
1275+
fn input_fetch_adds_skip_to_parent_fetch_without_own_fetch() {
1276+
let input = Arc::new(EmptyExec::new(child_schema()));
1277+
let limit: Arc<dyn ExecutionPlan> =
1278+
Arc::new(GlobalLimitExec::new(input, 5, None));
1279+
1280+
assert_eq!(input_fetch(&limit, None), None);
1281+
assert_eq!(input_fetch(&limit, Some(3)), Some(8));
1282+
}
1283+
1284+
/// `skip` and `fetch` are unrelated `usize`s, so `skip + fetch` can exceed
1285+
/// `usize::MAX`. Saturating keeps this at an (unreachable) upper bound
1286+
/// instead of panicking in debug builds or wrapping to a too-small fetch --
1287+
/// wrapping to 0 would push down a `TopK(fetch=0)` and drop every row.
1288+
#[test]
1289+
fn input_fetch_saturates_instead_of_overflowing() {
1290+
let input = Arc::new(EmptyExec::new(child_schema()));
1291+
let limit: Arc<dyn ExecutionPlan> =
1292+
Arc::new(GlobalLimitExec::new(input, usize::MAX, Some(1)));
1293+
1294+
assert_eq!(input_fetch(&limit, None), Some(usize::MAX));
1295+
}
1296+
12171297
/// Child (input) schema fed to the projections under test: `[a, b, c]`.
12181298
fn child_schema() -> Arc<Schema> {
12191299
Arc::new(Schema::new(vec![

‎datafusion/sqllogictest/test_files/limit.slt‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -339,6 +339,29 @@ 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.
345+
query TT
346+
EXPLAIN SELECT * FROM (SELECT a FROM t1 LIMIT 4 OFFSET 3) ORDER BY a;
347+
----
348+
logical_plan
349+
01)Sort: t1.a ASC NULLS LAST
350+
02)--Limit: skip=3, fetch=4
351+
03)----TableScan: t1 projection=[a], fetch=7
352+
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]
356+
357+
query I
358+
SELECT * FROM (SELECT a FROM t1 LIMIT 4 OFFSET 3) ORDER BY a;
359+
----
360+
4
361+
5
362+
6
363+
7
364+
342365
# The aggregate does not need to be computed because the input statistics are exact and
343366
# an OFFSET, but no LIMIT, is specified.
344367
query TT

0 commit comments

Comments
 (0)