TY - CONF T1 - Using state modules for adaptive query processing T2 - 19th International Conference on Data Engineering, 2003. Proceedings Y1 - 2003 A1 - Vijayshankar Raman A1 - Deshpande, Amol A1 - Hellerstein,J. M KW - adaptive query processing KW - Bandwidth KW - Calibration KW - data encapsulation KW - data structure KW - Data structures KW - Databases KW - Dictionaries KW - eddy routing KW - eddy routing operator KW - Encapsulation KW - join operator KW - multiple algorithm automatic hybridization KW - multiple competing join algorithm KW - query architecture KW - Query processing KW - query spanning tree KW - Routing KW - routing policy KW - Runtime KW - shared materialization point KW - State Module KW - SteMs KW - Telegraph dataflow system KW - Telegraphy KW - Tree data structures AB - 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 [R. Avnur et al., (2000)]. 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. 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. JA - 19th International Conference on Data Engineering, 2003. Proceedings PB - IEEE SN - 0-7803-7665-X M3 - 10.1109/ICDE.2003.1260805 ER -