Repository navigation
Stack Overflow with Deeply Nested Filter Expressions #8900
Description
Describe the bug
When running a query with a deeply nested filter expression the query fails with stack overflow – the bug initially manifested as a EXC_BAD_ACCESS error on macOS in our application. The problem is that the filter expression is recursively normalized using transform_up which can cause stack overflows. This probably also happens in other scenarios where one would end up with a deeply nested tree.
Tested/Reproduced with:
version = "34.0.0"
macOS = 14.2.1
To Reproduce
Minimal Reproducible Example:
use datafusion::arrow::array::Int64Array;
use datafusion::arrow::datatypes::DataType;
use datafusion::arrow::datatypes::Field;
use datafusion::arrow::datatypes::Schema;
use datafusion::arrow::record_batch::RecordBatch;
use datafusion::error::Result;
use datafusion::prelude::*;
use std::sync::Arc;
#[tokio::main]
async fn main() -> Result<()> {
let ctx = SessionContext::new();
let batch = RecordBatch::try_new(
Arc::new(Schema::new(vec![Field::new("a", DataType::Int64, false)])),
vec![Arc::new(Int64Array::from(vec![
1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
]))],
)?;
let df = ctx.read_batch(batch)?;
let mut expr = col("a").eq(lit(1));
for _ in 0..1000 {
expr = expr.or(col("a").eq(lit(1)));
}
let df = df.filter(expr).unwrap();
df.show().await
}For it to run into an SO with an optimized release build the depth needs to be increased to 10000.
Expected behavior
The query should complete without errors, despite the complexity of the filter expression.
Additional context
No response
/cc @nfnt
Activity
[-]Stack Overflo with Deeply Nested Filter Expressions[/-][+]Stack Overflow with Deeply Nested Filter Expressions[/+]orlandohohmeier commentedon Jan 18, 2024
Current Quickfix: Increasing the stack size e.g. via the RUST_MIN_STACK environment variable (e.g., to 16MB) temporarily resolves the issue.
Long-term Solution: We should probably implement and use a stackless variant of
transform_up,transform_down, and their mutable counterparts. I'd be happy to draft a PR, given their widespread use, the limited set of functions inTreeNodeand need for post-order traversal, I am unsure how to best fix this bug though.alamb commentedon Jan 21, 2024
Thanks @orlandohohmeier -- note there is some significant work currently being undertaken on the
TreeNodeAPIs -- see #8913Maybe once that is done, it will be easier to implement a stackless variant 🤔
We have some version of this pattern in the SQL planner already (SqlToRel)
orlandohohmeier commentedon Jan 23, 2024
@alamb, thanks for the pointers! I'll dive into #8913 to understand the ongoing changes in the TreeNode APIs better. Glancing over it and aiming at maintaining the interface things could be done in parallel. I'll also review the existing implementation of the
SqlToRelpattern in the SQL planner. This might provide valuable insights or a potential pathway for implementing a stackless variant fortransform_upand related functions. I will get back once I have an idea of how to do the refactoring.alamb commentedon Dec 14, 2024
This may have been fixed by