You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "fmonjalet (via GitHub)" <gi...@apache.org> on 2025/05/12 12:00:04 UTC
[PR] fix: stack overflow for substrait functions with large argument lists that translate to DataFusion binary operators [datafusion]
fmonjalet opened a new pull request, #16031:
URL: https://github.com/apache/datafusion/pull/16031
## Which issue does this PR close?
- Closes #16030
## Rationale for this change
Some substrait plans can cause DataFusion to trigger stack overflow, crashing the hosting process and preventing to run them. This stack overflow is caused by very large recursion levels. See issue for more details.
This kind of issue may also occur in the SQL --> Logical plan path, but I did not investigate it yet. The "ideal" fix would be not to rely on recursion for most operations on plans, but this sounds like an unreasonably large and complex code change for now.
## What changes are included in this PR?
When transforming a substrait function call to DataFusion logical plan,
if the substrait function maps to a DataFusion binary operator, but has
more than 2 arguments, it is mapped to a tree of BinaryExpr. This
BinaryExpr tree is not balanced, and its depth is the number of
arguments:
```
Op
/ \
arg1 Op
/ \
arg2 ...
/ \
argN Op
```
Since many functions manipulating the logical plan are recursive, it
means that N arguments result in an `O(N)` recursion, leading to stack
overflows for large N (1000 for example).
Transforming these function calls into a balanced tree mitigates the
issue:
```
.__ Op __.
/ \
Op Op
/ \ / \
... ... ... ...
/ \ / \ / \ / \
arg1 ... argN
```
The recursion depth is now `O(log2(N))`, meaning that 1000 arguments
results in a depth of ~10, and it would take 2^1000 arguments to reach a
depth of 1000, which is a vastly unreasonable amount of data.
Therefore, it's not possible to use this flaw anymore to trigger stack
overflows in processes running DataFusion.
The new balanced tree preserves the order of execution (`arg1` evaluated
before `arg2`) and has the same order of magnitude of operator nodes.
The main change is that there is now at least `O(log2(N))` operators evaluated,
whereas before the minimum was 1, if the first operator exited after evaluating
only its left side.
## Are these changes tested?
Yes
## Are there any user-facing changes?
No, the change to the logical plan is semantically equivalent and should not be exposed to users.
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] fix: stack overflow for substrait functions with large argument lists that translate to DataFusion binary operators [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on PR #16031:
URL: https://github.com/apache/datafusion/pull/16031#issuecomment-2876910540
> @jayzhan211 After looking into it, generating the plan programatically may become very unwieldy (very verbose). Is your concern about the size of the file checked into git, or the fact that it's hard to read because it's so large? If it's the former, I can put in two files and put together some string formatting. If it's the former, this won't help as much, but will still be more readable for humans.
My idea is that we can generate such parameters for the code we want to test, we don't need end to end test from json.
I take a quick look, if we enter this function, I think it is possible to generate a deep nested `Expression` that easily cause stack overflow.
```rust
async fn consume_expression(
&self,
expr: &Expression,
input_schema: &DFSchema,
) -> datafusion::common::Result<Expr> {
from_substrait_rex(self, expr, input_schema).await
}
```
If that doesn't work, I think we don't even need to keep such test since the change to me is quite trivial.
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] fix: stack overflow for substrait functions with large argument lists that translate to DataFusion binary operators [datafusion]
Posted by "fmonjalet (via GitHub)" <gi...@apache.org>.
fmonjalet commented on PR #16031:
URL: https://github.com/apache/datafusion/pull/16031#issuecomment-2876849092
@jayzhan211 After looking into it, generating the plan programatically may become very unwieldy (very verbose). Is your concern about the size of the file checked into git, or the fact that it's hard to read because it's so large?
If it's the former, I can put in two files and put together some string formatting. If it's the former, this won't help much as it will still be pretty hard to read and understand and we'll have to find another better way!
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] fix: stack overflow for substrait functions with large argument lists that translate to DataFusion binary operators [datafusion]
Posted by "fmonjalet (via GitHub)" <gi...@apache.org>.
fmonjalet commented on PR #16031:
URL: https://github.com/apache/datafusion/pull/16031#issuecomment-2877308068
@jayzhan211 and @gabotechs thank you for your guidance, I updated the PR:
- Expressions are not cloned anymore.
- The test has been scoped to a much more unit test style, where we build a substrait `ScalarFunction` call and translate it to a DataFusion expression. I manually checked that reverting the fix made the test fail. It requires a larger argument list to trigger the issue because the expressions are simpler than in the original complex plan I submitted.
Ready for a next round of feedback if any!
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] fix: stack overflow for substrait functions with large argument lists that translate to DataFusion binary operators [datafusion]
Posted by "fmonjalet (via GitHub)" <gi...@apache.org>.
fmonjalet commented on PR #16031:
URL: https://github.com/apache/datafusion/pull/16031#issuecomment-2873266272
> Is it possible to add the test that generate equivalent json?
@jayzhan211 sure, I can even try to build the substrait plan programatically. This will be more verbose, but more explicit.
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] fix: stack overflow for substrait functions with large argument lists that translate to DataFusion binary operators [datafusion]
Posted by "LiaCastaneda (via GitHub)" <gi...@apache.org>.
LiaCastaneda commented on code in PR #16031:
URL: https://github.com/apache/datafusion/pull/16031#discussion_r2084629270
##########
datafusion/substrait/src/logical_plan/consumer/expr/scalar_function.rs:
##########
@@ -124,6 +109,31 @@ pub fn name_to_op(name: &str) -> Option<Operator> {
}
}
+/// Build a balanced tree of binary operations from a binary operator and a list of arguments.
+///
+/// For example, `OR` `(a, b, c, d, e)` will be converted to: `OR(OR(a, OR(b, c)), OR(d, e))`.
+///
+/// `args` must not be empty.
+fn arg_list_to_binary_op_tree(
+ op: Operator,
+ args: &[Expr],
+) -> Expr {
+ if args.len() == 1 {
+ return args[0].clone();
+ } else if args.len() == 0 {
+ panic!("must not be called with empty args");
+ }
+ // Cut argument list in 2 balanced parts
+ let mid_idx = args.len() / 2;
+ let left = arg_list_to_binary_op_tree(op, &args[0..mid_idx]);
+ let right = arg_list_to_binary_op_tree(op, &args[mid_idx..]);
+ Expr::BinaryExpr(BinaryExpr {
+ left: Box::new(left),
+ op,
+ right: Box::new(right),
+ })
+}
Review Comment:
quick question: is it safe to balance any operator?
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] fix: stack overflow for substrait functions with large argument lists that translate to DataFusion binary operators [datafusion]
Posted by "gabotechs (via GitHub)" <gi...@apache.org>.
gabotechs commented on code in PR #16031:
URL: https://github.com/apache/datafusion/pull/16031#discussion_r2084556175
##########
datafusion/substrait/src/logical_plan/consumer/expr/scalar_function.rs:
##########
@@ -124,6 +109,31 @@ pub fn name_to_op(name: &str) -> Option<Operator> {
}
}
+/// Build a balanced tree of binary operations from a binary operator and a list of arguments.
+///
+/// For example, `OR` `(a, b, c, d, e)` will be converted to: `OR(OR(a, OR(b, c)), OR(d, e))`.
+///
+/// `args` must not be empty.
+fn arg_list_to_binary_op_tree(
+ op: Operator,
+ args: &[Expr],
+) -> Expr {
+ if args.len() == 1 {
+ return args[0].clone();
+ } else if args.len() == 0 {
+ panic!("must not be called with empty args");
+ }
+ // Cut argument list in 2 balanced parts
+ let mid_idx = args.len() / 2;
+ let left = arg_list_to_binary_op_tree(op, &args[0..mid_idx]);
+ let right = arg_list_to_binary_op_tree(op, &args[mid_idx..]);
+ Expr::BinaryExpr(BinaryExpr {
+ left: Box::new(left),
+ op,
+ right: Box::new(right),
+ })
+}
Review Comment:
Nice! do you think we can do it without cloning the expressions? something like:
```rust
fn arg_list_to_binary_op_tree(op: Operator, mut args: Vec<Expr>) -> Expr {
if args.is_empty() {
panic!("must not be called with empty args");
}
if args.len() == 1 {
return args.into_iter().next().unwrap();
}
// Cut argument list in 2 balanced parts
let mid_idx = args.len() / 2;
let right = arg_list_to_binary_op_tree(op, args.split_off(mid_idx));
let left = arg_list_to_binary_op_tree(op, args);
Expr::BinaryExpr(BinaryExpr {
left: Box::new(left),
op,
right: Box::new(right),
})
}
```
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] fix: stack overflow for substrait functions with large argument lists that translate to DataFusion binary operators [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb merged PR #16031:
URL: https://github.com/apache/datafusion/pull/16031
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] fix: stack overflow for substrait functions with large argument lists that translate to DataFusion binary operators [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #16031:
URL: https://github.com/apache/datafusion/pull/16031#issuecomment-2891772639
I plan to merge this PR to main once the CI has passed
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] fix: stack overflow for substrait functions with large argument lists that translate to DataFusion binary operators [datafusion]
Posted by "fmonjalet (via GitHub)" <gi...@apache.org>.
fmonjalet commented on PR #16031:
URL: https://github.com/apache/datafusion/pull/16031#issuecomment-2893193784
Thanks everyone for the review and the merge!
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] fix: stack overflow for substrait functions with large argument lists that translate to DataFusion binary operators [datafusion]
Posted by "fmonjalet (via GitHub)" <gi...@apache.org>.
fmonjalet commented on code in PR #16031:
URL: https://github.com/apache/datafusion/pull/16031#discussion_r2087256490
##########
datafusion/substrait/src/logical_plan/consumer/expr/scalar_function.rs:
##########
@@ -124,6 +109,31 @@ pub fn name_to_op(name: &str) -> Option<Operator> {
}
}
+/// Build a balanced tree of binary operations from a binary operator and a list of arguments.
+///
+/// For example, `OR` `(a, b, c, d, e)` will be converted to: `OR(OR(a, OR(b, c)), OR(d, e))`.
+///
+/// `args` must not be empty.
+fn arg_list_to_binary_op_tree(
+ op: Operator,
+ args: &[Expr],
+) -> Expr {
+ if args.len() == 1 {
+ return args[0].clone();
+ } else if args.len() == 0 {
+ panic!("must not be called with empty args");
+ }
+ // Cut argument list in 2 balanced parts
+ let mid_idx = args.len() / 2;
+ let left = arg_list_to_binary_op_tree(op, &args[0..mid_idx]);
+ let right = arg_list_to_binary_op_tree(op, &args[mid_idx..]);
+ Expr::BinaryExpr(BinaryExpr {
+ left: Box::new(left),
+ op,
+ right: Box::new(right),
+ })
+}
Review Comment:
@gabotechs unfortunately [`.split_off()` calls clone](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.split_off), but I got a simple enough version working with an explicit `Drain`. Thanks for making me look again!
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] fix: stack overflow for substrait functions with large argument lists that translate to DataFusion binary operators [datafusion]
Posted by "fmonjalet (via GitHub)" <gi...@apache.org>.
fmonjalet commented on PR #16031:
URL: https://github.com/apache/datafusion/pull/16031#issuecomment-2872319033
According to the [contributor guide](https://datafusion.apache.org/contributor-guide/index.html#pull-request-overview), mentioning @alamb to trigger the CI because you were the most frequent reviewer on the substrait topic recently (sorry if the direct ping is too noisy -- tell me if I should proceed otherwise).
Also pinging @gabotechs as the latest committer on this file.
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] fix: stack overflow for substrait functions with large argument lists that translate to DataFusion binary operators [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #16031:
URL: https://github.com/apache/datafusion/pull/16031#issuecomment-2891850119
Thanks again everyone
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] fix: stack overflow for substrait functions with large argument lists that translate to DataFusion binary operators [datafusion]
Posted by "fmonjalet (via GitHub)" <gi...@apache.org>.
fmonjalet commented on PR #16031:
URL: https://github.com/apache/datafusion/pull/16031#issuecomment-2877173240
Oh right it makes sense, I'll try to produce a test based on `consume_expression` then. Thanks!
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] fix: stack overflow for substrait functions with large argument lists that translate to DataFusion binary operators [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on PR #16031:
URL: https://github.com/apache/datafusion/pull/16031#issuecomment-2872337218
Is it possible to add the test that generate equivalent json?
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] fix: stack overflow for substrait functions with large argument lists that translate to DataFusion binary operators [datafusion]
Posted by "LiaCastaneda (via GitHub)" <gi...@apache.org>.
LiaCastaneda commented on code in PR #16031:
URL: https://github.com/apache/datafusion/pull/16031#discussion_r2084631098
##########
datafusion/substrait/src/logical_plan/consumer/expr/scalar_function.rs:
##########
@@ -124,6 +109,31 @@ pub fn name_to_op(name: &str) -> Option<Operator> {
}
}
+/// Build a balanced tree of binary operations from a binary operator and a list of arguments.
+///
+/// For example, `OR` `(a, b, c, d, e)` will be converted to: `OR(OR(a, OR(b, c)), OR(d, e))`.
+///
+/// `args` must not be empty.
+fn arg_list_to_binary_op_tree(
+ op: Operator,
+ args: &[Expr],
+) -> Expr {
+ if args.len() == 1 {
+ return args[0].clone();
+ } else if args.len() == 0 {
+ panic!("must not be called with empty args");
+ }
+ // Cut argument list in 2 balanced parts
+ let mid_idx = args.len() / 2;
+ let left = arg_list_to_binary_op_tree(op, &args[0..mid_idx]);
+ let right = arg_list_to_binary_op_tree(op, &args[mid_idx..]);
+ Expr::BinaryExpr(BinaryExpr {
+ left: Box::new(left),
+ op,
+ right: Box::new(right),
+ })
+}
Review Comment:
ah ok nvm, I just read order of execution is preserved ^
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org