apache / apache/datafusion

General framework to decorrelate the subqueries

Open
#5,492 37 comments 0 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? Please describe what you are trying to do.**

In the current DataFusion, it has very limited support for correlated subqueries. It can only decorrelate the (NOT) IN/Exists predicate subqueries to Semi/Anti Joins. Even in the simplest IN/Exists cases, if the correlated expressions are not in the Filter/Join conditions, the current decorrelate rules will not support them.

In the paper "Unnesting Arbitrary Queries" by T. Neumann; A. Kemper
(http://www.btw-2015.de/res/proceedings/Hauptband/Wiss/Neumann-Unnesting_Arbitrary_Querie.pdf). It raise a mechanism to unnest arbitrary queries. This was already implemented by the Hyper DB:

For example:
select * from orders
where 1 in (select 1 from part left join (select l_partkey from lineitem where o_orderkey = 2) lineitem on p_partkey = lineitem.l_partkey)

https://hyper-db.de/interface.html#

Both SparkSQL and PostgreSQL do not support decorrelate such kind of queries.

**Describe the solution you'd like**

**Describe alternatives you've considered**

**Additional context**

Contributor guide

Open the contributing guide

Research direction

Start by reading DataFusion's existing correlated-subquery decorrelation behavior and the referenced "Unnesting Arbitrary Queries" paper. Use the SQL example in the issue as a target case, and verify that arbitrary correlated subqueries beyond current IN/EXISTS semi- and anti-join support are handled correctly.

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
Quiet
Clarity
Needs clarification
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.