Skip to content

Commit 408527a

Browse files
fix: prevent DISTINCT ORDER BY LIMIT from returning too few rows (apache#24932)
## Which issue does this PR close? - Closes apache#24927. ## Rationale for this change With multiple partitions, `SELECT DISTINCT ... ORDER BY ... LIMIT` can return fewer rows than requested even when enough distinct values exist. `DISTINCT` runs in partial and final stages. Sort pushdown was moving the final TopK `fetch` (the sort's row limit) below the final aggregation, while duplicate partial results still existed: ```text SortPreservingMergeExec: fetch=3 AggregateExec: final DISTINCT SortExec: TopK(fetch=3) <-- limit is applied too early AggregateExec: partial DISTINCT ``` Duplicates could fill the limit and discard another value before the final `DISTINCT` had a chance to remove them. The corrected plan keeps the limit above the final `DISTINCT`: ```text SortPreservingMergeExec: fetch=3 <-- limit is applied after DISTINCT AggregateExec: final DISTINCT SortExec <-- ordering only; no limit AggregateExec: partial DISTINCT ``` I bisected this regression to [`450c861a8c`](apache@450c861) (apache#14821), first released in 47.0.0. That refactor made the ordering-satisfied fast path forward `fetch` to the current plan's children. It correctly established that the current plan preserved the requested ordering, but preserving order does not mean that moving a limit is safe. The shortcut consequently bypassed the existing limit-pushdown and cardinality checks: the parent of that commit returns `0`, `1`, and `2`, while the commit itself returns only `0` and `2`. ## What changes are included in this PR? When a plan already satisfies the requested ordering, sort pushdown first tries to keep a pending `fetch` on that plan through the generic `ExecutionPlan::with_fetch` capability. It forwards the fetch to children only when the plan explicitly supports limit pushdown and produces exactly one output row for every input row. If an already ordered plan can neither retain nor safely forward the fetch, the optimizer keeps the limit above it with a `LocalLimitExec` or `GlobalLimitExec`, adding a sort-preserving merge when a single output partition is required. This carries the limit without introducing a redundant sort and gives subsequent optimizer runs the same canonical plan shape. ## What is the testing strategy for this PR? An SQLLogicTest in `limit.slt` uses the exact two-partition query from apache#24927 and verifies that it returns `0`, `1`, and `2`. Focused physical optimizer tests verify the stable limit-carrier plan across another optimizer pass and verify that fetch is still forwarded through a safe equal-cardinality plan. ## Are there any user-facing changes? Yes. Affected queries now return all requested distinct rows. There are no API or configuration changes.
1 parent 9442d88 commit 408527a

3 files changed

Lines changed: 237 additions & 19 deletions

File tree

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

Lines changed: 100 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -30,6 +30,9 @@ use datafusion_physical_optimizer::ensure_requirements::EnsureRequirements;
3030
use datafusion_physical_optimizer::ensure_requirements::enforce_sorting::{
3131
PlanWithCorrespondingCoalescePartitions, parallelize_sorts,
3232
};
33+
use datafusion_physical_optimizer::ensure_requirements::enforce_sorting::sort_pushdown::{
34+
SortPushDown, assign_initial_requirements, pushdown_sorts,
35+
};
3336

3437
use std::sync::Arc;
3538

@@ -41,7 +44,7 @@ use datafusion_physical_expr::{
4144
EquivalenceProperties, LexOrdering, PhysicalExpr, PhysicalSortExpr,
4245
};
4346
use datafusion_physical_plan::execution_plan::{Boundedness, EmissionType};
44-
use datafusion_physical_plan::limit::GlobalLimitExec;
47+
use datafusion_physical_plan::limit::{GlobalLimitExec, LocalLimitExec};
4548
use datafusion_physical_plan::sorts::sort::SortExec;
4649
use datafusion_physical_plan::union::UnionExec;
4750
use datafusion_physical_plan::{
@@ -835,6 +838,102 @@ fn test_idempotent_sort_aggregate_sort_aggregate() {
835838
assert_idempotent(limit);
836839
}
837840

841+
/// Verifies the safe fallback for an already ordered, multi-partition plan that
842+
/// can neither retain a fetch nor pass it to its children. The fetch must stay
843+
/// above that plan in a `LocalLimitExec`, retain the ordering needed by the
844+
/// merge, and produce exactly the same plan on the next optimizer pass.
845+
///
846+
/// This prevents a late fallback from creating a temporary plan shape that
847+
/// `EnsureRequirements` rewrites when applied again.
848+
#[test]
849+
fn test_fetch_fallback_is_stable() {
850+
let source: Arc<dyn ExecutionPlan> = Arc::new(MockMultiPartitionExec::new(4));
851+
let union = UnionExec::try_new(vec![Arc::clone(&source), source]).unwrap();
852+
let ordering = sort_expr_on("a", 0, false, false);
853+
let sort: Arc<dyn ExecutionPlan> = Arc::new(
854+
SortExec::new(ordering.clone(), union)
855+
.with_fetch(Some(10))
856+
.with_preserve_partitioning(true),
857+
);
858+
let merge: Arc<dyn ExecutionPlan> = Arc::new(
859+
SortPreservingMergeExec::new(ordering.clone(), sort).with_fetch(Some(10)),
860+
);
861+
let plan: Arc<dyn ExecutionPlan> = Arc::new(OutputRequirementExec::new(
862+
merge,
863+
Some(OrderingRequirements::from(ordering.clone())),
864+
Distribution::SinglePartition,
865+
Some(10),
866+
));
867+
868+
// Exercise sort pushdown directly so the earlier sort-cleanup phase does
869+
// not canonicalize the redundant TopK before it reaches this fallback.
870+
let mut sort_push_down = SortPushDown::new_default(plan);
871+
assign_initial_requirements(&mut sort_push_down);
872+
let pushed_down = pushdown_sorts(sort_push_down).unwrap().plan;
873+
874+
// This fallback runs at the end of EnsureRequirements, so its output must
875+
// already be stable when the complete rule runs again.
876+
let next_pass = optimize_and_sanity_check(Arc::clone(&pushed_down)).unwrap();
877+
878+
let output_children = pushed_down.children();
879+
let merge_children = output_children[0].children();
880+
let limit = merge_children[0]
881+
.downcast_ref::<LocalLimitExec>()
882+
.expect("the fetch should be carried by a local limit");
883+
assert_eq!(limit.required_ordering(), &Some(ordering));
884+
885+
let pushed_down = plan_string(&pushed_down);
886+
let next_pass = plan_string(&next_pass);
887+
assert_snapshot!(pushed_down, @r"
888+
OutputRequirementExec: order_by=[(a@0, asc)], dist_by=SinglePartition
889+
SortPreservingMergeExec: [a@0 ASC NULLS LAST], fetch=10
890+
LocalLimitExec: fetch=10
891+
UnionExec
892+
MockMultiPartitionExec
893+
MockMultiPartitionExec
894+
");
895+
assert_eq!(pushed_down, next_pass);
896+
}
897+
898+
/// Verifies the complementary safe path. Before it has a fetch, a
899+
/// `SortPreservingMergeExec` returns one row per input row, so it may take the
900+
/// parent TopK fetch and forward that fetch to its input sort. Safety must be
901+
/// decided before adding the fetch, which changes the merge's cardinality.
902+
#[test]
903+
fn test_unfetched_spm_absorbs_and_forwards_fetch() {
904+
let source: Arc<dyn ExecutionPlan> = Arc::new(MockMultiPartitionExec::new(4));
905+
let ordering = sort_expr_on("a", 0, true, false);
906+
let sort: Arc<dyn ExecutionPlan> = Arc::new(
907+
SortExec::new(ordering.clone(), source).with_preserve_partitioning(true),
908+
);
909+
let merge: Arc<dyn ExecutionPlan> =
910+
Arc::new(SortPreservingMergeExec::new(ordering.clone(), sort));
911+
let topk: Arc<dyn ExecutionPlan> =
912+
Arc::new(SortExec::new(ordering, merge).with_fetch(Some(10)));
913+
914+
let mut sort_push_down = SortPushDown::new_default(topk);
915+
assign_initial_requirements(&mut sort_push_down);
916+
let optimized = pushdown_sorts(sort_push_down).unwrap().plan;
917+
918+
let merge = optimized
919+
.downcast_ref::<SortPreservingMergeExec>()
920+
.expect("the merge should retain the fetch");
921+
assert_eq!(merge.fetch(), Some(10));
922+
let sort = merge
923+
.input()
924+
.downcast_ref::<SortExec>()
925+
.expect("the fetch should be pushed to the input sort");
926+
assert_eq!(sort.fetch(), Some(10));
927+
928+
// The merge retains the global fetch while the input sort retains the
929+
// per-partition TopK optimization.
930+
assert_snapshot!(plan_string(&optimized), @r"
931+
SortPreservingMergeExec: [a@0 DESC NULLS LAST], fetch=10
932+
SortExec: TopK(fetch=10), expr=[a@0 DESC NULLS LAST], preserve_partitioning=[true]
933+
MockMultiPartitionExec
934+
");
935+
}
936+
838937
/// Stress test: idempotency with ALL partition counts from 1 to 64
839938
#[test]
840939
fn test_idempotent_all_partition_counts_1_to_64() {

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

Lines changed: 110 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -43,9 +43,11 @@ use datafusion_physical_plan::joins::utils::{
4343
ColumnIndex, calculate_join_output_ordering,
4444
};
4545
use datafusion_physical_plan::joins::{HashJoinExec, SortMergeJoinExec};
46+
use datafusion_physical_plan::limit::{GlobalLimitExec, LocalLimitExec};
4647
use datafusion_physical_plan::projection::{ProjectionExec, ProjectionExpr};
4748
use datafusion_physical_plan::repartition::RepartitionExec;
4849
use datafusion_physical_plan::sorts::sort::SortExec;
50+
use datafusion_physical_plan::sorts::sort_preserving_merge::SortPreservingMergeExec;
4951
use datafusion_physical_plan::tree_node::PlanContext;
5052
use datafusion_physical_plan::{ExecutionPlan, ExecutionPlanProperties};
5153

@@ -114,6 +116,72 @@ fn min_fetch(f1: Option<usize>, f2: Option<usize>) -> Option<usize> {
114116
}
115117
}
116118

119+
/// Returns whether a fetch on `plan` can also be applied to each child.
120+
fn can_push_fetch_through(plan: &Arc<dyn ExecutionPlan>) -> bool {
121+
plan.supports_limit_pushdown()
122+
&& matches!(plan.cardinality_effect(), CardinalityEffect::Equal)
123+
}
124+
125+
/// Returns a plan when the fast path for an already-satisfied ordering can also
126+
/// preserve `parent_fetch` at the current node.
127+
fn try_preserve_fetch_for_satisfied_plan(
128+
plan: &Arc<dyn ExecutionPlan>,
129+
parent_fetch: Option<usize>,
130+
) -> Option<Arc<dyn ExecutionPlan>> {
131+
let Some(parent_fetch) = parent_fetch else {
132+
return Some(Arc::clone(plan));
133+
};
134+
let fetch = min_fetch(plan.fetch(), Some(parent_fetch));
135+
136+
if plan.fetch() == fetch {
137+
return Some(Arc::clone(plan));
138+
}
139+
140+
plan.with_fetch(fetch)
141+
}
142+
143+
/// Preserves a fetch above an already ordered plan while satisfying the
144+
/// required distribution.
145+
fn preserve_fetch_above_ordered_plan(
146+
mut node: SortPushDown,
147+
ordering: LexOrdering,
148+
fetch: usize,
149+
required_distribution: &Distribution,
150+
) -> SortPushDown {
151+
// The new limit carries the fetch, so it is no longer pending on the
152+
// wrapped plan.
153+
node.data.fetch = None;
154+
155+
let input_has_multiple_partitions =
156+
node.plan.output_partitioning().partition_count() > 1;
157+
let input = Arc::clone(&node.plan);
158+
159+
let limit: Arc<dyn ExecutionPlan> = if input_has_multiple_partitions {
160+
let mut limit = LocalLimitExec::new(input, fetch);
161+
limit.set_required_ordering(Some(ordering.clone()));
162+
Arc::new(limit)
163+
} else {
164+
let mut limit = GlobalLimitExec::new(input, 0, Some(fetch));
165+
limit.set_required_ordering(Some(ordering.clone()));
166+
Arc::new(limit)
167+
};
168+
let limit_node = PlanContext::new(limit, ParentRequirements::default(), vec![node]);
169+
170+
if input_has_multiple_partitions
171+
&& matches!(required_distribution, Distribution::SinglePartition)
172+
{
173+
let merge = SortPreservingMergeExec::new(ordering, Arc::clone(&limit_node.plan))
174+
.with_fetch(Some(fetch));
175+
PlanContext::new(
176+
Arc::new(merge),
177+
ParentRequirements::default(),
178+
vec![limit_node],
179+
)
180+
} else {
181+
limit_node
182+
}
183+
}
184+
117185
/// Returns the stricter of two distribution requirements.
118186
/// `SinglePartition` is the strictest.
119187
#[expect(
@@ -244,8 +312,15 @@ fn pushdown_sorts_helper(
244312
}
245313
}
246314

315+
let can_push_fetch_to_children = can_push_fetch_through(&plan);
247316
sort_push_down.plan = plan;
248-
if satisfy_parent {
317+
let plan_with_preserved_fetch = if satisfy_parent {
318+
try_preserve_fetch_for_satisfied_plan(&sort_push_down.plan, parent_fetch)
319+
} else {
320+
None
321+
};
322+
if let Some(plan) = plan_with_preserved_fetch {
323+
sort_push_down.plan = plan;
249324
// For non-sort operators which satisfy ordering:
250325
let reqs = sort_push_down.plan.required_input_ordering();
251326
let dists = sort_push_down
@@ -261,12 +336,19 @@ fn pushdown_sorts_helper(
261336
} else {
262337
parent_distribution.clone()
263338
};
339+
// A fetch retained by the current node is the pushdown boundary unless
340+
// the original node can safely pass the limit through.
341+
let child_fetch = if can_push_fetch_to_children {
342+
parent_fetch
343+
} else {
344+
None
345+
};
264346

265347
for (idx, (child, order)) in
266348
sort_push_down.children.iter_mut().zip(reqs).enumerate()
267349
{
268350
child.data.ordering_requirement = order;
269-
child.data.fetch = min_fetch(parent_fetch, child.data.fetch);
351+
child.data.fetch = min_fetch(child_fetch, child.data.fetch);
270352
child.data.distribution_requirement = stronger_distribution(
271353
&effective_parent_dist,
272354
dists
@@ -306,6 +388,22 @@ fn pushdown_sorts_helper(
306388
);
307389
}
308390
sort_push_down.data.ordering_requirement = None;
391+
} else if satisfy_parent && let Some(fetch) = parent_fetch {
392+
// Use the plan's concrete ordering when the requirement leaves sort
393+
// options unspecified. If there is none, the requirement is satisfied
394+
// by constants, so either direction is valid.
395+
let ordering = sort_push_down
396+
.plan
397+
.output_ordering()
398+
.cloned()
399+
.unwrap_or_else(|| parent_requirement.into_single().into());
400+
sort_push_down = preserve_fetch_above_ordered_plan(
401+
sort_push_down,
402+
ordering,
403+
fetch,
404+
&parent_distribution,
405+
);
406+
assign_initial_requirements(&mut sort_push_down);
309407
} else {
310408
// Can not push down requirements, add new `SortExec` (distribution-aware):
311409
sort_push_down = add_sort_above_with_distribution(
@@ -326,14 +424,13 @@ fn pushdown_requirement_to_children(
326424
parent_required: OrderingRequirements,
327425
parent_fetch: Option<usize>,
328426
) -> Result<Option<Vec<Option<OrderingRequirements>>>> {
329-
// If there is a limit on the parent plan we cannot push it down through operators that change the cardinality.
330-
// E.g. consider if LIMIT 2 is applied below a FilteExec that filters out 1/2 of the rows we'll end up with 1 row instead of 2.
331-
// If the LIMIT is applied after the FilterExec and the FilterExec returns > 2 rows we'll end up with 2 rows (correct).
332-
if parent_fetch.is_some() && !plan.supports_limit_pushdown() {
333-
return Ok(None);
334-
}
335-
// Note: we still need to check the cardinality effect of the plan here, because the
336-
// limit pushdown is not always safe, even if the plan supports it. Here's an example:
427+
// A parent fetch can be pushed through a plan only if the plan explicitly
428+
// supports limit pushdown and does not change cardinality. For example, if
429+
// LIMIT 2 is applied below a FilterExec that removes half the rows, only one
430+
// row may remain. Applied after the filter, it correctly returns two rows
431+
// when at least two are available.
432+
//
433+
// Checking `supports_limit_pushdown()` alone is not enough. For example:
337434
//
338435
// UnionExec advertises `supports_limit_pushdown() == true` because it can
339436
// forward a LIMIT k to each of its children—i.e. apply “LIMIT k” separately
@@ -347,16 +444,11 @@ fn pushdown_requirement_to_children(
347444
// — Global LIMIT: take the first 3 rows from (A ∪ B) after merging.
348445
// — Pushed down: take 3 from A, 3 from B, then merge → up to 6 rows!
349446
//
350-
// That’s why we still block on cardinality: even though UnionExec can
447+
// That’s why we also require equal cardinality: even though UnionExec can
351448
// push a LIMIT to its children, its GreaterEqual effect means it cannot
352449
// preserve the global TopK semantics.
353-
if parent_fetch.is_some() {
354-
match plan.cardinality_effect() {
355-
CardinalityEffect::Equal => {
356-
// safe: only true sources (e.g. CoalesceBatchesExec, ProjectionExec) pass
357-
}
358-
_ => return Ok(None),
359-
}
450+
if parent_fetch.is_some() && !can_push_fetch_through(plan) {
451+
return Ok(None);
360452
}
361453

362454
let maintains_input_order = plan.maintains_input_order();

‎datafusion/sqllogictest/test_files/limit.slt‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -444,6 +444,33 @@ SELECT i FROM t1000 ORDER BY i LIMIT 3;
444444
2
445445
3
446446

447+
# Regression test for https://github.com/apache/datafusion/issues/24927
448+
# The TopK fetch must not be pushed below the final DISTINCT aggregation.
449+
statement ok
450+
SET datafusion.execution.target_partitions = 2;
451+
452+
query I
453+
WITH s(x) AS (
454+
VALUES (0), (1), (2)
455+
ORDER BY 1
456+
LIMIT 3
457+
),
458+
t AS (
459+
SELECT * FROM s
460+
UNION ALL
461+
SELECT * FROM s
462+
UNION ALL
463+
SELECT * FROM s
464+
)
465+
SELECT DISTINCT x FROM t ORDER BY x LIMIT 3;
466+
----
467+
0
468+
1
469+
2
470+
471+
statement ok
472+
SET datafusion.execution.target_partitions = 4;
473+
447474
query I
448475
SELECT COUNT(*) FROM (SELECT i FROM t1000 LIMIT 3);
449476
----

0 commit comments

Comments
 (0)