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