A chase too far?

ABSTRACT

In a previous paper we proposed a novel method for generating alternative query plans that uses chasing (and back-chasing) with logical constraints. The method brings together use of indexes, use of materialized views, semantic optimization and join elimination (minimization). Each of these techniques is known separately to be beneficial to query optimization. The novelty of our approach is in allowing these techniques to interact systematically, eg. non-trivial use of indexes and materialized views may be enabled only by semantic constraints.

We have implemented our method for a variety of schemas and queries. We examine how far we can push the method in term of complexity of both schemas and queries. We propose a technique for reducing the size of the search space by “stratifying” the sets of constraints used in the (back)chase. The experimental results demonstrate that our method is practical (i.e., feasible and worthwhile).

REFERENCES

• 1: Bonnie Baker. Responsible SQL: Creative Solutions for Performance Problems in DB2 for OS/390. DB2 Magazine, 4(2):5&55, Summer 1999. Available at htZp: //ww#. db2mag, corn/summer99199sp_prog, shtml.
• 2: Catriel Beeri , Yoram Kornatzky, Algebraic optimization of object-oriented query languages, Theoretical Computer Science, v.116 n.1, p.59-94, Aug. 2, 1993
• 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: Upen S. Chakravarthy , John Grant , Jack Minker, Logic-based approach to semantic query optimization, ACM Transactions on Database Systems (TODS), v.15 n.2, p.162-207, June 1990 [doi>10.1145/78922.78924]
• 5: 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
• 6: Qi Cheng , Jarek Gryz , Fred Koo , T. Y. Cliff Leung , Linqi Liu , Xiaoyan Qian , K. Bernhard Schiefer, Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database, Proceedings of the 25th International Conference on Very Large Data Bases, p.687-698, September 07-10, 1999
• 7: Mitch Cherniack , Stanley B. Zdonik, Inferring Function Semantics to Optimize Queries, Proceedings of the 24rd International Conference on Very Large Data Bases, p.239-250, August 24-27, 1998
• 8: Sophie Cluet , Claude Delobel, A general framework for the optimization of object-oriented queries, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.383-392, June 02-05, 1992, San Diego, California, United States
• 9: Alin Deutsch , Lucian Popa , Val Tannen, Physical Data Independence, Constraints, and Optimization with Universal Plans, Proceedings of the 25th International Conference on Very Large Data Bases, p.459-470, September 07-10, 1999
• 10: Leonidas Fegaras , David Maier, An Algebraic Framework for Physical OODB Design, Proceedings of the Fifth International Workshop on Database Programming Languages, p.9, September 06-08, 1995
• 11: D. Florescu. Design and implementation of the Flora Object Oriented Query Optimizer. PhD thesis, Universite of Paris 6, 1996.
• 12: D. Florescu, L. Rashid, and P. Valduriez. A methodology for query reformulation in cis using semantic knowledge. International Journal of Cooperative Information Systems, 5(4), 1996.
• 13: John Grant , Jarek Gryz , Jack Minker , Louiqa Raschid, Semantic Query Optimization for Object Databases, Proceedings of the Thirteenth International Conference on Data Engineering, p.444-453, April 07-11, 1997
• 14: Matthias Jarke , Jim Clifford , Yannis Vassiliou, An optimizing prolog front-end to a relational query system, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 15: Alfons Kemper , Guido Moerkotte, Access support in object bases, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.364-374, May 23-26, 1990, Atlantic City, New Jersey, United States
• 16: A. Levy. Answering Queries Using Views: A Survey. Forthcoming.
• 17: Greg Nelson and Derek C. Oppen. Fast decision algorithms ba#ed on union and find. In FOCS, pages 114-119.
• 18: Lucian Popa and Val Tannen. Chase and axioms for PC queries and dependencies. Technical Report MS- CIS-98-34. University of Pennsylvania, 1998. Available online at h#p://www.cis.upenn.edu/- techreports/.
• 19: Lucian Popa , Val Tannen, An Equational Chase for Path-Conjunctive Queries, Constraints, and Views, Proceeding of the 7th International Conference on Database Theory, p.39-57, January 10-12, 1999
• 20: Odysseas G. Tsatalos , Marvin H. Solomon , Yannis E. Ioannidis, The GMAP: a versatile tool for physical data independence, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.2, p.101-118, April 1996 [doi>10.1007/s007780050018]
• 21: Patrick Valduriez, Join indices, ACM Transactions on Database Systems (TODS), v.12 n.2, p.218-246, June 1987 [doi>10.1145/22952.22955]
• 22: 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

INDEX TERMS

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

General Terms:
Design, Languages, Theory