|
|
|
     |
                                     |
Return to Architecture
Speculation is an every day phenomenon whereby one acts in anticipation of particular conditions that are likely to hold in the future. Computer science research has seen many successfull applications of speculation: modern processors, for example, speculate on the run-time properties of a program and decide to pre-execute instructions accordingly. We draw inspiration from these techniques and introduce speculation to query processing. Our approach is based on a visual query interface that monitors the construction of a query and takes advantage of the user 'think time'. In particular, based on the features of the partial query specified at any point, the interface prepares the database by issuing asynchronous manipulations to it that are likely to make the final query (or even queries further into the future) more efficient. Furthermore, the interface applies machine learning techniques on past user actions and builds a user-behavior model that guides speculation and deals with future uncertainty. We formalize speculative query processing as an optimization problem and derive algebraic properties of the corresponding cost model that are sufficient to address the complexities of the particular optimization. We have implemented our framework on top of an existing commercial database system and have evaluated its electiveness experimentally, with actual user traces. Our results show that speculation outperforms normal query processing, reducing query execution time by an average of 35% and achieving performance improvements of more than 90% on certain queries.
@inproceedings {DBLP:conf/cidr/PolyzotisI03, author = {Neoklis Polyzotis and Yannis E. Ioannidis}, booktitle = {CIDR}, title = {Speculative Query Processing.}, year = {2003}, url = {db/conf/cidr/cidr2003.html#PolyzotisI03}, ee = {http://www-db.cs.wisc.edu/cidr/program/p2.pdf}, bibsource = {DBLP, http://dblp.uni-trier.de} }  ©2004 Association for Computing Machinery |
