ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Query Optimization by Predicate Move-Around.

Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv: Query Optimization by Predicate Move-Around. VLDB 1994: 96-107
@inproceedings{DBLP:conf/vldb/LevyMS94,
  author    = {Alon Y. Levy and
               Inderpal Singh Mumick and
               Yehoshua Sagiv},
  editor    = {Jorge B. Bocca and
               Matthias Jarke and
               Carlo Zaniolo},
  title     = {Query Optimization by Predicate Move-Around},
  booktitle = {VLDB'94, Proceedings of 20th International Conference on Very
               Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile},
  publisher = {Morgan Kaufmann},
  year      = {1994},
  isbn      = {1-55860-153-8},
  pages     = {96-107},
  ee        = {db/conf/vldb/vldb94-96.html},
  crossref  = {DBLP:conf/vldb/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

A new type of optimization, called Predicate Move-around, is introduced. It is shown how this optimization considerably improves the efficiency of evaluating SQL queries that have query graphs with a large number of query blocks (which is a typical situation when queries are defined in terms of multiple views and subqueries). Predicate move-around works by moving predicates across query blocks (in the query graph) that cannot be merged into one block. Predicate move-around is a generalization of and has many advantages over the traditional predicate pushdown. One key advantage arises from the fact that predicate move-around precedes pushdown by pulling predicates up the query graph. As a result, predicates that appear in the query in one part of the graph can be moved around the graph and applied also in other parts of graph. Moreover, predicate move-around optimization can move a wider class of predicates in a wider class of queries as compared to the standard predicate-pushdown techniques. In addition to the usual comparison and arithmetic predicates, other predicates that can be moved around are the EXISTS and NOT EXISTS clauses, the EXCEPT clause, and functional dependencies. The proposed optimization can also move predicates through aggregation. Moreover, the method can also infer new predicates when existing predicates are moved through aggregation or when certain functional dependencies are known to hold. Finally, the predicate move-around algorithm is easy to implement on top of existing query optimizers.

Copyright © 1994 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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Jorge B. Bocca, Matthias Jarke, Carlo Zaniolo (Eds.): VLDB'94, Proceedings of 20th International Conference on Very Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile. Morgan Kaufmann 1994, ISBN 1-55860-153-8
Contents BibTeX

References

[BMSU86]
François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 BibTeX
[BR87]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 BibTeX
[Day87]
Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208 BibTeX
[GW87]
Richard A. Ganski, Harry K. T. Wong: Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987: 23-33 BibTeX
[Hel94]
Joseph M. Hellerstein: Practical Predicate Placement. SIGMOD Conference 1994: 325-335 BibTeX
[HS93]
Joseph M. Hellerstein, Michael Stonebraker: Predicate Migration: Optimizing Queries with Expensive Predicates. SIGMOD Conference 1993: 267-276 BibTeX
[ISO93]
...
[Kim82]
Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) BibTeX
[LMSS93]
Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv, Oded Shmueli: Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions. PODS 1993: 109-122 BibTeX
[LS92]
Alon Y. Levy, Yehoshua Sagiv: Constraints and Redundancy in Datalog. PODS 1992: 67-80 BibTeX
[MFPR90a]
Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic is Relevant. SIGMOD Conference 1990: 247-258 BibTeX
[MFPR90b]
Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic Conditions. PODS 1990: 314-330 BibTeX
[Mur92]
M. Muralikrishna: Improved Unnesting Algorithms for Join Aggregate SQL Queries. VLDB 1992: 91-102 BibTeX
[PHH92]
Hamid Pirahesh, Joseph M. Hellerstein, Waqar Hasan: Extensible/Rule Based Query Rewrite Optimization in Starburst. SIGMOD Conference 1992: 39-48 BibTeX
[SR92]
Divesh Srivastava, Raghu Ramakrishnan: Pushing Constraint Selections. PODS 1992: 301-315 BibTeX
[SRSS94]
Kenneth A. Ross, Divesh Srivastava, Peter J. Stuckey, S. Sudarshan: Foundations of Aggregation Constraints. PPCP 1994: 193-204 BibTeX
[SR91]
S. Sudarshan, Raghu Ramakrishnan: Aggregation and Relevance in Deductive Databases. VLDB 1991: 501-511 BibTeX
[Ull89-1]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[Ull89-2]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX

Referenced by

  1. Divesh Srivastava: Review - Query Optimization by Predicate Move-Around. ACM SIGMOD Digital Review 2: (2000)
  2. 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. VLDB 1999: 687-698
  3. Joseph M. Hellerstein: Optimization Techniques for Queries with Expensive Methods. ACM Trans. Database Syst. 23(2): 113-157(1998)
  4. Mitch Cherniack, Stanley B. Zdonik: Inferring Function Semantics to Optimize Queries. VLDB 1998: 239-250
  5. Surajit Chaudhuri: An Overview of Query Optimization in Relational Systems. PODS 1998: 34-43
  6. Venky Harinarayan: Issues in Interactive Aggregation. IEEE Data Eng. Bull. 20(1): 12-18(1997)
  7. Alon Y. Levy, Dan Suciu: Deciding Containment for Queries with Complex Objects. PODS 1997: 20-31
  8. 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
  9. Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic Conditions. ACM Trans. Database Syst. 21(1): 107-155(1996)
  10. Divesh Srivastava, Shaul Dar, H. V. Jagadish, Alon Y. Levy: Answering Queries with Aggregation Using Views. VLDB 1996: 318-329
  11. William J. McKenna, Louis Burger, Chi Hoang, Melissa Truong: EROC: A Toolkit for Building NEATO Query Optimizers. VLDB 1996: 111-121
  12. Damianos Chatziantoniou, Kenneth A. Ross: Querying Multiple Features of Groups in Relational Databases. VLDB 1996: 295-306
  13. Gautam Bhargava, Piyush Goel, Balakrishna R. Iyer: Efficient Processing of Outer Joins and Aggregate Functions. ICDE 1996: 441-449
  14. Alon Y. Levy, Inderpal Singh Mumick: Reasoning with Aggregation Constraints. EDBT 1996: 514-534
  15. Surajit Chaudhuri, Kyuseok Shim: Optimizing Queries with Aggregate Views. EDBT 1996: 167-182
  16. Michael Steinbrunn, Klaus Peithner, Guido Moerkotte, Alfons Kemper: Bypassing Joins in Disjunctive Queries. VLDB 1995: 228-238
  17. Ashish Gupta, Inderpal Singh Mumick, Kenneth A. Ross: Adapting Materialized Views after Redefinitions. SIGMOD Conference 1995: 211-222
  18. Alon Y. Levy, Yehoshua Sagiv: Semantic Query Optimization in Datalog Programs. PODS 1995: 163-173
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
 ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:46:03 2009