apache / apache/datafusion

Additional ideas for optimizing subqueries

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

Description

Originally from @jon-chuang on https://github.com/apache/arrow-datafusion/issues/2248#issuecomment-1120280963, copied to new ticket so it didn't get lost:

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](https://cs.emis.de/LNI/Proceedings/Proceedings241/383.pdf)
- Implementation in DuckDB here: https://github.com/duckdb/duckdb/blob/bee8017bdcc5e652aee26ce8cfb260990cf6a369/src/planner/subquery/flatten_dependent_join.cpp#L72

Contributor guide

Open the contributing guide

Research direction

No DataFusion file or test is named. Start by reviewing the existing correlated-subquery handling, the linked unnesting paper, and DuckDB's src/planner/subquery/flatten_dependent_join.cpp; first define one narrowly scoped optimization. Done means the optimizer implements that transformation safely and focused planner tests demonstrate the expected query plans.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust, sql
Domain
databases, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
20/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.