Towards a Science of Database Systems

点击翻译按钮获取中文摘要

IIS-0639106Richard T. Snodgrass rts@cs.arizona.eduUniversity of ArizonaTowards a Science of Database SystemsThis research takes a scientifically rigorous approach to an area previouslydominated by the engineering perspective, that of database queryoptimization. The goal is to understand cost-based query optimizers as ageneral class of computational artifacts, to develop insights and ultimatelywith predictive theories about how such optimizers behave.The research focuses on one aspect, that of cardinality estimation. Indetermining the optimal query evaluation plan for a submitted query, theoptimizer estimates the size of the output produced by each operator of eachcandidate plan. An established DBMS has been observed exhibiting "flutter,"in which the query evaluation plans jump around or even alternate back andforth as inevitable cardinality estimate inaccuracies increase. This projectevaluates the theory that the flutter arises out of unanticipatedinteractions between components of the optimizer. The prevalence of flutterwill be examined across this range of DBMSes, to see if that prevalence(measured as percentage of queries exhibiting flutter) is positivelycorrelated to measures of optimizer complexity.In terms of broader impacts, this research studies a previously unknownphenomenon of cost-based query optimizers, offering a scientific rationalefor new architectures for query optimization that explicitly take intoaccount uncertainty. In doing so, it introduces a new perspective (science),adding to the existing mathematical and engineering perspectives now usedprominently in database research, helping to realize Herbert Simon's visionof "sciences of the artificial." The results will be disseminated via theproject Web site http://www.cs.arizona.edu/soc/sodb.