[dbolympics] General framework to decorrelate the subqueries

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

According to the discussions in this issue, i think we can list the following items to support a subqueries decorrelation framework:

Unify the optimizor for correlated query, regardless the query type (exists query, scalar query etc)
Support flexible decorrelation scheme (simple vs general approach), we can achieve this by following the algorithm mentioned in the 2nd paper. There is a prerequisite to introduce an index algebra during the rewrite. This index requires a pre-traversing over the whole query to detect all non-trivial subqueries, and answer the question whether simple unnesting is sufficient, or should the framework continue with the general approach
Implement general purpose + recursive aware subquery decorrelation for the most major operators (projection, filter, group by) using the top-down algorithm mentioned in the 2nd paper
Gradually support more complex expression (group by, order, limit, window function)

I am trying to organize a join task force for planning joins / subqueries: [DISCUSSION] JOIN "task force" / project team #15885

Unify the optimizor for correlated query, regardless the query type (exists query, scalar query etc)

I think a crucial starting point is to transform all correlated exprs into dependent join. (I'm unsure if we need to implement its Execution Plan before completing all decorrelation).

@irenjj

In case others haven't heard, @irenjj is working on additional subquery support as part of a Google Summer of Code Project (where @jayzhan211 and I are helping mentor).

Perhaps @suibianwanwank and @duongcongtoai would be interested in being involved too

cool, actually in this PR: #16016 i'm trying to introduce a unified structure to do decorrelation for the following usecases:

simple decorrelating plan with linear operators (straight forward projection/predicate pull up/ dependent join push down)
more complex decorrelation (group by, windows, limit ...)
recursive decorrelation/nested decorrelation

The parts that are not implemented are left with unimplemented! errors. I'm trying to make the PR mergable, so everyone can continue to contribute in parallel, but my current goal is to implement enough to satisfy existing slt tests

@duongcongtoai

From what I can see, this ticket (a general framework to decorrelate subqueries) is going to be the core of any subsequent improvements for subqueries, so I suggest we pool our efforts together to focus on this first.

I suggest, we all first review the PR from @duongcongtoai

feat: rewrite subquery into dependent join logical plan #16016

cc @suibianwanwank @duongcongtoai @irenjj

@suibianwanwank

I recommend we also do some research on existing systems. Can someone provide links to existing implementations in other systems?

DuckDB
Spark
Apache Calcite ( Maybe @suibianwanwank can help, as they have significant experience with this part of calcite's optimizer in this area -- https://github.com/apache/calcite/issues?q=is%3Apr+is%3Aopen+author%3Asuibianwanwank)

I recommend we also do some research on existing systems. Can someone provide links to existing implementations in other systems?

DuckDB

Spark

Apache Calcite ( Maybe @suibianwanwank can help, as they have significant experience with this part of calcite's optimizer in this area -- https://github.com/apache/calcite/issues?q=is%3Apr+is%3Aopen+author%3Asuibianwanwank)

For DuckDB: basic logic is in plan_subquery.cpp file(can't find a specific pr) https://github.com/duckdb/duckdb/blob/main/src/planner/binder/query_node/plan_subquery.cpp, For "Unnesting Arbitrary Subqueries," there is a complete implementation.
And 2nd paper implementation: duckdb/duckdb#17294

@irenjj

Thanks to @irenjj remind, I found this based on your input: https://github.com/duckdb/duckdb/blob/main/src/planner/binder/query_node/plan_subquery.cpp. If I understand correctly, this should be DuckDB's logic for converting subQuery to DependentJoin.
Additionally, in Calcite, the corresponding logic is here: https://github.com/apache/calcite/blob/main/core/src/main/java/org/apache/calcite/rel/rules/SubQueryRemoveRule.java
There should be many similarities between the two.

In this draft, dependent join detection is implemented inside this function. But i wonder if creating an explicit LogicalPlan::DependentJoin make sense in our case? if the only place it is being used is inside the optimizor that does the decorrelation

In duckdb PR he mentioned:

With this PR, that changes. Subqueries are fully algebraized, before entering a single decorrelation pass. This potentially provides optimization opportunities, that would not have been possible before.

I can relates this to the idea in the 2nd paper

At this point the accessing list is empty and we have two choices: either we introduce a
join with 𝐷 := Π𝑎:=𝑇1.𝑎 (𝜎𝑓 =123 (𝑇1)) and use that to substitute 𝑇1.𝑎; or we exploit the fact
that all outer column references are bound in cclasses and we simply replace 𝑇1.𝑎 with
the equivalent 𝑇2.𝑎. The optimal choice depends on the selectivity of 𝜎

which corresponds to this part of the draft PR, and is still within the detail implementation of a specific optimizor

I'm not sure if I fully understand your point. In this paper, the decorrelate should be based on DependentJoin, as can be seen from the example relational algebra diagram.

There are one thing we surely know that should be implemented: detect which nodes in the LogicalPlan AST is a dependent join node. However, we don't need to create a new LogicalPlan type like LogicalPlan::DependentJoin, if this plan type is only an intermediate form during the decorrelation phase, and i expect after the rewriting completes, no more dependent join node exists.

=> We can keep this concept internally to the decorelation framework

@suibianwanwank

There are one thing we surely know that should be implemented: detect which nodes in the LogicalPlan AST is a dependent join node. However, we don't need to create a new LogicalPlan type like LogicalPlan::DependentJoin, if this plan type is only an intermediate form during the decorrelation phase, and i expect after the rewriting completes, no more dependent join node exists.

=> We can keep this concept internally to the decorelation framework

In DuckDB, the final logical plan generated is DelimJoin. Besides identifying this as a Join produced by decorrelation operations, DelimJoin can also be used to eliminate redundant DelimJoin and DelimGet, which is a further optimization. I agree with @suibianwanwank 's point that adding a new LogicalType can make the current process clearer, and by breaking it down into multiple steps, tasks can be better refined for collaborative work (transform to dependent join -> top down/bottom up decorrelation -> further optimize), and it could also provide possibilities for subsequent further optimization (although unrelated to decorrelation).

Thank you everyone for your opinions. Looks like my implementation is trying to wrap everything inside a single optimizor, which is hard to follow and reduces space for collaborative work, and since we can use duckdb's implementation detail, the next steps can be the followings:

Define a new DelimGet LogicalPlan type and implement existing methods for a standard LogicalPlan. For DelimJoin we can reuse existing LogicalPlan::Join with a new join_type, because its purpose is only to detect if a join comes from a dependentJoin or not
Rewrite the Existing Subqueries into 2 operators DelimJoin and DelimGet (either at planning stage or optimizor stage, duckdb does this at planning stage)
Decorrelation (duckdb does this at planning stage)
DelimGet removal

Here is a good youtube video on the topic from the DuckDB folks

https://www.youtube.com/watch?v=ajpg_pMX620

I'm trying to revive the whole POC inside a PR (some tpch queries is failing because of some edgecases)

I'm trying to revive the whole POC inside a PR (some tpch queries is failing because of some edgecases)

In order for me (or anyone else) to realistically review the POC It would help A LOT if there was a clear writeup that explains how it works (not just a reference to the paper) but seomthing that explains the algorithm in DataFusion terms so we can follow along

That way we can first verify that the algorithm is correct and then we'll evaluate if the implementation matches the algorithm -- it is really hard to try and do both at the same time

@alamb

@alamb I managed to create a PR and document some details on the algorithm to rewrite dependent join operator: #21555

👋 I'm picking back up on this work as part of a directed study for my graduate degree. I put together a doc proposing a correctness target we can implement against which is essentially a catalog of query shapes that the current decorrelator gets wrong (either a hard failure or a plan that returns the wrong answer). This'll give any new implementation something to verify against as it grows.

Plan doc: https://docs.google.com/document/d/1rZoOeiNcJw0OLSDgSqjA7PoA8cf2yAvU6Bc-4o4K4L4/edit?usp=sharing
Shape catalog: https://docs.google.com/document/d/10dQRna0Dc8XBB74SkKbfKvPE1SvjNkXKMAcPeK8DiEw/edit?usp=sharing

I'm working on a theoretical mapping from Neumann's paper to DataFusion's plan structures next. Would appreciate early feedback on the approach before I start building against it.

Affects DB Olympics, see: #26661

@mohammadnaqvi04

@mohammadnaqvi04 after alamb's comment on #26710, I built a prototype of Neumann's top-down unnesting to check how it fits DataFusion, and compared it with your plan. It covers the mapping you mentioned, so it may help with your design doc. A short summary of both comes first, for readers who haven't opened the docs.

Branch: main...jayzhan211:datafusion:poc/general-decorrelation
Repros and fuzzer: https://github.com/jayzhan211/datafusion/tree/poc/general-decorrelation/dev/decorrelation-poc. The README says how to run them against main and the prototype, so anyone can check the numbers below.

This is a prototype to test the design, not a PR: it has no unit tests yet, the commits are work in progress, and a few shapes are still unsupported.

Your plan, in short

Your plan doc and shape catalog take Neumann's general unnesting as the goal and propose a fixed catalog of failing query shapes as the way to get there. The 11 shapes come mostly from DuckDB's subquery tests. Each would become an item under an EPIC and be fixed one at a time, so every PR has a checkpoint to verify against. Mapping Neumann's method onto DataFusion and LATERAL are left for later, and a design doc is in progress.

Why a general rule

Today a correlated subquery becomes a join by pulling its correlated filters up to the top of the subquery. Every operator a filter crosses needs its own check that the move is safe: a missing check is a "not supported" error, and a wrong check is a wrong result. The empty-input aggregate (the COUNT bug) is then compensated separately for scalar, EXISTS/IN and lateral subqueries. This design is behind most of the 36 open decorrelation issues, 17 of which are wrong results. Of the 16 fixes to this code in the last year, 5 made a wrong result safe by turning it into a "not supported" error.

How the prototype works

It does the opposite and pushes the outer values down. The domain is the set of distinct outer values the subquery reads. Every operator on the way down also groups, partitions or joins by the domain columns, so the subquery returns its rows for all outer values at once, tagged with the value, and is joined back to the outer plan on those columns. An aggregate without GROUP BY is handled in one place: the domain is left-joined to the aggregate grouped by the domain, and outer values with no input get the aggregate's empty-input value.

How it maps onto DataFusion

It is one logical optimizer rule that replaces the three rules DecorrelatePredicateSubquery, ScalarSubqueryToJoin and DecorrelateLateralJoin, and their shared helper PullUpCorrelatedExpr. As a logical rule, it also covers plans from the DataFrame API and Substrait.
The dependent join exists only inside the rule. No new LogicalPlan node or join type reaches Substrait, proto or the unparser.
When a conjunct is inner = outer, the rule binds the outer column to the inner one and builds no domain, which keeps today's plan shape for the common case.
"At most one row" is an aggregate that errors on a second value, like Calcite's SINGLE_VALUE.
The domain is computed by reading the outer plan again, so the rule refuses when that plan isn't deterministic.

Results, with the four old rules deleted

	main: right / wrong / error	prototype: right / wrong / error
Your catalog, the 9 shapes that are valid SQL	0 / 0 / 9	9 / 0 / 0
Repros, the 39 of 44 queries DuckDB can answer	6 / 10 / 23	38 / 0 / 1
Random correlated queries, the 14,999 of 15,000 with a reference answer	4,660 / 124 / 10,215	14,959 / 2 / 38
dbolympics, the 383 of 409 queries DuckDB can answer	325 / 8 / 50	366 / 8 / 9

The random queries use SQLite as the reference, because it runs each subquery once per outer row. DuckDB is the fallback where SQLite can't run the query, mostly LATERAL.
The prototype's 2 wrong random queries are LATERAL queries checked against DuckDB. Both are DuckDB 1.1.3 bugs with an EXISTS nested inside LATERAL, confirmed by rewriting the queries for SQLite. (Edited: this first listed a third query as a hash join bug on main. On a recheck it returns the right rows, so I've removed it.)
The one repro error is Correlated EXISTS on a CASE or UNION ALL column fails with "Can't compare arrays of different types" #26285, which panics in the hash join on main as well.
The 8 wrong dbolympics answers are the same queries on both, and none of the prototype's 9 dbolympics errors comes from a subquery.

The sqllogictests have no result changes, and 26 EXPLAIN expectations change. 6 of the 9 TPC-H subquery queries get identical plans, and the other 3 differ only in where scalar arithmetic runs.

Costs and gaps

The rule is about 3,000 lines against 2,500 for the code it replaces.
PullUpCorrelatedExpr is public, and lakehq/sail and alimardon123/pondra call it directly.
Still unsupported: three-valued multi-column IN over the domain, RIGHT/FULL lateral joins, outer join ON conditions with a subquery that reads both sides, and CUBE over more than 12 columns.
Untested: a subquery moved out of a CASE branch might raise its "more than one row" error for rows that don't take that branch.

Feedback on the catalog

The three shapes listed as correctness bugs fail at planning on main with a schema error. They don't return wrong rows.
The two shapes whose aggregate reads only outer columns are not valid SQL, because such an aggregate belongs to the outer query. Postgres and DuckDB reject both ("must appear in the GROUP BY clause", "aggregate functions are not allowed in WHERE"), and DataFusion should reject them too.
The shapes that return wrong rows today matter most, and none of them is in the catalog yet: Wrong results: correlated aggregate subquery with a lossy CAST in its filter returns one row per inner value #26014, Wrong results: a window function in an IN subquery sees every row when the correlated filter repeats the IN predicate #26032, Wrong results: LATERAL with SELECT DISTINCT and a non-equality correlated filter returns duplicate rows #25808, Correlated scalar subquery with count(*) returns 0 instead of NULL when HAVING references an outer column #26503 and Wrong results: decorrelation loses correlated columns when a subquery contains two equal subplans #26692. In the random queries, most of main's wrong answers come from a HAVING over an aggregate without GROUP BY (Correlated scalar subquery with count(*) returns 0 instead of NULL when HAVING references an outer column #26503) or from LATERAL with DISTINCT (Wrong results: LATERAL with SELECT DISTINCT and a non-equality correlated filter returns duplicate rows #25808).
The dbolympics failures add five more shapes: top-1 per outer row ([dbolympics] Correlated scalar subqueries with ORDER BY ... LIMIT 1 fail with "Physical plan does not support logical expression ScalarSubquery" #26710), range correlations ([dbolympics] Decorrelate scalar subqueries with more complex filter expressions #14554), scalar subqueries without an aggregate ([dbolympics] Support correlated scalar subquery without aggregation #16137), subqueries inside an aggregate ([dbolympics] Subqueries in an aggregate (GROUP BY key, aggregate argument or FILTER) fail with "Physical plan does not support logical expression" #26704), and references two levels up ([dbolympics] Support Nested correlated subquery error with a depth exceeding 1 #15558).

A path that combines the two

Your strangler-fig plan fits the prototype well, with one change: split the work by operator rather than by shape. Most of the missing-capability shapes need the same core, so the first shape would carry most of the rule.

A tests-only PR that adds the catalog as sqllogictests: your shapes, the issue repros and the cases the fuzzer found, each with its reference answer.
Add the new rule after the existing ones, so it only rewrites correlated subqueries they leave in the plan. Plans that work today should not change, but I haven't run that ordering yet. The first PR is the core (domain, join back, aggregate without GROUP BY), then one PR per operator (LIMIT, window, UNION, joins, grouping sets), each turning the catalog entries it fixes from errors into right answers.
Move one subquery kind at a time (lateral, scalar, EXISTS, IN/NOT IN) ahead of the old rules, reviewing each plan diff.
Delete the old rules, after a deprecation period for the public types.

I agree with alamb that a general rule is the way forward rather than more fixes shape by shape, and the prototype suggests this approach works for DataFusion. @mohammadnaqvi04 would you like to take the test PR, and build your design doc on the prototype? The repros and the fuzzer linked above are a starting point for it.

@jayzhan211

Thanks @jayzhan211, this is really helpful and the prototype results are interesting. Yes, I'll take the test PR and build the design doc on the prototype. I'd done some prototyping on my end as well, but I'll work off of what's in your branch going forward.

I'll rework the shapes in the catalog that you pointed out in your feedback. Thanks for reviewing it!

It is one logical optimizer rule that replaces the three rules DecorrelatePredicateSubquery, ScalarSubqueryToJoin and DecorrelateLateralJoin, and their shared helper PullUpCorrelatedExpr. As a logical rule, it also covers plans from the DataFrame API and Substrait.

I really like this property. It also points at an incremental rollout strategy that would be nice -- add a new logical rule and leave the existing rules to co-exist temporarily

Then at some point we can deprecate the old rules, and stop running the old phyiscal rules by default (and remove them in a release or two) but

Your strangler-fig plan fits the prototype well, with one change: split the work by operator rather than by shape. Most of the missing-capability shapes need the same core, so the first shape would carry most of the rule.

What does "strangler-fig" mean in this case?

The third is a hash join bug on main, unrelated to decorrelation: a LEFT hash join whose probe side is a UNION ALL drops an unmatched row in about a quarter of runs.

Do we have a ticket tracking this?

What does "strangler-fig" mean in this case?

It's the rollout you describe. The new rule runs next to the old ones and takes over one piece at a time, until the old rules have nothing left to do and can be removed. The name comes from the strangler fig pattern 😄 , after a vine that grows around a tree until it replaces it, and mohammadnaqvi04's plan doc uses it for this approach.

Do we have a ticket tracking this?

No. I rechecked it and couldn't reproduce it, so I'm not sure it's a hash join bug. I've removed it from the comment above.

The more I see / think about subquery related errors, the more I am convinced we can't just keep patching existing bugs / limitations. If we do so that will result in a non stop stream of complicated PRs to review and new bugs that re unlocked / fixed

So therefore I would like to propose:

We stop adding support for subqueries via patch immediately (no more new contributor PRs to the subquery rewrites)
We fix all the subquery related wrong results bugs - if we can do it with a simple fix, great, but otherwise we should make the query error rather than try and fix the semantics

Then we can take all the maintainer bandwidth that would have gone into managing the massive onslaught of subquery prs and focus on the actual framework

Open wrong results:

Open unsupported queries and errors:

@alamb

@alamb how can I help with this? Happy to take whatever is most useful.

Here is the latest run report: every repro in the list above, rerun on main (8733e2e) and checked against DuckDB 1.5.6.

Fixed on main, so these can be ticked or closed:

Nullable expression over non-null columns are planned as non-null-aware-joins #25024 now returns z
Wrong results: correlated NOT IN loses the correlation when it is an equality on the IN value column #25480 now returns 2, 4, NULL
Wrong results: correlated NOT IN (subquery) ignores NULLs in the subquery #25347 all 8 shapes match, including the six constant-value ones from Wrong results: correlated NOT IN (subquery) ignores NULLs in the subquery #25347 (comment)
Wrong results: correlated EXISTS/IN subqueries over a groupless aggregate get the wrong outer rows #24960 the EXISTS and NOT EXISTS repros are correct. The one shape still wrong (HAVING count(*) + t1.t1_int > 1) is already covered by Wrong results: correlated EXISTS over a groupless aggregate ignores a predicate on outer columns only #26695
Scalar subquery (Expr::ScalarSubquery) does not fail when subquery is not scalar #16134 and Subquery expressions in UDTF arguments are parsed but elided #17349 were closed today

Now an error instead of a wrong result, so it can move to the second list:

Unsupported: correlated scalar subquery with nested aggregates #26508 fails with Physical plan does not support logical expression ScalarSubquery

Listed as unsupported, but it actually returns wrong results:

Support LATERAL subqueries with HAVING clause #21198. An inner LATERAL with HAVING is planned as a right join, so outer rows that fail the HAVING come back with NULL instead of being dropped:

CREATE TABLE a(k INT) AS VALUES (1), (2), (3);
CREATE TABLE b(k INT, v INT) AS VALUES (1, 10), (1, 20), (2, 30);
SELECT a.k, s.c FROM a, LATERAL (SELECT count(*) AS c FROM b WHERE b.k = a.k HAVING count(*) > 1) s;
-- main: (1, 2), (2, NULL), (3, NULL)
-- DuckDB: (1, 2)

Still wrong as described: #26695, #26692, #26629, #26505, #26503, #26234, #26032, #26014, #25808, and #26569 (from the code: the value key count still defaults to 1). The #26234 repro uses outer as a table alias, which no longer parses, but with the alias renamed it is still wrong.

Every query in the unsupported list still fails to plan.

@alamb

@alamb how can I help with this? Happy to take whatever is most useful.

Thank you @raghavyadav01

Fixed on main, so these can be ticked or closed:

Thank you -- if you could post a comment on each of those tickets with the datafusion-cil query you ran and the output that currently results that would be super helpful

Listed as unsupported, but it actually returns wrong results:

Please comment on that ticket

Navigation Menu

Repository navigation

[dbolympics] General framework to decorrelate the subqueries #5492

19 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

[dbolympics] General framework to decorrelate the subqueries #5492

Description

Activity

duongcongtoai commented on Apr 28, 2025

alamb commented on Apr 28, 2025

suibianwanwank commented on Apr 29, 2025

alamb commented on May 15, 2025

duongcongtoai commented on May 15, 2025

alamb commented on May 18, 2025

alamb commented on May 18, 2025

irenjj commented on May 18, 2025

suibianwanwank commented on May 19, 2025

duongcongtoai commented on May 19, 2025

suibianwanwank commented on May 19, 2025

duongcongtoai commented on May 19, 2025

irenjj commented on May 19, 2025

duongcongtoai commented on May 20, 2025

19 remaining items

alamb commented on Feb 19, 2026

duongcongtoai commented on Feb 23, 2026

alamb commented on Feb 27, 2026

duongcongtoai commented on Apr 23, 2026

mohammadnaqvi04 commented on Oct 1, 2026

alamb commented on Oct 24, 2026

jayzhan211 commented on Oct 25, 2026

mohammadnaqvi04 commented on Oct 25, 2026

alamb commented on Oct 25, 2026

jayzhan211 commented on Oct 26, 2026

alamb commented on Oct 28, 2026

alamb commented on Oct 28, 2026

raghavyadav01 commented on Oct 29, 2026

alamb commented on Oct 29, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions