Seminar by Jayant R. Haritsa
Drawing Out the Artistic Talents of Database Query Optimizers
Jayant R. Haritsa
Indian Institute of Science, Bangalore Date: Thursday, April 22, 2010 Time: 5:30 PM Venue: CS102.
Abstract:
Modern 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 the above framework, a "plan diagram" is a pictorial enumeration of the execution plan choices of a database query optimizer over the relational selectivity space. Over the past five years, we have developed a Java-based visualization tool, called Picasso, for automatically generating plan diagrams. In this talk, we present and analyze representative plan diagrams produced by Picasso on a suite of popular commercial query optimizers for queries based on the TPC benchmarks. These diagrams, which often appear similar to cubist paintings, provide a variety of interesting insights, including that current optimizers make extremely fine-grained 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. The Picasso tool has been copyrighted by IISc and released into the public-domain -- it is currently operational at several academic and industrial organizations worldwide.
We will then show how these complex plan diagrams can almost always be reduced to ''anorexic'' pictures, featuring only a few plans, without materially affecting the query processing quality. The anorexic reduction property has several useful implications for the design and usage of query optimizers, and in particular, we will discuss how it can be used to minimize the adverse impact of selectivity estimation errors, a chronic problem in practice.
The talk will conclude with a discussion on the implications and applications of these results for next-generation database query optimizers.
About The Speaker:
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. He received the B. Tech. degree in Electronics and Communications Engineering from the Indian Institute of Technology (Madras), and the MS and PhD degrees in Computer Science from the University of Wisconsin (Madison). His research interests are in database systems.