Query simplification: Graceful degradation for join-order optimization

Join ordering is one of the most important, but also most challenging problems of query optimization. In general find- ing the optimal join order is NP-hard. Existing dynamic pro- gramming algorithms exhibit exponential runtime even for the restricted, but highly relevant class of star joins. There- fore, it is infeasible to find the optimal join order when the query includes a large number of joins. Existing approaches for large queries switch to greedy heuristics or randomized algorithms at some point, which can degrade query execu- tion performance by orders of magnitude. We propose a new paradigm for optimizing large queries: when a query is too complex to be optimized exactly, we simplify the query's join graph until the optimization prob- lem becomes tractable within a given time budget. Dur- ing simplification, we apply safe simplifications before more risky ones. This way join ordering problems are solved op- timally if possible, and gracefully degrade with increasing query complexity. This paper presents a general framework for query simplification and a strategy for directing the simplification pro- cess. Extensive experiments with difierent kinds of queries, difierent join-graph structures, and diferent cost functions indicate that query simplification is very robust and outper- forms previous methods for join-order optimization.