apache / apache/datafusion

Implement nested join optimization

Open
#3,843 15 comments 3 reactions 1 assignee Claimed by @clflushopt View on GitHub
enhancement optimizer performance
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.