apache / apache/datafusion

Avoid recompute CTEs (common table expressions) / share input plans

Open
#8,777 16 comments 3 reactions 0 assignees View on GitHub
enhancement
Dominant language
Rust
Stars
9.3k
Forks
2.4k
Avg merge
3d 7h
Merged PRs (30d)
344

Description

### Is your feature request related to a problem or challenge?

The core usecase is:
```sql
with x as (

)

select * from x where ...
union all
select * from x where ...
union all
select * from x where ...
```

DataFusion will effectively run the subquery `x` three times (it will basically copy the `LogicalPlan` for `x` wherever it is used.

```
┌─────────────────────┐
│ UNION ALL │
│ │
└─────────────────────┘
▲ ▲ ▲
│ │ │
┌─────────────────────────────┘ │ └─────────────────────────────┐
│ │ │
│ │ │
┌────────────────┐ ┌────────────────┐ ┌────────────────┐
│ Filter 1 │ │ Filter 2 │ │ Filter 3 │
└────────────────┘ └────────────────┘ └────────────────┘
▲ ▲ ▲
│ │ │
│ │ │
┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐
┌────────────────┐ ┌────────────────┐ ┌────────────────┐
│ │ Expensive Join │ │ │ │ Expensive Join │ │ │ │ Expensive Join │ │
└────────────────┘ └────────────────┘ └────────────────┘
│ ▲ │ │ ▲ │ │ ▲ │
┌──────┴──────┐ ┌──────┴──────┐ ┌──────┴──────┐
│ │ │ │ │ │ │ │ │ │ │ │
.───────. .───────. .───────. .───────. .───────. .───────.
│ ╱ ╲ ╱ ╲ │ │ ╱ ╲ ╱ ╲ │ │ ╱ ╲ ╱ ╲ │
( Input 1 ) ( Input 2 ) ( Input 1 ) ( Input 2 ) ( Input 1 ) ( Input 2 )
│ `. ,' `. ,' │ │ `. ,' `. ,' │ │ `. ,' `. ,' │
`─────' `─────' `─────' `─────' `─────' `─────'
│"x" │ │"x" │ │"x" │
─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
```

This design has certain benefits:
1. It is straightforward to implement (probably why DataFusion is like this)
3. If the different `UNION ALL` arms have different predicates, they could potentially be pushed down in one branch but not the others.

### Describe the solution you'd like

However, in many cases it would likely be better to do to the expensive join only once and reuse the results like this:

```text
┌─────────────────────┐
│ UNION ALL │
│ │
└─────────────────────┘
▲ ▲ ▲
│ │ │
┌─────────────────┘ │ └───────────────────┐
│ │ │
│ │ │
│ │ │
┌────────────────┐ ┌────────────────┐ ┌────────────────┐
│ Filter 1 │ │ Filter 2 │ │ Filter 3 │
└────────────────┘ └────────────────┘ └────────────────┘
▲ ▲ ▲
│ │ │
│ │ │
└────────────────────┐ │ ┌─────────────────────┘
│ │ │
│ │ │
│ │ │
┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐
┌────────────────┐
│ │ Expensive Join │ │
└────────────────┘
│ ▲ │
┌──────┴──────┐
│ │ │ │
.───────. .───────.
│ ╱ ╲ ╱ ╲ │
( Input 1 ) ( Input 2 )
│ `. ,' `. ,' │
`─────' `─────'
│"x" │
─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
```

### Describe alternatives you've considered

I think there are several considerations for this design, the biggest is that it is a 'diamond' plan where the same stream can be consumed at different rates potentially needing to buffer the entire intermediate result or else the plan will deadlock

For example

```
┌─────────────────────┐
│ Hash Join │
│ │
└─────────────────────┘
▲ ▲
│ │
┌─────────────┘ └────────────┐
│ │
│ │
│ │
Build Side Probe Side
(read completely (not read at all until Build
before probe side) Side is completely read)
▲ ▲
│ │
│ │
└────────────────────┬────────────────┘



┌ ─ ─ ─ ─ ─ ┴ ─ ─ ─ ─ ─ ─ ─ ┐
┌────────────────┐
│ │ Expensive Join │ │
└────────────────┘
│ ▲ │
┌──────┴──────┐
│ │ │ │
.───────. .───────.
│ ╱ ╲ ╱ ╲ │
( Input 1 ) ( Input 2 )
│ `. ,' `. ,' │
`─────' `─────'
│"x" │
─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
```

### Additional context

This came from a [discord thread](https://discord.com/channels/885562378132000778/1166447479609376850/1193369889323356221) from @sergiimk

Contributor guide

Open the contributing guide

Research direction

No repository files or tests are named. Start with the CTE and UNION ALL examples and review the linked Discord discussion, then trace how repeated CTE references are planned and executed. Done should demonstrate shared results across branches without deadlock, while preserving correct predicate behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
backend, databases
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.