apache / apache/datafusion

Stack Overflow with Deeply Nested Filter Expressions

Open
#8,900 4 comments 0 reactions 0 assignees View on GitHub
bug
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.