You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "jayzhan211 (via GitHub)" <gi...@apache.org> on 2026/10/18 02:52:49 UTC
[PR] fix: keep a sort in EnsureRequirements when the ordering cannot be proven [datafusion]
jayzhan211 opened a new pull request, #26459:
URL: https://github.com/apache/datafusion/pull/26459
## Which issue does this PR close?
- Closes #26283.
## Rationale for this change
A query that orders by a column that is constant on the probe side of a hash join fails to plan:
```text
SanityCheckPlan
caused by
Error during planning: Plan: ["SortPreservingMergeExec: [k@0 DESC]", " HashJoinExec: ..."] does not satisfy order requirements: [k@0 DESC]. Child-0 order: []
```
`EnsureRequirements` removes the sort because `pushdown_sorts` maps the requirement onto the probe side, where `k` is constant. Nothing then checks the node where the sort was removed against the equivalence properties of the operators in between. The hash join output does not report `k` as constant, so `SanityCheckPlan` rejects the plan that `EnsureRequirements` just produced.
The two use different reasoning: `pushdown_sorts` maps requirements top-down per operator, while `SanityCheckPlan` uses each node's bottom-up `equivalence_properties()`. Whenever the second knows less than the first, the query fails, although the plan is correct. Most `SanityCheckPlan` errors reported so far were correct plans rejected this way.
## What changes are included in this PR?
`EnsureRequirements` gets a step after `pushdown_sorts`, `add_sort_for_unproven_ordering`. It adds a `SortExec` below every node whose ordering requirement is not satisfied by its child's equivalence properties, the predicate `SanityCheckPlan` uses. The plans produced by `EnsureRequirements` then pass the check by construction.
- Constant sort keys are left out of the added sort, like `add_sort_above` does.
- When even the new `SortExec` cannot satisfy the requirement (the properties contradict themselves, as in #26430), nothing is added, and `SanityCheckPlan` still reports the plan.
- `LimitPushdown` still turns the added sort into a TopK under a `LIMIT`.
The step only adds a sort where the plan produced by `EnsureRequirements` would fail the check.
## What is the testing strategy for this PR?
- `order.slt`: both queries from #26283, with results and the `EXPLAIN` of the first. Without the change, all three cases fail to plan.
- `ensure_requirements.rs`: with the default rules up to `EnsureRequirements`, running `EnsureRequirements` again leaves the plan, including the added sort, unchanged.
- With a temporary counter, the step fires only in these new cases across all sqllogictest files and all `datafusion` core tests (including TPC-DS planning). It does not change any other plan.
- As an experiment, I reintroduced the sort pushdown bug fixed in #23591 (#23590). Without this change, `test_hash_join_interleaved_projection_preserves_parent_sort` fails in `SanityCheckPlan`. With it, the plan is valid: the correct sort is added above the join, and the wrong one pushed below it remains as wasted work. A pushdown bug therefore costs an extra sort instead of failing the query.
- The extended workspace suite passes.
`sql_planner` planning benchmarks, separate builds of `main` and this change, 5 alternating rounds, ratio branch / main:
| benchmark | best run | median |
| --- | --- | --- |
| `physical_plan_tpch_all` | 0.99 | 0.96 |
| `physical_plan_tpcds_all` | 1.04 | 1.01 |
| `physical_plan_clickbench_all` | 1.01 | 1.00 |
| `physical_many_self_joins` | 1.00 | 1.02 |
| `physical_select_all_from_1000` | 1.00 | 1.00 |
| `physical_select_aggregates_from_200` | 1.02 | 1.02 |
These are within the run-to-run noise of a shared machine; the step is one walk over the plan that returns early for nodes without an ordering requirement.
## Are there any user-facing changes?
Queries like the one in #26283 plan and run instead of failing. There are no 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: keep probe-side constants in join equivalence properties [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on PR #26459:
URL: https://github.com/apache/datafusion/pull/26459#issuecomment-6290907908
> Could you run the `sql_planner` benchmark to check the planning-time cost?
I ran it for the first version (the table was in the description, all within noise). That pass is gone now. The PR only copies one field per equivalence class when a join builds its properties, so I don't expect a measurable planning cost. I'm happy to rerun it if you'd like numbers for this version.
--
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: keep a sort in EnsureRequirements when the ordering cannot be proven [datafusion]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #26459:
URL: https://github.com/apache/datafusion/pull/26459#issuecomment-6245082299
## [Codecov](https://app.codecov.io/gh/apache/datafusion/pull/26459?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 `89.36170%` with `5 lines` in your changes missing coverage. Please review.
:white_check_mark: Project coverage is 82.89%. Comparing base ([`290ad15`](https://app.codecov.io/gh/apache/datafusion/commit/290ad15cc842167ca4d3c0774ccdf3a1d9d61862?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`8574ad8`](https://app.codecov.io/gh/apache/datafusion/commit/8574ad879c76620a3308b52718f2df423622daf7?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/26459?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
|---|---|---|
| [...zer/src/ensure\_requirements/enforce\_sorting/mod.rs](https://app.codecov.io/gh/apache/datafusion/pull/26459?src=pr&el=tree&filepath=datafusion%2Fphysical-optimizer%2Fsrc%2Fensure_requirements%2Fenforce_sorting%2Fmod.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9waHlzaWNhbC1vcHRpbWl6ZXIvc3JjL2Vuc3VyZV9yZXF1aXJlbWVudHMvZW5mb3JjZV9zb3J0aW5nL21vZC5ycw==) | 93.02% | [1 Missing and 2 partials :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/26459?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [.../physical-optimizer/src/ensure\_requirements/mod.rs](https://app.codecov.io/gh/apache/datafusion/pull/26459?src=pr&el=tree&filepath=datafusion%2Fphysical-optimizer%2Fsrc%2Fensure_requirements%2Fmod.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9waHlzaWNhbC1vcHRpbWl6ZXIvc3JjL2Vuc3VyZV9yZXF1aXJlbWVudHMvbW9kLnJz) | 50.00% | [0 Missing and 2 partials :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/26459?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 #26459 +/- ##
==========================================
- Coverage 82.89% 82.89% -0.01%
==========================================
Files 1154 1154
Lines 457656 457701 +45
Branches 457656 457701 +45
==========================================
+ Hits 379391 379422 +31
- Misses 55261 55268 +7
- Partials 23004 23011 +7
```
</details>
[:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/datafusion/pull/26459?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: keep probe-side constants in join equivalence properties [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on PR #26459:
URL: https://github.com/apache/datafusion/pull/26459#issuecomment-6356917032
run benchmark sql_planner
--
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: keep probe-side constants in join equivalence properties [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on code in PR #26459:
URL: https://github.com/apache/datafusion/pull/26459#discussion_r4324940656
##########
datafusion/physical-optimizer/src/ensure_requirements/mod.rs:
##########
@@ -69,6 +70,17 @@
//! <https://github.com/apache/datafusion/issues/21973>, where the old
//! two-rule pipeline could regress a parallel sort plan into a serial one
//! on pass 2.
+//! - **Requirements are provable**: Every ordering requirement in the
+//! output is satisfied according to the children's
+//! [`EquivalenceProperties`], the same check `SanityCheckPlan` applies.
+//! `pushdown_sorts` removes a sort when it can map the requirement onto a
+//! descendant that satisfies it, but the operators in between can report
+//! weaker properties than that mapping assumed (for example, a hash join
+//! that forgets a probe-side column is constant). Phase 3 then adds a sort
+//! where the requirement cannot be proven, so the rule never emits a plan
+//! that it cannot show to be valid.
Review Comment:
This no longer applies: following your comment on the root cause, the EnsureRequirements step is removed and the PR fixes the join instead.
##########
datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs:
##########
@@ -232,6 +235,71 @@ pub fn replace_with_partial_sort(
Ok(plan)
}
+/// Adds a [`SortExec`] below every node whose ordering requirement is not
+/// satisfied by its child's equivalence properties.
+///
+/// [`pushdown_sorts`] removes a sort when it can map the requirement onto a
+/// descendant that satisfies it. That mapping is computed separately from the
+/// equivalence properties of the operators in between, and the two can
+/// disagree. The plan may then be correct, but its properties cannot show it,
+/// and `SanityCheckPlan` rejects it. Adding the sort back keeps every plan
+/// produced by `EnsureRequirements` valid by the same check.
+///
+/// A requirement that a new [`SortExec`] still cannot satisfy is left as is,
+/// for `SanityCheckPlan` to report.
+///
+/// [`pushdown_sorts`]: sort_pushdown::pushdown_sorts
+pub fn add_sort_for_unproven_ordering(
+ plan: Arc<dyn ExecutionPlan>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ let requirements = plan.required_input_ordering();
+ if requirements.iter().all(Option::is_none) {
+ return Ok(Transformed::no(plan));
+ }
+ let mut children: Vec<_> = plan.children().into_iter().cloned().collect();
+ let mut changed = false;
+ for (child, requirement) in children.iter_mut().zip(requirements) {
+ let Some(requirement) = requirement else {
+ continue;
+ };
+ let requirement = requirement.into_single();
+ let eq_properties = child.equivalence_properties();
+ if eq_properties.ordering_satisfy_requirement(requirement.clone())? {
+ continue;
+ }
+ let sort_reqs: Vec<_> = requirement.clone().into();
+ let sort_exprs = sort_reqs
+ .into_iter()
+ .filter(|req| eq_properties.is_expr_constant(&req.expr).is_none())
+ .map(Into::into);
+ let Some(ordering) = LexOrdering::new(sort_exprs) else {
+ continue;
+ };
+ let sort: Arc<dyn ExecutionPlan> = Arc::new(
+ SortExec::new(ordering, Arc::clone(child)).with_preserve_partitioning(
+ child.output_partitioning().partition_count() > 1,
+ ),
Review Comment:
This no longer applies: following your comment on the root cause, the EnsureRequirements step is removed and the PR fixes the join instead.
##########
datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs:
##########
@@ -232,6 +235,71 @@ pub fn replace_with_partial_sort(
Ok(plan)
}
+/// Adds a [`SortExec`] below every node whose ordering requirement is not
+/// satisfied by its child's equivalence properties.
+///
+/// [`pushdown_sorts`] removes a sort when it can map the requirement onto a
+/// descendant that satisfies it. That mapping is computed separately from the
+/// equivalence properties of the operators in between, and the two can
+/// disagree. The plan may then be correct, but its properties cannot show it,
+/// and `SanityCheckPlan` rejects it. Adding the sort back keeps every plan
+/// produced by `EnsureRequirements` valid by the same check.
+///
+/// A requirement that a new [`SortExec`] still cannot satisfy is left as is,
+/// for `SanityCheckPlan` to report.
+///
+/// [`pushdown_sorts`]: sort_pushdown::pushdown_sorts
+pub fn add_sort_for_unproven_ordering(
+ plan: Arc<dyn ExecutionPlan>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ let requirements = plan.required_input_ordering();
+ if requirements.iter().all(Option::is_none) {
+ return Ok(Transformed::no(plan));
+ }
+ let mut children: Vec<_> = plan.children().into_iter().cloned().collect();
+ let mut changed = false;
+ for (child, requirement) in children.iter_mut().zip(requirements) {
+ let Some(requirement) = requirement else {
+ continue;
+ };
+ let requirement = requirement.into_single();
+ let eq_properties = child.equivalence_properties();
+ if eq_properties.ordering_satisfy_requirement(requirement.clone())? {
+ continue;
+ }
+ let sort_reqs: Vec<_> = requirement.clone().into();
Review Comment:
This no longer applies: following your comment on the root cause, the EnsureRequirements step is removed and the PR fixes the join instead.
##########
datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs:
##########
@@ -232,6 +235,71 @@ pub fn replace_with_partial_sort(
Ok(plan)
}
+/// Adds a [`SortExec`] below every node whose ordering requirement is not
+/// satisfied by its child's equivalence properties.
+///
+/// [`pushdown_sorts`] removes a sort when it can map the requirement onto a
+/// descendant that satisfies it. That mapping is computed separately from the
+/// equivalence properties of the operators in between, and the two can
+/// disagree. The plan may then be correct, but its properties cannot show it,
+/// and `SanityCheckPlan` rejects it. Adding the sort back keeps every plan
+/// produced by `EnsureRequirements` valid by the same check.
+///
+/// A requirement that a new [`SortExec`] still cannot satisfy is left as is,
+/// for `SanityCheckPlan` to report.
+///
+/// [`pushdown_sorts`]: sort_pushdown::pushdown_sorts
+pub fn add_sort_for_unproven_ordering(
+ plan: Arc<dyn ExecutionPlan>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ let requirements = plan.required_input_ordering();
+ if requirements.iter().all(Option::is_none) {
+ return Ok(Transformed::no(plan));
+ }
+ let mut children: Vec<_> = plan.children().into_iter().cloned().collect();
+ let mut changed = false;
+ for (child, requirement) in children.iter_mut().zip(requirements) {
+ let Some(requirement) = requirement else {
+ continue;
+ };
+ let requirement = requirement.into_single();
+ let eq_properties = child.equivalence_properties();
+ if eq_properties.ordering_satisfy_requirement(requirement.clone())? {
+ continue;
+ }
+ let sort_reqs: Vec<_> = requirement.clone().into();
+ let sort_exprs = sort_reqs
+ .into_iter()
+ .filter(|req| eq_properties.is_expr_constant(&req.expr).is_none())
+ .map(Into::into);
+ let Some(ordering) = LexOrdering::new(sort_exprs) else {
+ continue;
+ };
+ let sort: Arc<dyn ExecutionPlan> = Arc::new(
+ SortExec::new(ordering, Arc::clone(child)).with_preserve_partitioning(
+ child.output_partitioning().partition_count() > 1,
+ ),
+ );
+ if !sort
+ .equivalence_properties()
+ .ordering_satisfy_requirement(requirement)?
+ {
+ continue;
Review Comment:
This no longer applies: following your comment on the root cause, the EnsureRequirements step is removed and the PR fixes the join instead.
##########
datafusion/physical-optimizer/src/ensure_requirements/mod.rs:
##########
@@ -267,10 +279,15 @@ impl PhysicalOptimizerRule for EnsureRequirements {
assign_initial_requirements(&mut sort_pushdown);
let adjusted = pushdown_sorts(sort_pushdown)?;
- // 3d: Partial sort
- adjusted
+ // 3d: Sort where an ordering requirement cannot be proven
+ use super::enforce_sorting::add_sort_for_unproven_ordering;
+ let plan = adjusted
.plan
Review Comment:
This no longer applies: following your comment on the root cause, the EnsureRequirements step is removed and the PR fixes the join instead.
##########
datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs:
##########
@@ -232,6 +235,71 @@ pub fn replace_with_partial_sort(
Ok(plan)
}
+/// Adds a [`SortExec`] below every node whose ordering requirement is not
+/// satisfied by its child's equivalence properties.
+///
+/// [`pushdown_sorts`] removes a sort when it can map the requirement onto a
+/// descendant that satisfies it. That mapping is computed separately from the
+/// equivalence properties of the operators in between, and the two can
+/// disagree. The plan may then be correct, but its properties cannot show it,
+/// and `SanityCheckPlan` rejects it. Adding the sort back keeps every plan
+/// produced by `EnsureRequirements` valid by the same check.
+///
+/// A requirement that a new [`SortExec`] still cannot satisfy is left as is,
+/// for `SanityCheckPlan` to report.
+///
+/// [`pushdown_sorts`]: sort_pushdown::pushdown_sorts
+pub fn add_sort_for_unproven_ordering(
+ plan: Arc<dyn ExecutionPlan>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ let requirements = plan.required_input_ordering();
+ if requirements.iter().all(Option::is_none) {
+ return Ok(Transformed::no(plan));
+ }
+ let mut children: Vec<_> = plan.children().into_iter().cloned().collect();
+ let mut changed = false;
+ for (child, requirement) in children.iter_mut().zip(requirements) {
+ let Some(requirement) = requirement else {
+ continue;
+ };
+ let requirement = requirement.into_single();
+ let eq_properties = child.equivalence_properties();
+ if eq_properties.ordering_satisfy_requirement(requirement.clone())? {
+ continue;
+ }
+ let sort_reqs: Vec<_> = requirement.clone().into();
+ let sort_exprs = sort_reqs
+ .into_iter()
+ .filter(|req| eq_properties.is_expr_constant(&req.expr).is_none())
+ .map(Into::into);
+ let Some(ordering) = LexOrdering::new(sort_exprs) else {
+ continue;
+ };
+ let sort: Arc<dyn ExecutionPlan> = Arc::new(
+ SortExec::new(ordering, Arc::clone(child)).with_preserve_partitioning(
+ child.output_partitioning().partition_count() > 1,
+ ),
+ );
+ if !sort
+ .equivalence_properties()
+ .ordering_satisfy_requirement(requirement)?
+ {
+ continue;
+ }
+ *child = sort;
+ changed = true;
+ }
+ if changed {
+ plan.replace_children(
Review Comment:
This no longer applies: following your comment on the root cause, the EnsureRequirements step is removed and the PR fixes the join instead.
##########
datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs:
##########
@@ -232,6 +235,71 @@ pub fn replace_with_partial_sort(
Ok(plan)
}
+/// Adds a [`SortExec`] below every node whose ordering requirement is not
+/// satisfied by its child's equivalence properties.
+///
+/// [`pushdown_sorts`] removes a sort when it can map the requirement onto a
+/// descendant that satisfies it. That mapping is computed separately from the
+/// equivalence properties of the operators in between, and the two can
+/// disagree. The plan may then be correct, but its properties cannot show it,
+/// and `SanityCheckPlan` rejects it. Adding the sort back keeps every plan
+/// produced by `EnsureRequirements` valid by the same check.
+///
+/// A requirement that a new [`SortExec`] still cannot satisfy is left as is,
+/// for `SanityCheckPlan` to report.
+///
+/// [`pushdown_sorts`]: sort_pushdown::pushdown_sorts
+pub fn add_sort_for_unproven_ordering(
+ plan: Arc<dyn ExecutionPlan>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ let requirements = plan.required_input_ordering();
+ if requirements.iter().all(Option::is_none) {
+ return Ok(Transformed::no(plan));
+ }
+ let mut children: Vec<_> = plan.children().into_iter().cloned().collect();
+ let mut changed = false;
+ for (child, requirement) in children.iter_mut().zip(requirements) {
+ let Some(requirement) = requirement else {
+ continue;
+ };
+ let requirement = requirement.into_single();
+ let eq_properties = child.equivalence_properties();
+ if eq_properties.ordering_satisfy_requirement(requirement.clone())? {
+ continue;
+ }
+ let sort_reqs: Vec<_> = requirement.clone().into();
+ let sort_exprs = sort_reqs
+ .into_iter()
+ .filter(|req| eq_properties.is_expr_constant(&req.expr).is_none())
+ .map(Into::into);
+ let Some(ordering) = LexOrdering::new(sort_exprs) else {
+ continue;
+ };
+ let sort: Arc<dyn ExecutionPlan> = Arc::new(
Review Comment:
This no longer applies: following your comment on the root cause, the EnsureRequirements step is removed and the PR fixes the join instead.
--
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: keep probe-side constants in join equivalence properties [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on code in PR #26459:
URL: https://github.com/apache/datafusion/pull/26459#discussion_r4324942456
##########
datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs:
##########
@@ -232,6 +235,71 @@ pub fn replace_with_partial_sort(
Ok(plan)
}
+/// Adds a [`SortExec`] below every node whose ordering requirement is not
+/// satisfied by its child's equivalence properties.
+///
+/// [`pushdown_sorts`] removes a sort when it can map the requirement onto a
+/// descendant that satisfies it. That mapping is computed separately from the
+/// equivalence properties of the operators in between, and the two can
+/// disagree. The plan may then be correct, but its properties cannot show it,
+/// and `SanityCheckPlan` rejects it. Adding the sort back keeps every plan
+/// produced by `EnsureRequirements` valid by the same check.
+///
+/// A requirement that a new [`SortExec`] still cannot satisfy is left as is,
+/// for `SanityCheckPlan` to report.
+///
+/// [`pushdown_sorts`]: sort_pushdown::pushdown_sorts
+pub fn add_sort_for_unproven_ordering(
+ plan: Arc<dyn ExecutionPlan>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ let requirements = plan.required_input_ordering();
+ if requirements.iter().all(Option::is_none) {
+ return Ok(Transformed::no(plan));
+ }
+ let mut children: Vec<_> = plan.children().into_iter().cloned().collect();
+ let mut changed = false;
+ for (child, requirement) in children.iter_mut().zip(requirements) {
+ let Some(requirement) = requirement else {
+ continue;
+ };
+ let requirement = requirement.into_single();
+ let eq_properties = child.equivalence_properties();
+ if eq_properties.ordering_satisfy_requirement(requirement.clone())? {
+ continue;
+ }
+ let sort_reqs: Vec<_> = requirement.clone().into();
+ let sort_exprs = sort_reqs
+ .into_iter()
+ .filter(|req| eq_properties.is_expr_constant(&req.expr).is_none())
+ .map(Into::into);
+ let Some(ordering) = LexOrdering::new(sort_exprs) else {
+ continue;
+ };
+ let sort: Arc<dyn ExecutionPlan> = Arc::new(
+ SortExec::new(ordering, Arc::clone(child)).with_preserve_partitioning(
+ child.output_partitioning().partition_count() > 1,
+ ),
+ );
+ if !sort
+ .equivalence_properties()
+ .ordering_satisfy_requirement(requirement)?
+ {
+ continue;
+ }
+ *child = sort;
+ changed = true;
+ }
+ if changed {
+ plan.replace_children(
Review Comment:
This no longer applies: following your comment on the root cause, the EnsureRequirements step is removed and the PR fixes the join instead.
##########
datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs:
##########
@@ -232,6 +235,71 @@ pub fn replace_with_partial_sort(
Ok(plan)
}
+/// Adds a [`SortExec`] below every node whose ordering requirement is not
+/// satisfied by its child's equivalence properties.
+///
+/// [`pushdown_sorts`] removes a sort when it can map the requirement onto a
+/// descendant that satisfies it. That mapping is computed separately from the
+/// equivalence properties of the operators in between, and the two can
+/// disagree. The plan may then be correct, but its properties cannot show it,
+/// and `SanityCheckPlan` rejects it. Adding the sort back keeps every plan
+/// produced by `EnsureRequirements` valid by the same check.
+///
+/// A requirement that a new [`SortExec`] still cannot satisfy is left as is,
+/// for `SanityCheckPlan` to report.
+///
+/// [`pushdown_sorts`]: sort_pushdown::pushdown_sorts
+pub fn add_sort_for_unproven_ordering(
+ plan: Arc<dyn ExecutionPlan>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ let requirements = plan.required_input_ordering();
+ if requirements.iter().all(Option::is_none) {
+ return Ok(Transformed::no(plan));
+ }
+ let mut children: Vec<_> = plan.children().into_iter().cloned().collect();
+ let mut changed = false;
+ for (child, requirement) in children.iter_mut().zip(requirements) {
+ let Some(requirement) = requirement else {
+ continue;
+ };
+ let requirement = requirement.into_single();
+ let eq_properties = child.equivalence_properties();
+ if eq_properties.ordering_satisfy_requirement(requirement.clone())? {
+ continue;
+ }
+ let sort_reqs: Vec<_> = requirement.clone().into();
+ let sort_exprs = sort_reqs
+ .into_iter()
+ .filter(|req| eq_properties.is_expr_constant(&req.expr).is_none())
+ .map(Into::into);
+ let Some(ordering) = LexOrdering::new(sort_exprs) else {
+ continue;
+ };
+ let sort: Arc<dyn ExecutionPlan> = Arc::new(
Review Comment:
This no longer applies: following your comment on the root cause, the EnsureRequirements step is removed and the PR fixes the join instead.
##########
datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs:
##########
@@ -232,6 +235,71 @@ pub fn replace_with_partial_sort(
Ok(plan)
}
+/// Adds a [`SortExec`] below every node whose ordering requirement is not
+/// satisfied by its child's equivalence properties.
+///
+/// [`pushdown_sorts`] removes a sort when it can map the requirement onto a
+/// descendant that satisfies it. That mapping is computed separately from the
+/// equivalence properties of the operators in between, and the two can
+/// disagree. The plan may then be correct, but its properties cannot show it,
+/// and `SanityCheckPlan` rejects it. Adding the sort back keeps every plan
+/// produced by `EnsureRequirements` valid by the same check.
+///
+/// A requirement that a new [`SortExec`] still cannot satisfy is left as is,
+/// for `SanityCheckPlan` to report.
+///
+/// [`pushdown_sorts`]: sort_pushdown::pushdown_sorts
+pub fn add_sort_for_unproven_ordering(
+ plan: Arc<dyn ExecutionPlan>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ let requirements = plan.required_input_ordering();
+ if requirements.iter().all(Option::is_none) {
+ return Ok(Transformed::no(plan));
+ }
+ let mut children: Vec<_> = plan.children().into_iter().cloned().collect();
+ let mut changed = false;
+ for (child, requirement) in children.iter_mut().zip(requirements) {
+ let Some(requirement) = requirement else {
+ continue;
+ };
+ let requirement = requirement.into_single();
+ let eq_properties = child.equivalence_properties();
+ if eq_properties.ordering_satisfy_requirement(requirement.clone())? {
+ continue;
+ }
+ let sort_reqs: Vec<_> = requirement.clone().into();
+ let sort_exprs = sort_reqs
+ .into_iter()
+ .filter(|req| eq_properties.is_expr_constant(&req.expr).is_none())
+ .map(Into::into);
+ let Some(ordering) = LexOrdering::new(sort_exprs) else {
+ continue;
+ };
+ let sort: Arc<dyn ExecutionPlan> = Arc::new(
+ SortExec::new(ordering, Arc::clone(child)).with_preserve_partitioning(
Review Comment:
This no longer applies, since the step is removed. For the record, `LimitPushdown` ran after it and turned the added sort into a TopK under a `LIMIT`.
--
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: keep probe-side constants in join equivalence properties [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on code in PR #26459:
URL: https://github.com/apache/datafusion/pull/26459#discussion_r4324940656
##########
datafusion/physical-optimizer/src/ensure_requirements/mod.rs:
##########
@@ -69,6 +70,17 @@
//! <https://github.com/apache/datafusion/issues/21973>, where the old
//! two-rule pipeline could regress a parallel sort plan into a serial one
//! on pass 2.
+//! - **Requirements are provable**: Every ordering requirement in the
+//! output is satisfied according to the children's
+//! [`EquivalenceProperties`], the same check `SanityCheckPlan` applies.
+//! `pushdown_sorts` removes a sort when it can map the requirement onto a
+//! descendant that satisfies it, but the operators in between can report
+//! weaker properties than that mapping assumed (for example, a hash join
+//! that forgets a probe-side column is constant). Phase 3 then adds a sort
+//! where the requirement cannot be proven, so the rule never emits a plan
+//! that it cannot show to be valid.
Review Comment:
This no longer applies: following your comment on the root cause, the EnsureRequirements step is removed and the PR fixes the join instead.
##########
datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs:
##########
@@ -232,6 +235,71 @@ pub fn replace_with_partial_sort(
Ok(plan)
}
+/// Adds a [`SortExec`] below every node whose ordering requirement is not
+/// satisfied by its child's equivalence properties.
+///
+/// [`pushdown_sorts`] removes a sort when it can map the requirement onto a
+/// descendant that satisfies it. That mapping is computed separately from the
+/// equivalence properties of the operators in between, and the two can
+/// disagree. The plan may then be correct, but its properties cannot show it,
+/// and `SanityCheckPlan` rejects it. Adding the sort back keeps every plan
+/// produced by `EnsureRequirements` valid by the same check.
+///
+/// A requirement that a new [`SortExec`] still cannot satisfy is left as is,
+/// for `SanityCheckPlan` to report.
+///
+/// [`pushdown_sorts`]: sort_pushdown::pushdown_sorts
+pub fn add_sort_for_unproven_ordering(
+ plan: Arc<dyn ExecutionPlan>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ let requirements = plan.required_input_ordering();
+ if requirements.iter().all(Option::is_none) {
+ return Ok(Transformed::no(plan));
+ }
+ let mut children: Vec<_> = plan.children().into_iter().cloned().collect();
+ let mut changed = false;
+ for (child, requirement) in children.iter_mut().zip(requirements) {
+ let Some(requirement) = requirement else {
+ continue;
+ };
+ let requirement = requirement.into_single();
+ let eq_properties = child.equivalence_properties();
+ if eq_properties.ordering_satisfy_requirement(requirement.clone())? {
+ continue;
+ }
+ let sort_reqs: Vec<_> = requirement.clone().into();
+ let sort_exprs = sort_reqs
+ .into_iter()
+ .filter(|req| eq_properties.is_expr_constant(&req.expr).is_none())
+ .map(Into::into);
+ let Some(ordering) = LexOrdering::new(sort_exprs) else {
+ continue;
+ };
+ let sort: Arc<dyn ExecutionPlan> = Arc::new(
+ SortExec::new(ordering, Arc::clone(child)).with_preserve_partitioning(
+ child.output_partitioning().partition_count() > 1,
+ ),
Review Comment:
This no longer applies: following your comment on the root cause, the EnsureRequirements step is removed and the PR fixes the join instead.
##########
datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs:
##########
@@ -232,6 +235,71 @@ pub fn replace_with_partial_sort(
Ok(plan)
}
+/// Adds a [`SortExec`] below every node whose ordering requirement is not
+/// satisfied by its child's equivalence properties.
+///
+/// [`pushdown_sorts`] removes a sort when it can map the requirement onto a
+/// descendant that satisfies it. That mapping is computed separately from the
+/// equivalence properties of the operators in between, and the two can
+/// disagree. The plan may then be correct, but its properties cannot show it,
+/// and `SanityCheckPlan` rejects it. Adding the sort back keeps every plan
+/// produced by `EnsureRequirements` valid by the same check.
+///
+/// A requirement that a new [`SortExec`] still cannot satisfy is left as is,
+/// for `SanityCheckPlan` to report.
+///
+/// [`pushdown_sorts`]: sort_pushdown::pushdown_sorts
+pub fn add_sort_for_unproven_ordering(
+ plan: Arc<dyn ExecutionPlan>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ let requirements = plan.required_input_ordering();
+ if requirements.iter().all(Option::is_none) {
+ return Ok(Transformed::no(plan));
+ }
+ let mut children: Vec<_> = plan.children().into_iter().cloned().collect();
+ let mut changed = false;
+ for (child, requirement) in children.iter_mut().zip(requirements) {
+ let Some(requirement) = requirement else {
+ continue;
+ };
+ let requirement = requirement.into_single();
+ let eq_properties = child.equivalence_properties();
+ if eq_properties.ordering_satisfy_requirement(requirement.clone())? {
+ continue;
+ }
+ let sort_reqs: Vec<_> = requirement.clone().into();
Review Comment:
This no longer applies: following your comment on the root cause, the EnsureRequirements step is removed and the PR fixes the join instead.
##########
datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs:
##########
@@ -232,6 +235,71 @@ pub fn replace_with_partial_sort(
Ok(plan)
}
+/// Adds a [`SortExec`] below every node whose ordering requirement is not
+/// satisfied by its child's equivalence properties.
+///
+/// [`pushdown_sorts`] removes a sort when it can map the requirement onto a
+/// descendant that satisfies it. That mapping is computed separately from the
+/// equivalence properties of the operators in between, and the two can
+/// disagree. The plan may then be correct, but its properties cannot show it,
+/// and `SanityCheckPlan` rejects it. Adding the sort back keeps every plan
+/// produced by `EnsureRequirements` valid by the same check.
+///
+/// A requirement that a new [`SortExec`] still cannot satisfy is left as is,
+/// for `SanityCheckPlan` to report.
+///
+/// [`pushdown_sorts`]: sort_pushdown::pushdown_sorts
+pub fn add_sort_for_unproven_ordering(
+ plan: Arc<dyn ExecutionPlan>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ let requirements = plan.required_input_ordering();
+ if requirements.iter().all(Option::is_none) {
+ return Ok(Transformed::no(plan));
+ }
+ let mut children: Vec<_> = plan.children().into_iter().cloned().collect();
+ let mut changed = false;
+ for (child, requirement) in children.iter_mut().zip(requirements) {
+ let Some(requirement) = requirement else {
+ continue;
+ };
+ let requirement = requirement.into_single();
+ let eq_properties = child.equivalence_properties();
+ if eq_properties.ordering_satisfy_requirement(requirement.clone())? {
+ continue;
+ }
+ let sort_reqs: Vec<_> = requirement.clone().into();
+ let sort_exprs = sort_reqs
+ .into_iter()
+ .filter(|req| eq_properties.is_expr_constant(&req.expr).is_none())
+ .map(Into::into);
+ let Some(ordering) = LexOrdering::new(sort_exprs) else {
+ continue;
+ };
+ let sort: Arc<dyn ExecutionPlan> = Arc::new(
+ SortExec::new(ordering, Arc::clone(child)).with_preserve_partitioning(
+ child.output_partitioning().partition_count() > 1,
+ ),
+ );
+ if !sort
+ .equivalence_properties()
+ .ordering_satisfy_requirement(requirement)?
+ {
+ continue;
Review Comment:
This no longer applies: following your comment on the root cause, the EnsureRequirements step is removed and the PR fixes the join instead.
##########
datafusion/physical-optimizer/src/ensure_requirements/mod.rs:
##########
@@ -267,10 +279,15 @@ impl PhysicalOptimizerRule for EnsureRequirements {
assign_initial_requirements(&mut sort_pushdown);
let adjusted = pushdown_sorts(sort_pushdown)?;
- // 3d: Partial sort
- adjusted
+ // 3d: Sort where an ordering requirement cannot be proven
+ use super::enforce_sorting::add_sort_for_unproven_ordering;
+ let plan = adjusted
.plan
Review Comment:
This no longer applies: following your comment on the root cause, the EnsureRequirements step is removed and the PR fixes the join instead.
--
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: keep probe-side constants in join equivalence properties [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on PR #26459:
URL: https://github.com/apache/datafusion/pull/26459#issuecomment-6291069228
run sql_planner
--
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: keep probe-side constants in join equivalence properties [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on code in PR #26459:
URL: https://github.com/apache/datafusion/pull/26459#discussion_r4324942456
##########
datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs:
##########
@@ -232,6 +235,71 @@ pub fn replace_with_partial_sort(
Ok(plan)
}
+/// Adds a [`SortExec`] below every node whose ordering requirement is not
+/// satisfied by its child's equivalence properties.
+///
+/// [`pushdown_sorts`] removes a sort when it can map the requirement onto a
+/// descendant that satisfies it. That mapping is computed separately from the
+/// equivalence properties of the operators in between, and the two can
+/// disagree. The plan may then be correct, but its properties cannot show it,
+/// and `SanityCheckPlan` rejects it. Adding the sort back keeps every plan
+/// produced by `EnsureRequirements` valid by the same check.
+///
+/// A requirement that a new [`SortExec`] still cannot satisfy is left as is,
+/// for `SanityCheckPlan` to report.
+///
+/// [`pushdown_sorts`]: sort_pushdown::pushdown_sorts
+pub fn add_sort_for_unproven_ordering(
+ plan: Arc<dyn ExecutionPlan>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ let requirements = plan.required_input_ordering();
+ if requirements.iter().all(Option::is_none) {
+ return Ok(Transformed::no(plan));
+ }
+ let mut children: Vec<_> = plan.children().into_iter().cloned().collect();
+ let mut changed = false;
+ for (child, requirement) in children.iter_mut().zip(requirements) {
+ let Some(requirement) = requirement else {
+ continue;
+ };
+ let requirement = requirement.into_single();
+ let eq_properties = child.equivalence_properties();
+ if eq_properties.ordering_satisfy_requirement(requirement.clone())? {
+ continue;
+ }
+ let sort_reqs: Vec<_> = requirement.clone().into();
+ let sort_exprs = sort_reqs
+ .into_iter()
+ .filter(|req| eq_properties.is_expr_constant(&req.expr).is_none())
+ .map(Into::into);
+ let Some(ordering) = LexOrdering::new(sort_exprs) else {
+ continue;
+ };
+ let sort: Arc<dyn ExecutionPlan> = Arc::new(
+ SortExec::new(ordering, Arc::clone(child)).with_preserve_partitioning(
+ child.output_partitioning().partition_count() > 1,
+ ),
+ );
+ if !sort
+ .equivalence_properties()
+ .ordering_satisfy_requirement(requirement)?
+ {
+ continue;
+ }
+ *child = sort;
+ changed = true;
+ }
+ if changed {
+ plan.replace_children(
Review Comment:
This no longer applies: following your comment on the root cause, the EnsureRequirements step is removed in 05e298eb04, and the PR fixes the join instead.
##########
datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs:
##########
@@ -232,6 +235,71 @@ pub fn replace_with_partial_sort(
Ok(plan)
}
+/// Adds a [`SortExec`] below every node whose ordering requirement is not
+/// satisfied by its child's equivalence properties.
+///
+/// [`pushdown_sorts`] removes a sort when it can map the requirement onto a
+/// descendant that satisfies it. That mapping is computed separately from the
+/// equivalence properties of the operators in between, and the two can
+/// disagree. The plan may then be correct, but its properties cannot show it,
+/// and `SanityCheckPlan` rejects it. Adding the sort back keeps every plan
+/// produced by `EnsureRequirements` valid by the same check.
+///
+/// A requirement that a new [`SortExec`] still cannot satisfy is left as is,
+/// for `SanityCheckPlan` to report.
+///
+/// [`pushdown_sorts`]: sort_pushdown::pushdown_sorts
+pub fn add_sort_for_unproven_ordering(
+ plan: Arc<dyn ExecutionPlan>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ let requirements = plan.required_input_ordering();
+ if requirements.iter().all(Option::is_none) {
+ return Ok(Transformed::no(plan));
+ }
+ let mut children: Vec<_> = plan.children().into_iter().cloned().collect();
+ let mut changed = false;
+ for (child, requirement) in children.iter_mut().zip(requirements) {
+ let Some(requirement) = requirement else {
+ continue;
+ };
+ let requirement = requirement.into_single();
+ let eq_properties = child.equivalence_properties();
+ if eq_properties.ordering_satisfy_requirement(requirement.clone())? {
+ continue;
+ }
+ let sort_reqs: Vec<_> = requirement.clone().into();
+ let sort_exprs = sort_reqs
+ .into_iter()
+ .filter(|req| eq_properties.is_expr_constant(&req.expr).is_none())
+ .map(Into::into);
+ let Some(ordering) = LexOrdering::new(sort_exprs) else {
+ continue;
+ };
+ let sort: Arc<dyn ExecutionPlan> = Arc::new(
Review Comment:
This no longer applies: following your comment on the root cause, the EnsureRequirements step is removed in 05e298eb04, and the PR fixes the join instead.
##########
datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs:
##########
@@ -232,6 +235,71 @@ pub fn replace_with_partial_sort(
Ok(plan)
}
+/// Adds a [`SortExec`] below every node whose ordering requirement is not
+/// satisfied by its child's equivalence properties.
+///
+/// [`pushdown_sorts`] removes a sort when it can map the requirement onto a
+/// descendant that satisfies it. That mapping is computed separately from the
+/// equivalence properties of the operators in between, and the two can
+/// disagree. The plan may then be correct, but its properties cannot show it,
+/// and `SanityCheckPlan` rejects it. Adding the sort back keeps every plan
+/// produced by `EnsureRequirements` valid by the same check.
+///
+/// A requirement that a new [`SortExec`] still cannot satisfy is left as is,
+/// for `SanityCheckPlan` to report.
+///
+/// [`pushdown_sorts`]: sort_pushdown::pushdown_sorts
+pub fn add_sort_for_unproven_ordering(
+ plan: Arc<dyn ExecutionPlan>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ let requirements = plan.required_input_ordering();
+ if requirements.iter().all(Option::is_none) {
+ return Ok(Transformed::no(plan));
+ }
+ let mut children: Vec<_> = plan.children().into_iter().cloned().collect();
+ let mut changed = false;
+ for (child, requirement) in children.iter_mut().zip(requirements) {
+ let Some(requirement) = requirement else {
+ continue;
+ };
+ let requirement = requirement.into_single();
+ let eq_properties = child.equivalence_properties();
+ if eq_properties.ordering_satisfy_requirement(requirement.clone())? {
+ continue;
+ }
+ let sort_reqs: Vec<_> = requirement.clone().into();
+ let sort_exprs = sort_reqs
+ .into_iter()
+ .filter(|req| eq_properties.is_expr_constant(&req.expr).is_none())
+ .map(Into::into);
+ let Some(ordering) = LexOrdering::new(sort_exprs) else {
+ continue;
+ };
+ let sort: Arc<dyn ExecutionPlan> = Arc::new(
+ SortExec::new(ordering, Arc::clone(child)).with_preserve_partitioning(
Review Comment:
This no longer applies, since the step is removed in 05e298eb04. For the record, `LimitPushdown` ran after it and turned the added sort into a TopK under a `LIMIT`.
##########
datafusion/sqllogictest/test_files/order.slt:
##########
@@ -2276,3 +2276,79 @@ SELECT i, -i AS n FROM (
-128 -128
-128 -128
NULL NULL
+
+# EnsureRequirements removes the sort on `k` because `k` is constant on the
+# probe side of the join, but the join output does not report `k` as constant.
+# The sort must then be kept so the plan can be checked and run.
+# https://github.com/apache/datafusion/issues/26283
+statement ok
+CREATE TABLE probe_constant_t(a INT, b INT) AS VALUES (1, 1), (2, 2), (3, 3), (4, 4);
+
+statement ok
+CREATE TABLE probe_constant_u(a INT) AS VALUES (1);
+
+statement ok
+CREATE TABLE probe_constant_v(x INT) AS VALUES (1), (2);
+
+query II
+SELECT s.k, s.a
+FROM (
+ SELECT probe_constant_t.a, -2 AS k
+ FROM probe_constant_t JOIN probe_constant_v ON probe_constant_t.b <> probe_constant_v.x
+) s
+JOIN probe_constant_u ON s.a = probe_constant_u.a
+ORDER BY s.k DESC;
+----
+-2 1
+
+query TT
+EXPLAIN SELECT s.k, s.a
+FROM (
+ SELECT probe_constant_t.a, -2 AS k
+ FROM probe_constant_t JOIN probe_constant_v ON probe_constant_t.b <> probe_constant_v.x
+) s
+JOIN probe_constant_u ON s.a = probe_constant_u.a
+ORDER BY s.k DESC;
+----
+logical_plan
+01)Sort: s.k DESC NULLS FIRST
+02)--Projection: s.k, s.a
+03)----Inner Join: s.a = probe_constant_u.a
+04)------SubqueryAlias: s
+05)--------Projection: probe_constant_t.a, Int64(-2) AS k
+06)----------Inner Join: Filter: probe_constant_t.b != probe_constant_v.x
+07)------------TableScan: probe_constant_t projection=[a, b]
+08)------------TableScan: probe_constant_v projection=[x]
+09)------TableScan: probe_constant_u projection=[a]
+physical_plan
+01)SortPreservingMergeExec: [k@0 DESC]
+02)--SortExec: expr=[k@0 DESC], preserve_partitioning=[true]
+03)----HashJoinExec: mode=CollectLeft, join_type=Inner, on=[(a@0, a@0)], projection=[k@2, a@1]
+04)------DataSourceExec: partitions=1, partition_sizes=[1]
+05)------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
+06)--------ProjectionExec: expr=[a@0 as a, -2 as k]
+07)----------NestedLoopJoinExec: join_type=Inner, filter=b@0 != x@1, projection=[a@1]
+08)------------DataSourceExec: partitions=1, partition_sizes=[1]
+09)------------DataSourceExec: partitions=1, partition_sizes=[1]
+
+statement ok
+SET datafusion.execution.target_partitions = 1;
+
+query ITI
+SELECT s.a, s.k, row_number() OVER (PARTITION BY s.a ORDER BY s.k) AS r
Review Comment:
Done in 33193465ae: the window query has an `EXPLAIN` now. The Rust test went away with the step it tested. A unit test in `class.rs` covers the join change, and the slt queries run the whole optimizer, `SanityCheckPlan` included.
--
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: keep a sort in EnsureRequirements when the ordering cannot be proven [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on code in PR #26459:
URL: https://github.com/apache/datafusion/pull/26459#discussion_r4307426935
##########
datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs:
##########
@@ -232,6 +235,71 @@ pub fn replace_with_partial_sort(
Ok(plan)
}
+/// Adds a [`SortExec`] below every node whose ordering requirement is not
+/// satisfied by its child's equivalence properties.
+///
+/// [`pushdown_sorts`] removes a sort when it can map the requirement onto a
+/// descendant that satisfies it. That mapping is computed separately from the
+/// equivalence properties of the operators in between, and the two can
+/// disagree. The plan may then be correct, but its properties cannot show it,
+/// and `SanityCheckPlan` rejects it. Adding the sort back keeps every plan
+/// produced by `EnsureRequirements` valid by the same check.
+///
+/// A requirement that a new [`SortExec`] still cannot satisfy is left as is,
+/// for `SanityCheckPlan` to report.
+///
+/// [`pushdown_sorts`]: sort_pushdown::pushdown_sorts
+pub fn add_sort_for_unproven_ordering(
+ plan: Arc<dyn ExecutionPlan>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ let requirements = plan.required_input_ordering();
+ if requirements.iter().all(Option::is_none) {
+ return Ok(Transformed::no(plan));
+ }
+ let mut children: Vec<_> = plan.children().into_iter().cloned().collect();
+ let mut changed = false;
+ for (child, requirement) in children.iter_mut().zip(requirements) {
+ let Some(requirement) = requirement else {
+ continue;
+ };
+ let requirement = requirement.into_single();
+ let eq_properties = child.equivalence_properties();
+ if eq_properties.ordering_satisfy_requirement(requirement.clone())? {
+ continue;
+ }
+ let sort_reqs: Vec<_> = requirement.clone().into();
+ let sort_exprs = sort_reqs
+ .into_iter()
+ .filter(|req| eq_properties.is_expr_constant(&req.expr).is_none())
+ .map(Into::into);
+ let Some(ordering) = LexOrdering::new(sort_exprs) else {
+ continue;
+ };
+ let sort: Arc<dyn ExecutionPlan> = Arc::new(
+ SortExec::new(ordering, Arc::clone(child)).with_preserve_partitioning(
+ child.output_partitioning().partition_count() > 1,
+ ),
Review Comment:
**Share the existing sort-construction logic**
The constant-key filtering, requirement conversion, and partition-preservation logic duplicate `add_sort_above` and `add_sort_above_with_distribution` in `utils.rs`. Adding another implementation means future fixes to these behaviors must reach three separate paths. Extract a shared constructor that accepts an execution plan, while retaining this helper's additional satisfaction check.
##########
datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs:
##########
@@ -232,6 +235,71 @@ pub fn replace_with_partial_sort(
Ok(plan)
}
+/// Adds a [`SortExec`] below every node whose ordering requirement is not
+/// satisfied by its child's equivalence properties.
+///
+/// [`pushdown_sorts`] removes a sort when it can map the requirement onto a
+/// descendant that satisfies it. That mapping is computed separately from the
+/// equivalence properties of the operators in between, and the two can
+/// disagree. The plan may then be correct, but its properties cannot show it,
+/// and `SanityCheckPlan` rejects it. Adding the sort back keeps every plan
+/// produced by `EnsureRequirements` valid by the same check.
+///
+/// A requirement that a new [`SortExec`] still cannot satisfy is left as is,
+/// for `SanityCheckPlan` to report.
+///
+/// [`pushdown_sorts`]: sort_pushdown::pushdown_sorts
+pub fn add_sort_for_unproven_ordering(
+ plan: Arc<dyn ExecutionPlan>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ let requirements = plan.required_input_ordering();
+ if requirements.iter().all(Option::is_none) {
+ return Ok(Transformed::no(plan));
+ }
+ let mut children: Vec<_> = plan.children().into_iter().cloned().collect();
+ let mut changed = false;
+ for (child, requirement) in children.iter_mut().zip(requirements) {
+ let Some(requirement) = requirement else {
+ continue;
+ };
+ let requirement = requirement.into_single();
+ let eq_properties = child.equivalence_properties();
+ if eq_properties.ordering_satisfy_requirement(requirement.clone())? {
+ continue;
+ }
+ let sort_reqs: Vec<_> = requirement.clone().into();
+ let sort_exprs = sort_reqs
+ .into_iter()
+ .filter(|req| eq_properties.is_expr_constant(&req.expr).is_none())
+ .map(Into::into);
+ let Some(ordering) = LexOrdering::new(sort_exprs) else {
+ continue;
+ };
+ let sort: Arc<dyn ExecutionPlan> = Arc::new(
+ SortExec::new(ordering, Arc::clone(child)).with_preserve_partitioning(
+ child.output_partitioning().partition_count() > 1,
+ ),
+ );
+ if !sort
+ .equivalence_properties()
+ .ordering_satisfy_requirement(requirement)?
+ {
+ continue;
Review Comment:
**Test the fallback when a sort cannot prove the requirement**
The added tests exercise successful repair, but none covers this explicit fallback for contradictory properties. Add a focused regression asserting that an unsatisfying candidate sort is not installed and that `SanityCheckPlan` still rejects the unchanged requirement. Otherwise, removing this guard would not be caught despite changing a documented safety behavior.
##########
datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs:
##########
@@ -232,6 +235,71 @@ pub fn replace_with_partial_sort(
Ok(plan)
}
+/// Adds a [`SortExec`] below every node whose ordering requirement is not
+/// satisfied by its child's equivalence properties.
+///
+/// [`pushdown_sorts`] removes a sort when it can map the requirement onto a
+/// descendant that satisfies it. That mapping is computed separately from the
+/// equivalence properties of the operators in between, and the two can
+/// disagree. The plan may then be correct, but its properties cannot show it,
+/// and `SanityCheckPlan` rejects it. Adding the sort back keeps every plan
+/// produced by `EnsureRequirements` valid by the same check.
+///
+/// A requirement that a new [`SortExec`] still cannot satisfy is left as is,
+/// for `SanityCheckPlan` to report.
+///
+/// [`pushdown_sorts`]: sort_pushdown::pushdown_sorts
+pub fn add_sort_for_unproven_ordering(
+ plan: Arc<dyn ExecutionPlan>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ let requirements = plan.required_input_ordering();
+ if requirements.iter().all(Option::is_none) {
+ return Ok(Transformed::no(plan));
+ }
+ let mut children: Vec<_> = plan.children().into_iter().cloned().collect();
+ let mut changed = false;
+ for (child, requirement) in children.iter_mut().zip(requirements) {
+ let Some(requirement) = requirement else {
+ continue;
+ };
+ let requirement = requirement.into_single();
+ let eq_properties = child.equivalence_properties();
+ if eq_properties.ordering_satisfy_requirement(requirement.clone())? {
+ continue;
+ }
+ let sort_reqs: Vec<_> = requirement.clone().into();
Review Comment:
This re-implements add_sort_above / add_sort_above_with_check from physical-optimizer/src/utils.rs:38-128: the same constant-key filter, LexOrdering::new None check, and preserve_partitioning-if-multi-partition logic.
##########
datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs:
##########
@@ -232,6 +235,71 @@ pub fn replace_with_partial_sort(
Ok(plan)
}
+/// Adds a [`SortExec`] below every node whose ordering requirement is not
+/// satisfied by its child's equivalence properties.
+///
+/// [`pushdown_sorts`] removes a sort when it can map the requirement onto a
+/// descendant that satisfies it. That mapping is computed separately from the
+/// equivalence properties of the operators in between, and the two can
+/// disagree. The plan may then be correct, but its properties cannot show it,
+/// and `SanityCheckPlan` rejects it. Adding the sort back keeps every plan
+/// produced by `EnsureRequirements` valid by the same check.
+///
+/// A requirement that a new [`SortExec`] still cannot satisfy is left as is,
+/// for `SanityCheckPlan` to report.
+///
+/// [`pushdown_sorts`]: sort_pushdown::pushdown_sorts
+pub fn add_sort_for_unproven_ordering(
+ plan: Arc<dyn ExecutionPlan>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ let requirements = plan.required_input_ordering();
+ if requirements.iter().all(Option::is_none) {
+ return Ok(Transformed::no(plan));
+ }
+ let mut children: Vec<_> = plan.children().into_iter().cloned().collect();
+ let mut changed = false;
+ for (child, requirement) in children.iter_mut().zip(requirements) {
+ let Some(requirement) = requirement else {
+ continue;
+ };
+ let requirement = requirement.into_single();
+ let eq_properties = child.equivalence_properties();
+ if eq_properties.ordering_satisfy_requirement(requirement.clone())? {
+ continue;
+ }
+ let sort_reqs: Vec<_> = requirement.clone().into();
+ let sort_exprs = sort_reqs
+ .into_iter()
+ .filter(|req| eq_properties.is_expr_constant(&req.expr).is_none())
+ .map(Into::into);
+ let Some(ordering) = LexOrdering::new(sort_exprs) else {
+ continue;
+ };
+ let sort: Arc<dyn ExecutionPlan> = Arc::new(
+ SortExec::new(ordering, Arc::clone(child)).with_preserve_partitioning(
+ child.output_partitioning().partition_count() > 1,
+ ),
+ );
+ if !sort
+ .equivalence_properties()
+ .ordering_satisfy_requirement(requirement)?
+ {
+ continue;
+ }
+ *child = sort;
+ changed = true;
+ }
+ if changed {
+ plan.replace_children(
Review Comment:
After replace_children(Recompute), nodes such as AggregateExec and BoundedWindowAggExec recompute required_input_ordering (ordered_partition_by_indices, the soft aggregate requirement) from the new child, but the new node's requirement is never checked again.
##########
datafusion/physical-optimizer/src/ensure_requirements/mod.rs:
##########
@@ -267,10 +279,15 @@ impl PhysicalOptimizerRule for EnsureRequirements {
assign_initial_requirements(&mut sort_pushdown);
let adjusted = pushdown_sorts(sort_pushdown)?;
- // 3d: Partial sort
- adjusted
+ // 3d: Sort where an ordering requirement cannot be proven
+ use super::enforce_sorting::add_sort_for_unproven_ordering;
+ let plan = adjusted
.plan
Review Comment:
add_sort_for_unproven_ordering runs after parallelize_sorts (3a) and replace_with_order_preserving_variants (3b), so a sort it adds never gets those rewrites.
##########
datafusion/physical-optimizer/src/ensure_requirements/mod.rs:
##########
@@ -267,10 +279,15 @@ impl PhysicalOptimizerRule for EnsureRequirements {
assign_initial_requirements(&mut sort_pushdown);
let adjusted = pushdown_sorts(sort_pushdown)?;
- // 3d: Partial sort
- adjusted
+ // 3d: Sort where an ordering requirement cannot be proven
Review Comment:
The fix patches the symptom in EnsureRequirements, not the cause: EquivalenceClass::try_with_offset (physical-expr/src/equivalence/class.rs:249) starts from Self::default() and never copies `constant`, so EquivalenceGroup::join drops every probe-side (right) constant, and is_trivial() then deletes the single-member class.
##########
datafusion/physical-optimizer/src/ensure_requirements/mod.rs:
##########
@@ -69,6 +70,17 @@
//! <https://github.com/apache/datafusion/issues/21973>, where the old
//! two-rule pipeline could regress a parallel sort plan into a serial one
//! on pass 2.
+//! - **Requirements are provable**: Every ordering requirement in the
+//! output is satisfied according to the children's
+//! [`EquivalenceProperties`], the same check `SanityCheckPlan` applies.
+//! `pushdown_sorts` removes a sort when it can map the requirement onto a
+//! descendant that satisfies it, but the operators in between can report
+//! weaker properties than that mapping assumed (for example, a hash join
+//! that forgets a probe-side column is constant). Phase 3 then adds a sort
+//! where the requirement cannot be proven, so the rule never emits a plan
+//! that it cannot show to be valid.
Review Comment:
Qualify the guarantee that all ordering requirements are proven
For contradictory equivalence properties, `add_sort_for_unproven_ordering` deliberately leaves an unsatisfied requirement unchanged when even the candidate sort cannot satisfy it. This contradicts the new claim that the rule never emits an unprovable plan. Document this exception here, consistent with the helper's documentation, so callers do not mistake this pass for successful validation.
##########
datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs:
##########
@@ -232,6 +235,71 @@ pub fn replace_with_partial_sort(
Ok(plan)
}
+/// Adds a [`SortExec`] below every node whose ordering requirement is not
+/// satisfied by its child's equivalence properties.
+///
+/// [`pushdown_sorts`] removes a sort when it can map the requirement onto a
+/// descendant that satisfies it. That mapping is computed separately from the
+/// equivalence properties of the operators in between, and the two can
+/// disagree. The plan may then be correct, but its properties cannot show it,
+/// and `SanityCheckPlan` rejects it. Adding the sort back keeps every plan
+/// produced by `EnsureRequirements` valid by the same check.
+///
+/// A requirement that a new [`SortExec`] still cannot satisfy is left as is,
+/// for `SanityCheckPlan` to report.
+///
+/// [`pushdown_sorts`]: sort_pushdown::pushdown_sorts
+pub fn add_sort_for_unproven_ordering(
+ plan: Arc<dyn ExecutionPlan>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ let requirements = plan.required_input_ordering();
+ if requirements.iter().all(Option::is_none) {
+ return Ok(Transformed::no(plan));
+ }
+ let mut children: Vec<_> = plan.children().into_iter().cloned().collect();
+ let mut changed = false;
+ for (child, requirement) in children.iter_mut().zip(requirements) {
+ let Some(requirement) = requirement else {
+ continue;
+ };
+ let requirement = requirement.into_single();
+ let eq_properties = child.equivalence_properties();
+ if eq_properties.ordering_satisfy_requirement(requirement.clone())? {
+ continue;
+ }
+ let sort_reqs: Vec<_> = requirement.clone().into();
+ let sort_exprs = sort_reqs
+ .into_iter()
+ .filter(|req| eq_properties.is_expr_constant(&req.expr).is_none())
+ .map(Into::into);
+ let Some(ordering) = LexOrdering::new(sort_exprs) else {
+ continue;
+ };
+ let sort: Arc<dyn ExecutionPlan> = Arc::new(
Review Comment:
The new SortExec is always stacked on top of the child, even when the child is already a SortExec (without fetch) whose ordering is wrong or too weak, and the misplaced sort left lower in the plan by pushdown_sorts is never removed.
##########
datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs:
##########
@@ -232,6 +235,71 @@ pub fn replace_with_partial_sort(
Ok(plan)
}
+/// Adds a [`SortExec`] below every node whose ordering requirement is not
+/// satisfied by its child's equivalence properties.
+///
+/// [`pushdown_sorts`] removes a sort when it can map the requirement onto a
+/// descendant that satisfies it. That mapping is computed separately from the
+/// equivalence properties of the operators in between, and the two can
+/// disagree. The plan may then be correct, but its properties cannot show it,
+/// and `SanityCheckPlan` rejects it. Adding the sort back keeps every plan
+/// produced by `EnsureRequirements` valid by the same check.
+///
+/// A requirement that a new [`SortExec`] still cannot satisfy is left as is,
+/// for `SanityCheckPlan` to report.
+///
+/// [`pushdown_sorts`]: sort_pushdown::pushdown_sorts
+pub fn add_sort_for_unproven_ordering(
+ plan: Arc<dyn ExecutionPlan>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ let requirements = plan.required_input_ordering();
+ if requirements.iter().all(Option::is_none) {
+ return Ok(Transformed::no(plan));
+ }
+ let mut children: Vec<_> = plan.children().into_iter().cloned().collect();
+ let mut changed = false;
+ for (child, requirement) in children.iter_mut().zip(requirements) {
+ let Some(requirement) = requirement else {
+ continue;
+ };
+ let requirement = requirement.into_single();
+ let eq_properties = child.equivalence_properties();
+ if eq_properties.ordering_satisfy_requirement(requirement.clone())? {
+ continue;
+ }
+ let sort_reqs: Vec<_> = requirement.clone().into();
+ let sort_exprs = sort_reqs
+ .into_iter()
+ .filter(|req| eq_properties.is_expr_constant(&req.expr).is_none())
+ .map(Into::into);
+ let Some(ordering) = LexOrdering::new(sort_exprs) else {
+ continue;
+ };
+ let sort: Arc<dyn ExecutionPlan> = Arc::new(
+ SortExec::new(ordering, Arc::clone(child)).with_preserve_partitioning(
Review Comment:
The added SortExec never carries a fetch, even when the requiring parent (SortPreservingMergeExec / OutputRequirementExec) has one or the sort that pushdown_sorts removed was a TopK.
##########
datafusion/sqllogictest/test_files/order.slt:
##########
@@ -2276,3 +2276,79 @@ SELECT i, -i AS n FROM (
-128 -128
-128 -128
NULL NULL
+
+# EnsureRequirements removes the sort on `k` because `k` is constant on the
+# probe side of the join, but the join output does not report `k` as constant.
+# The sort must then be kept so the plan can be checked and run.
+# https://github.com/apache/datafusion/issues/26283
+statement ok
+CREATE TABLE probe_constant_t(a INT, b INT) AS VALUES (1, 1), (2, 2), (3, 3), (4, 4);
+
+statement ok
+CREATE TABLE probe_constant_u(a INT) AS VALUES (1);
+
+statement ok
+CREATE TABLE probe_constant_v(x INT) AS VALUES (1), (2);
+
+query II
+SELECT s.k, s.a
+FROM (
+ SELECT probe_constant_t.a, -2 AS k
+ FROM probe_constant_t JOIN probe_constant_v ON probe_constant_t.b <> probe_constant_v.x
+) s
+JOIN probe_constant_u ON s.a = probe_constant_u.a
+ORDER BY s.k DESC;
+----
+-2 1
+
+query TT
+EXPLAIN SELECT s.k, s.a
+FROM (
+ SELECT probe_constant_t.a, -2 AS k
+ FROM probe_constant_t JOIN probe_constant_v ON probe_constant_t.b <> probe_constant_v.x
+) s
+JOIN probe_constant_u ON s.a = probe_constant_u.a
+ORDER BY s.k DESC;
+----
+logical_plan
+01)Sort: s.k DESC NULLS FIRST
+02)--Projection: s.k, s.a
+03)----Inner Join: s.a = probe_constant_u.a
+04)------SubqueryAlias: s
+05)--------Projection: probe_constant_t.a, Int64(-2) AS k
+06)----------Inner Join: Filter: probe_constant_t.b != probe_constant_v.x
+07)------------TableScan: probe_constant_t projection=[a, b]
+08)------------TableScan: probe_constant_v projection=[x]
+09)------TableScan: probe_constant_u projection=[a]
+physical_plan
+01)SortPreservingMergeExec: [k@0 DESC]
+02)--SortExec: expr=[k@0 DESC], preserve_partitioning=[true]
+03)----HashJoinExec: mode=CollectLeft, join_type=Inner, on=[(a@0, a@0)], projection=[k@2, a@1]
+04)------DataSourceExec: partitions=1, partition_sizes=[1]
+05)------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
+06)--------ProjectionExec: expr=[a@0 as a, -2 as k]
+07)----------NestedLoopJoinExec: join_type=Inner, filter=b@0 != x@1, projection=[a@1]
+08)------------DataSourceExec: partitions=1, partition_sizes=[1]
+09)------------DataSourceExec: partitions=1, partition_sizes=[1]
+
+statement ok
+SET datafusion.execution.target_partitions = 1;
+
+query ITI
+SELECT s.a, s.k, row_number() OVER (PARTITION BY s.a ORDER BY s.k) AS r
Review Comment:
The second regression query (window over a probe-side constant at target_partitions=1) only checks results, with no EXPLAIN. The Rust test only checks idempotency up to EnsureRequirements and never runs SanityCheckPlan or the later rules.
--
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: keep probe-side constants in join equivalence properties [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on code in PR #26459:
URL: https://github.com/apache/datafusion/pull/26459#discussion_r4324943045
##########
datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs:
##########
@@ -232,6 +235,71 @@ pub fn replace_with_partial_sort(
Ok(plan)
}
+/// Adds a [`SortExec`] below every node whose ordering requirement is not
+/// satisfied by its child's equivalence properties.
+///
+/// [`pushdown_sorts`] removes a sort when it can map the requirement onto a
+/// descendant that satisfies it. That mapping is computed separately from the
+/// equivalence properties of the operators in between, and the two can
+/// disagree. The plan may then be correct, but its properties cannot show it,
+/// and `SanityCheckPlan` rejects it. Adding the sort back keeps every plan
+/// produced by `EnsureRequirements` valid by the same check.
+///
+/// A requirement that a new [`SortExec`] still cannot satisfy is left as is,
+/// for `SanityCheckPlan` to report.
+///
+/// [`pushdown_sorts`]: sort_pushdown::pushdown_sorts
+pub fn add_sort_for_unproven_ordering(
+ plan: Arc<dyn ExecutionPlan>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ let requirements = plan.required_input_ordering();
+ if requirements.iter().all(Option::is_none) {
+ return Ok(Transformed::no(plan));
+ }
+ let mut children: Vec<_> = plan.children().into_iter().cloned().collect();
+ let mut changed = false;
+ for (child, requirement) in children.iter_mut().zip(requirements) {
+ let Some(requirement) = requirement else {
+ continue;
+ };
+ let requirement = requirement.into_single();
+ let eq_properties = child.equivalence_properties();
+ if eq_properties.ordering_satisfy_requirement(requirement.clone())? {
+ continue;
+ }
+ let sort_reqs: Vec<_> = requirement.clone().into();
+ let sort_exprs = sort_reqs
+ .into_iter()
+ .filter(|req| eq_properties.is_expr_constant(&req.expr).is_none())
+ .map(Into::into);
+ let Some(ordering) = LexOrdering::new(sort_exprs) else {
+ continue;
+ };
+ let sort: Arc<dyn ExecutionPlan> = Arc::new(
+ SortExec::new(ordering, Arc::clone(child)).with_preserve_partitioning(
Review Comment:
This no longer applies, since the step is removed. For the record, `LimitPushdown` ran after it and turned the added sort into a TopK under a `LIMIT`.
##########
datafusion/sqllogictest/test_files/order.slt:
##########
@@ -2276,3 +2276,79 @@ SELECT i, -i AS n FROM (
-128 -128
-128 -128
NULL NULL
+
+# EnsureRequirements removes the sort on `k` because `k` is constant on the
+# probe side of the join, but the join output does not report `k` as constant.
+# The sort must then be kept so the plan can be checked and run.
+# https://github.com/apache/datafusion/issues/26283
+statement ok
+CREATE TABLE probe_constant_t(a INT, b INT) AS VALUES (1, 1), (2, 2), (3, 3), (4, 4);
+
+statement ok
+CREATE TABLE probe_constant_u(a INT) AS VALUES (1);
+
+statement ok
+CREATE TABLE probe_constant_v(x INT) AS VALUES (1), (2);
+
+query II
+SELECT s.k, s.a
+FROM (
+ SELECT probe_constant_t.a, -2 AS k
+ FROM probe_constant_t JOIN probe_constant_v ON probe_constant_t.b <> probe_constant_v.x
+) s
+JOIN probe_constant_u ON s.a = probe_constant_u.a
+ORDER BY s.k DESC;
+----
+-2 1
+
+query TT
+EXPLAIN SELECT s.k, s.a
+FROM (
+ SELECT probe_constant_t.a, -2 AS k
+ FROM probe_constant_t JOIN probe_constant_v ON probe_constant_t.b <> probe_constant_v.x
+) s
+JOIN probe_constant_u ON s.a = probe_constant_u.a
+ORDER BY s.k DESC;
+----
+logical_plan
+01)Sort: s.k DESC NULLS FIRST
+02)--Projection: s.k, s.a
+03)----Inner Join: s.a = probe_constant_u.a
+04)------SubqueryAlias: s
+05)--------Projection: probe_constant_t.a, Int64(-2) AS k
+06)----------Inner Join: Filter: probe_constant_t.b != probe_constant_v.x
+07)------------TableScan: probe_constant_t projection=[a, b]
+08)------------TableScan: probe_constant_v projection=[x]
+09)------TableScan: probe_constant_u projection=[a]
+physical_plan
+01)SortPreservingMergeExec: [k@0 DESC]
+02)--SortExec: expr=[k@0 DESC], preserve_partitioning=[true]
+03)----HashJoinExec: mode=CollectLeft, join_type=Inner, on=[(a@0, a@0)], projection=[k@2, a@1]
+04)------DataSourceExec: partitions=1, partition_sizes=[1]
+05)------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
+06)--------ProjectionExec: expr=[a@0 as a, -2 as k]
+07)----------NestedLoopJoinExec: join_type=Inner, filter=b@0 != x@1, projection=[a@1]
+08)------------DataSourceExec: partitions=1, partition_sizes=[1]
+09)------------DataSourceExec: partitions=1, partition_sizes=[1]
+
+statement ok
+SET datafusion.execution.target_partitions = 1;
+
+query ITI
+SELECT s.a, s.k, row_number() OVER (PARTITION BY s.a ORDER BY s.k) AS r
Review Comment:
The window query has an `EXPLAIN` now. The Rust test went away with the step it tested. A unit test in `class.rs` covers the join change, and the slt queries run the whole optimizer, `SanityCheckPlan` included.
--
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: keep probe-side constants in join equivalence properties [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on code in PR #26459:
URL: https://github.com/apache/datafusion/pull/26459#discussion_r4324940273
##########
datafusion/physical-optimizer/src/ensure_requirements/mod.rs:
##########
@@ -267,10 +279,15 @@ impl PhysicalOptimizerRule for EnsureRequirements {
assign_initial_requirements(&mut sort_pushdown);
let adjusted = pushdown_sorts(sort_pushdown)?;
- // 3d: Partial sort
- adjusted
+ // 3d: Sort where an ordering requirement cannot be proven
Review Comment:
Copying the constant in `try_with_offset` fixes both queries, and the plan no longer needs a sort on `k` at all. One caveat: for Left and Full joins, unmatched rows pad the right side with NULLs, so its constants have to be cleared there, or a sort that is needed gets dropped. There is a test for that case now. The PR now fixes the join instead of adding the EnsureRequirements step.
The left side has the same problem for Right and Full joins: its constants survive the NULL padding and can give wrongly ordered results. #26042 already rebuilds the classes of the side padded with NULLs, which covers that, so I left the left side alone here and noted it in the description.
--
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: keep probe-side constants in join equivalence properties [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #26459:
URL: https://github.com/apache/datafusion/pull/26459#issuecomment-6357757850
🤖 Benchmark completed (GKE) | [trigger](https://github.com/apache/datafusion/pull/26459#issuecomment-6356917032)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
Comparing ensure-requirements-unproven-ordering (33193465ae2873a1ac13c4ec6a171811e5d2c31c) to 290ad15 (merge-base) [diff](https://github.com/apache/datafusion/compare/290ad15cc842167ca4d3c0774ccdf3a1d9d61862..33193465ae2873a1ac13c4ec6a171811e5d2c31c)
<details><summary>Run configuration</summary>
```yaml
run benchmark sql_planner
```
</details>
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Details</summary>
<p>
```
group HEAD ensure-requirements-unproven-ordering
----- ---- -------------------------------------
logical_aggregate_with_join 1.00 342.7±1.89µs ? ?/sec 1.02 349.5±7.91µs ? ?/sec
logical_correlated_subquery_exists 1.00 202.2±0.74µs ? ?/sec 1.00 201.9±0.59µs ? ?/sec
logical_correlated_subquery_in 1.00 204.1±1.34µs ? ?/sec 1.00 205.1±1.44µs ? ?/sec
logical_distinct_many_columns 1.00 287.4±0.82µs ? ?/sec 1.00 288.1±1.64µs ? ?/sec
logical_join_4_with_agg_and_filter 1.00 188.8±1.37µs ? ?/sec 1.01 190.5±1.23µs ? ?/sec
logical_join_8_with_agg_sort_limit 1.00 333.2±0.78µs ? ?/sec 1.00 333.8±1.29µs ? ?/sec
logical_join_chain_16 1.01 614.7±2.33µs ? ?/sec 1.00 609.7±1.55µs ? ?/sec
logical_join_chain_4 1.00 72.2±0.19µs ? ?/sec 1.02 73.5±0.24µs ? ?/sec
logical_join_chain_8 1.00 196.6±0.50µs ? ?/sec 1.00 196.9±0.40µs ? ?/sec
logical_multiple_subqueries 1.01 383.5±1.71µs ? ?/sec 1.00 381.0±1.15µs ? ?/sec
logical_nested_cte_4_levels 1.01 192.6±1.19µs ? ?/sec 1.00 191.2±0.84µs ? ?/sec
logical_plan_struct_join_agg_sort 1.00 120.0±0.67µs ? ?/sec 1.01 121.7±2.61µs ? ?/sec
logical_plan_tpcds_all 1.04 74.7±2.91ms ? ?/sec 1.00 72.1±0.12ms ? ?/sec
logical_plan_tpch_all 1.04 5.3±0.13ms ? ?/sec 1.00 5.1±0.02ms ? ?/sec
logical_scalar_subquery 1.00 212.1±0.81µs ? ?/sec 1.00 211.5±0.86µs ? ?/sec
logical_select_all_from_1000 1.00 6.9±0.02ms ? ?/sec 1.00 6.9±0.13ms ? ?/sec
logical_select_one_from_700 1.00 225.6±1.64µs ? ?/sec 1.01 228.3±2.86µs ? ?/sec
logical_trivial_join_high_numbered_columns 1.00 205.0±1.34µs ? ?/sec 1.02 208.8±3.60µs ? ?/sec
logical_trivial_join_low_numbered_columns 1.00 194.5±1.26µs ? ?/sec 1.00 193.6±1.31µs ? ?/sec
logical_union_4_branches 1.00 304.3±1.66µs ? ?/sec 1.00 305.0±2.03µs ? ?/sec
logical_union_8_branches 1.01 618.7±4.69µs ? ?/sec 1.00 615.1±4.85µs ? ?/sec
logical_wide_aggregate_1000_exprs 1.01 41.9±0.28ms ? ?/sec 1.00 41.3±0.15ms ? ?/sec
logical_wide_aggregate_100_exprs 1.00 1531.7±7.81µs ? ?/sec 1.00 1534.0±3.77µs ? ?/sec
logical_wide_case_50_exprs 1.00 1690.3±4.13µs ? ?/sec 1.00 1694.3±4.65µs ? ?/sec
logical_wide_filter_200_predicates 1.00 1292.9±9.09µs ? ?/sec 1.00 1294.2±4.95µs ? ?/sec
logical_wide_filter_50_predicates 1.00 340.6±2.11µs ? ?/sec 1.00 339.7±1.46µs ? ?/sec
optimizer_correlated_exists 1.01 219.0±1.79µs ? ?/sec 1.00 216.5±0.72µs ? ?/sec
optimizer_join_4_with_agg_filter 1.00 393.3±2.90µs ? ?/sec 1.00 392.2±2.17µs ? ?/sec
optimizer_join_chain_4 1.01 156.0±1.47µs ? ?/sec 1.00 154.2±0.25µs ? ?/sec
optimizer_join_chain_8 1.00 533.1±6.80µs ? ?/sec 1.00 534.0±1.04µs ? ?/sec
optimizer_select_all_from_1000 1.03 6.9±0.12ms ? ?/sec 1.00 6.7±0.01ms ? ?/sec
optimizer_select_one_from_700 1.00 237.5±1.25µs ? ?/sec 1.00 237.1±2.28µs ? ?/sec
optimizer_tpcds_all 1.02 250.5±5.95ms ? ?/sec 1.00 245.7±0.42ms ? ?/sec
optimizer_tpch_all 1.02 15.2±0.30ms ? ?/sec 1.00 14.9±0.03ms ? ?/sec
optimizer_wide_aggregate_100 1.01 1751.5±25.02µs ? ?/sec 1.00 1741.7±3.27µs ? ?/sec
optimizer_wide_filter_200 1.02 4.1±0.06ms ? ?/sec 1.00 4.0±0.01ms ? ?/sec
physical_intersection 1.00 504.6±2.77µs ? ?/sec 1.00 504.8±5.38µs ? ?/sec
physical_join_consider_sort 1.00 953.4±1.71µs ? ?/sec 1.00 957.8±12.59µs ? ?/sec
physical_join_distinct 1.00 186.9±1.34µs ? ?/sec 1.01 188.8±2.90µs ? ?/sec
physical_many_self_joins 1.00 7.2±0.01ms ? ?/sec 1.04 7.5±0.19ms ? ?/sec
physical_plan_clickbench_all 1.01 129.8±0.28ms ? ?/sec 1.00 128.5±0.43ms ? ?/sec
physical_plan_clickbench_q1 1.00 1276.0±4.93µs ? ?/sec 1.01 1293.5±8.56µs ? ?/sec
physical_plan_clickbench_q10 1.00 1822.3±5.44µs ? ?/sec 1.02 1865.1±9.21µs ? ?/sec
physical_plan_clickbench_q11 1.00 1972.8±7.48µs ? ?/sec 1.02 2.0±0.01ms ? ?/sec
physical_plan_clickbench_q12 1.00 2.0±0.02ms ? ?/sec 1.03 2.1±0.01ms ? ?/sec
physical_plan_clickbench_q13 1.00 1865.0±6.62µs ? ?/sec 1.03 1920.5±7.57µs ? ?/sec
physical_plan_clickbench_q14 1.00 2.0±0.01ms ? ?/sec 1.00 2.0±0.01ms ? ?/sec
physical_plan_clickbench_q15 1.01 1948.9±6.40µs ? ?/sec 1.00 1921.8±7.94µs ? ?/sec
physical_plan_clickbench_q16 1.00 1650.7±3.95µs ? ?/sec 1.00 1645.0±7.54µs ? ?/sec
physical_plan_clickbench_q17 1.00 1695.4±5.14µs ? ?/sec 1.02 1734.6±8.33µs ? ?/sec
physical_plan_clickbench_q18 1.00 1534.7±4.49µs ? ?/sec 1.02 1561.1±8.00µs ? ?/sec
physical_plan_clickbench_q19 1.00 1866.2±6.07µs ? ?/sec 1.02 1894.8±8.31µs ? ?/sec
physical_plan_clickbench_q2 1.00 1651.7±5.72µs ? ?/sec 1.02 1684.6±8.02µs ? ?/sec
physical_plan_clickbench_q20 1.00 1448.7±4.10µs ? ?/sec 1.02 1480.7±9.81µs ? ?/sec
physical_plan_clickbench_q21 1.00 1660.6±4.55µs ? ?/sec 1.00 1664.0±11.62µs ? ?/sec
physical_plan_clickbench_q22 1.01 1999.6±2.86µs ? ?/sec 1.00 1986.9±10.98µs ? ?/sec
physical_plan_clickbench_q23 1.00 2.1±0.00ms ? ?/sec 1.01 2.1±0.01ms ? ?/sec
physical_plan_clickbench_q24 1.00 4.8±0.01ms ? ?/sec 1.00 4.8±0.01ms ? ?/sec
physical_plan_clickbench_q25 1.00 1767.7±5.30µs ? ?/sec 1.00 1763.3±7.46µs ? ?/sec
physical_plan_clickbench_q26 1.01 1642.8±4.20µs ? ?/sec 1.00 1623.3±13.81µs ? ?/sec
physical_plan_clickbench_q27 1.00 1776.8±5.11µs ? ?/sec 1.01 1802.8±7.25µs ? ?/sec
physical_plan_clickbench_q28 1.00 2.1±0.00ms ? ?/sec 1.02 2.1±0.01ms ? ?/sec
physical_plan_clickbench_q29 1.01 2.2±0.01ms ? ?/sec 1.00 2.2±0.01ms ? ?/sec
physical_plan_clickbench_q3 1.00 1536.5±3.69µs ? ?/sec 1.01 1552.3±6.96µs ? ?/sec
physical_plan_clickbench_q30 1.00 12.4±0.02ms ? ?/sec 1.00 12.3±0.02ms ? ?/sec
physical_plan_clickbench_q31 1.00 2.2±0.01ms ? ?/sec 1.00 2.2±0.01ms ? ?/sec
physical_plan_clickbench_q32 1.00 2.2±0.01ms ? ?/sec 1.00 2.2±0.01ms ? ?/sec
physical_plan_clickbench_q33 1.00 1853.2±4.43µs ? ?/sec 1.00 1849.4±8.80µs ? ?/sec
physical_plan_clickbench_q34 1.00 1644.1±5.07µs ? ?/sec 1.01 1665.5±7.78µs ? ?/sec
physical_plan_clickbench_q35 1.00 1704.6±4.70µs ? ?/sec 1.00 1712.8±8.51µs ? ?/sec
physical_plan_clickbench_q36 1.00 1929.9±4.86µs ? ?/sec 1.01 1952.9±9.09µs ? ?/sec
physical_plan_clickbench_q37 1.02 2.4±0.02ms ? ?/sec 1.00 2.4±0.01ms ? ?/sec
physical_plan_clickbench_q38 1.01 2.4±0.01ms ? ?/sec 1.00 2.4±0.01ms ? ?/sec
physical_plan_clickbench_q39 1.00 2.4±0.01ms ? ?/sec 1.00 2.4±0.01ms ? ?/sec
physical_plan_clickbench_q4 1.00 1387.4±4.29µs ? ?/sec 1.01 1400.2±6.89µs ? ?/sec
physical_plan_clickbench_q40 1.01 3.1±0.01ms ? ?/sec 1.00 3.0±0.02ms ? ?/sec
physical_plan_clickbench_q41 1.00 2.8±0.01ms ? ?/sec 1.00 2.7±0.01ms ? ?/sec
physical_plan_clickbench_q42 1.00 2.7±0.00ms ? ?/sec 1.01 2.7±0.01ms ? ?/sec
physical_plan_clickbench_q43 1.00 2.9±0.01ms ? ?/sec 1.02 2.9±0.01ms ? ?/sec
physical_plan_clickbench_q44 1.00 1469.0±3.78µs ? ?/sec 1.00 1462.3±6.97µs ? ?/sec
physical_plan_clickbench_q45 1.00 1455.4±4.28µs ? ?/sec 1.02 1480.0±7.75µs ? ?/sec
physical_plan_clickbench_q46 1.00 1695.9±4.44µs ? ?/sec 1.02 1724.6±7.89µs ? ?/sec
physical_plan_clickbench_q47 1.00 2.2±0.01ms ? ?/sec 1.01 2.3±0.01ms ? ?/sec
physical_plan_clickbench_q48 1.00 2.4±0.01ms ? ?/sec 1.02 2.4±0.01ms ? ?/sec
physical_plan_clickbench_q49 1.00 2.5±0.02ms ? ?/sec 1.01 2.5±0.02ms ? ?/sec
physical_plan_clickbench_q5 1.00 1479.1±3.80µs ? ?/sec 1.01 1500.0±5.88µs ? ?/sec
physical_plan_clickbench_q50 1.00 2.6±0.01ms ? ?/sec 1.01 2.6±0.02ms ? ?/sec
physical_plan_clickbench_q51 1.00 1820.6±5.29µs ? ?/sec 1.02 1850.5±8.31µs ? ?/sec
physical_plan_clickbench_q52 1.00 2.3±0.00ms ? ?/sec 1.01 2.3±0.01ms ? ?/sec
physical_plan_clickbench_q53 1.00 1636.1±6.21µs ? ?/sec 1.01 1648.2±7.52µs ? ?/sec
physical_plan_clickbench_q54 1.00 1637.6±4.38µs ? ?/sec 1.04 1701.9±8.37µs ? ?/sec
physical_plan_clickbench_q55 1.00 1589.7±4.03µs ? ?/sec 1.03 1638.0±8.09µs ? ?/sec
physical_plan_clickbench_q56 1.00 1592.1±4.55µs ? ?/sec 1.02 1620.5±7.62µs ? ?/sec
physical_plan_clickbench_q57 1.00 1742.3±5.85µs ? ?/sec 1.00 1733.7±7.63µs ? ?/sec
physical_plan_clickbench_q58 1.00 2.1±0.01ms ? ?/sec 1.01 2.1±0.01ms ? ?/sec
physical_plan_clickbench_q59 1.02 1622.7±3.93µs ? ?/sec 1.00 1596.3±9.02µs ? ?/sec
physical_plan_clickbench_q6 1.02 1507.3±4.52µs ? ?/sec 1.00 1476.5±6.82µs ? ?/sec
physical_plan_clickbench_q60 1.00 1600.5±4.98µs ? ?/sec 1.00 1594.8±7.61µs ? ?/sec
physical_plan_clickbench_q7 1.01 1349.7±3.76µs ? ?/sec 1.00 1335.9±13.06µs ? ?/sec
physical_plan_clickbench_q8 1.01 1837.3±5.53µs ? ?/sec 1.00 1810.3±9.30µs ? ?/sec
physical_plan_clickbench_q9 1.00 1783.7±9.49µs ? ?/sec 1.00 1777.7±8.95µs ? ?/sec
physical_plan_struct_join_agg_sort 1.00 1186.7±2.28µs ? ?/sec 1.03 1223.1±76.73µs ? ?/sec
physical_plan_tpcds_all 1.00 557.5±0.40ms ? ?/sec 1.00 558.3±0.81ms ? ?/sec
physical_plan_tpch_all 1.00 39.4±0.06ms ? ?/sec 1.00 39.2±0.29ms ? ?/sec
physical_plan_tpch_q1 1.00 1375.4±3.14µs ? ?/sec 1.02 1402.1±66.24µs ? ?/sec
physical_plan_tpch_q10 1.00 2.1±0.00ms ? ?/sec 1.02 2.1±0.04ms ? ?/sec
physical_plan_tpch_q11 1.00 2.1±0.00ms ? ?/sec 1.04 2.1±0.13ms ? ?/sec
physical_plan_tpch_q12 1.00 1191.1±2.36µs ? ?/sec 1.02 1218.0±79.48µs ? ?/sec
physical_plan_tpch_q13 1.00 953.8±1.87µs ? ?/sec 1.01 963.0±9.56µs ? ?/sec
physical_plan_tpch_q14 1.03 1249.2±10.78µs ? ?/sec 1.00 1216.3±2.17µs ? ?/sec
physical_plan_tpch_q16 1.04 1559.7±7.05µs ? ?/sec 1.00 1496.2±3.82µs ? ?/sec
physical_plan_tpch_q17 1.01 1525.3±5.60µs ? ?/sec 1.00 1515.9±3.55µs ? ?/sec
physical_plan_tpch_q18 1.01 1699.6±3.52µs ? ?/sec 1.00 1682.1±3.37µs ? ?/sec
physical_plan_tpch_q19 1.02 1985.0±7.17µs ? ?/sec 1.00 1944.0±5.20µs ? ?/sec
physical_plan_tpch_q2 1.00 3.2±0.00ms ? ?/sec 1.10 3.5±0.27ms ? ?/sec
physical_plan_tpch_q20 1.00 1917.6±4.22µs ? ?/sec 1.00 1909.0±2.50µs ? ?/sec
physical_plan_tpch_q21 1.01 2.4±0.00ms ? ?/sec 1.00 2.4±0.00ms ? ?/sec
physical_plan_tpch_q22 1.02 1482.6±4.19µs ? ?/sec 1.00 1450.3±2.68µs ? ?/sec
physical_plan_tpch_q3 1.00 1591.3±4.03µs ? ?/sec 1.03 1641.6±50.23µs ? ?/sec
physical_plan_tpch_q4 1.00 1040.7±2.82µs ? ?/sec 1.04 1078.3±31.35µs ? ?/sec
physical_plan_tpch_q5 1.00 2.1±0.01ms ? ?/sec 1.02 2.2±0.10ms ? ?/sec
physical_plan_tpch_q6 1.00 585.0±5.45µs ? ?/sec 1.01 592.6±13.61µs ? ?/sec
physical_plan_tpch_q7 1.01 2.5±0.02ms ? ?/sec 1.00 2.4±0.00ms ? ?/sec
physical_plan_tpch_q8 1.01 3.3±0.00ms ? ?/sec 1.00 3.3±0.02ms ? ?/sec
physical_plan_tpch_q9 1.00 2.5±0.00ms ? ?/sec 1.08 2.7±0.24ms ? ?/sec
physical_select_aggregates_from_200 1.00 7.4±0.01ms ? ?/sec 1.04 7.7±0.14ms ? ?/sec
physical_select_all_from_1000 1.00 17.0±0.09ms ? ?/sec 1.01 17.1±0.17ms ? ?/sec
physical_select_one_from_700 1.00 635.4±3.67µs ? ?/sec 1.00 637.8±9.01µs ? ?/sec
physical_sorted_union_order_by_10_int64 1.00 3.5±0.00ms ? ?/sec 1.05 3.7±0.14ms ? ?/sec
physical_sorted_union_order_by_10_uint64 1.00 6.7±0.01ms ? ?/sec 1.03 6.9±0.22ms ? ?/sec
physical_sorted_union_order_by_50_int64 1.00 77.7±0.32ms ? ?/sec 1.01 78.4±1.61ms ? ?/sec
physical_sorted_union_order_by_50_uint64 1.00 252.4±0.48ms ? ?/sec 1.06 266.8±10.50ms ? ?/sec
physical_theta_join_consider_sort 1.01 982.3±2.20µs ? ?/sec 1.00 974.9±2.31µs ? ?/sec
physical_unnest_to_join 1.00 546.6±2.44µs ? ?/sec 1.00 547.4±8.22µs ? ?/sec
physical_window_function_partition_by_12_on_values 1.02 632.0±5.57µs ? ?/sec 1.00 621.1±6.44µs ? ?/sec
physical_window_function_partition_by_30_on_values 1.00 1208.8±9.55µs ? ?/sec 1.00 1203.2±32.20µs ? ?/sec
physical_window_function_partition_by_4_on_values 1.00 385.2±3.30µs ? ?/sec 1.00 384.2±7.12µs ? ?/sec
physical_window_function_partition_by_7_on_values 1.01 476.4±1.58µs ? ?/sec 1.00 469.5±6.95µs ? ?/sec
physical_window_function_partition_by_8_on_values 1.00 507.6±1.32µs ? ?/sec 1.00 507.6±6.12µs ? ?/sec
with_param_values_many_columns 1.00 367.8±1.53µs ? ?/sec 1.00 368.3±1.60µs ? ?/sec
```
</p>
</details>
<details><summary>Resource Usage</summary>
**sql_planner — base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 1845.4s |
| Peak memory | 145.1 MiB |
| Avg memory | 103.4 MiB |
| CPU user | 1974.6s |
| CPU sys | 1.4s |
| Peak spill | 0 B |
**sql_planner — branch**
| Metric | Value |
|--------|-------|
| Wall time | 2080.5s |
| Peak memory | 141.0 MiB |
| Avg memory | 89.4 MiB |
| CPU user | 1974.2s |
| CPU sys | 1.6s |
| Peak spill | 0 B |
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: keep probe-side constants in join equivalence properties [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on code in PR #26459:
URL: https://github.com/apache/datafusion/pull/26459#discussion_r4324940273
##########
datafusion/physical-optimizer/src/ensure_requirements/mod.rs:
##########
@@ -267,10 +279,15 @@ impl PhysicalOptimizerRule for EnsureRequirements {
assign_initial_requirements(&mut sort_pushdown);
let adjusted = pushdown_sorts(sort_pushdown)?;
- // 3d: Partial sort
- adjusted
+ // 3d: Sort where an ordering requirement cannot be proven
Review Comment:
You're right, thanks. Copying the constant in `try_with_offset` fixes both queries, and the plan no longer needs a sort on `k` at all. One caveat: for Left and Full joins, unmatched rows pad the right side with NULLs, so its constants have to be cleared there, or a sort that is needed gets dropped. There is a test for that case now. The EnsureRequirements step is removed in 05e298eb04, and the join is fixed in 33193465ae.
The left side has the same problem for Right and Full joins: its constants survive the NULL padding and can give wrongly ordered results. #26042 already rebuilds the classes of the side padded with NULLs, which covers that, so I left the left side alone here and noted it in the description.
##########
datafusion/physical-optimizer/src/ensure_requirements/mod.rs:
##########
@@ -69,6 +70,17 @@
//! <https://github.com/apache/datafusion/issues/21973>, where the old
//! two-rule pipeline could regress a parallel sort plan into a serial one
//! on pass 2.
+//! - **Requirements are provable**: Every ordering requirement in the
+//! output is satisfied according to the children's
+//! [`EquivalenceProperties`], the same check `SanityCheckPlan` applies.
+//! `pushdown_sorts` removes a sort when it can map the requirement onto a
+//! descendant that satisfies it, but the operators in between can report
+//! weaker properties than that mapping assumed (for example, a hash join
+//! that forgets a probe-side column is constant). Phase 3 then adds a sort
+//! where the requirement cannot be proven, so the rule never emits a plan
+//! that it cannot show to be valid.
Review Comment:
This no longer applies: following your comment on the root cause, the EnsureRequirements step is removed in 05e298eb04, and the PR fixes the join instead.
##########
datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs:
##########
@@ -232,6 +235,71 @@ pub fn replace_with_partial_sort(
Ok(plan)
}
+/// Adds a [`SortExec`] below every node whose ordering requirement is not
+/// satisfied by its child's equivalence properties.
+///
+/// [`pushdown_sorts`] removes a sort when it can map the requirement onto a
+/// descendant that satisfies it. That mapping is computed separately from the
+/// equivalence properties of the operators in between, and the two can
+/// disagree. The plan may then be correct, but its properties cannot show it,
+/// and `SanityCheckPlan` rejects it. Adding the sort back keeps every plan
+/// produced by `EnsureRequirements` valid by the same check.
+///
+/// A requirement that a new [`SortExec`] still cannot satisfy is left as is,
+/// for `SanityCheckPlan` to report.
+///
+/// [`pushdown_sorts`]: sort_pushdown::pushdown_sorts
+pub fn add_sort_for_unproven_ordering(
+ plan: Arc<dyn ExecutionPlan>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ let requirements = plan.required_input_ordering();
+ if requirements.iter().all(Option::is_none) {
+ return Ok(Transformed::no(plan));
+ }
+ let mut children: Vec<_> = plan.children().into_iter().cloned().collect();
+ let mut changed = false;
+ for (child, requirement) in children.iter_mut().zip(requirements) {
+ let Some(requirement) = requirement else {
+ continue;
+ };
+ let requirement = requirement.into_single();
+ let eq_properties = child.equivalence_properties();
+ if eq_properties.ordering_satisfy_requirement(requirement.clone())? {
+ continue;
+ }
+ let sort_reqs: Vec<_> = requirement.clone().into();
+ let sort_exprs = sort_reqs
+ .into_iter()
+ .filter(|req| eq_properties.is_expr_constant(&req.expr).is_none())
+ .map(Into::into);
+ let Some(ordering) = LexOrdering::new(sort_exprs) else {
+ continue;
+ };
+ let sort: Arc<dyn ExecutionPlan> = Arc::new(
+ SortExec::new(ordering, Arc::clone(child)).with_preserve_partitioning(
+ child.output_partitioning().partition_count() > 1,
+ ),
Review Comment:
This no longer applies: following your comment on the root cause, the EnsureRequirements step is removed in 05e298eb04, and the PR fixes the join instead.
##########
datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs:
##########
@@ -232,6 +235,71 @@ pub fn replace_with_partial_sort(
Ok(plan)
}
+/// Adds a [`SortExec`] below every node whose ordering requirement is not
+/// satisfied by its child's equivalence properties.
+///
+/// [`pushdown_sorts`] removes a sort when it can map the requirement onto a
+/// descendant that satisfies it. That mapping is computed separately from the
+/// equivalence properties of the operators in between, and the two can
+/// disagree. The plan may then be correct, but its properties cannot show it,
+/// and `SanityCheckPlan` rejects it. Adding the sort back keeps every plan
+/// produced by `EnsureRequirements` valid by the same check.
+///
+/// A requirement that a new [`SortExec`] still cannot satisfy is left as is,
+/// for `SanityCheckPlan` to report.
+///
+/// [`pushdown_sorts`]: sort_pushdown::pushdown_sorts
+pub fn add_sort_for_unproven_ordering(
+ plan: Arc<dyn ExecutionPlan>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ let requirements = plan.required_input_ordering();
+ if requirements.iter().all(Option::is_none) {
+ return Ok(Transformed::no(plan));
+ }
+ let mut children: Vec<_> = plan.children().into_iter().cloned().collect();
+ let mut changed = false;
+ for (child, requirement) in children.iter_mut().zip(requirements) {
+ let Some(requirement) = requirement else {
+ continue;
+ };
+ let requirement = requirement.into_single();
+ let eq_properties = child.equivalence_properties();
+ if eq_properties.ordering_satisfy_requirement(requirement.clone())? {
+ continue;
+ }
+ let sort_reqs: Vec<_> = requirement.clone().into();
Review Comment:
This no longer applies: following your comment on the root cause, the EnsureRequirements step is removed in 05e298eb04, and the PR fixes the join instead.
##########
datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs:
##########
@@ -232,6 +235,71 @@ pub fn replace_with_partial_sort(
Ok(plan)
}
+/// Adds a [`SortExec`] below every node whose ordering requirement is not
+/// satisfied by its child's equivalence properties.
+///
+/// [`pushdown_sorts`] removes a sort when it can map the requirement onto a
+/// descendant that satisfies it. That mapping is computed separately from the
+/// equivalence properties of the operators in between, and the two can
+/// disagree. The plan may then be correct, but its properties cannot show it,
+/// and `SanityCheckPlan` rejects it. Adding the sort back keeps every plan
+/// produced by `EnsureRequirements` valid by the same check.
+///
+/// A requirement that a new [`SortExec`] still cannot satisfy is left as is,
+/// for `SanityCheckPlan` to report.
+///
+/// [`pushdown_sorts`]: sort_pushdown::pushdown_sorts
+pub fn add_sort_for_unproven_ordering(
+ plan: Arc<dyn ExecutionPlan>,
+) -> Result<Transformed<Arc<dyn ExecutionPlan>>> {
+ let requirements = plan.required_input_ordering();
+ if requirements.iter().all(Option::is_none) {
+ return Ok(Transformed::no(plan));
+ }
+ let mut children: Vec<_> = plan.children().into_iter().cloned().collect();
+ let mut changed = false;
+ for (child, requirement) in children.iter_mut().zip(requirements) {
+ let Some(requirement) = requirement else {
+ continue;
+ };
+ let requirement = requirement.into_single();
+ let eq_properties = child.equivalence_properties();
+ if eq_properties.ordering_satisfy_requirement(requirement.clone())? {
+ continue;
+ }
+ let sort_reqs: Vec<_> = requirement.clone().into();
+ let sort_exprs = sort_reqs
+ .into_iter()
+ .filter(|req| eq_properties.is_expr_constant(&req.expr).is_none())
+ .map(Into::into);
+ let Some(ordering) = LexOrdering::new(sort_exprs) else {
+ continue;
+ };
+ let sort: Arc<dyn ExecutionPlan> = Arc::new(
+ SortExec::new(ordering, Arc::clone(child)).with_preserve_partitioning(
+ child.output_partitioning().partition_count() > 1,
+ ),
+ );
+ if !sort
+ .equivalence_properties()
+ .ordering_satisfy_requirement(requirement)?
+ {
+ continue;
Review Comment:
This no longer applies: following your comment on the root cause, the EnsureRequirements step is removed in 05e298eb04, and the PR fixes the join instead.
##########
datafusion/physical-optimizer/src/ensure_requirements/mod.rs:
##########
@@ -267,10 +279,15 @@ impl PhysicalOptimizerRule for EnsureRequirements {
assign_initial_requirements(&mut sort_pushdown);
let adjusted = pushdown_sorts(sort_pushdown)?;
- // 3d: Partial sort
- adjusted
+ // 3d: Sort where an ordering requirement cannot be proven
+ use super::enforce_sorting::add_sort_for_unproven_ordering;
+ let plan = adjusted
.plan
Review Comment:
This no longer applies: following your comment on the root cause, the EnsureRequirements step is removed in 05e298eb04, and the PR fixes the join instead.
--
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: keep probe-side constants in join equivalence properties [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on PR #26459:
URL: https://github.com/apache/datafusion/pull/26459#issuecomment-6358278443
sql_planner looks unchanged
--
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: keep probe-side constants in join equivalence properties [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 merged PR #26459:
URL: https://github.com/apache/datafusion/pull/26459
--
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: keep probe-side constants in join equivalence properties [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on PR #26459:
URL: https://github.com/apache/datafusion/pull/26459#issuecomment-6366682745
Thanks @zhuqi-lucas @kumarUjjawal !
--
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: keep probe-side constants in join equivalence properties [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #26459:
URL: https://github.com/apache/datafusion/pull/26459#issuecomment-6356944559
🤖 Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/26459#issuecomment-6356917032)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c6356917032-3786-jmgct 6.12.105+ #1 SMP Sat Sep 5 07:54:11 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
Comparing ensure-requirements-unproven-ordering (33193465ae2873a1ac13c4ec6a171811e5d2c31c) to 290ad15 (merge-base) [diff](https://github.com/apache/datafusion/compare/290ad15cc842167ca4d3c0774ccdf3a1d9d61862..33193465ae2873a1ac13c4ec6a171811e5d2c31c)
<details><summary>Run configuration</summary>
```yaml
run benchmark sql_planner
```
</details>
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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