Implement nested join optimization

[Dandandan]

Is your feature request related to a problem or challenge? Please describe what you are trying to do.
For complex queries, like those in TCP-H and TCP-DS it is essential to find a good Join order.
HashBuildProbeOrder implements a rule to optimize the probe / build side of joins, but this only optimizes the joins locally (e.g. swapping the join left / right).

We should implement an algorithm that (tries to) find a (close to) global optimum based on the total estimated cost of the joins.

Describe the solution you'd like
Implement an efficient algorithm for optimizing
I'm not sure what the SOTA is on this. Some material I found with some Googling:

https://db.in.tum.de/teaching/ws1415/queryopt/chapter3.pdf
https://db.in.tum.de/~radke/papers/hugejoins.pdf
https://www.cockroachlabs.com/blog/join-ordering-pt1/
https://www.cockroachlabs.com/blog/join-ordering-ii-the-ikkbz-algorithm/
http://mlwiki.org/index.php/Join_Ordering

Describe alternatives you've considered

Additional context

[andygrove]

We could also look at DuckDB join reordering: https://www.youtube.com/watch?v=aNRoR0Z3SzU

I filed a duplicate issue before I saw this one, although mine is specifically for the logical plan. #3984

[cristian-ilies-vasile]

Other resources:
Simplicity Done Right for Join Ordering - https://www.cidrdb.org/cidr2021/papers/cidr2021_paper01.pdf
Using the Join-Order-Benchmark (JOB), our simple approach provides better join orderings with significantly less optimization overhead, resulting in a substantially faster response time for all 113 JOB queries compared to state-of-the-art and recent approaches.

The MonetDB Architecture Martin Kersten CWI - https://homepages.cwi.nl/~manegold/teaching/adt/lectures/lecture2.pdf

[maruschin]

Hi, is there any progress?
I can take the issue for initial development.

[clflushopt]

Hi, I've been doing some reading on the side and I am interested into taking a stab at this if the issue is still open and no one is working on it.

[clflushopt]

take

[clflushopt]

Small update; I started looking at the initial join selection rule implemented by backtracking from the reference to HashBuildProbeOrder and went through the PR that introduced the JoinSelection rule in the physical optimizer #4219. I've also been looking at work done for the cost calculations and cost-based optimizations EPIC here #3929.

I've also started revisiting the no-statistics approach of DuckDB to try and get a better intuition for how their cardinality estimator approach works, implementation wise I think I want to get a small set of queries with nested joins running to get a better view of the current way they are handled before I draft an early implementation.

[clflushopt]

@alamb quick question what's considered higher priority here between better join ordering approach (potentially like DuckDB's) vs picking up the couple tickets left in the EPIC for #3929 (implementing interval analysis for AND and OR) ?

[alamb]

@alamb quick question what's considered higher priority here between better join ordering approach (potentially like DuckDB's) vs picking up the couple tickets left in the EPIC for #3929 (implementing interval analysis for AND and OR) ?

Hi @clflushopt

In my opinion getting Cardinality Estimation / interval analysis is higher priority as that feature has many use cases and is needed for almost any more sophisticated join ordering approach.

In terms of a more sophisticated join ordering approach, I have some ideas about this which I will try and write up over the nect week or two