TY - CONF T1 - Lifting the burden of history from adaptive query processing T2 - Proceedings of the Thirtieth international conference on Very large data bases - Volume 30 Y1 - 2004 A1 - Deshpande, Amol A1 - Hellerstein,Joseph M. AB - Adaptive query processing schemes attempt to re-optimize query plans during the course of query execution. A variety of techniques for adaptive query processing have been proposed, varying in the granularity at which they can make decisions [8]. The eddy [1] is the most aggressive of these techniques, with the flexibility to choose tuple-by-tuple how to order the application of operators. In this paper we identify and address a fundamental limitation of the original eddies proposal: the burden of history in routing. We observe that routing decisions have long-term effects on the state of operators in the query, and can severely constrain the ability of the eddy to adapt over time. We then propose a mechanism we call STAIRs that allows the query engine to manipulate the state stored inside the operators and undo the effects of past routing decisions. We demonstrate that eddies with STAIRs achieve both high adaptivity and good performance in the face of uncertainty, outperforming prior eddy proposals by orders of magnitude. JA - Proceedings of the Thirtieth international conference on Very large data bases - Volume 30 T3 - VLDB '04 PB - VLDB Endowment SN - 0-12-088469-0 UR - http://dl.acm.org/citation.cfm?id=1316689.1316771 ER -