Join Order Selection | Good Enough is Easy

Abstract. Uniform sampling of join orders is known to be a competitive alternative to transformation-based optimization techniques. However, uniformity of the sampling process is dicult to establish and only for a restricted class of join queries techniques are known. In this paper, we investigate non-uniform sampling devising a simple yet powerful algorithm that is generally applicable. The key element of the algorithm is a mapping of randomly generated sequences of join predi-cates to query plans. We take advantage of the bottom-up constructing of query plans by simultaneously computing the costs and discarding partial plans as soon as they exceed the best costs found so far, which implements a highly eective cost-bound pruning component. Sampling does not produce the optimal plan but a near-optimal solution which is fully sucient as the cost function grows more and more inac-curate with increasing query size. In return, our algorithm establishes a well-balanced trade-o between result quality and time invested in the optimization process.