Ron Avnur
Joseph M. Hellerstein
Skip Abstract Section
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.
- AAC+97 A. C. Arpaci-Dusseau, R. H. Arpaci-Dusseau, D. E. Culler, J. M. Hellerstein, and D. A. Patterson. High-Performance Sorting on Networks of Workstations. In Proc. ACM-SIGMOD International Conference on Management of Data, Tucson, May 1997.]] Google Scholar
Digital Library
- AAT+99 R. H. Arpaci-Dusseau, E. Anderson, N. Treuhaft, D. E. Culler, J. M. Hellerstein, D. A. Patterson, and K. Yelick. Cluster I/O with River: Making the Fast Case Common. In Sixth Workshop on I/O in Parallel and Distributed Systems (IOPADS '99), pages 10-22, Atlanta, May 1999.]] Google ScholarDigital Library
- AFTU96 L. Amsaleg, M. J. Franklin, A. Tomasic, and T. Urhan. Scrambling Query Plans to Cope With Unexpected Delays. In 4th International Conference on Parallel and Distributed Information Systems (PDIS), Miami Beach, December 1996.]] Google ScholarDigital Library
- AH99 R. Avnur and J. M. Hellerstein. Continuous query optimization. Technical Report CSD-99-1078, University of California, Berkeley, November 1999.]] Google ScholarDigital Library
- Aok99 P. M. Aoki. How to Avoid Building DataBlades That Know the Value of Everything and the Cost of Nothing. In 11th International Conference on Scientific and Statistical Database Management, Cleveland, July 1999.]] Google ScholarDigital Library
- AZ96 G. Antoshenkov and M. Ziauddin. Query Processing and Optimization in Oracle Rdb. VLDB Journal, 5(4):229-237, 1996.]] Google ScholarDigital Library
- Bar99 R. Barnes. Scale Out. In High Performance Transaction Processing Workshop (HPTS '99), Asilomar, September 1999.]]Google Scholar
- BDF+97 D. Barbara, W. DuMouchel, C. Faloutsos, P. J. Haas, J. M. Hellerstein, Y. E. Ioannidis, H. V. Jagadish, T. Johnson, R. T. Ng, V. Poosala, K. A. Ross, and K. C. Sevcik. The New Jersey Data Reduction Report. IEEE Data Engineering Bulletin, 20(4), December 1997.]]Google Scholar
- BO99 J. Boulos and K. Ono. Cost Estimation of User-Defined Methods in Object-Relational Database Systems. SIGMOD Record, 28(3):22-28, September 1999.]] Google ScholarDigital Library
- DGS+90 D. J. DeWitt, S. Ghandeharizadeh, D. Schneider, A. Bricker, H.-I Hsiao, and R. Rasmussen. The Gamma database machine project. IEEE Transactions on Knowledge and Data Engineering, 2(1):44-62, Mar 1990.]] Google ScholarDigital Library
- DKO+84 D. J. DeWitt, R. H. Katz, F. Olken, L. D. Shapiro, M. R. Stonebraker, and D. Wood. Implementation Techniques for Main Memory Database Systems. In Proc. ACM-SIGMOD International Conference on Management of Data, pages 1-8, Boston, June 1984.]] Google ScholarDigital Library
- FMLS99 D. Florescu, I. Manolescu, A. Levy, and D. Suciu. Query Optimization in the Presence of Limited Access Patterns. In Proc. ACM-SIGMOD International Conference on Management of Data, Phildelphia, June 1999.]] Google ScholarDigital Library
- GC94 G. Graefe and R. Cole. Optimization of Dynamic Query Evaluation Plans. In Proc. ACM-SIGMOD International Conference on Management of Data, Minneapolis, 1994.]] Google ScholarDigital Library
- GMPQ+97 H. Garcia-Molina, Y. Papakonstantinou, D. Quass, A Rajaraman, Y. Sagiv, J. Ullman, and J. Widom. The TSIMMIS Project: Integration of Heterogeneous Information Sources. Journal of Intelligent Information Systems, 8(2):117-132, March 1997.]] Google ScholarDigital Library
- Gra90 G. Graefe. Encapsulation of Parallelism in the Volcano Query Processing System. In Proc. ACM-SIGMOD International Conference on Management of Data, pages 102-111, Atlantic City, May 1990.]] Google ScholarDigital Library
- GWBC99 S. D. Gribble, M. Welsh, E. A. Brewer, and D. Culler. The Multi- Space: an Evolutionary Platform for Infrastructural Services. In Proceedings of the 1999 Usenix Annual Technical Conference, Monterey, June 1999.]] Google ScholarDigital Library
- HAC+99 J. M. Hellerstein, R. Avnur, A. Chou, C. Hidber, C. Olston, V. Raman, T. Roth, and P. J. Haas. Interactive Data Analysis: The Control Project. IEEE Computer, 32(8):51-59, August 1999.]] Google ScholarDigital Library
- Hel98 J. M. Hellerstein. Optimization Techniques for Queries with Expensive Methods. ACM Transactions on Database Systems, 23(2):113-157, 1998.]] Google ScholarDigital Library
- HH99 P. J. Haas and J. M. Hellerstein. Ripple Joins for Online Aggregation. In Proc. ACM-SIGMOD International Conference on Management of Data, pages 287-298, Philadelphia, 1999.]] Google ScholarDigital Library
- HKWY97 L. Haas, D. Kossmann, E. Wimmers, and J. Yang. Optimizing Queries Across Diverse Data Sources. In Proc. 23rd International Conference on Very Large Data Bases (VLDB), Athens, 1997.]] Google ScholarDigital Library
- HSC99 J. M. Hellerstein, M. Stonebraker, and R. Caccia. Open, Independent Enterprise Data Integration. IEEE Data Engineering Bulletin, 22(1), March 1999. http://www.cohera.com.]]Google Scholar
- IFF+99 Z. G. Ives, D. Florescu, M. Friedman, A. Levy, and D. S. Weld. An Adaptive Query Execution System for Data Integration. In Proc. ACM-SIGMOD International Conference on Management of Data, Philadelphia, 1999.]] Google ScholarDigital Library
- IK84 T. Ibaraki and T. Kameda. Optimal Nesting for Computing N-relational Joins. ACM Transactions on Database Systems, 9(3):482-502, October 1984.]] Google ScholarDigital Library
- INSS97 Y. E. Ioannidis, R. T. Ng, K. Shim, and T. K. Sellis. Parametric Query Optimization. VLDB Journal, 6(2):132-151, 1997.]] Google ScholarDigital Library
- KBZ86 R. Krishnamurthy, H. Boral, and C. Zaniolo. Optimization of Nonrecursive Queries. In Proc. 12th International Conference on Very Large Databases (VLDB), pages 128-137, August 1986.]] Google ScholarDigital Library
- KD98 N. Kabra and D. J. DeWitt. Efficient Mid-Query Reoptimization of Sub-Optimal Query Execution Plans. In Proc. ACM-SIGMOD International Conference on Management of Data, pages 106- 117, Seattle, 1998.]] Google ScholarDigital Library
- Met97 R. Van Meter. Observing the Effects of Multi-Zone Disks. In Proceedings of the Usenix 1997 Technical Conference, Anaheim, January 1997.]] Google ScholarDigital Library
- Mit97 T. Mitchell. Machine Learning. McGraw Hill, 1997.]] Google ScholarDigital Library
- NWMN99 K. W. Ng, Z. Wang, R. R. Muntz, and S. Nittel. Dynamic Query Re-Optimization. In 11th International Conference on Scientific and Statistical Database Management, Cleveland, July 1999.]] Google ScholarDigital Library
- RPK+99 B. Reinwald, H. Pirahesh, G. Krishnamoorthy, G. Lapis, B. Tran, and S. Vora. Heterogeneous Query Processing Through SQL Table Functions. In 15th International Conference on Data Engineering, pages 366-373, Sydney, March 1999.]] Google ScholarDigital Library
- RRH99 V. Raman, B. Raman, and J. M. Hellerstein. Online Dynamic Reordering for Interactive Data Processing. In Proc. 25th International Conference on Very Large Data Bases (VLDB), pages 709-720, Edinburgh, 1999.]] Google ScholarDigital Library
- SB98 R. S. Sutton and A. G. Bartow. Reinforcement Learning. MIT Press, Cambridge, MA, 1998.]] Google ScholarDigital Library
- SBH98 M. Stonebraker, P. Brown, and M. Herbach. Interoperability, Distributed Applications, and Distributed Databases: The Virtual Table Interface. IEEE Data Engineering Bulletin, 21(3):25-34, September 1998.]]Google Scholar
- Son98 E. D. Sontag. Mathematical Control Theory: Deterministic Finite-Dimensional Systems, Second Edition. Number 6 in Texts in Applied Mathematics. Springer-Verlag, New York, 1998.]] Google ScholarDigital Library
- SWK76 M. R. Stonebraker, E. Wong, and P. Kreps. The Design and Implementation of INGRES. ACM Transactions on Database Systems, 1(3):189-222, September 1976.]] Google ScholarDigital Library
- UF99 T. Urhan and M. Franklin. XJoin: Getting Fast Answers From Slow and Bursty Networks. Technical Report CS-TR-3994, University of Maryland, February 1999.]]Google Scholar
- UFA98 T. Urhan, M. Franklin, and L. Amsaleg. Cost-Based Query Scrambling for Initial Delays. In Proc. ACM-SIGMOD International Conference on Management of Data, Seattle, June 1998.]] Google ScholarDigital Library
- WA91 A. N. Wilschut and P. M. G. Apers. Dataflow Query Execution in a Parallel Main-Memory Environment. In Proc. First International Conference on Parallel and Distributed Info. Sys. (PDIS), pages 68-77, 1991.]] Google ScholarDigital Library
- WW94 C. A. Waldspurger and W. E. Weihl. Lottery scheduling: Flexible proportional-share resource management. In Proc. of the First Symposium on Operating Systems Design and Implementation (OSDI '94), pages 1-11, Monterey, CA, November 1994. USENIX Assoc.]] Google ScholarDigital Library
Index Terms
- Eddies: continuously adaptive query processing
Recommendations
Eddies: continuously adaptive query processing
SIGMOD '00: Proceedings of the 2000 ACM SIGMOD international conference on Management of dataIn 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 ...
An initial study of overheads of eddies
An eddy [2] is a highly adaptive query processing operator that continuously reoptimizes a query in response to changing runtime conditions. It does this by treating query processing as routing of tuples through operators and making per-tuple routing ...
Networks of Linked Data Eddies: An Adaptive Web Query Processing Engine for RDF Data
The Semantic Web - ISWC 2015AbstractClient-side query processing techniques that rely on the materialization of fragments of the original RDF dataset provide a promising solution for Web query processing. However, because of unexpected data transfers, the traditional optimize-then-...
Comments