Exploiting Uniqueness in Query Optimization.

G. N. Paulley, Per-Åke Larson: Exploiting Uniqueness in Query Optimization. ICDE 1994: 68-79
  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,}


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 ... BibTeX

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 BibTeX


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

Referenced by

  1. 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
  2. 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
  3. Michael H. Böhlen, Richard T. Snodgrass, Michael D. Soo: Coalescing in Temporal Databases. VLDB 1996: 180-191
  4. David E. Simmen, Eugene J. Shekita, Timothy Malkemus: Fundamental Techniques for Order Optimization. SIGMOD Conference 1996: 57-67
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ICDE Proceedings: Copyright © by IEEE,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:18:12 2009