 |
|
|
Reusing Invariants: A New Strategy for Correlated Queries |
Correlated queries are very common and important in decision support systems. Traditional nested iteration evaluation methods for such queries can be very time consuming. When they apply, query rewriting techniques have been shown to be much more efficient. But query rewriting is not always possible. When query rewriting does not apply, can we do something better than the traditional nested iteration methods? In this paper, we propose a new invariant technique to evaluate correlated queries efficiently. The basic idea is to recognize the part of the subquery that is not related to the outer references and cache the result of that part after its first execution. Later, we can reuse the result and combine it with the result of the rest of the subquery that is changing for each iteration. Our technique applies to arbitrary correlated subqueries.
This paper introduces algorithms to recognize the invariant part of a data flow tree, and to restructure the evaluation plan to reuse the stored intermediate result. We also propose an efficient method to teach an existing join optimizer to understand the invariant feature and thus allow it to be able to generate better join plans in the new context. Some other related optimization techniques are also discussed. The proposed techniques were implemented within three months on an existing real commercial database system.
We also experimentally evaluate our proposed technique. Our evaluation indicates that, when query rewriting is not possible, the invariant technique is significantly better than the traditional nested iteration method. Even when query rewriting applies, the invariant technique is sometimes better than the query rewriting technique. Our conclusion is that the invariant technique should be considered as one of the alternatives in evaluating correlated queries since it fills the gap left by rewriting techniques. |
References, where available, link to the DBLP on the World Wide Web.
[Bel96]...
[CD85]Hong-Tai Chou, David J. DeWitt:
An Evaluation of Buffer Management Strategies for Relational Database Systems.
VLDB 1985: 127-141[Cha97]...
[CR97]Damianos Chatziantoniou, Kenneth A. Ross:
Groupwise Processing of Relational Queries.
VLDB 1997: 476-485[Day87]Umeshwar Dayal:
Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers.
VLDB 1987: 197-208[Gra94]Goetz Graefe:
Volcano - An Extensible and Parallel Query Evaluation System.
TKDE 6(1): 120-135(1994)[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[HHW97]Joseph M. Hellerstein, Peter J. Haas, Helen Wang:
Online Aggregation.
SIGMOD Conference 1997: 171-182[HN96]Joseph M. Hellerstein, Jeffrey F. Naughton:
Query Execution Techniques for Caching Expensive Methods.
SIGMOD Conf. 1996: 423-434[JM96]Roberto J. Bayardo Jr., Daniel P. Miranker:
Processing Queries for First Few Answers.
CIKM 1996: 45-52[Kim82]Won Kim:
On Optimizing an SQL-like Nested Query.
TODS 7(3): 443-469(1982)[Lea96]...
[Mic68]...
[OL90]Kiyoshi Ono, Guy M. Lohman:
Measuring the Complexity of Join Enumeration in Query Optimization.
VLDB 1990: 314-325[OQ97]Patrick E. O'Neil, Dallan Quass:
Improved Query Performance with Variant Indexes.
SIGMOD Conference 1997: 38-49[Pau97]...
[PHH92]Hamid Pirahesh, Joseph M. Hellerstein, Waqar Hasan:
Extensible/Rule Based Query Rewrite Optimization in Starburst.
SIGMOD Conference 1992: 39-48[SAC+79]Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price:
Access Path Selection in a Relational Database Management System.
SIGMOD Conference 1979: 23-34[Sel88]Timos K. Sellis:
Multiple-Query Optimization.
TODS 13(1): 23-52(1988)[SG90]Timos K. Sellis, Subrata Ghosh:
On the Multiple-Query Optimization Problem.
TKDE 2(2): 262-266(1990)[SPL96]Praveen Seshadri, Hamid Pirahesh, T. Y. Cliff Leung:
Complex Query Decorrelation.
ICDE 1996: 450-458[SSM96]David E. Simmen, Eugene J. Shekita, Timothy Malkemus:
Fundamental Techniques for Order Optimization.
SIGMOD Conf. 1996: 57-67[Syb97a]...
[Syb97b]...
[TPC95]...
[YL95]Weipeng P. Yan, Per-Åke Larson:
Eager Aggregation and Lazy Aggregation.
VLDB 1995: 345-357
|
@inproceedings{DBLP:conf/sigmod/RaoR98,
author = {Jun Rao and
Kenneth A. Ross},
editor = {Laura M. Haas and
Ashutosh Tiwary},
title = {Reusing Invariants: A New Strategy for Correlated Queries},
booktitle = {SIGMOD 1998, Proceedings ACM SIGMOD International Conference
on Management of Data, June 2-4, 1998, Seattle, Washington, USA},
publisher = {ACM Press},
year = {1998},
isbn = {0-89791-955-5},
pages = {37-48},
crossref = {DBLP:conf/sigmod/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
