Efficient mid-query re-optimization of sub-optimal query execution plans

ABSTRACT

For a number of reasons, even the best query optimizers can very often produce sub-optimal query execution plans, leading to a significant degradation of performance. This is especially true in databases used for complex decision support queries and/or object-relational databases. In this paper, we describe an algorithm that detects sub-optimality of a query execution plan during query execution and attempts to correct the problem. The basic idea is to collect statistics at key points during the execution of a complex query. These statistics are then used to optimize the execution of the query, either by improving the resource allocation for that query, or by changing the execution plan for the remainder of the query. To ensure that this does not significantly slow down the normal execution of a query, the Query Optimizer carefully chooses what statistics to collect, when to collect them, and the circumstances under which to re-optimize the query. We describe an implementation of this algorithm in the Paradise Database System, and we report on performance studies, which indicate that this can result in significant improvements in the performance of complex queries.

REFERENCES

• 1: Laurent Amsaleg , Michael J. Franklin , Anthony Tomasic , Tolga Urhan, Scrambling query plans to cope with unexpected delays, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.208-219, December 18-20, 1996, Miami Beach, Florida, United States
• 2: Gennady Antoshenkov, Dynamic Query Optimization in Rdb/VMS, Proceedings of the Ninth International Conference on Data Engineering, p.538-547, April 19-23, 1993
• 3: Gennady Antoshenkov, Dynamic Optimization of Index Scans Restricted by Booleans, Proceedings of the Twelfth International Conference on Data Engineering, p.430-440, February 26-March 01, 1996
• 4: Ming-Syan Chen , Ming-Ling Lo , Philip S. Yu , Honesty C. Young, Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins, Proceedings of the 18th International Conference on Very Large Data Bases, p.15-26, August 23-27, 1992
• 5: Marcia A. Derr, Adaptive query optimization in a deductive database system, Proceedings of the second international conference on Information and knowledge management, p.206-215, November 01-05, 1993, Washington, D.C., United States [doi>10.1145/170088.170134]
• 6: Philippe Flajolet , G. Nigel Martin, Probabilistic counting algorithms for data base applications, Journal of Computer and System Sciences, v.31 n.2, p.182-209, Sept. 1985 [doi>10.1016/0022-0000(85)90041-8]
• 7: Richard L. Cole , Goetz Graefe, Optimization of dynamic query evaluation plans, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.150-160, May 24-27, 1994, Minneapolis, Minnesota, United States
• 8: 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
• 9: 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
• 10: Yannis E. Ioannidis , Raymond T. Ng , Kyuseok Shim , Timos K. Sellis, Parametric Query Optimization, Proceedings of the 18th International Conference on Very Large Data Bases, p.103-114, August 23-27, 1992
• 11: Yannis E. Ioannidis , Viswanath Poosala, Balancing histogram optimality and practicality for query result size estimation, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.233-244, May 22-25, 1995, San Jose, California, United States
• 12: Navin Kabra , David J. Dewitt, Query optimization for object-relational database systems, 1999
• 13: Navin Kabra , David J. DeWitt, OPT++ : an object-oriented implementation for extensible database query optimization, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.1, p.55-78, April 1999 [doi>10.1007/s007780050074]
• 14: Manish Mehta , David J. DeWitt, Dynamic Memory Allocation for Multiple-Query Workloads, Proceedings of the 19th International Conference on Very Large Data Bases, p.354-367, August 24-27, 1993
• 15: NAG, B., AND DEWITT, D.J. "Memory Allocation Strategies for Complex Decision Support Queries". Submitted for publication.
• 16: Kiyoshi Ono , Guy M. Lohman, Measuring the Complexity of Join Enumeration in Query Optimization, Proceedings of the 16th International Conference on Very Large Data Bases, p.314-325, August 13-16, 1990
• 17: Jignesh Patel , JieBing Yu , Navin Kabra , Kristin Tufte , Biswadeep Nag , Josef Burger , Nancy Hall , Karthikeyan Ramasamy , Roger Lueder , Curt Ellmann , Jim Kupsch , Shelly Guo , Johan Larson , David De Witt , Jeffrey Naughton, Building a scaleable geo-spatial DBMS: technology, implementation, and evaluation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.336-347, May 11-15, 1997, Tucson, Arizona, United States
• 18: POOSALA, V. "Zipf's Law". Tech. rep., University of Wisconsin, Madison, 1995.
• 19: POOSALA, V., AND IOANNIDIS, Y. "Histogram-Based Solutions to Diverse Database Estimation Problems". In Data Engineering Bulletin (1995), vol. 18(3), pp. 10- 18.
• 20: Viswanath Poosala , Peter J. Haas , Yannis E. Ioannidis , Eugene J. Shekita, Improved histograms for selectivity estimation of range predicates, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.294-305, June 04-06, 1996, Montreal, Quebec, Canada
• 21: RAAB, F. "TPC Benchmark D - Standard Specification, Revision 1.0". Transaction Processing Performance Council, May 1995.
• 22: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 23: STONEBRAKER, M., ANTON, J., AND HIROHAMA, M. "Extendability in POSTGRES". In Data Engineering Bulletin (1987), vol. 10(2), pp. 16-23.
• 24: Jeffrey S. Vitter, Random sampling with a reservoir, ACM Transactions on Mathematical Software (TOMS), v.11 n.1, p.37-57, March 1985 [doi>10.1145/3147.3165]
• 25: Eugene Wong , Karel Youssefi, Decomposition—a strategy for query processing, ACM Transactions on Database Systems (TODS), v.1 n.3, p.223-241, Sept. 1976 [doi>10.1145/320473.320479]
• 26: Philip S. Yu , Douglas W. Cornell, Buffer management based on return on consumption in a multi-query environment, The VLDB Journal — The International Journal on Very Large Data Bases, v.2 n.1, p.1-38, January 1993 [doi>10.1007/BF01231797]
• 27: ZIPF, G.K. "Human Behavior and the Principle of Least Resistance". Addison-Wesley, Reading, MA, 1949.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

General Terms:
Algorithms, Experimentation, Measurement