Declarative query processing with performance guarantees has been a highly desirable but equally elusive goal for the database community over the last five decades. The difficulty stems from two primary sources: errors in the cost models of the execution operators, and in the selectivity estimates that serve as inputs to these models. While the former error, which depends on the underlying computing environment, can be curbed to a fair degree, the latter is much harder to control since it is based on data distributions and correlations, which can be arbitrarily complex in nature. The net result is poor query execution plan choices, leading to grossly inflated and extremely unpredictable response times.
In this talk, we present a new approach to address the selectivity estimation problem, wherein this process is completely eschewed for error-prone selectivities. Instead, a small "bouquet"' of plans is identified from the set of optimal plans in the query's selectivity error space, such that at least one among this subset is near-optimal at each location in the space. Then, at run time, the actual selectivities of the query are incrementally "discovered" through a sequence of partial executions of bouquet plans, eventually identifying the appropriate bouquet plan to execute. The duration and switching of the partial executions is controlled by a graded progression of isocost surfaces projected onto the optimal performance profile. We prove that this construction results in bounded overheads for the selectivity discovery process and consequently, guaranteed worst-case performance.
The plan bouquet approach provides repeatable execution strategies and can be easily incorporated in current database engines. Overall, it provides novel guarantees that open up new possibilities for robust query processing.
Jayant Haritsa is on the faculty of the Department of Computational & Data Sciences at the Indian Institute of Science, Bangalore, since 1993. He received a BTech degree from the Indian Institute of Technology (Madras), and MS and PhD degrees from the University of Wisconsin (Madison). He is a Fellow of ACM and IEEE, and a recipient of the Swarnajayanti Fellowship, the Shanti Swarup Bhatnagar Award, and the Infosys Prize.