Towards a Science of Database Systems

University Of Arizona, Tucson AZ

Investigators

Abstract

IIS-0639106 Richard T. Snodgrass <rts@cs.arizona.edu> University of Arizona Towards a Science of Database Systems This research takes a scientifically rigorous approach to an area previously dominated by the engineering perspective, that of database query optimization. The goal is to understand cost-based query optimizers as a general class of computational artifacts, to develop insights and ultimately with predictive theories about how such optimizers behave. The research focuses on one aspect, that of cardinality estimation. In determining the optimal query evaluation plan for a submitted query, the optimizer estimates the size of the output produced by each operator of each candidate plan. An established DBMS has been observed exhibiting "flutter," in which the query evaluation plans jump around or even alternate back and forth as inevitable cardinality estimate inaccuracies increase. This project evaluates the theory that the flutter arises out of unanticipated interactions between components of the optimizer. The prevalence of flutter will be examined across this range of DBMSes, to see if that prevalence (measured as percentage of queries exhibiting flutter) is positively correlated to measures of optimizer complexity. In terms of broader impacts, this research studies a previously unknown phenomenon of cost-based query optimizers, offering a scientific rationale for new architectures for query optimization that explicitly take into account uncertainty. In doing so, it introduces a new perspective (science), adding to the existing mathematical and engineering perspectives now used prominently in database research, helping to realize Herbert Simon's vision of "sciences of the artificial." The results will be disseminated via the project Web site http://www.cs.arizona.edu/soc/sodb.