Login
Talks & Seminars
Title: Plan Bouquets: A Fragrant Approach to Robust Query Processing
Prof. Jayant R. Haritsa, Database Systems Lab, IISc Bangalore
Date & Time: July 9, 2014 11:30
Venue: Conference Room, C Block, 01st Floor, Department of Computer Science & Engineering, Kanwal Rekhi (KReSIT) Building
Abstract:
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 errors 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 conceptually 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. In addition, it provides repeatable execution strategies across different invocations of a query. The plan bouquet approach has been empirically evaluated on both PostgreSQL and a commercial DBMS, over standard benchmark environments. Our experimental results indicate that, even with conservative assumptions, it delivers substantial improvements in the worst-case behavior, without impairing the average-case performance, as compared to the native optimizers of these systems. Moreover, it can be largely implemented using existing optimizer infrastructure, facilitating easy incorporation in current database engines. Overall, the bouquet approach provides novel guarantees that open up new possibilities for robust query processing. [This is joint work with Anshuman Dutt.]
Speaker Profile:
Jayant R. Haritsa is on the faculty of the Supercomputer Education & Research Centre and the Department of Computer Science & Automation at the Indian Institute of Science, Bangalore, since 1992. He received a BTech degree from the Indian Institute of Technology (Madras), and a PhD degree from the University of Wisconsin (Madison). His research interests are in database system design and testing.
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback