Technical Perspective: Broadening and Deepening Query Optimization Yet Still Making Progress

Query optimization is a fundamental problem in data management. Simply put, most database query languages are declarative rather than imperative--that is, they specify properties the answer should satisfy, rather than give an algorithm to compute the answer. The best known and most widely used database query language--SQL--is a prime example of a language for which optimization is essential. By "essential," I mean that database optimization is not a matter of shaving 10% or even a factor of 2x from a query's execution time. In database query evaluation, the difference between a good plan and a bad or even average plan can be multiple orders of magnitude--so successful query optimization makes the difference between a plan that runs quickly and one that never finishes at all.