Fundamental techniques for order optimization

ABSTRACT

Decision support applications are growing in popularity as more business data is kept on-line. Such applications typically include complex SQL queries that can test a query optimizer's ability to produce an efficient access plan. Many access plan strategies exploit the physical ordering of data provided by indexes or sorting. Sorting is an expensive operation, however. Therefore, it is imperative that sorting is optimized in some way or avoided all together. Toward that goal, this paper describes novel optimization techniques for pushing down sorts in joins, minimizing the number of sorting columns, and detecting when sorting can be avoided because of predicates, keys, or indexes. A set of fundamental operations is described that provide the foundation for implementing such techniques. The operations exploit data properties that arise from predicate application, uniqueness, and functional dependencies. These operations and techniques have been implemented in IBM's DB2/CS.

REFERENCES

• Ant93: G. Antosheknov. Query processing in dec rdb: Major issues and future challenges. In IEEE Bulletin on the Technical Comittee on Data Engineer:ng, December 1993.
• BB79: Catriel Beeri , Philip A. Bernstein, Computational problems related to the design of normal form relational schemas, ACM Transactions on Database Systems (TODS), v.4 n.1, p.30-59, March 1979 [doi>10.1145/320064.320066]
• BD83: Dina Bitton , David J. DeWitt, Duplicate record elimination in large data files, ACM Transactions on Database Systems (TODS), v.8 n.2, p.255-265, June 1983 [doi>10.1145/319983.319987]
• BE76: M. Blasgen and K. Eswaran. On the evaluation of queries in a relational data base system. Technical Report 1745, IBM Santa Teresa Lab, April 1976.
• CS93: Surajit Chaudhuri , Kyuseok Shim, Query Optimization in the Presence of Foreign Functions, Proceedings of the 19th International Conference on Very Large Data Bases, p.529-542, August 24-27, 1993
• DD92: H. Darwen and C. Date. The role of functional dependencies in query decomposition. In Relatzonal Database Writings 1989-1991~ Addison Wesley, 1992.
• DKO+84: David J DeWitt , Randy H Katz , Frank Olken , Leonard D Shapiro , Michael R Stonebraker , David Wood, Implementation techniques for main memory database systems, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• Eng95: S. Englert. Tpc benchmark d. In Transact:on Processing Performance Council, 777 N. First St, Suite 600, San Jose CA 95112-6311, October 1995.
• GD87: Goetz Graefe , David J. DeWitt, The EXODUS optimizer generator, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.160-172, May 27-29, 1987, San Francisco, California, 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]
• Hel94: Joseph M. Hellerstein, Practical predicate placement, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.325-335, May 24-27, 1994, Minneapolis, Minnesota, United States
• HFLP89: L. M. Haas , J. C. Freytag , G. M. Lohman , H. Pirahesh, Extensible query processing in starburst, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.377-388, June 1989, Portland, Oregon, United States
• JV84: Matthias Jarke , Jurgen Koch, Query Optimization in Database Systems, ACM Computing Surveys (CSUR), v.16 n.2, p.111-152, June 1984 [doi>10.1145/356924.356928]
• Loh88: Guy M. Lohman, Grammar-like functional rules for representing query optimization alternatives, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.18-27, June 01-03, 1988, Chicago, Illinois, United States
• OL90: 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
• PHH92: Hamid Pirahesh , Joseph M. Hellerstein , Waqar Hasan, Extensible/rule based query rewrite optimization in Starburst, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.39-48, June 02-05, 1992, San Diego, California, United States
• PL94: G. N. Paulley , Per-Åke Larson, Exploiting Uniqueness in Query Optimization, Proceedings of the Tenth International Conference on Data Engineering, p.68-79, February 14-18, 1994
• SAC+79: 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]
• YL93: Weipeng P. Yan , Per-Åke Larson, Performing Group-By before Join, Proceedings of the Tenth International Conference on Data Engineering, p.89-100, February 14-18, 1994

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Algorithms, Theory