Repository navigation
Deeply recursive UNION queries cause stack overflow #9373
Description
Activity
take
I believe there are two ways to fully resolve this issue:
-
Switch from the recursion to iteration like Switch to non-recursive on heap virtual stack when building logical plan from SQL expression #6360 and Refactor physical create_initial_plan to iteratively & concurrently construct plan from the bottom up #10023. To do this, we would need to process nodes via VecDeque or Vec. We also need to reimplement support for
TreeNodeRecursionso users can still control the processing flow. -
Keep the recursion but use something like https://github.com/DelSkayn/reblessive. The downside is adding another dependency, but on the plus side, it will make fixing stack overflow bugs easier in the future. That way, the current
TreeNodeRecursionimplementation would still work.
I will go with the first option, because it was suggested by @alamb, but open to discussing this further if needed 🙂
Reacted by Andrew Lamb and Marko Grujic-
Just wanted to share my thoughts on the task before I bombard you with PRs 😅
I think
ConcreteTreeNodeandDynTreeNodeare the best places to write iterative algorithms. They already have methods to get and replace children, so we can flatten and update them iteratively. Re-implementing non-recursivevisit/rewrite/transformmethods forConcreteTreeNodeandDynTreeNodefeels like a good first step to me.Once this is done, we will need to implement either of those two traits for
LogicalPlan:Because
LogicalPlanstores its children inArcs, it feels natural to implement support forDynTreeNode. But I think this approach will be slow. Right now, when we domap_children, we destructselfbefore invoking the given function on theArc::unwrap_or_clone(Arc<LogicalPlan>). This means that most likely, we just unwrap the child logical plan without copy because no one else is probably referencing it. However, if we implement support for theDynTreeNode, we won't be able to pull off the same trick with zero copy. The node will still be referenced by its parent, sounwrap_or_clonewill become costly.Hence, I think
ConcreteTreeNodewill probably be a better candidate. The transition will be a bit tricky, because currentlyLogicalPlanstores only shared references to the objects. But I think we can update this with not a lot of API changes.I see two options for that:
-
To me personally, it feels natural for
LogicalPlanto own its children, for example by storing them inBoxrather than inArc. Even now, if the child plan is referenced multiple times, we'll copy it on rewrite anyway, so I don't think this proposal will increase the clone rate. But on the negative side, we'll have to changeLogicalPlan,Subquery,Exprinner types and some methods... -
Alternatively, we can switch to capturing state in closures, for example:
pub enum MaybeBarren<T> { Present(T), // node has been destructed, but can be re-constructed when we get its children Barren(Box<dyn FnOnce(Vec<T>) -> Result<T>>), }
There will still be some struct and methods changes, but probably less than in the option one. But then it will be harder to implement functions like
transform_down_up_with_subqueriesReacted by Andrew Lamb and Bruce Ritchie-
To me personally, it feels natural for LogicalPlan to own its children
I do think that has been brought up many times before. Now that we have a better infrastructure for rewriting plans without forcing copies I think it might make more sense than it did previously (where we had to have relatively cheap LogicalPlan::clone)
Reacted by Dmitrii Blaginin
Describe the bug
In InfluxDB we sometimes create deeply nested queries like this that cause a stack overflow, even in release builds:
To Reproduce
Download: blowout.zip
And run
This results in
andrewlamb@Andrews-MacBook-Pro Downloads % datafusion-cli -f blowout.sql datafusion-cli -f blowout.sql DataFusion CLI v36.0.0 thread 'main' has overflowed its stack fatal runtime error: stack overflowThe query looks like this
Expected behavior
a runtime error rather than stack overflow. Bonus points if the query actually completed
Additional context
It may be possible to change the treenode recursion to use an iterative approach rather than a recursive one (aka keep a worklist), much as we did in the sql parser to protect against deeply nested expressions
Note it is important to use a release build (as the debug build fails earlier in the process)
In a release build, the stack looks like this: