Probabilistic bottom-up join order selection - breaking the curse of NP-completeness

Join-ordering is known to be NP-complete and therefore a variety of heuristics have been devised to tackle large queries which are considered computational intractable otherwise. However, practitioners often point out that typical problem instances are not difficult to optimize at all. In this paper we address that seeming discrepancy. We present a probabilistic bottom-up join-ordering technique that is distinguished by the high-quality results achieved, the extremely short running time and---most notable---its independence of the search space's size. The subsequent thorough analysis of the algorithm's principle confirm our experimental results.