ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Exploiting Uniqueness in Query Optimization.

G. N. Paulley, Per-Åke Larson: Exploiting Uniqueness in Query Optimization. ICDE 1994: 68-79
@inproceedings{DBLP:conf/icde/PaulleyL94,
  author    = {G. N. Paulley and
               Per-{\AA}ke Larson},
  title     = {Exploiting Uniqueness in Query Optimization},
  booktitle = {Proceedings of the Tenth International Conference on Data Engineering,
               February 14-18, 1994, Houston, Texas, USA},
  publisher = {IEEE Computer Society},
  year      = {1994},
  isbn      = {0-8186-5400-7},
  pages     = {68-79},
  ee        = {db/conf/icde/PaulleyL94.html},
  crossref  = {DBLP:conf/icde/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Consider an SQL query that specifies duplicate elimination via a DISTINCT clause. Because duplicate elimination often requires an expensive sort of the query result, it is often worthwhile to identify unnecessary DISTINCT clauses and avoid the sort altogether. We prove a necessary and sufficient condition for deciding if a query requires duplicate elimination. The condition exploits knowledge about keys, table constraints, and query predicates. Because the condition cannot always be tested efficiently, we offer a practical algorithm that tests a simpler, sufficient condition. We consider applications of this condition for various types of queries, and show that we can exploit this condition in both relational and non relational database systems.

Keywords: query optimization, DISTINCT, SQL, duplicate elimination

Copyright © 1994 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.


ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 2 Issue 6, ICDE 1984-1995" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Proceedings of the Tenth International Conference on Data Engineering, February 14-18, 1994, Houston, Texas, USA. IEEE Computer Society 1994, ISBN 0-8186-5400-7
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
Stefano Ceri, Georg Gottlob: Translating SQL Into Relational Algebra: Optimization, Semantics, and Equivalence of SQL Queries. IEEE Trans. Software Eng. 11(4): 324-345(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Stefano Ceri, Jennifer Widom: Deriving Production Rules for Incremental View Maintenance. VLDB 1991: 577-589 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
...
[4]
C. J. Date: An Introduction to Database Systems, Volume I, 5th Edition. Addison-Wesley 1990, ISBN 0-201-52878-9
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
...
[6]
Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Richard A. Ganski, Harry K. T. Wong: Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987: 23-33 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
...
[9]
...
[10]
Werner Kießling: On Semantic Reefs and Efficient Processing of Correlation Queries with Aggregates. VLDB 1985: 241-250 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
...
[13]
Anthony C. Klug: Calculating Constraints on Relational Expressions. ACM Trans. Database Syst. 5(3): 260-290(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
...
[15]
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
...
[17]
M. Muralikrishna: Improved Unnesting Algorithms for Join Aggregate SQL Queries. VLDB 1992: 91-102 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[18]
Mauro Negri, Giuseppe Pelagatti, Licia Sbattella: Formal Semantics of SQL Queries. ACM Trans. Database Syst. 16(3): 513-534(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
Hamid Pirahesh, Joseph M. Hellerstein, Waqar Hasan: Extensible/Rule Based Query Rewrite Optimization in Starburst. SIGMOD Conference 1992: 39-48 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[20]
...
[21]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[22]
Günter von Bültzingsloewen: Translating and Optimizing SQL Queries Having Aggregates. VLDB 1987: 235-243 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[23]
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[24]
Weipeng P. Yan, Per-Åke Larson: Performing Group-By before Join. ICDE 1994: 89-100 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Mon Mar 15 03:39:18 2010 by Michael Ley (ley@uni-trier.de)