Reusing Invariants: A New Strategy for Correlated Queries.
Jun Rao, Kenneth A. Ross:
Reusing Invariants: A New Strategy for Correlated Queries.
SIGMOD Conference 1998: 37-48@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-995-5},
pages = {37-48},
ee = {http://doi.acm.org/10.1145/276304.276309, db/conf/sigmod/RaoR98.html},
crossref = {DBLP:conf/sigmod/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
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.
Copyright © 1998 by the ACM,
Inc., used by permission. Permission to make
digital or hard copies is granted provided that
copies are not made or distributed for profit or
direct commercial advantage, and that copies show
this notice on the first page or initial screen of
a display along with the full citation.
CDROM Version: Load the CDROM "DiSC, Volume 1 Number 1" and ...
Online Version (ACM WWW Account required): Full Text in PDF Format
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
BibTeX
Printed Edition
Laura M. Haas, Ashutosh Tiwary (Eds.):
SIGMOD 1998, Proceedings ACM SIGMOD International Conference on Management of Data, June 2-4, 1998, Seattle, Washington, USA.
ACM Press 1998, ISBN 0-89791-995-5 BibTeX
,
SIGMOD Record 27(2),
June 1998
Contents
[Abstract]
[Full Text (Postscript)]
References
- [Bel96]
- ...
- [CD85]
- Hong-Tai Chou, David J. DeWitt:
An Evaluation of Buffer Management Strategies for Relational Database Systems.
VLDB 1985: 127-141 BibTeX
- [Cha97]
- ...
- [CR97]
- Damianos Chatziantoniou, Kenneth A. Ross:
Groupwise Processing of Relational Queries.
VLDB 1997: 476-485 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
- [Gra94]
- Goetz Graefe:
Volcano - An Extensible and Parallel Query Evaluation System.
IEEE Trans. Knowl. Data Eng. 6(1): 120-135(1994) 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
- [HHW97]
- Joseph M. Hellerstein, Peter J. Haas, Helen J. Wang:
Online Aggregation.
SIGMOD Conference 1997: 171-182 BibTeX
- [HN96]
- Joseph M. Hellerstein, Jeffrey F. Naughton:
Query Execution Techniques for Caching Expensive Methods.
SIGMOD Conference 1996: 423-434 BibTeX
- [JM96]
- Roberto J. Bayardo Jr., Daniel P. Miranker:
Processing Queries for First Few Answers.
CIKM 1996: 45-52 BibTeX
- [Kim82]
- Won Kim:
On Optimizing an SQL-like Nested Query.
ACM Trans. Database Syst. 7(3): 443-469(1982) BibTeX
- [Lea96]
- ...
- [Mic68]
- ...
- [OL90]
- Kiyoshi Ono, Guy M. Lohman:
Measuring the Complexity of Join Enumeration in Query Optimization.
VLDB 1990: 314-325 BibTeX
- [OQ97]
- Patrick E. O'Neil, Dallan Quass:
Improved Query Performance with Variant Indexes.
SIGMOD Conference 1997: 38-49 BibTeX
- [Pau97]
- ...
- [PHH92]
- Hamid Pirahesh, Joseph M. Hellerstein, Waqar Hasan:
Extensible/Rule Based Query Rewrite Optimization in Starburst.
SIGMOD Conference 1992: 39-48 BibTeX
- [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 BibTeX
- [Sel88]
- Timos K. Sellis:
Multiple-Query Optimization.
ACM Trans. Database Syst. 13(1): 23-52(1988) BibTeX
- [SG90]
- Timos K. Sellis, Subrata Ghosh:
On the Multiple-Query Optimization Problem.
IEEE Trans. Knowl. Data Eng. 2(2): 262-266(1990) BibTeX
- [SPL96]
- Praveen Seshadri, Hamid Pirahesh, T. Y. Cliff Leung:
Complex Query Decorrelation.
ICDE 1996: 450-458 BibTeX
- [SSM96]
- David E. Simmen, Eugene J. Shekita, Timothy Malkemus:
Fundamental Techniques for Order Optimization.
SIGMOD Conference 1996: 57-67 BibTeX
- [Syb97a]
- ...
- [Syb97b]
- ...
- [TPC95]
- ...
- [YL95]
- Weipeng P. Yan, Per-Åke Larson:
Eager Aggregation and Lazy Aggregation.
VLDB 1995: 345-357 BibTeX
Referenced by
- Prasan Roy, S. Seshadri, S. Sudarshan, Siddhesh Bhobe:
Efficient and Extensible Algorithms for Multi Query Optimization.
SIGMOD Conference 2000: 249-260
- Daniela Florescu, Alon Y. Levy, Dan Suciu, Khaled Yagoub:
Optimization of Run-time Management of Data Intensive Web-sites.
VLDB 1999: 627-638
- Shih-Fu Chang, Luis Gravano, Gail E. Kaiser, Kenneth A. Ross, Salvatore J. Stolfo:
Database Research at Columbia University.
SIGMOD Record 27(3): 75-80(1998)
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
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:40:41 2009