Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database.

@inproceedings{DBLP:conf/vldb/ChengGKLLQS99,
  author    = {Qi Cheng and
               Jarek Gryz and
               Fred Koo and
               T. Y. Cliff Leung and
               Linqi Liu and
               Xiaoyan Qian and
               K. Bernhard Schiefer},
  editor    = {Malcolm P. Atkinson and
               Maria E. Orlowska and
               Patrick Valduriez and
               Stanley B. Zdonik and
               Michael L. Brodie},
  title     = {Implementation of Two Semantic Query Optimization Techniques
               in DB2 Universal Database},
  booktitle = {VLDB'99, Proceedings of 25th International Conference on Very
               Large Data Bases, September 7-10, 1999, Edinburgh, Scotland,
               UK},
  publisher = {Morgan Kaufmann},
  year      = {1999},
  isbn      = {1-55860-615-7},
  pages     = {687-698},
  ee        = {db/conf/vldb/ChengGKLLQS99.html},
  crossref  = {DBLP:conf/vldb/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In the early 1980's, researchers recognized that semantic information stored in databases as integrity constraints could be used for Query optimization. A new set of techniques called semantic query optimization (SQO) was developed. Some of the ideas developed for SQO have been used commercically, but to the best of our knowledge, no extensive implementations of SQO exist today.

In this paper, we describe an implementation to two SQO techniques, Predicate Introduction and Join Elimination, in DB2 Universal Database. We present the implemented algorithms and performance results using the TPCS and APB-1 OLAP benchmarks. Our experiments show that SQO can lead to dramatic query performance improvements. A crucial aspect of our implementation of SQO is the fact that it does not rely on complex integrity constraints (as many previous SQO techniques did); we use only referential integrity constraints and check constraints.

Copyright © 1999 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

References

[1]

Upen S. Chakravarthy, John Grant, Jack Minker: Logic-Based Approach to Semantic Query Optimization. ACM Trans. Database Syst. 15(2): 162-207(1990) BibTeX

[2]

Surajit Chaudhuri, Kyuseok Shim: Including Group-By in Query Optimization. VLDB 1994: 354-366 BibTeX

[3]

...

[4]

...

[5]

...

[6]

Laura M. Haas, Walter Chang, Guy M. Lohman, John McPherson, Paul F. Wilms, George Lapis, Bruce G. Lindsay, Hamid Pirahesh, Michael J. Carey, Eugene J. Shekita: Starburst Mid-Flight: As the Dust Clears. IEEE Trans. Knowl. Data Eng. 2(1): 143-160(1990) BibTeX

[7]

Michael Hammer, Stanley B. Zdonik: Knowledge-Based Query Processing. VLDB 1980: 137-147 BibTeX

[8]

Matthias Jarke, James Clifford, Yannis Vassiliou: An Optimizing Prolog Front-End to a Relational Query System. SIGMOD Conference 1984: 296-306 BibTeX

[9]

Jonathan J. King: QUIST: A System for Semantic Query Optimization in Relational Databases. VLDB 1981: 510-517 BibTeX

[10]

Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv: Query Optimization by Predicate Move-Around. VLDB 1994: 96-107 BibTeX

[11]

Inderpal Singh Mumick, Hamid Pirahesh: Implementation of Magic-sets in a Relational Database System. SIGMOD Conference 1994: 103-114 BibTeX

[12]

G. N. Paulley, Per-Åke Larson: Exploiting Uniqueness in Query Optimization. ICDE 1994: 68-79 BibTeX

[13]

Hamid Pirahesh, Joseph M. Hellerstein, Waqar Hasan: Extensible/Rule Based Query Rewrite Optimization in Starburst. SIGMOD Conference 1992: 39-48 BibTeX

[14]

Hamid Pirahesh, T. Y. Cliff Leung, Waqar Hasan: A Rule Engine for Query Transformation in Starburst and IBM DB2 C/S DBMS. ICDE 1997: 391-400 BibTeX

[15]

Praveen Seshadri, Joseph M. Hellerstein, Hamid Pirahesh, T. Y. Cliff Leung, Raghu Ramakrishnan, Divesh Srivastava, Peter J. Stuckey, S. Sudarshan: Cost-Based Optimization for Magic: Algebra and Implementation. SIGMOD Conference 1996: 435-446 BibTeX

[16]

Shashi Shekhar, Jaideep Srivastava, Soumitra Dutta: A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization. VLDB 1988: 457-467 BibTeX

[17]

Sreekumar T. Shenoy, Z. Meral Özsoyoglu: Design and Implementation of a Semantic Query Optimizer. IEEE Trans. Knowl. Data Eng. 1(3): 344-361(1989) BibTeX

[18]

David E. Simmen, Eugene J. Shekita, Timothy Malkemus: Fundamental Techniques for Order Optimization. SIGMOD Conference 1996: 57-67 BibTeX

[19]

Transaction Processing Performance Council. http://www.tpc.org BibTeX

Referenced by

1. Jeff Edmonds, Jarek Gryz, Dongming Liang, Renée J. Miller: Mining for Empty Rectangles in Large Data Sets. ICDT 2001: 174-188
2. Richard T. Snodgrass: Review - Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database. ACM SIGMOD Digital Review 2: (2000)
3. Lucian Popa, Alin Deutsch, Arnaud Sahuguet, Val Tannen: A Chase Too Far? SIGMOD Conference 2000: 273-284