Add Optimizer Sanity Checker, improve sortedness equivalence properties #11196

mustafasrepo · 2024-07-01T15:10:03Z

Rationale for this change

Most of the contribution in this PR comes from @yfy- . Thanks @yfy- for working on this issue.

We extend the existing PipelineChecker with additional checks of order and distribution requirements. In a physical plan each plan should be pipeline friendly (previously checked by PipelineChecker) and each child plan's output order and partitioning should satisfy the parent's respective requirements. We combine these checks into the SanityCheckPlan proposed with this PR.

With the SanityCheckPlan, as the optimizer steps change and grow, we ensure that the order and distribution requirements of the final phsyical plan are always satisfied so that it can yield correct results.

What changes are included in this PR?

The SanityCheckPlan step as the last step of the physical plan optimizations.
SanityCheckPlan contains the former PipelineChecker, that's why PipelineChecker is deleted.
Add a ConstExpr API to manage tracking constant expressions

Are these changes tested?

We use the existing test cases of the former PipelineChecker. In addition following cases are added:

Using `BoundedWindowAggExec`

2 cases: First with the child order requirement is satisfied and another one that is not satisifed.

Using `GlobalLimitExec`

2 cases: First with the child distribution requirement is satisfied and another one that is not satisifed.

Using `LocalLimitExec`

We check when there are no requirements at all our check passes.

Using `SortMergeJoinExec`

3 cases: First case with both children satisify both requirements. Second case, where the second child does not satisfy the order requirement. Finally, a case where the second child does not satisfy distribution requirements.

Only includes sort reqs, docs will be added.

Co-authored-by: Mehmet Ozan Kabak <[email protected]>

Optimizer Sanity Checker

ozankabak

I reviewed this PR carefully and it looks good to me. Thank you @yfy- and @mustafasrepo for collaborating on this.

Hopefully this rule will make us discover plan bugs much earlier, prevent regressions and increase developer discipline on operator and rule implementations.

alamb

Thank you @mustafasrepo (and @yfy- ) - I found this PR very well written, documented and tested.

I had a few small comment suggestions as I read this PR, but overall I thought it looked quite nice

I also added a few notes to the description / title of the PR to make it clear this also improves some of the sortedness matching calculations in addtion to adding a new sanity check

datafusion/core/src/physical_optimizer/sanity_checker.rs

datafusion/physical-expr/src/equivalence/class.rs

alamb · 2024-07-02T20:01:22Z

datafusion/physical-expr/src/equivalence/properties.rs

@@ -173,6 +174,12 @@ impl EquivalenceProperties {
        self.oeq_class.clear();
    }

+    /// Removes constant expressions that may change across partitions.
+    /// This method should be used when different partitions are fused.


What does a "fused" partition mean? That is not a term I have run into previously

What I mean is data from multiple partitions ends up in another partition (operators that does this CoalescePartitionsExec, SortPreservingMergeExec, InterleaveExec, RepartitionExec). I changed to term to "merge" in 747b69b. However, If you have other suggestions which communicates the intent in this context better (maybe more common vocabulary in literature). I can update with that term.

merge sounds good -- thank you

alamb · 2024-07-02T20:04:06Z

datafusion/physical-expr/src/equivalence/properties.rs

        // First, project existing constants. For example, assume that `a + b`
        // is known to be constant. If the projection were `a as a_new`, `b as b_new`,
        // then we would project constant `a + b` as `a_new + b_new`.
        let mut projected_constants = self
            .constants
            .iter()
-            .flat_map(|expr| self.eq_group.project_expr(mapping, expr))
+            .flat_map(|const_expr| {
+                self.eq_group


I wonder if you could add an API like ConstExpr::map that applied a function to the contained Expr. That way this could look like

.flat_map(|expr| expr.map(|expr| self.eq_group.project_expr(mapping, expr))))

Changed in 747b69b.

alamb · 2024-07-02T20:07:14Z

datafusion/sqllogictest/test_files/joins.slt

-12)--------RepartitionExec: partitioning=Hash([a@1], 2), input_partitions=2
-13)----------RepartitionExec: partitioning=RoundRobinBatch(2), input_partitions=1
-14)------------CsvExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/core/tests/data/window_2.csv]]}, projection=[a0, a, b, c, d], output_ordering=[a@1 ASC, b@2 ASC NULLS LAST, c@3 ASC NULLS LAST], has_header=true
+03)----CoalesceBatchesExec: target_batch_size=2


Are these results due to changing the setting

set datafusion.optimizer.prefer_existing_sort = true;

Or to the changes in the calculations for the sortedness calculations?

The plan seems better to me (there is no sort)

Actually, previous plan was wrong (Another case this new rule helped us discover), since one of the children of the SortMergeJoin doesn't have ordering: [a ASC]. After fix, generated plan was quite different. the intent of this test was (as far as I can tell) to see order by at the top of the SortMergeJoin can be pushed down through SortMergeJoin. Hence, I changed the setting to preserve this behaviour.

The result change (where sort is removed) comes from the setting change indeed. However, as I said the plan has changed with the setting set datafusion.optimizer.prefer_existing_sort = false; also. Hence, I decided to change flag to preserve the intent of the test.

Co-authored-by: Andrew Lamb <[email protected]>

alamb · 2024-07-03T10:06:18Z

Thanks @mustafasrepo !

alamb · 2024-07-07T20:05:14Z

FYI this check is now failing on one of the sql planning benchmarks: #11322

…es (apache#11196) * Initial optimizer sanity checker. Only includes sort reqs, docs will be added. * Add distro and pipeline friendly checks * Also check the plans we create are correct. * Add distribution test cases using global limit exec. * Add test for multiple children using SortMergeJoinExec. * Move PipelineChecker to SanityCheckPlan * Fix some tests and add docs * Add some test docs and fix clippy diagnostics. * Fix some failing tests * Replace PipelineChecker with SanityChecker in .slt files. * Initial commit * Slt tests pass * Resolve linter errors * Minor changes * Minor changes * Minor changes * Minor changes * Sort PreservingMerge clear per partition * Minor changes * Update output_requirements.rs * Address reviews * Update datafusion/core/src/physical_optimizer/optimizer.rs Co-authored-by: Mehmet Ozan Kabak <[email protected]> * Update datafusion/core/src/physical_optimizer/sanity_checker.rs Co-authored-by: Mehmet Ozan Kabak <[email protected]> * Address reviews * Minor changes * Apply suggestions from code review Co-authored-by: Andrew Lamb <[email protected]> * Update comment * Add map implementation --------- Co-authored-by: Erman Yafay <[email protected]> Co-authored-by: berkaysynnada <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> Co-authored-by: Andrew Lamb <[email protected]>

alamb · 2024-07-16T16:05:13Z

We found an issue (that I think is exposed by this change, not caused by it) while upgrading InfluxDB 3.0: #11492

…es (apache#11196) * Initial optimizer sanity checker. Only includes sort reqs, docs will be added. * Add distro and pipeline friendly checks * Also check the plans we create are correct. * Add distribution test cases using global limit exec. * Add test for multiple children using SortMergeJoinExec. * Move PipelineChecker to SanityCheckPlan * Fix some tests and add docs * Add some test docs and fix clippy diagnostics. * Fix some failing tests * Replace PipelineChecker with SanityChecker in .slt files. * Initial commit * Slt tests pass * Resolve linter errors * Minor changes * Minor changes * Minor changes * Minor changes * Sort PreservingMerge clear per partition * Minor changes * Update output_requirements.rs * Address reviews * Update datafusion/core/src/physical_optimizer/optimizer.rs Co-authored-by: Mehmet Ozan Kabak <[email protected]> * Update datafusion/core/src/physical_optimizer/sanity_checker.rs Co-authored-by: Mehmet Ozan Kabak <[email protected]> * Address reviews * Minor changes * Apply suggestions from code review Co-authored-by: Andrew Lamb <[email protected]> * Update comment * Add map implementation --------- Co-authored-by: Erman Yafay <[email protected]> Co-authored-by: berkaysynnada <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> Co-authored-by: Andrew Lamb <[email protected]>

* fix(11397): do not surface errors for closed channels, and instead let the task join errors be surfaced * fix(11397): terminate early on channel send failure Add Optimizer Sanity Checker, improve sortedness equivalence properties (apache#11196) * Initial optimizer sanity checker. Only includes sort reqs, docs will be added. * Add distro and pipeline friendly checks * Also check the plans we create are correct. * Add distribution test cases using global limit exec. * Add test for multiple children using SortMergeJoinExec. * Move PipelineChecker to SanityCheckPlan * Fix some tests and add docs * Add some test docs and fix clippy diagnostics. * Fix some failing tests * Replace PipelineChecker with SanityChecker in .slt files. * Initial commit * Slt tests pass * Resolve linter errors * Minor changes * Minor changes * Minor changes * Minor changes * Sort PreservingMerge clear per partition * Minor changes * Update output_requirements.rs * Address reviews * Update datafusion/core/src/physical_optimizer/optimizer.rs Co-authored-by: Mehmet Ozan Kabak <[email protected]> * Update datafusion/core/src/physical_optimizer/sanity_checker.rs Co-authored-by: Mehmet Ozan Kabak <[email protected]> * Address reviews * Minor changes * Apply suggestions from code review Co-authored-by: Andrew Lamb <[email protected]> * Update comment * Add map implementation --------- Co-authored-by: Erman Yafay <[email protected]> Co-authored-by: berkaysynnada <[email protected]> Co-authored-by: Mehmet Ozan Kabak <[email protected]> Co-authored-by: Andrew Lamb <[email protected]>

alamb · 2024-07-26T18:53:53Z

This check was being triggered in our downstream tests, but I think it actually found a real bug: #11675

alamb · 2024-09-12T15:22:17Z

I believe this check also found another bug / limitation: #12414

yfy- and others added 30 commits June 9, 2024 20:36

Initial optimizer sanity checker.

8f0c30f

Only includes sort reqs, docs will be added.

Add distro and pipeline friendly checks

2538702

Also check the plans we create are correct.

aea95c6

Add distribution test cases using global limit exec.

9aef599

Add test for multiple children using SortMergeJoinExec.

49aba4b

Move PipelineChecker to SanityCheckPlan

d89b1c9

Fix some tests and add docs

defebb0

Add some test docs and fix clippy diagnostics.

b392cf6

Fix some failing tests

5bdec62

Merge branch 'apache_main' into optimizer-sanity-checker

46bf900

Replace PipelineChecker with SanityChecker in .slt files.

7148c07

Initial commit

1e888c4

Slt tests pass

c08a92b

Resolve linter errors

6d79881

Minor changes

cd49e2e

Minor changes

338f451

Minor changes

1959488

Minor changes

1c5c0c0

Sort PreservingMerge clear per partition

24e32b6

Minor changes

9b77608

Merge branch 'optimizer-sanity-checker' into sanity_checker_subs

655a010

Update output_requirements.rs

e93cf6e

Address reviews

58cbf9a

Merge branch 'apache_main' into optimizer-sanity-checker

6f8db29

Merge branch 'optimizer-sanity-checker' into sanity_checker_subs

0cb86b9

Update datafusion/core/src/physical_optimizer/optimizer.rs

5a34ae0

Co-authored-by: Mehmet Ozan Kabak <[email protected]>

Update datafusion/core/src/physical_optimizer/sanity_checker.rs

f3ac546

Co-authored-by: Mehmet Ozan Kabak <[email protected]>

Address reviews

0491c13

Merge branch 'apache_main' into optimizer-sanity-checker

aa075e2

Minor changes

dfd219c

Merge pull request #24 from yfy-/optimizer-sanity-checker

0c2eb45

Optimizer Sanity Checker

github-actions bot added physical-expr Physical Expressions core Core DataFusion crate sqllogictest SQL Logic Tests (.slt) labels Jul 1, 2024

ozankabak approved these changes Jul 1, 2024

View reviewed changes

alamb mentioned this pull request Jul 1, 2024

DataFusion weekly project plan (Andrew Lamb) - July 1, 2024 #11190

Closed

10 tasks

alamb changed the title ~~Optimizer Sanity Checker~~ Add Optimizer Sanity Checker, improve sortedness equivalence properties Jul 2, 2024

alamb approved these changes Jul 2, 2024

View reviewed changes

mustafasrepo and others added 3 commits July 3, 2024 08:57

Apply suggestions from code review

d8ebc14

Co-authored-by: Andrew Lamb <[email protected]>

Update comment

747b69b

Add map implementation

aa1382b

alamb merged commit b76c1b7 into apache:main Jul 3, 2024
23 checks passed

alamb mentioned this pull request Jul 7, 2024

SanityCheckPlan failed on sql_planning1 benchmark: , Plan("Child: [\"ProjectionExec: expr=[]\", \" CoalesceBatchesExec: target_batch_size=8192\", #11322

Closed

alamb mentioned this pull request Jul 16, 2024

SanityCheckPlan Error during planning: ... does not satisfy parent order requirements: ... #11492

Closed

alamb mentioned this pull request Jul 26, 2024

pushdown_sorts pushes a SortExec through a node in violation of its stated input ordering requirements #11675

Closed

alamb mentioned this pull request Sep 12, 2024

SanityChecker rejects certain valid UNION plans #12446

Open

This pull request was closed.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add Optimizer Sanity Checker, improve sortedness equivalence properties #11196

Add Optimizer Sanity Checker, improve sortedness equivalence properties #11196

mustafasrepo commented Jul 1, 2024 •

edited by alamb

Loading

ozankabak left a comment •

edited

Loading

alamb left a comment

alamb Jul 2, 2024

mustafasrepo Jul 3, 2024

alamb Jul 3, 2024

alamb Jul 2, 2024

mustafasrepo Jul 3, 2024

alamb Jul 2, 2024

mustafasrepo Jul 3, 2024 •

edited

Loading

alamb commented Jul 3, 2024

alamb commented Jul 7, 2024 •

edited

Loading

alamb commented Jul 16, 2024

alamb commented Jul 26, 2024

alamb commented Sep 12, 2024

Add Optimizer Sanity Checker, improve sortedness equivalence properties #11196

Add Optimizer Sanity Checker, improve sortedness equivalence properties #11196

Conversation

mustafasrepo commented Jul 1, 2024 • edited by alamb Loading

Rationale for this change

What changes are included in this PR?

Are these changes tested?

Using BoundedWindowAggExec

Using GlobalLimitExec

Using LocalLimitExec

Using SortMergeJoinExec

ozankabak left a comment • edited Loading

Choose a reason for hiding this comment

alamb left a comment

Choose a reason for hiding this comment

alamb Jul 2, 2024

Choose a reason for hiding this comment

mustafasrepo Jul 3, 2024

Choose a reason for hiding this comment

alamb Jul 3, 2024

Choose a reason for hiding this comment

alamb Jul 2, 2024

Choose a reason for hiding this comment

mustafasrepo Jul 3, 2024

Choose a reason for hiding this comment

alamb Jul 2, 2024

Choose a reason for hiding this comment

mustafasrepo Jul 3, 2024 • edited Loading

Choose a reason for hiding this comment

alamb commented Jul 3, 2024

alamb commented Jul 7, 2024 • edited Loading

alamb commented Jul 16, 2024

alamb commented Jul 26, 2024

alamb commented Sep 12, 2024

mustafasrepo commented Jul 1, 2024 •

edited by alamb

Loading

Using `BoundedWindowAggExec`

Using `GlobalLimitExec`

Using `LocalLimitExec`

Using `SortMergeJoinExec`

ozankabak left a comment •

edited

Loading

mustafasrepo Jul 3, 2024 •

edited

Loading

alamb commented Jul 7, 2024 •

edited

Loading