Published Articles >> Table of Contents >> Abstract

19th International Conference on Data Engineering (ICDE'03)   p. 353
Using State Modules for Adaptive Query Processing
Vijayshankar Raman, IBM Almaden Research Center
Amol Deshpande, University of California, Berkeley
Joseph M. Hellerstein, University of California, Berkeley

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICDE.2003.1260805
Send link to a friend

Abstract
We present a query architecture in which join operators are decomposed into their constituent data structures (State Modules, or SteMs), and dataflow among these SteMs is managed adaptively by an eddy routing operator [2]. Breaking the encapsulation of joins serves two purposes. First, it allows the eddy to observe multiple physical operations embedded in a join algorithm, allowing for better calibration and control of these operations. Second, the SteM on a relation serves as a shared materialization point, enabling multiple competing access methods to share results, which can be leveraged by multiple competing join algorithms. Our architecture extends prior work significantly, allowing continuously adaptive decisions for most major aspects of traditional query optimization: choice of access methods and join algorithms, ordering of operators, and choice of a query spanning tree. SteMs introduce significant routing flexibility to the eddy, enabling more opportunities for adaptation, but also introducing the possibility of incorrect query results. We present constraints on eddy routing through SteMs that ensure correctness while preserving a great deal of flexibility. We also demonstrate the benefits of our architecture via experiments in the Telegraph dataflow system [26]. We show that even a simple routing policy allows significant flexibility in adaptation, including novel effects like automatic "hybridization" of multiple algorithms for a single join.
Back to Top Additional Information
Citation:  Vijayshankar Raman, Amol Deshpande, Joseph M. Hellerstein, "Using State Modules for Adaptive Query Processing," icde, p. 353,  19th International Conference on Data Engineering (ICDE'03),  2003