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

blowout2.zip

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)

Most upvoted comments

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] to get_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 functions

@alamb I’m thinking of introducing CommutativeExpr that specialize these kind of query to make them possible to transform iteratively. What do you think about this?

I 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 B would that be represented as BinaryExpr { left: A, op: Or, rigith: B} or CommutativeExpr { exprs: [A, B], op: Or} 🤔

But that is starting to sound like a large change 🤔

FYI @Lordworms I think this will be a pretty challenging task

Also, @peter-toth has an outstanding substantial change to TreeNode APIs here: #8891 which you should be aware of.

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