Optimization of dynamic query evaluation plans

ABSTRACT

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 “static” plans produced by traditional optimizers may not be optimal for many of their actual run-time invocations. Instead, we propose a novel optimization model that assigns the bulk of the optimization effort to compile-time and delays carefully selected optimization decisions until run-time. Our previous work defined the run-time primitives, “dynamic plans” using “choose-plan” operators, for executing such delayed decisions, but did not solve the problem of constructing dynamic plans at compile-time. The present paper introduces techniques that solve this problem. Experience with a working prototype optimizer demonstrates (i) that the additional optimization and start-up overhead of dynamic plans compared to static plans is dominated by their advantage at run-time, (ii) that dynamic plans are as robust as the “brute-force” remedy of run-time optimization, i.e., dynamic plans maintain their optimality even if parameters change between compile-time and run-time, and (iii) that the start-up overhead of dynamic plans is significantly less than the time required for complete optimization at run-time. In other words, our proposed techniques are superior to both techniques considered to-date, namely compile-time optimization into a single static plan as well as run-time optimization. Finally, we believe that the concepts and technology described can be transferred to commercial query optimizers in order to improve the performance of embedded queries with host variables in the query predicate and to adapt to run-time system loads unpredictable at compile time.

REFERENCES

• Ant93: Gennady Antoshenkov, Dynamic Query Optimization in Rdb/VMS, Proceedings of the Ninth International Conference on Data Engineering, p.538-547, April 19-23, 1993
• BMG93: José A. Blakeley , William J. McKenna , Goetz Graefe, Experiences building the open OODB query optimizer, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.287-296, May 25-28, 1993, Washington, D.C., United States
• BPR90: P. Bodorik , J. Pyra , J. S. Riordon, Correcting execution of distributed queries, Proceedings of the second international symposium on Databases in parallel and distributed systems, p.192-201, July 02-04, 1990, Dublin, Ireland [doi>10.1145/319057.319098]
• CAK81: D. D. Chamberlin , M. M. Astrahan , W. F. King , R. A. Lorie , J. W. Mehl , T. G. Price , M. Schkolnick , P. Griffiths Selinger , D. R. Slutz , B. W. Wade , R. A. Yost, Support for repetitive transactions and ad hoc queries in System R, ACM Transactions on Database Systems (TODS), v.6 n.1, p.70-94, March 1981 [doi>10.1145/319540.319550]
• Chr84: S. Christodoulakis, Implications of certain assumptions in database performance evauation, ACM Transactions on Database Systems (TODS), v.9 n.2, p.163-186, June 1984 [doi>10.1145/329.318578]
• CAB93: R.L. Cole, M. J. Anderson, and R. J. Bestgen, "Query Processing in the IBM Application System/400", IEEE Data Eng. Bull. 16, 4 (December 1993), 19.
• CLR89: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• DMP93: Marcia A. Derr , Shinichi Morishita , Geoffrey Phipps, Design and implementation of the glue-nail database system, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.147-156, May 25-28, 1993, Washington, D.C., United States
• GHK92: Sumit Ganguly , Waqar Hasan , Ravi Krishnamurthy, Query optimization for parallel execution, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.9-18, June 02-05, 1992, San Diego, California, United States
• GrW89: G. Graefe , K. Ward, Dynamic query evaluation plans, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.358-366, June 1989, Portland, Oregon, United States
• Gra93: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• GrM93: Goetz Graefe , William J. McKenna, The Volcano Optimizer Generator: Extensibility and Efficient Search, Proceedings of the Ninth International Conference on Data Engineering, p.209-218, April 19-23, 1993
• HaP88: W. Hasan and H. Pirahesh, "Query Rewrite Optimization in Starburst", Comp. Sci. Res. Rep., San Jose, CA, August 1988.
• HoS93: Wei Hong , Michael Stonebraker, Optimization of parallel query execution plans in XPRS, Distributed and Parallel Databases, v.1 n.1, p.9-32, Jan. 1993 [doi>10.1007/BF01277518]
• IoC91: Yannis E. Ioannidis , Stavros Christodoulakis, On the propagation of errors in the size of join results, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.268-277, May 29-31, 1991, Denver, Colorado, United States
• INS92: Y.E. Ioannidis, R. T. Ng, K. Shim, and T. K. Sellis, "Parametric Query Processing", Proc. lnt'l. Conf. on Very Large Data Bases, Vancouver, BC, Canada, August 1992, 103.
• KGM91: Tom Keller , Goetz Graefe , David Maier, Efficient assembly for complex objects, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.148-157, May 29-31, 1991, Denver, Colorado, United States
• Loh89: G.M. Lohman, "Is Query Optimization a 'Solved' Problem?", in Proc. Workshop on Database Query Optimization, G. Graefe (editor), Oregon Graduate Center Comp. Sci. Tech. Rep. 89-005, Beaverton, OR, May 1989, 13.
• MaL89: Lothar F. Mackert , Guy M. Lohman, Index scans using a finite LRU buffer: a validated I/O model, ACM Transactions on Database Systems (TODS), v.14 n.3, p.401-424, Sept. 1989 [doi>10.1145/68012.68016]
• MHW90: C. Mohan , Don Haderle , Yun Wang , Josephine Cheng, Single table access using multiple indexes: optimization, execution, and concurrency control techniques, Proceedings of the international conference on extending database technology on Advances in database technology, p.29-43, March 1990, Venice, Italy
• OnL90: Kiyoshi Ono , Guy M. Lohman, Measuring the complexity of join enumeration in query optimization, Proceedings of the sixteenth international conference on Very large databases, p.314-325, September 1990, Brisbane, Australia
• OHM92: Jack Orenstein , Sam Haradhvala , Benson Margulies , Don Sakahara, Query processing in the ObjectStore database system, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.403-412, June 02-05, 1992, San Diego, California, United States
• SAC79: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Readings in database systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• SBM89: K. Seppi, J. Barnes, and C. Morris, "A Bayesian Approach to Query Optimization in Large Scale Data Bases", The Univ. of Texas at Austin ORP 89-19, Austin, TX, 1989.
• TsN92: Manolis M. Tsangaris , Jeffrey F. Naughton, On the performance of object clustering techniques, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.144-153, June 02-05, 1992, San Diego, California, United States
• WoG93: Richard H. Wolniewicz , Goetz Graefe, Algebraic Optimization of Computations over Scientific Databases, Proceedings of the 19th International Conference on Very Large Data Bases, p.13-24, August 24-27, 1993

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Experimentation, Performance, Verification