Lifting the Burden of History from Adaptive Query Processing Amol Deshpande and Joseph M. Hellerstein   View Paper (PDF)   Return to RESEARCH SESSION 24:QUERY PROCESSING AND OPTIMIZATION Abstract Adaptive query processing schemes attempt to reoptimize 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. The eddy 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 adaptively and good performance in the face of uncertainty, outperforming prior eddy proposals by orders of magnitude. ©2005 Association for Computing Machinery