Transform Correlated Subquery Into Dependent Join #16173
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:
┌─────────────────────────────┐
│┌───────────────────────────┐│
││ 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
WHEREto DependentJoin: Transform scalar correlated subqueries inWhereto DependentJoin #16172 - Transform scalar correlated subqueries in
SELECTto DependentJoin: - Transform scalar correlated subqueries in
FROMto DependentJoin: - Transform scalar correlated subqueries in
PROJECTIONto DependentJoin: - Transform scalar correlated subqueries in
UNNESTto DependentJoin: - Transform scalar correlated subqueries in
WINDOWto DependentJoin: - Other subquery type support:
...
Describe alternatives you've considered
No response
Additional context
No response