Transform Correlated Subquery Into Dependent Join
- 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?
As the first step implementation of the HyPer paper 'Unnesting Arbitrary Queries', it will converts correlated subqueries into the form of dependent joins.
In DuckDB:
```sql
┌─────────────────────────────┐
│┌───────────────────────────┐│
││ Unoptimized Logical Plan ││
│└───────────────────────────┘│
└─────────────────────────────┘
┌───────────────────────────┐
│ PROJECTION │
│ ──────────────────── │
│ Expressions: │
│ id │
│ value │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ FILTER │
│ ──────────────────── │
│ Expressions: │
│ (CAST(value AS BIGINT) > │
│ SUBQUERY) │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ DEPENDENT_JOIN │
│ ──────────────────── ├──────────────┐
│ Join Type: SINGLE │ │
└─────────────┬─────────────┘ │
┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│ SEQ_SCAN ││ PROJECTION │
│ ──────────────────── ││ ──────────────────── │
│ Table: table1 ││ Expressions: │
│ Type: Sequential Scan ││ count_star() │
└───────────────────────────┘└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ AGGREGATE │
│ ──────────────────── │
│ Expressions: │
│ count_star() │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ FILTER │
│ ──────────────────── │
│ Expressions: │
│ (ref_id = id) │
│ (CAST(quantity AS BIGINT) │
│ = SUBQUERY) │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ DEPENDENT_JOIN │
│ ──────────────────── ├──────────────┐
│ Join Type: SINGLE │ │
└─────────────┬─────────────┘ │
┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│ SEQ_SCAN ││ PROJECTION │
│ ──────────────────── ││ ──────────────────── │
│ Table: table2 ││ Expressions: │
│ Type: Sequential Scan ││ count_star() │
└───────────────────────────┘└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ AGGREGATE │
│ ──────────────────── │
│ Expressions: │
│ count_star() │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ FILTER │
│ ──────────────────── │
│ Expressions: │
│ (id = id) │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ SEQ_SCAN │
│ ──────────────────── │
│ Table: table1 │
│ Type: Sequential Scan │
└───────────────────────────┘
```
### Describe the solution you'd like
I'd like to split into follow small tasks:
- [ ] Transform scalar correlated subqueries in `WHERE` to DependentJoin: #16172
- [ ] Transform scalar correlated subqueries in `SELECT` to DependentJoin:
- [ ] Transform scalar correlated subqueries in `FROM` to DependentJoin:
- [ ] Transform scalar correlated subqueries in `PROJECTION` to DependentJoin:
- [ ] Transform scalar correlated subqueries in `UNNEST` to DependentJoin:
- [ ] Transform scalar correlated subqueries in `WINDOW` to DependentJoin:
- [ ] Other subquery type support:
...
### Describe alternatives you've considered
_No response_
### Additional context
_No response_
Contributor guide
Research direction
Start with the correlated-subquery plan shown in the issue and the linked WHERE-specific task, #16172; no implementation file or test is named here. Done means defining and implementing the remaining scalar correlated-subquery transformations into DependentJoin, with coverage for the listed query locations and other supported subquery types.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust, sql
- Domain
- databases
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 30/100