Flatter representation of deeply nested `AND` / `OR` Expressions

[alamb]

Is your feature request related to a problem or challenge?

DataFusion represents arbitrary binary Operator trees like

(a OR (b OR (c OR (d OR ...)))

Using a binary tree structure called BinaryExpr:

datafusion/datafusion/expr/src/expr.rs

Lines 770 to 779 in 2da8887

	/// Binary expression for [`Expr::BinaryExpr`]
	#[derive(Clone, PartialEq, Eq, PartialOrd, Hash, Debug)]
	pub struct BinaryExpr {
	/// Left-hand side of the expression
	pub left: Box<Expr>,
	/// The comparison operator
	pub op: Operator,
	/// Right-hand side of the expression
	pub right: Box<Expr>,
	}

There are also many places in the codebase where recursive algorithms are used to walk over Expr trees,

An example of this is Treenode::apply:

datafusion/datafusion/common/src/tree_node.rs

Lines 196 to 209 in 0838a4d

	fn apply<'n, F: FnMut(&'n Self) -> Result<TreeNodeRecursion>>(
	&'n self,
	mut f: F,
	) -> Result<TreeNodeRecursion> {
	#[cfg_attr(feature = "recursive_protection", recursive::recursive)]
	fn apply_impl<'n, N: TreeNode, F: FnMut(&'n N) -> Result<TreeNodeRecursion>>(
	node: &'n N,
	f: &mut F,
	) -> Result<TreeNodeRecursion> {
	f(node)?.visit_children(|| node.apply_children(|c| apply_impl(c, f)))
	}
	apply_impl(self, &mut f)
	}

The stack depth is a function of the nesting depth of the expression, which means that

Important

In some cases processing deeply nested expressions can lean to a stack overflow (and thus a process abort)

This shows up in practice from Machine-generated SQL/filters with thousands of OR/AND terms (e.g. IN lists rewritten to OR, or large predicate pushdown

This representation has served us quite well, but we do have several mitigations

1. recursive crate + recursive_protection feature (segmented stack growth)

The primary mitigation. Recursive TreeNode drivers are annotated #[cfg_attr(feature = "recursive_protection", recursive::recursive)], which uses the recursive crate to grow the stack on the heap when it runs low, instead of overflowing. See the TreeNode walkers (6 sites — apply/transform_down/transform_up/rewrite/etc.):

datafusion/datafusion/common/src/tree_node.rs

Lines 196 to 209 in 0838a4d

	fn apply<'n, F: FnMut(&'n Self) -> Result<TreeNodeRecursion>>(
	&'n self,
	mut f: F,
	) -> Result<TreeNodeRecursion> {
	#[cfg_attr(feature = "recursive_protection", recursive::recursive)]
	fn apply_impl<'n, N: TreeNode, F: FnMut(&'n N) -> Result<TreeNodeRecursion>>(
	node: &'n N,
	f: &mut F,
	) -> Result<TreeNodeRecursion> {
	f(node)?.visit_children(|| node.apply_children(|c| apply_impl(c, f)))
	}
	apply_impl(self, &mut f)
	}

2. SQL parser recursion limit (bounded recursion → error, not crash)

The sqlparser crate itself caps nesting depth (default 50) and returns RecursionLimitExceeded rather than overflowing the stack.

3. Explicit-stack (iterative) SQL→Expr conversion

• See issue Avoid stack overflow in Datafusion #1444

We also hit this a bunch when converting a sqlparser binary-operator tree into Expr and have a stack based conversion approach (see

datafusion/datafusion/sql/src/expr/mod.rs

Lines 76 to 120 in 0838a4d

	) -> Result<Expr> {
	enum StackEntry {
	SQLExpr(Box<SQLExpr>),
	Operator(BinaryOperator),
	}
	// Virtual stack machine to convert SQLExpr to Expr
	// This allows visiting the expr tree in a depth-first manner which
	// produces expressions in postfix notations, i.e. `a + b` => `a b +`.
	// See https://github.com/apache/datafusion/issues/1444
	let mut stack = vec![StackEntry::SQLExpr(Box::new(sql))];
	let mut eval_stack = vec![];
	while let Some(entry) = stack.pop() {
	match entry {
	StackEntry::SQLExpr(sql_expr) => {
	match *sql_expr {
	SQLExpr::BinaryOp { left, op, right } => {
	// Note the order that we push the entries to the stack
	// is important. We want to visit the left node first.
	stack.push(StackEntry::Operator(op));
	stack.push(StackEntry::SQLExpr(right));
	stack.push(StackEntry::SQLExpr(left));
	}
	_ => {
	let expr = self.sql_expr_to_logical_expr_internal(
	*sql_expr,
	schema,
	planner_context,
	)?;
	eval_stack.push(expr);
	}
	}
	}
	StackEntry::Operator(op) => {
	let right = eval_stack.pop().unwrap();
	let left = eval_stack.pop().unwrap();
	let expr = self.build_logical_expr(op, left, right, schema)?;
	eval_stack.push(expr);
	}
	}
	}
	assert_eq!(1, eval_stack.len());
	let expr = eval_stack.pop().unwrap();

)

4. Out-of-line match arms in the expression simplifier

Large match arms are extracted into separate functions specifically to shrink per-frame stack usage and avoid overflow during simplification.

• datafusion/datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs

  Lines 2335 to 2341 in 0838a4d

  	// Move this function body out of the large match branch avoid stack overflow
  	fn simplify_right_is_one_case(
  	info: &SimplifyContext,
  	left: Box<Expr>,
  	op: &Operator,
  	right: &Expr,
  	) -> Result<Transformed<Expr>> {

Recently people seem to be hitting recursion limits again and trying to put in patches, such as

• fix: drop a deep BinaryExpr chain iteratively to avoid a stack overflow #23198 from @mdashti
• fix: graceful error for deeply nested expressions instead of stack overflow #22943 from @nathanb

Describe the solution you'd like

I would like a more fool proof way to avoid stack overflow issues

Describe alternatives you've considered

Option 1: n-ary expressions

The approach taken by DuckDb Mysql and Postgres is to represent AND and OR as n-ary rather than binary (2)

So that would be something like this (could also have an enum for And/Or)

enum ConjunctionType { And, Or }
/// AND/OR of some number of expressions
struct Conjunction {
  conjunction_type: ConjunctionType,
  /// Logically `exprs[0] AND (exprs[1] AND (exprs[2] AND ...`
  exprs : Vec<Expr>.
}

And then

/// extend the Expr enum
enum Expr { 
  ...
  // AND
  Conjunction(Conjunction),
 ...
}

Examples:

DuckDB uses ConjunctionExpression: https://github.com/duckdb/duckdb/blob/b8a06e4a22672e254cd0baa68a3dbed2eb51c56e/src/include/duckdb/parser/expression/conjunction_expression.hpp#L17-L27

Postrgres uses BoolExpr https://github.com/postgres/postgres/blob/REL_17_0/src/include/nodes/primnodes.h#L929-L942

Mysql uses Item_cond_and / Item_cond_or (based on Item_cond base which stores args as a List list;

Cons

This would be a major downstream API change
Also unless we removed Operator::And / Operator::Or we would potentially have multiple ways to express the same logical expression

Keep Binary Expr, have some sort of "balance" operation

Another approach taken by spark is to use Binary expressions: https://github.com/apache/spark/blob/fa33ea000a0bda9e5a3fa1af98e8e85b8cc5e4d4/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/predicates.scala#L828

buildBalancedPredicate rebuilds a predicate list into a height-balanced tree in

• [SPARK-34222][SQL][FOLLOWUP] Non-recursive implementation of buildBalancedPredicate spark#31724

Additional context

Recent PRs

• fix: drop a deep BinaryExpr chain iteratively to avoid a stack overflow #23198 from @mdashti
• fix: graceful error for deeply nested expressions instead of stack overflow #22943 from @nathanb

🎯 Umbrella / strategic (open)

• Restructure core codepaths to prevent stack overflows #16788 — the epic to explore iterative rewrites / Box-ing / n-ary to remove the need for #[recursive] and regain the 1–2% planning overhead.
• Update recursion limit in DataFusion #14857
• reduce recursion level of unparser part #19787
• Find a safe alternative to LogicalPlan::using_columns() #14118

🐛 Open stack-overflow bugs (motivating cases)

• panic: deep binary expression in SELECT projection aborts with stack overflow #22229
• Deep WHERE clause overflow stack in select_to_plan via derived expr::clone #22936
• Stack Overflow with Deeply Nested Filter Expressions #8900
• StackGuard races recursive's process-global stack-size minimum across threads #23246

📜 Closed — the history that motivated the current mitigations

• Avoid stack overflow in Datafusion #1444
• Query with 100 OR conditions overflows stack #1434
• Large OR list overflows the stack #9375
• Excessive number of filters overflows the stack #11102
• Stack overflow for substrait functions with large argument lists that translate to DataFusion binary operators #16030
• Support serializing more deeply nested AND / OR expressions #4066
• Expr::to_bytes can produce output that hits Expr::from_bytes recursion limit #3968
• Unparser stack overflow: recursive_protection is bypassed for nested function arguments / dialect overrides (public expr_to_sql not #[recursive]) #23056
• Improve create_initial_plan to get rid of "stack overflow" issues on complex queries #9573
• Deeply recursive UNION queries cause stack overflow #9373
• stack overflow on PhysicalPlanNode::try_from_physical_plan #15087
• TPC-DS planning overflows: thread 'tpcds_logical_q64' has overflowed its stack #6277, thread 'tpcds_logical_q64' has overflowed its stack #6264, Stack overflow while generating logical plan from statement #6040, Stack overflows when planning tpcds 22 in debug mode #4786, Stack overflow planning complex query #4065, [CI] Investigate stack overflow errors on TPC-DS queries #8837

[devanbenz]

@alamb thanks for putting this together. If this is something we actually want to do I would love to help with the implementation.

[alamb]

Thanks @devanbenz -- i think the hardest part of this would be to manage the downtream fallout -- like it will be quite disruptive to a lot of people for whom the current representation is working just fine 🤔

[devanbenz]

Thanks @devanbenz -- i think the hardest part of this would be to manage the downtream fallout -- like it will be quite disruptive to a lot of people for whom the current representation is working just fine 🤔

Totally makes sense.

[devanbenz]

FYI @nathanb9 I was able to compile datafusion-cli with and without the recursive_protection feature flag. It seemed to have fixed the issue.

Without recursive_protection flag.

DataFusion CLI v54.0.0
> select * from 'test.csv' WHERE a = 1 OR a = 2 ... OR a = 1000; // repeated with 1000 ORs.

thread 'main' (841365) has overflowed its stack
fatal runtime error: stack overflow, aborting

With recursive_protection (albeit pretty slow, which makes sense)

DataFusion CLI v54.0.0
> select * from 'test.csv' WHERE a = 1 OR a = 2 ... OR a = 1000; // repeated with 1000 ORs.

+---+---+
| a | b |
+---+---+
| 1 | 2 |
+---+---+
1 row(s) fetched. 
Elapsed 1.132 seconds.

@alamb I have an internal ticket for this bug at InfluxData as well, so I'll go ahead and try to recompile influx with this feature flag and see if that fixes the issue.

[nathanb9]

@devanbenz nice, I didnt even think the recursive_protection would even help because the failure in your issue is at a derived Clone...
but FYI this is may not be super reliable because the stack is not protected if it grows at derived Clone . Since that portion of the code can't be wrapped with the annotation, it can still overflow...

[devanbenz]

@devanbenz nice, I didnt even think the recursive_protection would even help because the failure in your issue is at a derived Clone... but FYI this is may not be super reliable because the stack is not protected if it grows at derived Clone . Since that portion of the code can't be wrapped with the annotation, it can still overflow...

I need to test in InfluxDB still, it could very well still be the case.

[mbutrovich]

Just for some context, Comet had to tackle this due to Protobuf plan serialization limits: apache/datafusion-comet#4531

[alamb]

The rebalancing idea is pretty neat and non disruptive -- maybe we someone could prototype what that looks like / port it upstreat to DataFUsion 🤔

[devanbenz]

The rebalancing idea is pretty neat and non disruptive -- maybe we someone could prototype what that looks like / port it upstreat to DataFUsion 🤔

So, essentially implementing something similar to this re-balancing algorithm? https://github.com/apache/spark/blob/fa33ea000a0bda9e5a3fa1af98e8e85b8cc5e4d4/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/predicates.scala#L160-L184