Physical design refinement: The ‘merge-reduce’ approach

ABSTRACT

Physical database design tools rely on a DBA-provided workload to pick an “optimal” set of indexes and materialized views. Such tools allow either creating a new such configuration or adding new structures to existing ones. However, these tools do not provide adequate support for the incremental and flexible refinement of existing physical structures. Although such refinements are often very valuable for DBAs, a completely manual approach to refinement can lead to infeasible solutions (e.g., excessive use of space). In this article, we focus on the important problem of physical design refinement and propose a transformational architecture that is based upon two novel primitive operations, called merging and reduction. These operators help refine a configuration, treating indexes and materialized views in a unified way, as well as succinctly explain the refinement process to DBAs.

REFERENCES

• 1: Sanjay Agrawal , Surajit Chaudhuri , Lubor Kollar , Arun Marathe , Vivek Narasayya , Manoj Syamala, Database tuning advisor for microsoft SQL server 2005: demo, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066292]
• 2: Sanjay Agrawal , Surajit Chaudhuri , Vivek R. Narasayya, Automated Selection of Materialized Views and Indexes in SQL Databases, Proceedings of the 26th International Conference on Very Large Data Bases, p.496-505, September 10-14, 2000
• 3: Sanjay Agrawal , Eric Chu , Vivek Narasayya, Automatic physical design tuning: workload as a sequence, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142549]
• 4: Gilles Brassard , Paul Bratley, Fundamentals of algorithmics, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 5: Nicolas Bruno , Surajit Chaudhuri, Automatic physical database tuning: a relaxation-based approach, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066184]
• 6: Bruno, N. and Chaudhuri, S. 2006a. Physical design refinement: The “Merge-Reduce” approach. In Proceedings of the International Conference on Extending Database Technology (EDBT).
• 7: Nicolas Bruno , Surajit Chaudhuri, To tune or not to tune?: a lightweight physical design alerter, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 8: Nicolas Bruno , Surajit Chaudhuri, Online autoadmin: (physical design tuning), Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247608]
• 9: Chaitin, G. J., Auslander, M. A., Chandra, A. K., Cocke, J., Hopkins, M. E., and Markstein, P. W. 1981. Register allocation via coloring. In Computer Languages 6, 1, 47--57.
• 10: Surajit Chaudhuri , Ashish Kumar Gupta , Vivek Narasayya, Compressing SQL workloads, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564747]
• 11: Surajit Chaudhuri , Vivek R. Narasayya, An Efficient Cost-Driven Index Selection Tool for Microsoft SQL Server, Proceedings of the 23rd International Conference on Very Large Data Bases, p.146-155, August 25-29, 1997
• 12: Index Merging, Proceedings of the 15th International Conference on Data Engineering, p.296, March 23-26, 1999
• 13: Benoit Dageville , Dinesh Das , Karl Dias , Khaled Yagoub , Mohamed Zait , Mohamed Ziauddin, Automatic SQL tuning in oracle 10g, Proceedings of the Thirtieth international conference on Very large data bases, p.1098-1109, August 31-September 03, 2004, Toronto, Canada
• 14: 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]
• 15: Jonathan Goldstein , Per-Åke Larson, Optimizing queries using materialized views: a practical, scalable solution, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.331-342, May 21-24, 2001, Santa Barbara, California, United States
• 16: Graefe, G. 1995. The Cascades framework for query optimization. Data Eng. Bull. 18, 3.
• 17: Arnd Christian Konig , Shubha U. Nabar, Scalable Exploration of Physical Database Design, Proceedings of the 22nd International Conference on Data Engineering, p.37, April 03-07, 2006 [doi>10.1109/ICDE.2006.133]
• 18: Hoshi Mistry , Prasan Roy , S. Sudarshan , Krithi Ramamritham, Materialized view selection and maintenance using multi-query optimization, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.307-318, May 21-24, 2001, Santa Barbara, California, United States
• 19: Nils J. Nilsson, Problem-Solving Methods in Artificial Intelligence, McGraw-Hill Pub. Co., 1971
• 20: 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
• 21: 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
• 22: Prasan Roy , S. Seshadri , S. Sudarshan , Siddhesh Bhobe, Efficient and extensible algorithms for multi query optimization, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.249-260, May 15-18, 2000, Dallas, Texas, United States
• 23: 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]
• 24: 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]
• 25: Alan Skelley, DB2 Advisor: An Optimizer Smart Enough to Recommend its own Indexes, Proceedings of the 16th International Conference on Data Engineering, p.101, February 28-March 03, 2000
• 26: Daniel C. Zilio , Jun Rao , Sam Lightstone , Guy Lohman , Adam Storm , Christian Garcia-Arellano , Scott Fadden, DB2 design advisor: integrated automatic physical database design, Proceedings of the Thirtieth international conference on Very large data bases, p.1087-1097, August 31-September 03, 2004, Toronto, Canada
• 27: Daniel C. Zilio , Calisto Zuzarte , Guy M. Lohman , Hamid Pirahesh , Jarek Gryz , Eric Alton , Dongming Liang , Gary Valentin, Recommending Materialized Views and Indexes with IBM DB2 Design Advisor, Proceedings of the First International Conference on Autonomic Computing, p.180-188, May 17-18, 2004

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

General Terms:
Algorithms, Design, Performance

Keywords:
Physical database design, physical design refinment, view merging and reduction