You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "discord9 (via GitHub)" <gi...@apache.org> on 2026/07/22 11:38:22 UTC

[PR] fix: preserve global limit for multi-partition fetch [datafusion]

discord9 opened a new pull request, #23800:
URL: https://github.com/apache/datafusion/pull/23800

   ## Which issue does this PR close?
   
   - Closes #23799.
   
   ## Rationale for this change
   
   An operator-level fetch on a plan with multiple output partitions is applied to
   each partition. It can reduce work, but it does not satisfy a global limit. The
   LimitPushdown rule could conflate those scopes and remove the remaining global
   enforcement, producing too many rows or composing global and local limits
   incorrectly.
   
   ## What changes are included in this PR?
   
   - Track whether a pushed requirement still needs global enforcement.
   - Preserve or tighten per-partition fetches as early-stop hints without treating
     them as global limits.
   - Materialize a `CoalescePartitionsExec` or `SortPreservingMergeExec` boundary
     before a multi-partition global requirement is considered satisfied.
   - Keep OFFSET and per-partition `LocalLimitExec` semantics separate from the
     global fetch.
   - Ignore no-op global limits without changing pending limit state.
   
   ## Are these changes tested?
   
   Yes. Physical optimizer regression tests cover:
   
   - fetch-capable and unfetchable multi-partition inputs;
   - LIMIT, OFFSET + LIMIT, and OFFSET-only plans;
   - an existing smaller per-partition fetch;
   - Union input fan-out;
   - global limits above multi-partition local limits;
   - no-op global limits; and
   - fetch absorption at HashJoin without leaking fetch to its inputs.
   
   The complete `physical_optimizer::limit_pushdown` integration test module and
   workspace clippy were run from the final PR head.
   
   ## Are there any user-facing changes?
   
   Yes. Queries using these physical plan shapes now preserve the requested global
   LIMIT/OFFSET rather than returning too many rows or over-restricting results.
   There are no public API changes.
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: preserve global limit for multi-partition fetch [datafusion]

Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #23800:
URL: https://github.com/apache/datafusion/pull/23800#issuecomment-6406183488

   Marked as draft after 14 days without activity: merge conflicts.
   
   Please address these items and mark **Ready for review** when ready.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: preserve global limit for multi-partition fetch [datafusion]

Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #23800:
URL: https://github.com/apache/datafusion/pull/23800#issuecomment-5103337761

   ## [Codecov](https://app.codecov.io/gh/apache/datafusion/pull/23800?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
   :x: Patch coverage is `88.99083%` with `12 lines` in your changes missing coverage. Please review.
   :white_check_mark: Project coverage is 80.69%. Comparing base ([`1b32517`](https://app.codecov.io/gh/apache/datafusion/commit/1b32517ace9bca3dbc0f65072798aeceeb9ea076?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`4b30ece`](https://app.codecov.io/gh/apache/datafusion/commit/4b30eced586ee35b55cc204b353d34a9f7c64926?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
   
   | [Files with missing lines](https://app.codecov.io/gh/apache/datafusion/pull/23800?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
   |---|---|---|
   | [...atafusion/physical-optimizer/src/limit\_pushdown.rs](https://app.codecov.io/gh/apache/datafusion/pull/23800?src=pr&el=tree&filepath=datafusion%2Fphysical-optimizer%2Fsrc%2Flimit_pushdown.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9waHlzaWNhbC1vcHRpbWl6ZXIvc3JjL2xpbWl0X3B1c2hkb3duLnJz) | 88.99% | [10 Missing and 2 partials :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/23800?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
   
   <details><summary>Additional details and impacted files</summary>
   
   
   
   ```diff
   @@            Coverage Diff             @@
   ##             main   #23800      +/-   ##
   ==========================================
   - Coverage   80.69%   80.69%   -0.01%     
   ==========================================
     Files        1095     1095              
     Lines      372623   372671      +48     
     Branches   372623   372671      +48     
   ==========================================
   + Hits       300695   300731      +36     
   - Misses      53979    53986       +7     
   - Partials    17949    17954       +5     
   ```
   </details>
   
   [:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/datafusion/pull/23800?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).   
   :loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
   <details><summary> :rocket: New features to boost your workflow: </summary>
   
   - :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
   - :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
   </details>


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: preserve global limit for multi-partition fetch [datafusion]

Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on code in PR #23800:
URL: https://github.com/apache/datafusion/pull/23800#discussion_r3778262856


##########
datafusion/physical-optimizer/src/limit_pushdown.rs:
##########
@@ -148,58 +152,117 @@ pub fn pushdown_limit_helper(
     mut pushdown_plan: Arc<dyn ExecutionPlan>,
     mut global_state: GlobalRequirements,
 ) -> Result<(Transformed<Arc<dyn ExecutionPlan>>, GlobalRequirements)> {
-    // Extract limit, if exist, and return child inputs.
-    if let Some(limit_info) = extract_limit(&pushdown_plan) {
-        // If we have fetch/skip info in the global state already, we need to
-        // decide which one to continue with:
-        let (skip, fetch) = combine_limit(
+    if global_state.pending == Some(PendingScope::Local)
+        && pushdown_plan.output_partitioning().partition_count() == 1
+    {
+        // Local and global scope are equivalent with one output partition, but
+        // retain the global scope in case recursion later exposes multi-partition
+        // children, including through extension combiners.
+        global_state.pending = Some(PendingScope::Global);
+    }
+
+    if let Some(global_limit) = pushdown_plan.downcast_ref::<GlobalLimitExec>()
+        && global_limit.skip() == 0
+        && global_limit.fetch().is_none()
+    {
+        // Remove this no-op wrapper without clearing inherited state, which may
+        // have been promoted from local to global scope at a one-output boundary.

Review Comment:
   I found this comment confusing. What about
   
   ```rust
           // A GlobalLimitExec with no skip and no fetch enforces nothing, so
           // remove it and keep the carried state untouched. Falling through to
           // the general limit handling would instead re-derive `pending` from
           // this node, which could reopen an already-satisfied requirement.
           // The local-to-global promotion above is kept as well: it relied only
           // on this node having one output partition, and it remains correct
           // after the node is removed.
   ```



##########
datafusion/physical-optimizer/src/limit_pushdown.rs:
##########
@@ -83,20 +83,31 @@ use datafusion_physical_plan::{ExecutionPlan, ExecutionPlanProperties};
 #[derive(Default, Debug)]
 pub struct LimitPushdown {}
 
-/// This is a "data class" we use within the [`LimitPushdown`] rule to push
-/// down limits in the plan. GlobalRequirements are hold as a rule-wide state
-/// and holds the fetch and skip information. The struct also has a field named
-/// satisfied which means if the "current" plan is valid in terms of limits or not.
+/// State carried through [`LimitPushdown`] while it pushes limits down the plan.
 ///
-/// For example: If the plan is satisfied with current fetch info, we decide to not add a LocalLimit
+/// `pending` keeps the semantic requirement's scope separate from its numeric
+/// payload. `Some(PendingScope::Local)` means a per-output-partition cap is
+/// still owed, and `Some(PendingScope::Global)` means a subtree-wide cap is
+/// still owed. When `pending` is `None`, no semantic enforcement remains
+/// outstanding; a retained `fetch` is a descendant early-stop hint only.
 ///
 /// [`LimitPushdown`]: crate::limit_pushdown::LimitPushdown
-#[derive(Default, Clone, Debug)]
+#[derive(Clone, Debug)]

Review Comment:
   Why remove `Default`?



##########
datafusion/physical-optimizer/src/limit_pushdown.rs:
##########
@@ -148,58 +152,117 @@ pub fn pushdown_limit_helper(
     mut pushdown_plan: Arc<dyn ExecutionPlan>,
     mut global_state: GlobalRequirements,
 ) -> Result<(Transformed<Arc<dyn ExecutionPlan>>, GlobalRequirements)> {
-    // Extract limit, if exist, and return child inputs.
-    if let Some(limit_info) = extract_limit(&pushdown_plan) {
-        // If we have fetch/skip info in the global state already, we need to
-        // decide which one to continue with:
-        let (skip, fetch) = combine_limit(
+    if global_state.pending == Some(PendingScope::Local)
+        && pushdown_plan.output_partitioning().partition_count() == 1
+    {
+        // Local and global scope are equivalent with one output partition, but
+        // retain the global scope in case recursion later exposes multi-partition
+        // children, including through extension combiners.
+        global_state.pending = Some(PendingScope::Global);
+    }
+
+    if let Some(global_limit) = pushdown_plan.downcast_ref::<GlobalLimitExec>()
+        && global_limit.skip() == 0
+        && global_limit.fetch().is_none()
+    {
+        // Remove this no-op wrapper without clearing inherited state, which may
+        // have been promoted from local to global scope at a one-output boundary.
+        return Ok((
+            Transformed {
+                data: Arc::clone(global_limit.input()),
+                transformed: true,
+                tnr: TreeNodeRecursion::Stop,
+            },
+            global_state,
+        ));
+    }
+
+    if global_state.pending == Some(PendingScope::Global)
+        && pushdown_plan.output_partitioning().partition_count() > 1
+    {
+        // This must precede generic `plan.fetch()` handling: a fetch on multiple
+        // outputs cannot by itself prove a global cap, because the `ExecutionPlan`
+        // trait does not formally encode scope. Retain it only as a per-partition
+        // hint; an existing smaller hint does not imply a smaller global cap.
+        let hint = global_state.fetch.map(|fetch| fetch + global_state.skip);
+        if let Some(hint) = hint {
+            let hint = pushdown_plan.fetch().map_or(hint, |fetch| fetch.min(hint));
+            if pushdown_plan.fetch() != Some(hint)
+                && let Some(plan_with_fetch) = pushdown_plan.with_fetch(Some(hint))
+            {
+                pushdown_plan = plan_with_fetch;
+            }
+        }
+
+        let plan = materialize_global_requirement(
+            pushdown_plan,
             global_state.skip,
             global_state.fetch,
-            limit_info.skip,
-            limit_info.fetch,
+            global_state.preserve_order,
         );
-        global_state.skip = skip;
-        global_state.fetch = fetch;
-        global_state.preserve_order = limit_info.preserve_order;
-        global_state.satisfied = false;
+        global_state.fetch = hint;
+        global_state.skip = 0;
+        global_state.pending = None;
+        return Ok((Transformed::yes(plan), global_state));
+    }
 
-        if let Some(fetch) = fetch
-            && limit_satisfied_by_input(&limit_info.input, skip, fetch)?
+    if let Some(global_limit) = pushdown_plan.downcast_ref::<GlobalLimitExec>() {
+        let input = Arc::clone(global_limit.input());
+        let skip = global_limit.skip();
+        let fetch = global_limit.fetch();
+
+        (global_state.skip, global_state.fetch) =
+            combine_limit(global_state.skip, global_state.fetch, skip, fetch);
+        global_state.preserve_order |= global_limit.required_ordering().is_some();
+        global_state.pending = Some(PendingScope::Global);
+        if let Some(fetch) = global_state.fetch
+            && limit_satisfied_by_input(&input, global_state.skip, fetch)?
         {
-            // The input already produces at most `fetch` rows, so no new limit
-            // node is needed. Mark satisfied so downstream won't re-add one,
-            // but preserve skip/fetch so any nested limit nodes (e.g. an inner
-            // GlobalLimitExec) can still be merged with the outer constraint.
-            global_state.satisfied = true;
-
-            return Ok((
-                Transformed {
-                    data: limit_info.input,
-                    transformed: true,
-                    tnr: TreeNodeRecursion::Stop,
-                },
-                global_state,
-            ));
+            global_state.pending = None;
         }
+        return Ok((
+            Transformed {
+                data: input,
+                transformed: true,
+                tnr: TreeNodeRecursion::Stop,
+            },
+            global_state,
+        ));
+    }
 
-        // Now the global state has the most recent information, we can remove
-        // the limit node. We will decide later if we should add it again or
-        // not.
+    if let Some(local_limit) = pushdown_plan.downcast_ref::<LocalLimitExec>() {
+        let input = Arc::clone(local_limit.input());
+        (global_state.skip, global_state.fetch) = combine_limit(
+            global_state.skip,
+            global_state.fetch,
+            0,
+            Some(local_limit.fetch()),
+        );
+        global_state.preserve_order |= local_limit.required_ordering().is_some();
+        global_state.pending = if input.output_partitioning().partition_count() == 1 {
+            Some(PendingScope::Global)
+        } else {
+            Some(PendingScope::Local)
+        };
+        if let Some(fetch) = global_state.fetch
+            && limit_satisfied_by_input(&input, global_state.skip, fetch)?
+        {
+            global_state.pending = None;
+        }
         return Ok((
             Transformed {
-                data: limit_info.input,
+                data: input,
                 transformed: true,
                 tnr: TreeNodeRecursion::Stop,
             },
             global_state,
         ));
     }
 
-    // If we have a non-limit operator with fetch capability, update global
-    // state as necessary:
+    // Merge a fetch already present on a non-limit operator into global state.
     if pushdown_plan.fetch().is_some() {
         if global_state.skip == 0 {
-            global_state.satisfied = true;
+            global_state.pending = None;
         }
         (global_state.skip, global_state.fetch) = combine_limit(
             global_state.skip,

Review Comment:
   Why if we owe `fetch=5` but the fetch on the operator is `> 5`?
   
   We rebuild the operator below via `pushdown_plan.with_fetch(skip_and_fetch)` below, but some operators might support `fetch` but not `with_fetch` (e.g., `PartialSort`).



##########
datafusion/physical-optimizer/src/limit_pushdown.rs:
##########


Review Comment:
   Is copying the global state into _every_ child correct, for an operator with multiple children? e.g., if we have an operator with `n` children and a single output partition, wouldn't this result in copying the fetch limit into `n` different operators, so we'd produce too many rows?



##########
datafusion/physical-optimizer/src/limit_pushdown.rs:
##########
@@ -83,20 +83,31 @@ use datafusion_physical_plan::{ExecutionPlan, ExecutionPlanProperties};
 #[derive(Default, Debug)]
 pub struct LimitPushdown {}
 
-/// This is a "data class" we use within the [`LimitPushdown`] rule to push
-/// down limits in the plan. GlobalRequirements are hold as a rule-wide state
-/// and holds the fetch and skip information. The struct also has a field named
-/// satisfied which means if the "current" plan is valid in terms of limits or not.
+/// State carried through [`LimitPushdown`] while it pushes limits down the plan.
 ///
-/// For example: If the plan is satisfied with current fetch info, we decide to not add a LocalLimit
+/// `pending` keeps the semantic requirement's scope separate from its numeric
+/// payload. `Some(PendingScope::Local)` means a per-output-partition cap is
+/// still owed, and `Some(PendingScope::Global)` means a subtree-wide cap is
+/// still owed. When `pending` is `None`, no semantic enforcement remains
+/// outstanding; a retained `fetch` is a descendant early-stop hint only.
 ///
 /// [`LimitPushdown`]: crate::limit_pushdown::LimitPushdown
-#[derive(Default, Clone, Debug)]
+#[derive(Clone, Debug)]
 pub struct GlobalRequirements {
     fetch: Option<usize>,
     skip: usize,
-    satisfied: bool,
     preserve_order: bool,
+    pending: Option<PendingScope>,
+}
+
+/// Scope of a semantic cap that remains pending independently of its numeric
+/// `skip` and `fetch` payload.

Review Comment:
   I found this comment confusing (e.g., whose `skip` and `fetch` are we referring to? What is a "semantic cap", and is a "non-semantic cap" a thing?). Calling it `PendingScope` only makes sense if you know the field in `GlobalRequirements` is named `pending`, which isn't obvious.
   
   What about:
   
   ```rust
   /// The scope of a row limit: what the limited row count applies to.
   #[derive(Clone, Copy, Debug, PartialEq, Eq)]
   enum LimitScope {
       /// The limit caps each output partition independently, as enforced by
       /// [`LocalLimitExec`].
       Local,
       /// The limit caps the combined output of all partitions, as enforced by
       /// [`GlobalLimitExec`] over a single-partition input. A fetch on a
       /// multi-partition operator cannot satisfy this scope; the partitions
       /// must first be merged into one stream.
       Global,
   }
   ```



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: preserve global limit for multi-partition fetch [datafusion]

Posted by "discord9 (via GitHub)" <gi...@apache.org>.
discord9 commented on code in PR #23800:
URL: https://github.com/apache/datafusion/pull/23800#discussion_r3795402991


##########
datafusion/physical-optimizer/src/limit_pushdown.rs:
##########


Review Comment:
   > This is true of the operators in the tree but I don't think it's true in general. Suppose there's a custom operator with n children, a single output partition, and `supports_limit_pushdown() == true`: at that node the materialization branch doesn't fire (one partition) and the blocker branch doesn't run (pushdown supported), so the helper returns with `pending == Some(LimitScope::Global)` still open, and pushdown_limits clones that open requirement into all of its children.
   
   fair enough, changed to not push down pending(only push down skip/fetch), childrens gets something like:
   ```
   pending: None
   skip: 0
   fetch: Some(7)
   ```
   now



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: preserve global limit for multi-partition fetch [datafusion]

Posted by "discord9 (via GitHub)" <gi...@apache.org>.
discord9 commented on code in PR #23800:
URL: https://github.com/apache/datafusion/pull/23800#discussion_r3781605972


##########
datafusion/physical-optimizer/src/limit_pushdown.rs:
##########


Review Comment:
   > Is copying the global state into _every_ child correct, for an operator with multiple children? e.g., if we have an operator with `n` children and a single output partition, wouldn't this result in copying the fetch limit into `n` different operators, so we'd produce too many rows?
   
   The final results is still comes from a single partition output CoalescePartitionsExec/SortPreservingMergeExec so the result will only be like what limit=N needs, as the cloned global state to every child should be like this anyway:
   ```
   pending = None
   skip = 0
   fetch = Some(N) -- just a early stop hint for child
   ```



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] fix: preserve global limit for multi-partition fetch [datafusion]

Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on code in PR #23800:
URL: https://github.com/apache/datafusion/pull/23800#discussion_r3785458751


##########
datafusion/physical-optimizer/src/limit_pushdown.rs:
##########


Review Comment:
   This is true of the operators in the tree but I don't think it's true in general. Suppose there's a custom operator with n children, a single output partition, and `supports_limit_pushdown() == true`: at that node the materialization branch doesn't fire (one partition) and the blocker branch doesn't run (pushdown supported), so the helper returns with `pending == Some(LimitScope::Global)` still open, and pushdown_limits clones that open requirement into all of its children.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org