Skip to content
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

Avoid stack overflow in Datafusion #1444

Closed
xudong963 opened this issue Dec 14, 2021 · 2 comments · Fixed by #6360
Closed

Avoid stack overflow in Datafusion #1444

xudong963 opened this issue Dec 14, 2021 · 2 comments · Fixed by #6360

Comments

@xudong963
Copy link
Member

xudong963 commented Dec 14, 2021

Rewrite recursive procedures into iterative procedures, suggested by @houqp @alamb

This is an acceptable short term workaround, but I think it would be more efficient and more elegant if we rewrite these recursive procedures into iterative procedures.

Do you mean to use push-based model?

@xudong963 , I think what @houqp is suggesting is to rewrite code that is recursive to not be recursive.

The pattern for Datafusion probably looks like taking code like

fn visit(expr: &expr)  {
  for child in expr.children() {
    visit(child)
  }
  // do actual expr logic
}

And changing it so the state is tracked with a structure on the heap rather than a stack. I think VecDeque is a good one for rust:

fn visit(expr: &expr)  {
  let mut worklist = VecDequeue::new();
  worklist.push_back(expr);
  while !worklist.is_empty() {
    let parent = worklist.pop_front();
    for child in parent.children() {
      worklist.push_back(child)
    }
    // do actual expr logic on parent
  }
}

(aka avoid the call back to visit)

Originally posted by @alamb in #1437 (comment)

@alamb
Copy link
Contributor

alamb commented Dec 14, 2021

👍

@Dandandan
Copy link
Contributor

For normal (depth first / FIFO) recursion like the example on top a plain Vec could be used to push and pop the recursive values.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
3 participants