I always wondered how SQL databases executed the JOINs. Always knew the theory, but today I spent some time digging into MySQL’s code to understand the nuances.
Turns out, MySQL builds the best join plans incrementally to make sure it figures out the most optimal join order. It goes from single-table access paths to 2-table joins, then to 3-table joins, and so on. As an optimization, it prunes any subtrees that are guaranteed to result in suboptimal costs.
Interestingly, I noticed traces of dynamic programming in action. MySQL caches intermediate results to avoid redundant cost computations as it builds up join plans.
This is what I absolutely love about open source - if you have a question, you can just dive into the code and find the answer for yourself.
If you’re curious, start with the file sql_optimizer, and in that, you will find the function called - get_best_combination. More importantly, use your favorite LLM to understand the code; I did the same.
I’ve linked the relevant part of the source code in the comments.