You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by GitBox <gi...@apache.org> on 2021/10/21 16:24:12 UTC
[GitHub] [arrow-datafusion] alamb opened a new issue #1160: Support simplification that requires multiple applications of constant folding / simplification
alamb opened a new issue #1160:
URL: https://github.com/apache/arrow-datafusion/issues/1160
**Is your feature request related to a problem or challenge? Please describe what you are trying to do.**
The constant folding and constant evaluation in https://github.com/apache/arrow-datafusion/blob/master/datafusion/src/optimizer/constant_folding.rs (and added to in https://github.com/apache/arrow-datafusion/pull/1153) can not fold certain types of expressions where it takes
For example there is an expression like this in https://github.com/apache/arrow-datafusion/pull/1153
```
now() < cast(to_timestamp(...) as int) + 5000000000
```
It is entirely evaluateable at query time, however, as formulated in #1153 it will not be folded because it requires the constant evaluator to run after the simplifier (because the simplifier can fill in now()` and then the evaluator will fill in the rest).
However, there are other types of exprs such as `(true or false) != col` which need to have the constant evaluator run before the simplifier to be fully simplified.
It is a more general problem where running either the `Simplifier` or `ConstEvaluator` could allow a second pass of the other to proceed
**Describe the solution you'd like**
In general this is typically handled with some sort of 'fixed point' algorithm where there is a loop that runs the two passes until the Expr is not changed. It may also be possible to combine the Simplifier pass with the constant rewriter.
**Describe alternatives you've considered**
I think there are two possible approaches I can think if:
1. applying constant eval / simplifier in a loop until no changes are detected
2. Combining the `ConstantEval` and `Simplify` steps into a single pass
**Additional context**
https://github.com/apache/arrow-datafusion/pull/1153
--
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
[GitHub] [arrow-datafusion] alamb commented on issue #1160: Support simplification that requires multiple applications of constant folding / simplification
Posted by GitBox <gi...@apache.org>.
alamb commented on issue #1160:
URL: https://github.com/apache/arrow-datafusion/issues/1160#issuecomment-952905624
@rdettai I think it is still relevant (though the `now()` example will work after #1175)
One (silly) example
```
(expr != NULL) OR (5 > 10)
```
We need to apply at least one pass twice to fully simplify
```
(expr != NULL) OR (5 > 10)
(expr != NULL) OR FALSE # after constant evaluation
NULL OR FALSE # after simplify
NULL # after second constant evaluation
```
In this this case if we applied simplify first and then constant evaluation the expression would be folded completely
However, for other examples if you apply simplification first that is insufficient
```
expr != (5 > NULL)
expr != (5 > NULL) # after simplification
expr != NULL # after constant evaluation
```
(would need a second call to simplify now)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] rdettai edited a comment on issue #1160: Support simplification that requires multiple applications of constant folding / simplification
Posted by GitBox <gi...@apache.org>.
rdettai edited a comment on issue #1160:
URL: https://github.com/apache/arrow-datafusion/issues/1160#issuecomment-952853942
Is this still relevant after #1175 (PR #1176) ? If you think it is, do you have an example in mind ? I can't come up with one 😃
--
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
[GitHub] [arrow-datafusion] alamb commented on issue #1160: Support simplification that requires multiple applications of constant folding / simplification
Posted by GitBox <gi...@apache.org>.
alamb commented on issue #1160:
URL: https://github.com/apache/arrow-datafusion/issues/1160#issuecomment-953071964
> (I think this is already what you mentioned in #1128 (review), but I thought a recap wouldn't hurt 😄)
👍 it is a nice summary;
--
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
[GitHub] [arrow-datafusion] rdettai commented on issue #1160: Support simplification that requires multiple applications of constant folding / simplification
Posted by GitBox <gi...@apache.org>.
rdettai commented on issue #1160:
URL: https://github.com/apache/arrow-datafusion/issues/1160#issuecomment-952958330
Great thanks! This is very clear now. So if I understand correctly, this problem has two solutions:
- walk the tree once, and at each node apply either expression folding or constant evaluation
- walk the tree multiple times, alternating between expression folding and constant evaluation
The solution 1 (similar to what @pjmore proposed in #1128) would likely be more expensive in terms of space because more state needs no be tracked in the subtrees, and more critically would result in a much more complex algorithm. So we have opted for solution 2, which will be easier to implement and test, and the time overhead of walking the tree multiple times will likely be negligible as expression trees are usually rather small (and will grow even smaller at each iteration).
--
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
[GitHub] [arrow-datafusion] rdettai edited a comment on issue #1160: Support simplification that requires multiple applications of constant folding / simplification
Posted by GitBox <gi...@apache.org>.
rdettai edited a comment on issue #1160:
URL: https://github.com/apache/arrow-datafusion/issues/1160#issuecomment-952958330
Great thanks! This is very clear now. So if I understand correctly, this problem has two solutions:
- walk the tree once, and at each node apply either expression folding or constant evaluation
- walk the tree multiple times, alternating between expression folding and constant evaluation
The solution 1 (similar to what @pjmore proposed in #1128) would likely be more expensive in terms of space because more state needs no be tracked in the subtrees, and more critically would result in a much more complex algorithm. So we have opted for solution 2, which will be easier to implement and test, and the time overhead of walking the tree multiple times will likely be negligible as expression trees are usually rather small (and will grow even smaller at each iteration).
(I think this is already what you mentioned in https://github.com/apache/arrow-datafusion/pull/1128#pullrequestreview-782535004, but I thought a recap wouldn't hurt 😄)
--
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
[GitHub] [arrow-datafusion] rdettai commented on issue #1160: Support simplification that requires multiple applications of constant folding / simplification
Posted by GitBox <gi...@apache.org>.
rdettai commented on issue #1160:
URL: https://github.com/apache/arrow-datafusion/issues/1160#issuecomment-952853942
Is this still relevant after #1175 (PR #1176) ?
--
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