datafusion: Large `OR` list overflows the stack
Describe the bug
In InfluxDB we saw people issue queries with many OR chains that caused a stack overflow
SELECT ... WHERE x = 1 OR x = 2 OR ..... x = 10000
To Reproduce
Download: blowout.zip
And run
datafusion-cli -f blowout2.sql
This results in
andrewlamb@Andrews-MacBook-Pro Downloads % datafusion-cli -f blowout2.sql
datafusion-cli -f blowout2.sql
DataFusion CLI v36.0.0
0 rows in set. Query took 0.015 seconds.
+-------+
| count |
+-------+
| 1 |
+-------+
1 row in set. Query took 0.001 seconds.
thread 'main' has overflowed its stack
fatal runtime error: stack overflow
The query looks like this
SELECT *
FROM foo
WHERE x = 1
OR x = 1
OR x = 1
OR x = 1
OR x = 1
....
Expected behavior
a runtime error rather than stack overflow. Bonus points if the query actually completed
Additional context
Here is the stack trace in a release build:
datafusion_common::tree_node::TreeNode::transform_up 0x0000000103cb96f4
datafusion_expr::tree_node::expr::transform_boxed 0x0000000103d86c7c
datafusion_common::tree_node::TreeNode::transform_up 0x0000000103cb9d34
.... MANY MORE ....
datafusion_expr::tree_node::expr::transform_boxed 0x0000000103d86c7c
datafusion_common::tree_node::TreeNode::transform_up 0x0000000103cb9d34
datafusion_expr::tree_node::expr::transform_boxed 0x0000000103d86c7c
datafusion_common::tree_node::TreeNode::transform_up 0x0000000103cb9d34
datafusion_expr::tree_node::expr::transform_boxed 0x0000000103d86c7c
datafusion_common::tree_node::TreeNode::transform_up 0x0000000103cb9d34
datafusion_expr::tree_node::expr::transform_boxed 0x0000000103d86c7c
datafusion_common::tree_node::TreeNode::transform_up 0x0000000103cb9d34
datafusion_expr::tree_node::expr::transform_boxed 0x0000000103d86c7c
datafusion_common::tree_node::TreeNode::transform_up 0x0000000103cb9d34
datafusion_expr::tree_node::expr::transform_boxed 0x0000000103d86c7c
datafusion_common::tree_node::TreeNode::transform_up 0x0000000103cb9d34
datafusion_expr::expr::Expr::infer_placeholder_types 0x0000000103cd30e8
datafusion_sql::expr::<impl datafusion_sql::planner::SqlToRel<S>>::sql_to_expr 0x0000000102b4b180
datafusion_sql::select::<impl datafusion_sql::planner::SqlToRel<S>>::plan_selection 0x0000000102b63980
datafusion_sql::select::<impl datafusion_sql::planner::SqlToRel<S>>::select_to_plan 0x0000000102b64b5c
datafusion_sql::set_expr::<impl datafusion_sql::planner::SqlToRel<S>>::set_expr_to_plan 0x0000000102b710b4
datafusion_sql::query::<impl datafusion_sql::planner::SqlToRel<S>>::query_to_plan_with_schema 0x0000000102b60414
datafusion_sql::statement::<impl datafusion_sql::planner::SqlToRel<S>>::sql_statement_to_plan_with_context_impl 0x0000000102b7ab30
datafusion_sql::statement::<impl datafusion_sql::planner::SqlToRel<S>>::statement_to_plan 0x0000000102b76b84
datafusion::execution::context::SessionState::statement_to_plan::{{closure}} 0x0000000102bded28
datafusion_cli::exec::exec_and_print::{{closure}} 0x0000000102be8428
datafusion_cli::exec::exec_from_lines::{{closure}} 0x0000000102be9efc
datafusion_cli::exec::exec_from_files::{{closure}} 0x0000000102be9a38
datafusion_cli::main_inner::{{closure}} 0x0000000102c051b4
tokio::runtime::park::CachedParkThread::block_on 0x0000000102bfef64
tokio::runtime::runtime::Runtime::block_on 0x0000000102d1ae7c
datafusion_cli::main 0x0000000102ca84d0
std::sys_common::backtrace::__rust_begin_short_backtrace 0x0000000102cd44f0
std::rt::lang_start::{{closure}} 0x0000000102d033f0
[Inlined] core::ops::function::impls::<impl core::ops::function::FnOnce<A> for &F>::call_once function.rs:284
[Inlined] std::panicking::try::do_call panicking.rs:552
[Inlined] std::panicking::try panicking.rs:516
[Inlined] std::panic::catch_unwind panic.rs:142
[Inlined] std::rt::lang_start_internal::{{closure}} rt.rs:148
[Inlined] std::panicking::try::do_call panicking.rs:552
[Inlined] std::panicking::try panicking.rs:516
[Inlined] std::panic::catch_unwind panic.rs:142
std::rt::lang_start_internal rt.rs:148
main 0x0000000102ca85d8
start 0x00000001825fd0e0
About this issue
- Original URL
- State: closed
- Created 3 years ago
- Comments: 26 (26 by maintainers)
i am not saying we shouldn’t do this (OTOH i believe the stack overflows on generates queries, and usually because long associative operations. it’s harder to generate otherwise) let’s do
#[recursive]since it’s simple to do and brings immediate benefit, but it’s likely same benefits (and other perf benefits) would be available by restructuring IR. likely worth exploring as a follow-up to #[recursive]I evaluated stacker as part of sqlparser and I thought it was doing some too crazy stuff that made it hard to use in embedded / wasm environments. Maybe that is better now
FYI @Lordworms I think this will be a pretty challenging task
Also, @peter-toth has an outstanding substantial change to TreeNode APIs here: https://github.com/apache/arrow-datafusion/pull/8891 which you should be aware of.
Yeah, works if I add
#[recursive]toget_type(). Let me open a follow-up PR.Actually, the release build has a different issue. Let me check…
Here is how the recursion guard is implemented in sqlparser: https://github.com/sqlparser-rs/sqlparser-rs/blob/f9ab8dcc27fd2d55030b9c5fa71e41d5c08dd601/src/parser/mod.rs#L67-L127
And then at the start of each major statement, this gets called:
https://github.com/sqlparser-rs/sqlparser-rs/blob/f9ab8dcc27fd2d55030b9c5fa71e41d5c08dd601/src/parser/mod.rs#L469-L470
So I don’t think we would have to change the
transform_*functions, but simply update the closure that was being called by those functionsI think that sounds like a good idea to me
One thing that would be nice would be to somehow avoid having two potential representions for the same expression
So like
A OR Bwould that be represented asBinaryExpr { left: A, op: Or, rigith: B}orCommutativeExpr { exprs: [A, B], op: Or}🤔But that is starting to sound like a large change 🤔
Yes, My basic plan for this is to change recursion in treenode into iteration, I will test my implementation first and read this PR #8891