You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "jonahgao (via GitHub)" <gi...@apache.org> on 2023/11/22 03:09:35 UTC

[I] Conflicting optimization rules: `common_sub_expression_eliminate` and `push_down_projection` [arrow-datafusion]

jonahgao opened a new issue, #8296:
URL: https://github.com/apache/arrow-datafusion/issues/8296

   ### Describe the bug
   
   Rule `push_down_projection` negates the optimization results of `common_sub_expression_eliminate`, but leaves the useless aliases introduced by `common_sub_expression_eliminate`. Those added aliases change the signature of the logical plan, also causing the optimizer to never reach the fixed point.
   
   In summary, there are two problems: 
   1. The optimization of  `common_sub_expression_elimination` did not work.
   2. Ineffective optimization leads to the optimizer not being able to exit early until it reaches the limit of `datafusion.optimizer.max_passes`.
   
   ### To Reproduce
   
   Run `explain verbose select a/2, a/2 + 1 from t` in CLI
   ```sh
   DataFusion CLI v33.0.0
   
   ❯ create table t(a bigint);
   0 rows in set. Query took 0.006 seconds.
   
   ❯ explain verbose select a/2, a/2 + 1 from t;
   | logical_plan after common_sub_expression_eliminate         | Projection: t.a / Int64(2)Int64(2)t.a AS t.a / Int64(2), t.a / Int64(2)Int64(2)t.a AS t.a / Int64(2) + Int64(1)                                                                         |
   |                                                            |   Projection: t.a / Int64(2) AS t.a / Int64(2)Int64(2)t.a, t.a                                                                                                                          |
   |                                                            |     TableScan: t
   | ...
   |
   | logical_plan after push_down_projection                    | Projection: t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2), t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) + Int64(1)                                                           |
   |                                                            |   TableScan: t projection=[a]
   
   ❯ explain select a/2, a/2 + 1 from t;
   +---------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------+
   | plan_type     | plan                                                                                                                                                              |
   +---------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------+
   | logical_plan  | Projection: t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2), t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) + Int64(1) |
   |               |   TableScan: t projection=[a]                                                                                                                                     |
   | physical_plan | ProjectionExec: expr=[a@0 / 2 as t.a / Int64(2), a@0 / 2 + 1 as t.a / Int64(2) + Int64(1)]                                                                        |
   |               |   MemoryExec: partitions=1, partition_sizes=[0]                                                                                                                   |
   |               |                                                                                                                                                                   |
   +---------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------+
   ```
   The final projection is: 
   - `a/2`: t.a / Int64(2) **AS** t.a / Int64(2) **AS** t.a / Int64(2) **AS** t.a / Int64(2)
   - `a/2+1`: t.a / Int64(2) **AS** t.a / Int64(2) **AS** t.a / Int64(2) **AS** t.a / Int64(2) + Int64(1)
   
   Three duplicate aliases appeared, corresponding to `datafusion.optimizer.max_passes=3`.
   
   
   
   If I set `datafusion.optimizer.max_passes=10`
   ```sh
   ❯ set datafusion.optimizer.max_passes=10;
   0 rows in set. Query took 0.002 seconds.
   
   ❯ explain select a/2, a/2 + 1 from t;
   +---------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
   | plan_type     | plan                                                                                                                                                                                                                                                                                                                                                                                                                          |
   +---------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
   | logical_plan  | Projection: t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2), t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) + Int64(1) |
   |               |   TableScan: t projection=[a]                                                                                                                                                                                                                                                                                                                                                                                                 |
   | physical_plan | ProjectionExec: expr=[a@0 / 2 as t.a / Int64(2), a@0 / 2 + 1 as t.a / Int64(2) + Int64(1)]                                                                                                                                                                                                                                                                                                                                    |
   |               |   MemoryExec: partitions=1, partition_sizes=[0]                                                                                                                                                                                                                                                                                                                                                                               |
   |               |                                                                                                                                                                                                                                                                                                                                                                                                                               |
   +---------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
   2 rows in set. Query took 0.025 seconds.
   ```
   One of the expr in the final projection will be `t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2) AS t.a / Int64(2)`. 
   There are too many unnecessary aliases.
   
   ### Expected behavior
   
   The logic `merge_projection` inside the rule `push_down_projection` should not undo `common_sub_expression_eliminate`.
   
   
   ### Additional context
   
   I plan to work on this in the next few days.
   
   My initial thought is to fix it in the `push_down_projection` side.
   
   Do not execute `merge_projection` if an expression in the child projection satisfies the following conditions:
   1. It has been referenced by the parent projection two or more times.
   2. Its evaluation is non-trivial. Its type is not `Column` or `Literal`.
   


-- 
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@arrow.apache.org.apache.org

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


Re: [I] Conflicting optimization rules: `common_sub_expression_eliminate` and `push_down_projection` [arrow-datafusion]

Posted by "mustafasrepo (via GitHub)" <gi...@apache.org>.
mustafasrepo commented on issue #8296:
URL: https://github.com/apache/arrow-datafusion/issues/8296#issuecomment-1825465680

   I have examined how we can support merge_projections under this [PR](https://github.com/synnada-ai/arrow-datafusion/pull/201). It seems that we can support this feature, with this PR all of the optimizations related to the `Projection` is handled with a single rule. 
   
   Also as part of that PR, I have changed projection merge logic, such that it doesn't always merges consecutive projections(when previous projection is used to cache complex computation for subsequent projection). With this support, the problem in this issue is resolved also. See [test](https://github.com/synnada-ai/arrow-datafusion/blob/81b55af099220c59787ce8b2bbf9ef5c4052973a/datafusion/sqllogictest/test_files/subquery.slt#L1023)


-- 
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@arrow.apache.org

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


Re: [I] Conflicting optimization rules: `common_sub_expression_eliminate` and `push_down_projection` [arrow-datafusion]

Posted by "mustafasrepo (via GitHub)" <gi...@apache.org>.
mustafasrepo closed issue #8296: Conflicting optimization rules: `common_sub_expression_eliminate` and `push_down_projection`
URL: https://github.com/apache/arrow-datafusion/issues/8296


-- 
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@arrow.apache.org

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


Re: [I] Conflicting optimization rules: `common_sub_expression_eliminate` and `push_down_projection` [arrow-datafusion]

Posted by "mustafasrepo (via GitHub)" <gi...@apache.org>.
mustafasrepo commented on issue #8296:
URL: https://github.com/apache/arrow-datafusion/issues/8296#issuecomment-1822483392

   @jonahgao I am working on a PR to optimize projections. (It is almost ready, in our interval review process. You can find it [here](https://github.com/synnada-ai/arrow-datafusion/pull/201)). I think this PR will solve this problem. (I didn't verify it though). I suggest you to try whether that PR solves this issue. If that is the case, it should be ready in couple of days for upstream. In this way, we wouldn't duplicate efforts. 


-- 
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@arrow.apache.org

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


Re: [I] Conflicting optimization rules: `common_sub_expression_eliminate` and `push_down_projection` [arrow-datafusion]

Posted by "mustafasrepo (via GitHub)" <gi...@apache.org>.
mustafasrepo commented on issue #8296:
URL: https://github.com/apache/arrow-datafusion/issues/8296#issuecomment-1822969187

   > Thank you @mustafasrepo I have tested on [this branch](https://github.com/synnada-ai/arrow-datafusion/commits/enhance/aggregate_pk), and it looks really nice.
   > 
   > ```
   > ❯ explain  verbose select a/2, a/2+1 from t;
   > | logical_plan after common_sub_expression_eliminate         | Projection: t.a / Int64(2)Int64(2)t.a AS t.a / Int64(2), t.a / Int64(2)Int64(2)t.a AS t.a / Int64(2) + Int64(1)                                                                                        |
   > |                                                            |   Projection: t.a / Int64(2) AS t.a / Int64(2)Int64(2)t.a, t.a                                                                                                                                         |
   > |                                                            |     TableScan: t
   > | logical_plan after optimize_projections                    | Projection: t.a / Int64(2)Int64(2)t.a AS t.a / Int64(2), t.a / Int64(2)Int64(2)t.a AS t.a / Int64(2) + Int64(1)                                                                                        |
   > |                                                            |   Projection: t.a / Int64(2) AS t.a / Int64(2)Int64(2)t.a                                                                                                                                              |
   > |                                                            |     TableScan: t projection=[a]
   > | logical_plan after merge_projection                        | Projection: t.a / Int64(2) AS t.a / Int64(2), t.a / Int64(2) AS t.a / Int64(2) + Int64(1)                                                                                                              |
   > |                                                            |   TableScan: t projection=[a]
   > ```
   > 
   > The new `optimize_projections` rule **no longer** undo the optimization of `common_sub_expression_eliminate`.
   > 
   > However, the `merge_projection` rule still causes the same problem, because it contains the same [merge](https://github.com/apache/arrow-datafusion/blob/f2b03443260cade7e43eba568d94d8c09cd002f4/datafusion/optimizer/src/push_down_projection.rs#L92) logic as the old `push_down_projection` rule. The merge logic is the root cause.
   > 
   > I’m wondering if the new `OptimizeProjections` rule can also cover the functionality of [MergeProjection](https://github.com/apache/arrow-datafusion/blob/f2b03443260cade7e43eba568d94d8c09cd002f4/datafusion/optimizer/src/merge_projection.rs#L31). I believe that, in this way, we can solve this problem. Or wait until your PR is merged, and then reconsider this issue.
   
   I think we can cover merge functionality in the new rule also. I will try it out, then let you know about the result.


-- 
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@arrow.apache.org

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


Re: [I] Conflicting optimization rules: `common_sub_expression_eliminate` and `push_down_projection` [arrow-datafusion]

Posted by "mustafasrepo (via GitHub)" <gi...@apache.org>.
mustafasrepo commented on issue #8296:
URL: https://github.com/apache/arrow-datafusion/issues/8296#issuecomment-1829530397

   @jonahgao I have opened the PR in upstream. You can find the upstream PR [here](https://github.com/apache/arrow-datafusion/pull/8340).


-- 
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@arrow.apache.org

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


Re: [I] Conflicting optimization rules: `common_sub_expression_eliminate` and `push_down_projection` [arrow-datafusion]

Posted by "jonahgao (via GitHub)" <gi...@apache.org>.
jonahgao commented on issue #8296:
URL: https://github.com/apache/arrow-datafusion/issues/8296#issuecomment-1826476167

   > I have examined how we can support merge_projections under this [PR](https://github.com/synnada-ai/arrow-datafusion/pull/201). It seems that we can support this feature, with this PR all of the optimizations related to the `Projection` is handled with a single rule.
   > 
   > Also as part of that PR, I have changed projection merge logic, such that it doesn't always merges consecutive projections(when previous projection is used to cache complex computation for subsequent projection). With this support, the problem in this issue is resolved also. See [test](https://github.com/synnada-ai/arrow-datafusion/blob/81b55af099220c59787ce8b2bbf9ef5c4052973a/datafusion/sqllogictest/test_files/subquery.slt#L1023)
   
   A great job 🎉 ! 
   I will leave this issue here, waiting for your PR to be merged.


-- 
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@arrow.apache.org

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


Re: [I] Conflicting optimization rules: `common_sub_expression_eliminate` and `push_down_projection` [arrow-datafusion]

Posted by "jonahgao (via GitHub)" <gi...@apache.org>.
jonahgao commented on issue #8296:
URL: https://github.com/apache/arrow-datafusion/issues/8296#issuecomment-1822954845

   Thank you @mustafasrepo  I have tested on [this branch](https://github.com/synnada-ai/arrow-datafusion/commits/enhance/aggregate_pk), and it looks really nice.
   ```
   ❯ explain  verbose select a/2, a/2+1 from t;
   | logical_plan after common_sub_expression_eliminate         | Projection: t.a / Int64(2)Int64(2)t.a AS t.a / Int64(2), t.a / Int64(2)Int64(2)t.a AS t.a / Int64(2) + Int64(1)                                                                                        |
   |                                                            |   Projection: t.a / Int64(2) AS t.a / Int64(2)Int64(2)t.a, t.a                                                                                                                                         |
   |                                                            |     TableScan: t
   | logical_plan after optimize_projections                    | Projection: t.a / Int64(2)Int64(2)t.a AS t.a / Int64(2), t.a / Int64(2)Int64(2)t.a AS t.a / Int64(2) + Int64(1)                                                                                        |
   |                                                            |   Projection: t.a / Int64(2) AS t.a / Int64(2)Int64(2)t.a                                                                                                                                              |
   |                                                            |     TableScan: t projection=[a]
   | logical_plan after merge_projection                        | Projection: t.a / Int64(2) AS t.a / Int64(2), t.a / Int64(2) AS t.a / Int64(2) + Int64(1)                                                                                                              |
   |                                                            |   TableScan: t projection=[a]
   ```
   The new `optimize_projections` rule **no longer** undo the optimization of `common_sub_expression_eliminate`.
   
   However, the `merge_projection` rule still causes the same problem, because it contains the same [merge](https://github.com/apache/arrow-datafusion/blob/f2b03443260cade7e43eba568d94d8c09cd002f4/datafusion/optimizer/src/push_down_projection.rs#L92) logic as the old `push_down_projection` rule. The merge logic is the root cause.
   
   I’m wondering if the new `OptimizeProjections` rule can also cover the functionality of `merge_projection`. I believe that, in this way, we can solve this problem. Or wait until your PR is merged, and then reconsider this issue.


-- 
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@arrow.apache.org

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