[EPIC] Subquery support

[andygrove]

Is your feature request related to a problem or challenge? Please describe what you are trying to do.

We have many issues now for subquery support, with some duplication so I thought it would be good to create one epic to track all of this work.

There is also a design document.

Logical Plan

• LogicalPlan::TableScan should not depend on the physical plan #2247
• Move LogicalPlan to datafusion-expr crate #2245
• [Discuss] Add struct Query for datafusion #2181
• Add Expr::Exists to logical plan #2337
• Add Expr::InSubquery and Expr::ScalarSubquery #2342

SQL Query Planner

• Add SQL query planning support for simple/nested subqueries #2238
• Add SQL query planning support for EXISTS subqueries #2219
• Add SQL query planning support for IN subqueries #2237
• Add SQL query planner support for scalar subqueries #2353

Logical Plan Optimizations

• Validate subquery expressions #2361
• Optimize EXISTS subquery expressions by rewriting as semi-join #2351
• Optimize queries that contain IN subqueries by rewriting as semi join #488

Physical Plan

• Implement physical plan for IN Subquery #1835
• Implement physical plan for EXISTS subquery #123

Ballista

• Add EXISTS subquery support to Ballista #2338

[jon-chuang]

Some additional ideas for subquery optimizations:

• If rest of subquery is not correlated, push up correlated filter (in particular, correlated equality filter) into a left join on the filter.
• More here: https://www.alibabacloud.com/blog/query-optimization-technology-for-correlated-subqueries_597644

More generally, one can attempt this approach, which is a lot less messy than relying on countless rewriting heuristics (which is also highly error-prone):

• Unnesting arbitrary queries
• Implementation in DuckDB here: https://github.com/duckdb/duckdb/blob/bee8017bdcc5e652aee26ce8cfb260990cf6a369/src/planner/subquery/flatten_dependent_join.cpp#L72

[jon-chuang]

• [Feature] (All) logical optimizers should optimize subqueries #2480

[alamb]

I filed #5483 to track the few items that are not done yet, and am going to close this ticket as we have subquery support in DataFusion now 🎉