Stack Overflow with Deeply Nested Filter Expressions
- Dominant language
- Rust
- Stars
- 9.3k
- Forks
- 2.4k
- Avg merge
- 3d 7h
- Merged PRs (30d)
- 344
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:
```rust
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
Contributor guide
Research direction
Start by reproducing the Rust example with the deeply nested filter and trace the filter-expression normalization that uses transform_up. Investigate how that traversal behaves at the reported depths; done means the query completes without a stack overflow for the reproduction and the behavior is covered by an appropriate regression check.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- backend, performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100