-
-
Notifications
You must be signed in to change notification settings - Fork 1.7k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Quadratic scaling in expression depth when collecting expressions #16224
Comments
How does it perform if you turn off And how do you get so deep expressions? 😉 |
Same, indeed with all optimisations off it's still quadratic, just faster overall:
I've seen things... It was more that I was transpiling the plan and noticed performance slowdowns when annotating the logical plan with dtypes for every expression node. |
Will see if we can apply some memoization in the |
I am not entirely sure the tree itself isn't quadratic. I need to do double the |
I don't think so. The expression is (for
Or
So if you need to call |
BTW: should I expect that the AExpr processing treats expressions with common sub-expressions like DAGs, or like trees (increasing the perceived size?). That is, if I write:
Which is:
Is it "seen" as:
|
It is seen as trees. They are turned into DAGS during execution if CSE recognized it. |
Thanks. I suspect that means there are (perhaps pathological) cases where expression processing time can be exponential: any time there is sharing in the expression. Though perhaps that is an unlikely case for typical queries. |
Checks
Reproducible example
Log output
Issue description
Optimising, I think, the logical plan has performance that is quadratic in the expression depth. I think the culprit is
AExpr::to_field
which is called to attach a dtype at every node in the graph. But since the result is not cached, this is O(N) for a node, and done O(N) times.Running
samply python run.py 1600
shows almost all the time is inget_arithmetic_field -> to_field -> stacker::maybe_grow -> get_arithmetic_field -> ...
Expected behavior
Although this is somewhat pathological, I would expect this to be linear in the expression depth.
Installed versions
The text was updated successfully, but these errors were encountered: