On the Propagation of Errors in the Size of Join Results.

Yannis E. Ioannidis, Stavros Christodoulakis: On the Propagation of Errors in the Size of Join Results. SIGMOD Conference 1991: 268-277

@inproceedings{DBLP:conf/sigmod/IoannidisC91,
  author    = {Yannis E. Ioannidis and
               Stavros Christodoulakis},
  editor    = {James Clifford and
               Roger King},
  title     = {On the Propagation of Errors in the Size of Join Results},
  booktitle = {Proceedings of the 1991 ACM SIGMOD International Conference on
               Management of Data, Denver, Colorado, May 29-31, 1991},
  publisher = {ACM Press},
  year      = {1991},
  pages     = {268-277},
  ee        = {http://doi.acm.org/10.1145/115790.115835, db/conf/sigmod/IoannidisC91.html},
  crossref  = {DBLP:conf/sigmod/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Query optimizers of current relational database systems use several statistics maintained by the system on the contents of the database to decide on the most efficient access plan for a given query. These statistics contain errors that transitively affect many estimates derived by the optimizer. We present a formal framework based on which the principles of this error propagation can be studied. Within this framework, we obtain several analytic results on how the error propagates in general, as well as in the extreme and average cases. We also provide results on guarantees that the database system can make based on the statistics that it maintains. Finally, we discuss some promising approaches to controlling the error propagation and derive several interesting properties of them.

Copyright © 1991 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.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/smod7592 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

James Clifford, Roger King (Eds.): Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data, Denver, Colorado, May 29-31, 1991. ACM Press 1991

, SIGMOD Record 20(2), June 1991
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 914 KB]

References

[Chr84]: Stavros Christodoulakis: Implications of Certain Assumptions in Database Performance Evaluation. ACM Trans. Database Syst. 9(2): 163-186(1984)
[Chr89]: ...
[IC91]: ...
[Kaz64]: ...
[MCS88]: Michael V. Mannino, Paicheng Chu, Thomas Sager: Statistical Profile Estimation in Database Systems. ACM Comput. Surv. 20(3): 191-221(1988)
[ML86a]: Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Distributed Queries. VLDB 1986: 149-159
[ML86b]: Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Local Queries. SIGMOD Conference 1986: 84-95
[MO79]: ...
[S+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
[Sel89]: ...
[Zip49]: George Kingsley Zipf: Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology. Addison-Wesley 1949