loading...
Using State Modules for Adaptive Query Processing
Bangalore, India March 05-March 08
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICDE.2003.126080519th International Conference on Data ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Vijayshankar Raman, IBM Almaden Research Center
Amol Deshpande, University of California, Berkeley
Joseph M. Hellerstein, University of California, Berkeley
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.
Citation:
Vijayshankar Raman, Amol Deshpande, Joseph M. Hellerstein, "Using State Modules for Adaptive Query Processing," icde, pp.353, 19th International Conference on Data Engineering (ICDE'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.