Switch from Bottom-Up to Top-Down Decorrelation Strategy #17294
Merged
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Do not blindly mark all CTE scans as correlated. This is no longer a valid assumption.
|
Thanks! Looks great - amazing that you got this to work :) |
|
For future reference: the BTW 2025 paper introducing the method. |
2 tasks
krlmlr
added a commit
to duckdb/duckdb-r
that referenced
this pull request
May 18, 2025
Switch from Bottom-Up to Top-Down Decorrelation Strategy (duckdb/duckdb#17294)
krlmlr
added a commit
to duckdb/duckdb-r
that referenced
this pull request
May 18, 2025
Switch from Bottom-Up to Top-Down Decorrelation Strategy (duckdb/duckdb#17294)
krlmlr
added a commit
to duckdb/duckdb-r
that referenced
this pull request
May 19, 2025
Switch from Bottom-Up to Top-Down Decorrelation Strategy (duckdb/duckdb#17294)
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
This PR implements the recently published version of @neumannt's query unnesting strategy "Improving Unnesting of Complex Queries"—which is an updated version of "Unnesting Arbitrary Queries".
Why do we want this? Separation of concerns and phase separation. With bottom-up decorrelation, we never fully algebraize plans containing (nested) subqueries into a logical plan—possibly containing
DEPENDENT_JOINS. This results in problems trying to decorrelate complex SQL constructs such as recursive CTEs (see #13404). 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.Fix: #15307
Fix: #15483