Implement nested join optimization
- 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.**
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**
Contributor guide
Assessment
This issue has not been assessed yet.