Efficient and extensible algorithms for multi query optimization

ABSTRACT

Complex queries are becoming commonplace, with the growing use of decision support systems. These complex queries often have a lot of common sub-expressions, either within a single query, or across multiple such queries run as a batch. Multiquery optimization aims at exploiting common sub-expressions to reduce evaluation cost. Multi-query optimization has hither-to been viewed as impractical, since earlier algorithms were exhaustive, and explore a doubly exponential search space.

In this paper we demonstrate that multi-query optimization using heuristics is practical, and provides significant benefits. We propose three cost-based heuristic algorithms: Volcano-SH and Volcano-RU, which are based on simple modifications to the Volcano search strategy, and a greedy heuristic. Our greedy heuristic incorporates novel optimizations that improve efficiency greatly. Our algorithms are designed to be easily added to existing optimizers. We present a performance study comparing the algorithms, using workloads consisting of queries from the TPC-D benchmark. The study shows that our algorithms provide significant benefits over traditional optimization, at a very acceptable overhead in optimization time.

REFERENCES

• CKPS95: Surajit Chaudhuri , Ravi Krishnamurthy , Spyros Potamianos , Kyuseok Shim, Optimizing Queries with Materialized Views, Proceedings of the Eleventh International Conference on Data Engineering, p.190-200, March 06-10, 1995
• CR94: Chungmin Melvin Chen , Nicholas Roussopoulos, The implementation and performance evaluation of the ADMS query optimizer: integrating query result caching and matching, Proceedings of the 4th international conference on extending database technology on Advances in database technology, p.323-336, May 1994, Cambridge, United Kingdom
• Fin82: Sheldon Finkelstein, Common expression analysis in database applications, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582400]
• GHRU97: Himanshu Gupta , Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Index Selection for OLAP, Proceedings of the Thirteenth International Conference on Data Engineering, p.208-219, April 07-11, 1997
• GM93: 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
• Gup97: Himanshu Gupta, Selection of Views to Materialize in a Data Warehouse, Proceedings of the 6th International Conference on Database Theory, p.98-112, January 08-10, 1997
• PS88: Jooseok Park , Arie Segev, Using Common Subexpressions to Optimize Multiple Queries, Proceedings of the Fourth International Conference on Data Engineering, p.311-319, February 01-05, 1988
• Rou82: Nicholas Roussopoulos, View indexing in relational databases, ACM Transactions on Database Systems (TODS), v.7 n.2, p.258-290, June 1982 [doi>10.1145/319702.319729]
• RR98: Jun Rao , Kenneth A. Ross, Reusing invariants: a new strategy for correlated queries, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.37-48, June 01-04, 1998, Seattle, Washington, United States
• RSS96: Kenneth A. Ross , Divesh Srivastava , S. Sudarshan, Materialized view maintenance and integrity constraint checking: trading space for time, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.447-458, June 04-06, 1996, Montreal, Quebec, Canada
• RSSB98: Prasan Roy, S. Seshadri, S. Sudarshan, and Siddhesh Bhobe. Efficient and extensible algorithms for multi query optimization. Technical report, Indian Institute of Technology, Bombay, October Nov 1998.
• Sel88: Timos K. Sellis, Multiple-query optimization, ACM Transactions on Database Systems (TODS), v.13 n.1, p.23-52, March 1988 [doi>10.1145/42201.42203]
• SHT+99: Jayavel Shanmugasundaram , Kristin Tufte , Chun Zhang , Gang He , David J. DeWitt , Jeffrey F. Naughton, Relational Databases for Querying XML Documents: Limitations and Opportunities, Proceedings of the 25th International Conference on Very Large Data Bases, p.302-314, September 07-10, 1999
• SPL96: Praveen Seshadri , Hamid Pirahesh , T. Y. Cliff Leung, Complex Query Decorrelation, Proceedings of the Twelfth International Conference on Data Engineering, p.450-458, February 26-March 01, 1996
• SSN94: Kyuseok Shim , Timos Sellis , Dana Nau, Improvements on a heuristic algorithm for multiple-query optimization, Data & Knowledge Engineering, v.12 n.2, p.197-222, March 1994 [doi>10.1016/0169-023X(94)90014-0]
• SV98: Subbu N. Subramanian , Shivakumar Venkataraman, Cost-based optimization of decision support queries using transient-views, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.319-330, June 01-04, 1998, Seattle, Washington, United States
• YL87: H. Z. Yang , Per-Åke Larson, Query Transformation for PSJ-Queries, Proceedings of the 13th International Conference on Very Large Data Bases, p.245-254, September 01-04, 1987
• ZDNS98: Yihong Zhao , Prasad M. Deshpande , Jeffrey F. Naughton , Amit Shukla, Simultaneous optimization and evaluation of multiple dimensional queries, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.271-282, June 01-04, 1998, Seattle, Washington, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

General Terms:
Algorithms, Design, Languages