G. Graefe
Abstract
In most database systems, a query embedded in a program written in a conventional programming language is optimized when the program is compiled. The query optimizer must make assumptions about the values of the program variables that appear as constants in the query, the resources that can be committed to query evaluation, and the data in the database. The optimality of the resulting query evaluation plan depends on the validity of these assumptions. If a query evaluation plan is used repeatedly over an extended period of time, it is important to determine when reoptimization is necessary. Our work aims at developing criteria when reoptimization is required, how these criteria can be implemented efficiently, and how reoptimization can be avoided by using a new technique called dynamic query evaluation plans. We experimentally demonstrate the need for dynamic plans and outline modifications to the EXODUS optimizer generator required for creating dynamic query evaluation plans.
- 1 P. Griffiths Selinger, M.M. Astrahan, D.D. Chamberlin, R.A. Lorie, and T.G. Price, "Access Path Selection in a Relational Database Management System," Proceedings of the A CM SIGMOD Conference, pp. 23-34 (May- June 1979). Google Scholar
Digital Library
- 2 D.D. Chamberlin, M.M. Astrahan, W.F. King, R.A. Lorie, J.W. Mehl, T.G. Price, M. Schkolnik, P. Griffiths Selinger, D.R. Slutz, B.W. Wade, and R.A. Yost, "Support for Repetitive Transactions and Ad Hoc Queries in System R," A CM Transactions on Database Systems 6(1) pp. 70-94 (March 1981). Google ScholarDigital Library
- 3 E. Wong and K. Youssefi, "Decomposition- A Strategy for Query Processing," A CM Transactions on Database Systems l(3) pp. 223-241 (September 1976). Google ScholarDigital Library
- 4 K. Youssefi and E. Wong, "Query Processing in a Relational Database Management System," Proceedings of the Conference on Very Large Data Bases, pp. 409-417 (October 1979).Google Scholar
- 5 C.T. Yu and C.C. Chang, "On the Design of a Query Processing Strategy in a Distributed Database Environment," Proceedings of the A CM SIGMOD Conference, pp. 30-39 (May 1983). Google ScholarDigital Library
- 6 M.V. Mannino, P. Chu, and T. Sager, "Statistical Profile Estimation in Database Systems," ACM Computing Surveys 20(3)(September 1988). Google ScholarDigital Library
- 7 L.F. Mackert and G.M. Lohman, "R* Optimizer Validation and Performance Evaluation for Local Queries," Proceedings of the A CM SIG- MOD Conference, pp. 84-95 (May 1986). Google ScholarDigital Library
- 8 L.F. Mackert and G.M. Lohman, "R* Optimizer Validation and Performance Evaluation for Distributed Queries," Proceedings of the Conference on Very Large Data Bases, pp. 149- 159 (August 1986). Google ScholarDigital Library
- 9 Y.H. Lee and P.S. Yu, "Adaptive Selection of Access Path and Join Method," unpublished manuscript, (1988).Google Scholar
- 10 M. Stonebraker, R. Katz, D. Patterson, and J. Ousterhout, "The Design of XPRS," Proceedings of the Conference on Very Large Databases, pp. 318-330 (August 1988). Google ScholarDigital Library
- 11 W. Hasan and H. Pirahesh, "Query Rewrite Optimization in Starburst," Computer Science Research Report, (RJ 6367 (62349))IBM Almaden Research Center, (August 1988).Google Scholar
- 12 D.H.D. Warren, L.M. Pereira, and F. Pereira, "PROLOG - The Language and its Implementation Compared with Lisp," Proceedings of ACM SIGART-SIGPLAN Symposion on AI and Programming Languages, (1977). Google ScholarDigital Library
- 13 W. Clocksin and (3. Mellish, Programming in Prolog, Springer, New York (1981). Google ScholarDigital Library
- 14 A. Goldberg, D. Robson, and D. Ingalls, Smalltalk-80: The Language and its Implementation, Addison-Wesley, Reading, MA. (1983, 1985). Google ScholarDigital Library
- 15 G. Copeland and D. Maier, "Making Smalltalk a Database System," Proceedings of the A CM SIGMOD Conference, pp. 316-325 (June 1984). Google ScholarDigital Library
- 16 G. Graefe, "Volcano: An Extensible and Parallel Dataflow Query Evaluation System," in preparation, (February 1989).Google Scholar
- 17 G. Graefe and D. Maier, "Query Optimization in Object-Oriented Database Systems: A Prospectus," pp. 358-363 in Advances in Object- Oriented Database Systems, ed. K.R. Dittrieh,Springer-Verlag (September 1988). Google ScholarDigital Library
- 18 S.B. Yao, "Optimization of Query Evaluation Algorithms," A CM Transactions on Database Systems 4(2) pp. 133-155 (June 1979). Google ScholarDigital Library
- 19 S. Christodoulakis, "Estimating Block Transfers and Join Sizes," Proceedings of the A CM SIG- MOD Conference, pp. 40-54 (May 1983). Google ScholarDigital Library
- 20 S. Christodoulakis, "Estimating Record Seleetivities," Information Systems 8(2)pp. 105-115 (a983).Google ScholarCross Ref
- 21 S. Christodoulakis, "Estimating Block Selectivities," Information System8 9(1) p. 69 (1984).Google ScholarCross Ref
- 22 B.T. Vander Zanden, H.M. Taylor, and D. Bitton, "Estimating Block Accesses When Attributes Are Correlated," Proceeding of the Conference on Very Large Data Bases, pp. 119- 127 (August 1986). Google ScholarDigital Library
- 23 B.T. Vander Zanden, H.M. Taylor, and D. Bitton, "A general framework for computing block accesses," Information Systems 12(2) p. 177 (1987). Google ScholarDigital Library
- 24 G. Graefe, "Relational Division: Four Algorithms and Their Performance," Proceedings of the IEEE Conference on Data Engineering, pp. 94-101 (February 1989). Google ScholarDigital Library
- 25 J.E. Richardson and M.J. Carey, "Programming Constructs for Database System Implementation in EXODUS," Proceedings of the ACM SIGMOD Conference, pp. 208-219 (May 1987). Google ScholarDigital Library
- 26 L.M. Haas, W.F. Cody, J.C. Freytag, G. Lapis, B.C. Lindsay, G.M. Lohman, K. Ono, and H. Pirahesh, "An Extensible Processor for an Extended Relational Query Language," Computer Science Research Report, (RJ 6182 (60892))IBM Almaden Research Center, (April x088).Google Scholar
- 27 G. Graefe and D.J. DeWitt, "The EXODUS Optimizer Generator," Proceedings of the A CM SIGMOD Conference, pp. 160-171 (May 1987). Google ScholarDigital Library
- 28 G. Graefe, "Rule-Based Query Optimization in Extensible Database Systems," Ph.D. Thesis, University of Wisconsin, (August 1987). Google ScholarDigital Library
- 29 G. Graefe, "Software Modularization with the EXODUS Optimizer Generator," IEEE Data Engineering, (December 1987).Google Scholar
Index Terms
- Dynamic query evaluation plans
Recommendations
Optimization of dynamic query evaluation plans
SIGMOD '94: Proceedings of the 1994 ACM SIGMOD international conference on Management of dataTraditional query optimizers assume accurate knowledge of run-time parameters such as selectivities and resource availability during plan optimization, i.e., at compile time. In reality, however, this assumption is often not justified. Therefore, the “...
Optimization of dynamic query evaluation plans
Traditional query optimizers assume accurate knowledge of run-time parameters such as selectivities and resource availability during plan optimization, i.e., at compile time. In reality, however, this assumption is often not justified. Therefore, the “...
Dynamic query evaluation plans
SIGMOD '89: Proceedings of the 1989 ACM SIGMOD international conference on Management of dataIn most database systems, a query embedded in a program written in a conventional programming language is optimized when the program is compiled. The query optimizer must make assumptions about the values of the program variables that appear as ...
Comments