Eddies: Continuously Adaptive Query Processing Ron Avnur and Joseph M. Hellerstein   View Paper (PDF)   Return to Research Sessions Abstract In large federated and shared-nothing databases, resources can exhibit widely fluctuating characteristics. Assumptions made at the time a query is submitted will rarely hold throughout the duration of query processing. As a result, traditional static query optimization and execution techniques are ineffective in these environments. In this paper we introduce a query processing mechanism called an eddy, which continuously reorders operators in a query plan as it runs. We characterize the moments of symmetry during which pipelined joins can be easily reordered, and the synchronization barriers that require inputs from different sources to be coordinated. By combining eddies with appropriate join algorithms, we merge the optimization and execution phases of query processing, allowing each tuple to have a flexible ordering of the query operators. This flexibility is controlled by a combination of fluid dynamics and a simple learning algorithm. Our initial implementation demonstrates promising results, with eddies performing nearly as well as a static optimizer/executor in static scenarios, and providing dramatic improvements in dynamic execution environments. References Note: References link to DBLP on the Web. [AAC+97] Andrea C. Arpaci-Dusseau , Remzi Arpaci-Dusseau , David E. Culler , Joseph M. Hellerstein , David A. Patterson : High-Performance Sorting on Networks of Workstations. SIGMOD Conference 1997 : 243-254 [AAT+99] Remzi H. Arpaci-Dusseau , Eric Anderson , Noah Treuhaft , David E. Culler , Joseph M. Hellerstein , David A. Patterson , Katherine A. Yelick : Cluster I/O with River: Making the Fast Case Common. IOPADS 1999 : 10-22 [AFTU96] Laurent Amsaleg , Michael J. Franklin , Anthony Tomasic , Tolga Urhan : Scrambling Query Plans to Cope With Unexpected Delays. PDIS 1996 : 208-219 [AH99] ... [Aok99] Paul M. Aoki : How to Avoid Building DataBlades That Know the Value of Everything and the Cost of Nothing. SSDBM 1999 : 122-133 [AZ96] Gennady Antoshenkov , Mohamed Ziauddin : Query Processing and Optimization in Oracle Rdb. VLDB Journal 5(4) : 229-237(1996) [Bar99] ... [BDF+97] Daniel Barbará , William DuMouchel , Christos Faloutsos , Peter J. Haas , Joseph M. Hellerstein , Yannis E. Ioannidis , H. V. Jagadish , Theodore Johnson , Raymond T. Ng , Viswanath Poosala , Kenneth A. Ross , Kenneth C. Sevcik : The New Jersey Data Reduction Report. Data Engineering Bulletin 20(4) : 3-45(1997) [BO99] Jihad Boulos , Kinji Ono : Cost Estimation of User-Defined Methods in Object-Relational Database Systems. SIGMOD Record 28(3) : 22-28(1999) [DGS+90] David J. DeWitt , Shahram Ghandeharizadeh , Donovan A. Schneider , Allan Bricker , Hui-I Hsiao , Rick Rasmussen : The Gamma Database Machine Project. TKDE 2(1) : 44-62(1990) [DKO+84] David J. DeWitt , Randy H. Katz , Frank Olken , Leonard D. Shapiro , Michael Stonebraker , David A. Wood : Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984 : 1-8 [FMLS99] Daniela Florescu , Alon Y. Levy , Ioana Manolescu , Dan Suciu : Query Optimization in the Presence of Limited Access Patterns. SIGMOD Conference 1999 : 311-322 [GC94] Richard L. Cole , Goetz Graefe : Optimization of Dynamic Query Evaluation Plans. SIGMOD Conference 1994 : 150-160 [GMPQ+97] Hector Garcia-Molina , Yannis Papakonstantinou , Dallan Quass , Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman , Vasilis Vassalos , Jennifer Widom : The TSIMMIS Approach to Mediation: Data Models and Languages. JIIS 8(2) : 117-132(1997) [Gra90] Goetz Graefe : Encapsulation of Parallelism in the Volcano Query Processing System. SIGMOD Conference 1990 : 102-111 [GWBC99] ... [HAC+99] Joseph M. Hellerstein , Ron Avnur , Andy Chou , Christian Hidber , Chris Olston , Vijayshankar Raman , Tali Roth , Peter J. Haas : Interactive data Analysis: The Control Project. IEEE Computer 32(8) : 51-59(1999) [Hel98] Joseph M. Hellerstein : Optimization Techniques for Queries with Expensive Methods. TODS 23(2) : 113-157(1998) [HH99] Peter J. Haas , Joseph M. Hellerstein : Ripple Joins for Online Aggregation. SIGMOD Conference 1999 : 287-298 [HKWY97] Laura M. Haas , Donald Kossmann , Edward L. Wimmers , Jun Yang : Optimizing Queries Across Diverse Data Sources. VLDB 1997 : 276-285 [HSC99] Joseph M. Hellerstein , Michael Stonebraker , Rick Caccia : Independent, Open Enterprose Data Integration. IEEE Data Engineering Bulletin 22(1) : 43-49(1999) [IFF+99] Zachary G. Ives , Daniela Florescu , Marc Friedman , Alon Y. Levy , Daniel S. Weld : An Adaptive Query Execution System for Data Integration. SIGMOD Conference 1999 : 299-310 [IK84] Toshihide Ibaraki , Tiko Kameda : On the Optimal Nesting Order for Computing N-Relational Joins. TODS 9(3) : 482-502(1984) [INSS97] Yannis E. Ioannidis , Raymond T. Ng , Kyuseok Shim , Timos K. Sellis : Parametric Query Optimization. VLDB Journal 6(2) : 132-151(1997) [KBZ86] Ravi Krishnamurthy , Haran Boral , Carlo Zaniolo : Optimization of Nonrecursive Queries. VLDB 1986 : 128-137 [KD98] Navin Kabra , David J. DeWitt : Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans. SIGMOD Conference 1998 : 106-117 [Met97] ... [Mit97] ... [NWMN99] Kenneth W. Ng , Zhenghao Wang , Richard R. Muntz , Silvia Nittel : Dynamic Query Re-Optimization. SSDBM 1999 : 264-273 [RPK+99] Berthold Reinwald , Hamid Pirahesh , Ganapathy Krishnamoorthy , George Lapis , Brian T. Tran , Swati Vora : Heterogeneous Query Processing through SQL Table Functions. ICDE 1999 : 366-373 [RRH99] Vijayshankar Raman , Bhaskaran Raman , Joseph M. Hellerstein : Online Dynamic Reordering for Interactive Data Processing. VLDB 1999 : 709-720 [SB98] ... [SBH98] Michael Stonebraker , Paul Brown , Martin Herbach : Interoperability, Distributed Applications and Distributed Databases: The Virtual Table Interface. Data Engineering Bulletin 21(3) : 25-33(1998) [Son98] ... [SWK76] Michael Stonebraker , Eugene Wong , Peter Kreps , Gerald Held : The Design and Implementation of INGRES. TODS 1(3) : 189-222(1976) [UF99] ... [UFA98] Tolga Urhan , Michael J. Franklin , Laurent Amsaleg : Cost Based Query Scrambling for Initial Delays. SIGMOD Conference 1998 : 130-141 [WA91] Annita N. Wilschut , Peter M. G. Apers : Dataflow Query Execution in a Parallel Main-Memory Environment. PDIS 1991 : 68-77 [WW94] Carl A. Waldspurger , William E. Weihl : Lottery Scheduling: Flexible Proportional-Share Resource Management. OSDI 1994 : 1-11 BIBTEX @inproceedings{DBLP:conf/sigmod/HellersteinA00,   author    = {Ron Avnur and                 Joseph M. Hellerstein},    editor    = {Weidong Chen and                 Jeffrey F. Naughton and                 Philip A. Bernstein},    title     = {Eddies: Continuously Adaptive Query Processing},    booktitle = {Proceedings of the 2000 ACM SIGMOD International Conference on                 Management of Data, May 16-18, 2000, Dallas, Texas, USA},    journal   = {SIGMOD Record},    publisher = {ACM},    volume    = {29},    number    = {2},    year      = {2000},    isbn      = {1-58113-218-2},    pages     = {261-272},    crossref  = {DBLP:conf/sigmod/2000},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.