Detail

Dynamic Programming for Join Ordering Revisited

The problem we are looking at is the generation of optimal
bushy join operator trees which do not contain a cross product.
In the literature as well as in commercial systems, several
alternatives exist to solve this problem. Some of them use
dynamic programming. We carefully analyze their complexity.
Comparing the result with lower bounds will show that there
exists room for improvement.
This motivates a new algorithm, whose complexity will meet
the lower bounds.