Skip to content

fix: preserve input ordering required by limits - #23744

Closed
jayhan94 wants to merge 1 commit into
apache:mainfrom
jayhan94:fix_limit_sort
Closed

fix: preserve input ordering required by limits#23744
jayhan94 wants to merge 1 commit into
apache:mainfrom
jayhan94:fix_limit_sort

Conversation

@jayhan94

@jayhan94 jayhan94 commented Jul 21, 2026 •
edited
Loading

Copy link
Copy Markdown

Which issue does this PR close?

Rationale for this change

EnsureRequirements may remove a descendant SortExec when the child has no visible output ordering.

This is incorrect at a LIMIT boundary because LIMIT and OFFSET depend on the input sequence to determine which rows are returned. When an intervening ProjectionExec removes the sort key, its output_ordering() becomes None, even though it still preserves the row sequence. The optimizer then incorrectly removes the sort below the projection, producing incorrect results.

What changes are included in this PR?

  • Prevent EnsureRequirements from removing a linked SortExec at a limit boundary.

  • Add a SQL regression test that verifies the correct row is selected by an ordered subquery with OFFSET.

  • Configure the regression test with one logical optimizer pass to ensure correctness does not depend on a later logical rewrite.

No public API changes are included.

Are these changes tested?

Yes. The regression test fails without the fix, returning sorted_first instead of physical_second.

The following checks were run:

cargo test -p datafusion --test core_integration \
  ordered_offset_subquery_preserves_selected_row -- --nocapture

cargo fmt --all

cargo clippy --all-targets --all-features -- -D warnings

RUST_BACKTRACE=1 cargo test --profile ci \
  --exclude datafusion-examples \
  --exclude datafusion-benchmarks \
  --exclude datafusion-cli \
  --workspace --lib --tests --bins \
  --features
  avro,json,backtrace,extended_tests,recursive_protection,parquet_
  encryption

Are there any user-facing changes?

Yes. Ordered subqueries followed by LIMIT or OFFSET now preserve the sort needed to select the correct rows when an intervening projection hides the sort key.

There are no public API or documentation changes.

@github-actions github-actions Bot added optimizer Optimizer rules core Core DataFusion crate sqllogictest SQL Logic Tests (.slt) physical-plan Changes to the physical-plan crate labels Jul 21, 2026
@jayhan94
jayhan94 marked this pull request as ready for review July 23, 2026 06:41
@jayhan94
jayhan94 force-pushed the fix_limit_sort branch 2 times, most recently from 6ce79b4 to eb5a24a Compare July 24, 2026 02:33
@github-actions github-actions Bot added the ffi Changes to the ffi crate label Jul 24, 2026
@jayhan94

jayhan94 commented Jul 24, 2026

Copy link
Copy Markdown
Author

@alamb PTAL🙏

alamb
alamb reviewed Jul 24, 2026
View reviewed changes

@alamb alamb left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks for this PR @jayhan94

Comment thread datafusion/physical-plan/src/execution_plan.rs Outdated
/// Unlike [`Self::required_input_ordering`], this property does not require
/// a particular ordering that can be expressed using the child's schema.
/// It only requires that an existing input ordering is not discarded or
/// replaced with an incompatible ordering by physical optimizations. For

@alamb alamb Jul 24, 2026

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This property seems like it is some internal invariant of EnforceDistribution rather than something that describes how the ExecutionPlan behaves

I don't think we should add this to the ExecutionPlan trait

@alamb

alamb commented Jul 24, 2026

Copy link
Copy Markdown
Contributor

Isn't LIMIT already handled for subqueries? Perhaps we just need to extend the same logic to handle OFFSET

I don't understand the need to add a new method to ExecutionPlan

@github-actions github-actions Bot added sql SQL Planner logical-expr Logical plan and expressions proto Related to proto crate and removed ffi Changes to the ffi crate labels Jul 27, 2026
@jayhan94
jayhan94 marked this pull request as draft July 27, 2026 03:03
@github-actions github-actions Bot removed sql SQL Planner logical-expr Logical plan and expressions sqllogictest SQL Logic Tests (.slt) proto Related to proto crate physical-plan Changes to the physical-plan crate labels Aug 3, 2026
@jayhan94
jayhan94 force-pushed the fix_limit_sort branch 2 times, most recently from 9f4b5c8 to 322826b Compare August 3, 2026 10:22
@jayhan94
jayhan94 marked this pull request as ready for review August 9, 2026 09:20
@jayhan94

jayhan94 commented Aug 9, 2026 •
edited
Loading

Copy link
Copy Markdown
Author

Isn't LIMIT already handled for subqueries? Perhaps we just need to extend the same logic to handle OFFSET

I don't understand the need to add a new method to ExecutionPlan

I tried extending PushDownLimit for OFFSET, but correctness still depended on optimizer pass order. With one pass, Limit → Projection → Sort remains and EnsureRequirements incorrectly removes the sort. So, I simplified the patch: no ExecutionPlan API changes—just use the existing is_limit check to preserve linked sorts below a limit, with a regression test proving the fix. Please review again @alamb.

@jayhan94

jayhan94 commented Aug 13, 2026

Copy link
Copy Markdown
Author

@alamb Would you please take a look?

@jayhan94 jayhan94 closed this by deleting the head repository Sep 14, 2026
@kumarUjjawal kumarUjjawal mentioned this pull request Oct 26, 2026
Merged
dwsmith1983 pushed a commit to dwsmith1983/datafusion that referenced this pull request Oct 26, 2026
@kumarUjjawal
fix: preserve sorts before limits when projections hide sort keys (ap…
16c1f26 
…ache#26763)

## Which issue does this PR close?

Closes apache#23534.

This follows the closed, unmerged apache#23744.

## Rationale for this change

A grouped query over `ORDER BY sort_key OFFSET 1` can return
`sorted_first` instead of `physical_second`. A projection hides the sort
key, so the physical optimizer drops the sort even though it determines
which rows the offset retains.

## What changes are included in this PR?

Preserve linked sorts through operators that maintain input order,
including when a projection removes their ordering metadata. Remove
superseded sorts when enforcing a new ordering, and stop sort removal at
explicit limits and operators with embedded fetch limits.

Add SQL and physical optimizer regressions for projections, intervening
filters, local and global limits, replacement sorts, and optimizer
idempotence. An execution test verifies that an embedded filter limit
still selects the correct rows after one or two optimizer passes.

## What is the testing strategy for this PR?

- The ordered-offset SQL regression and embedded-fetch execution
regression fail without their respective fixes.
- The full extended suite passes: 12,987 Rust tests and 542 SQL files.
- `cargo fmt --all`, `cargo clippy --all-targets --all-features -- -D
warnings`, and the complete `./dev/rust_lint.sh` suite pass.
- Compared `physical_plan_struct_join_agg_sort` and
`physical_sorted_union_order_by_10_int64` against main at
`350ca76505c9513d16e7dd9910bcd9bde2c911ed`, using 30 samples each.
Neither benchmark showed a statistically significant performance change.

## Are there any user-facing changes?

Queries retain the rows selected by ordered LIMIT/OFFSET when a
projection hides the sort key. No public API changes.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@alamb alamb alamb left review comments

Assignees

No one assigned

Labels

core Core DataFusion crate optimizer Optimizer rules

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Returns the wrong grouped row when an outer GROUP BY consumes a subquery containing ORDER BY ... OFFSET.

2 participants

@jayhan94 @alamb