Tutorial: The Strange and Wondrous Ways of Industrial-strength Database Query Optimizers.
Jayant R. Haritsa · 2009
Modern relational database systems incorporate a query optimizer module to identify the most efficient strategy, or plan, to execute the declarative SQL queries submitted by users. Optimization is a mandatory exercise since the difference between the cost of the best plan and a random choice could be in orders of magnitude. The role of query optimizers has become especially critical in recent times due to the high complexity of current data warehousing and mining applications. In this tutorial, we will conduct a visual exploration of the plan choices made by industrial-strength (commercial and public-domain) optimizers as a function of the input parameter space, whose dimensions include database, query and system-related features. We begin by presenting a suite of diagrams (called plan, cost and cardinality diagrams) that capture the overall behavior of the optimizers over this parameter space. These diagrams are typically remarkably complex and intricate with a large number of plans covering the space, often appearing similar to cubist paintings. They provide a variety of interesting insights, including that current optimizers make extremely finegrained plan choices, that the plan optimality regions may have highly intricate patterns and irregular boundaries, indicating strongly non-linear cost models; that non-monotonic cost behavior exists where increasing result cardinalities decrease the estimated cost; and, that the basic assumptions underlying the research literature on parametric query optimization often do not hold in practice. In the next stage, we will show how these complex diagrams can almost always be reduced to much simpler pictures, featuring only a few plans, without materially affecting the query processing quality. The reduction property has several useful implications for the design and usage of query optimizers, including quantifying the redundancy in the plan search space, providing better candidates for plan-cacheing, enhanc-