Query optimization using restructured views

ABSTRACT

We study optimization of relational queries using materialized views, where views may be regular or restructured. In a restructured view, some data from the base table(s) are represented as metadata - that is, schema information, such as table and attribute names - or vice versa.Using restructured views in query optimization opens up a new spectrum of views that were not previously available, and can result in significant additional savings in query-evaluation costs. These savings can be obtained due to a significantly larger set of views to choose from, and may involve reduced table sizes, elimination of self-joins, clustering produced by restructuring, and horizontal partitioning.In this paper we propose a general query-optimization framework that treats regular and restructured views in a uniform manner and is applicable to SQL select-project-join queries and views with or without aggregation. Within the framework we provide (1) algorithms to determine when a view (regular or restructured) is usable in answering a query, and (2) algorithms to rewrite a query using usable views.Semantic information, such as knowledge of the key of a view, can be used to further optimize a rewritten query. Within our general query-optimization framework, we develop techniques for determining the key of a (regular or restructured) view, and show how this information can be used to further optimize a rewritten query. It is straightforward to integrate all our algorithms and techniques into standard query-optimization algorithms.

REFERENCES

• 1: F. Afrati and R. Chirkova. Selecting and using views to compute aggregate queries. In Proc. ICDT, 2005.
• 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: Randall G. Bello , Karl Dias , Alan Downing , James J. Feenan, Jr. , James L. Finnerty , William D. Norcott , Harry Sun , Andrew Witkowski , Mohamed Ziauddin, Materialized Views in Oracle, Proceedings of the 24rd International Conference on Very Large Data Bases, p.659-664, August 24-27, 1998
• 4: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 5: Surajit Chaudhuri , Umeshwar Dayal, An overview of data warehousing and OLAP technology, ACM SIGMOD Record, v.26 n.1, p.65-74, March 1997 [doi>10.1145/248603.248616]
• 6: Surajit Chaudhuri , Umeshwar Dayal, An overview of data warehousing and OLAP technology, ACM SIGMOD Record, v.26 n.1, p.65-74, March 1997 [doi>10.1145/248603.248616]
• 7: 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
• 8: Sara Cohen , Werner Nutt , Alexander Serebrenik, Rewriting aggregate queries using views, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.155-166, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303992]
• 9: Conor Cunningham, Goetz Graefe, and César A. Galindo-Legaria. PIVOT and UNPIVOT: Optimization and execution strategies in an RDBMS. In vldb, pages 998--1009, 2004.
• 10: Keir B. Davis , Fereidoon Sadri, Optimization of SchemaSQL Queries, Proceedings of the International Database Engineering & Applications Symposium, p.111-116, July 16-18, 2001
• 11: David DeHaan , Per-Ake Larson , Jingren Zhou, Stacked indexed views in microsoft SQL server, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066179]
• 12: 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
• 13: Ashish Gupta , Venky Harinarayan , Dallan Quass, Aggregate-Query Processing in Data Warehousing Environments, Proceedings of the 21th International Conference on Very Large Data Bases, p.358-369, September 11-15, 1995
• 14: Marc Gyssens , Laks V. S. Lakshmanan , Iyer N. Subramanian, Tables as a paradigm for querying and restructuring (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.93-103, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237688]
• 15: Alon Y. Halevy, Answering queries using views: A survey, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.270-294, December 2001 [doi>10.1007/s007780100054]
• 16: Andreas Koeller , Elke A. Rundensteiner, Incremental Maintenance of Schema-Restructuring Views, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.354-371, March 25-27, 2002
• 17: Andreas Koeller , Elke A. Rundensteiner, Incremental Maintenance of Schema-Restructuring Views in SchemaSQL, IEEE Transactions on Knowledge and Data Engineering, v.16 n.9, p.1096-1111, September 2004 [doi>10.1109/TKDE.2004.42]
• 18: Ravi Krishnamurthy , Witold Litwin , William Kent, Language features for interoperability of databases with schematic discrepancies, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.40-49, May 29-31, 1991, Denver, Colorado, United States
• 19: Laks V. S. Lakshmanan, Fereidoon Sadri, and Iyer N. Subramanian. On the logical foundations of schema integration and evolution in heterogeneous database systems. In dood, pages 81--100, 1993.
• 20: Laks V. S. Lakshmanan , Fereidoon Sadri , Iyer N. Subramanian, SchemaSQL - A Language for Interoperability in Relational Multi-Database Systems, Proceedings of the 22th International Conference on Very Large Data Bases, p.239-250, September 03-06, 1996
• 21: Laks V. S. Lakshmanan, Fereidoon Sadri, and Iyer N. Subramanian. Logic and algebraic languages for interoperability in multidatabase systems. jlp, 33(2):101--149, November 1997.
• 22: Laks V. S. Lakshmanan , Fereidoon Sadri , Subbu N. Subramanian, On Efficiently Implementing SchemaSQL on an SQL Database System, Proceedings of the 25th International Conference on Very Large Data Bases, p.471-482, September 07-10, 1999
• 23: Laks V. S. Lakshmanan , Fereidoon Sadri , Subbu N. Subramanian, SchemaSQL: An extension to SQL for multidatabase interoperability, ACM Transactions on Database Systems (TODS), v.26 n.4, p.476-519, December 2001 [doi>10.1145/503099.503102]
• 24: Werner Nutt , Yehoshus Sagiv , Sara Shurin, Deciding equivalences among aggregate queries, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.214-223, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275512]
• 25: Stephen P. Slocum. Optimizing SQL and SchemaSQL queries by restructuring. Master's thesis, Department of Mathematical Sciences, University of North Carolina at Greensboro, April 2001.
• 26: Divesh Srivastava , Shaul Dar , H. V. Jagadish , Alon Y. Levy, Answering Queries with Aggregation Using Views, Proceedings of the 22th International Conference on Very Large Data Bases, p.318-329, September 03-06, 1996
• 27: Subbu N. Subramanian and Shivakumar Venkataraman. Query optimization using restructuring views, 1998. IBM Internal Report.
• 28: Transaction processing performance council: TPC benchmarks. http://www.tpc.org.
• 29: Markos Zaharioudakis , Roberta Cochrane , George Lapis , Hamid Pirahesh , Monica Urata, Answering complex SQL queries using automatic summary tables, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.105-116, May 15-18, 2000, Dallas, Texas, United States

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
materialized views, query optimization, restructured views