Efficient and Extensible Algorithms for Multi Query Optimization Prasan Roy, S. Seshadri, S. Sudarshan, and Siddhesh Bhobe   View Paper (PDF)   Return to Research Sessions 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. Multi-query 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 Note: References link to DBLP on the Web. [CKPS95] Surajit Chaudhuri , Ravi Krishnamurthy , Spyros Potamianos , Kyuseok Shim : Optimizing Queries with Materialized Views. ICDE 1995 : 190-200 [CR94] Chung-Min Chen , Nick Roussopoulos : The Implementation and Performance Evaluation of the ADMS Query Optimizer: Integrating Query Result Caching and Matching. EDBT 1994 : 323-336 [Fin82] Sheldon J. Finkelstein : Common Subexpression Analysis in Database Applications. SIGMOD Conference 1982 : 235-245 [GHRU97] Himanshu Gupta , Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman : Index Selection for OLAP. ICDE 1997 : 208-219 [GM93] Goetz Graefe , William J. McKenna : The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993 : 209-218 [Gup97] Himanshu Gupta : Selection of Views to Materialize in a Data Warehouse. ICDT 1997 : 98-112 [PS88] Jooseok Park , Arie Segev : Using Common Subexpressions to Optimize Multiple Queries. ICDE 1988 : 311-319 [Rou82] Nick Roussopoulos : View Indexing in Relational Databases. TODS 7(2) : 258-290(1982) [RR98] Jun Rao , Kenneth A. Ross : Reusing Invariants: A New Strategy for Correlated Queries. SIGMOD Conference 1998 : 37-48 [RSS96] Kenneth A. Ross , Divesh Srivastava , S. Sudarshan : Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time. SIGMOD Conf. 1996 : 447-458 [RSSB98] ... [Sel88] Timos K. Sellis : Multiple-Query Optimization. TODS 13(1) : 23-52(1988) [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. VLDB 1999 : 302-314 [SPL96] Praveen Seshadri , Hamid Pirahesh , T. Y. Cliff Leung : Complex Query Decorrelation. ICDE 1996 : 450-458 [SSN94] Kyuseok Shim , Timos K. Sellis , Dana S. Nau : Improvements on a Heuristic Algorithm for Multiple-Query Optimization. DKE 12(2) : 197-222(1994) [SV98] Subbu N. Subramanian , Shivakumar Venkataraman : Cost-Based Optimization of Decision Support Queries Using Transient Views. SIGMOD Conference 1998 : 319-330 [YL87] H. Z. Yang , Per-Åke Larson : Query Transformation for PSJ-Queries. VLDB 1987 : 245-254 [ZDNS98] Yihong Zhao , Prasad Deshpande , Jeffrey F. Naughton , Amit Shukla : Simultaneous Optimization and Evaluation of Multiple Dimensional Queries. SIGMOD Conference 1998 : 271-282 BIBTEX @inproceedings{DBLP:conf/sigmod/RoySSB00,   author    = {Prasan Roy and                 S. Seshadri and                 S. Sudarshan and                 Siddhesh Bhobe},    editor    = {Weidong Chen and                 Jeffrey F. Naughton and                 Philip A. Bernstein},    title     = {Efficient and Extensible Algorithms for Multi Query Optimization},    booktitle = {Proceedings of the 2000 ACM SIGMOD International Conference on                 Management of Data, May 16-18, 2000, Dallas, Texas, USA},    journal   = {SIGMOD Record},    publisher = {ACM},    volume    = {29},    number    = {2},    year      = {2000},    isbn      = {1-58113-218-2},    pages     = {249-260},    crossref  = {DBLP:conf/sigmod/2000},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.