To find the optimal join order two different generative join enumeration strategies have been proposed. The most commonly used one is dynamic programming which proceeds bottom-up. The alternative is top down enumeration with memoization. For both strategies algorithms exist that enumerate only solutions without cartesian products, which is a commonly used heuristics. With top-down enumeration it is possible to further improve optimization time by pruning the search space while still obtaining the optimal solution. In this paper we compare the performance of the different join enumeration strategies and possible pruning strategies. We propose improvements to the pruning algorithms from the literature and empirically evaluate the effect of pruning using different synthetic queries and cost functions in order to understand when significant speedups can be achieved. We find that for many queries a speedup by a factor of 2 to 10 can be expected.      «

To find the optimal join order two different generative join enumeration strategies have been proposed. The most commonly used one is dynamic programming which proceeds bottom-up. The alternative is top down enumeration with memoization. For both strategies algorithms exist that enumerate only solutions without cartesian products, which is a commonly used heuristics. With top-down enumeration it is possible to further improve optimization time by pruning the search space while still obtaining th...     »