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

Estimating Block Transfers and Join Sizes.

Stavros Christodoulakis: Estimating Block Transfers and Join Sizes. SIGMOD Conference 1983: 40-54
@inproceedings{DBLP:conf/sigmod/Christodoulakis83,
  author    = {Stavros Christodoulakis},
  editor    = {David J. DeWitt and
               Georges Gardarin},
  title     = {Estimating Block Transfers and Join Sizes},
  booktitle = {SIGMOD'83, Proceedings of Annual Meeting, San Jose, California,
               May 23-26, 1983},
  publisher = {ACM Press},
  year      = {1983},
  pages     = {40-54},
  ee        = {http://doi.acm.org/10.1145/582192.582204, db/conf/sigmod/Christodoulakis83.html},
  crossref  = {DBLP:conf/sigmod/83},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In this paper we provide estimates of the number of sequential end random block accesses required for retrieving a number of records of a file when the distribution of records in blocks of secondary storage is not uniform. We show how these results apply to estimating sizes of joins and semi-joins. We prove that when the uniformity of placement assumption is not satisfied it often leads to pessimistic estimates of performance. Finally we show a recursive estimation of the probability distribution of the number of blocks containing a given number of records.

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

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

Printed Edition

David J. DeWitt, Georges Gardarin (Eds.): SIGMOD'83, Proceedings of Annual Meeting, San Jose, California, May 23-26, 1983. ACM Press 1983 BibTeX , SIGMOD Record 13(4)
Contents

Online Edition: ACM Digital Library


References

[Aho et al.74]
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX
[Batory81]
...
[Bernstein et al.81]
Philip A. Bernstein, Nathan Goodman, Eugene Wong, Christopher L. Reeve, James B. Rothnie Jr.: Query Processing in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 6(4): 602-625(1981) BibTeX
[Cardenas75]
Alfonso F. Cardenas: Analysis and Performance of Inverted Data Base Structures. Commun. ACM 18(5): 253-263(1975) BibTeX
[Cheung82]
To-Yat Cheung: Estimating Block Accesses and Number of Recorde in File Management. Commun. ACM 25(7): 484-487(1982) BibTeX
[Christodoulakis81]
...
[Christodoulakis82a]
Stavros Christodoulakis: Implications of Certain Assumptions in Database Performance Evaluation. ACM Trans. Database Syst. 9(2): 163-186(1984) BibTeX
[Christodoulakis82b]
Stavros Christodoulakis: Issues in Query Evaluation. IEEE Database Eng. Bull. 5(3): 48-51(1982) BibTeX
[Christodoulakis83]
Stavros Christodoulakis: Estimating record selectivities. Inf. Syst. 8(2): 105-115(1983) BibTeX
[Christodoulakis and Faloutsos82]
...
[Gelenbe and Cardy82]
Erol Gelenbe, Danièle Gardy: The Size of Projections of Relations Satisfying a Functional Dependency. VLDB 1982: 325-333 BibTeX
[Gelenbe and Cardy83]
Erol Gelenbe, Danièle Gardy: On the Size of Projections: I. Inf. Process. Lett. 14(1): 18-21(1982) BibTeX
[Kerschberg et al.80]
...
[Kollias78]
John G. Kollias: An Estimate of Seek Time for Batched Searching of Random or Index Sequential Structured Files. Comput. J. 21(2): 132-133(1978) BibTeX
[Langer and Shum82]
A. M. Langer, Annie W. Shum: The Distribution of Granule Accesses Made by Database Transactions. Commun. ACM 25(11): 831-832(1982) BibTeX
[Marshall and Olkin79]
Albert W. Marshall, Ingram Olkin: Inequalities: Theory of Majorization and Its Application. Academic Press 1979, ISBN 0-12-473750-1
BibTeX
[Potier and Leblank80]
Dominique Potier, Ph. Leblanc: Analysis of Locking Policies in Database Management Systems. Commun. ACM 23(10): 584-593(1980) BibTeX
[Rosenthal81]
Arnon Rosenthal: Note on the Expected Size of a Join. SIGMOD Record 11(4): 19-25(1981) BibTeX
[Ries79]
Daniel R. Ries: The Effects of Concurrency Control on the Performance of a Distributed Data Management System. Berkeley Workshop 1979: 75-112 BibTeX
[Riordan58]
...
[Schneiderman and Goodman76]
Ben Shneiderman, Victor Goodman: Batched Searching of Sequential and Tree Structured Files. ACM Trans. Database Syst. 1(3): 268-275(1976) BibTeX
[Sevcik81]
Kenneth C. Sevcik: Data Base System Performance Prediction Using an Analytical Model (Invited Paper). VLDB 1981: 182-198 BibTeX
[Siler76]
Kenneth F. Siler: A Stochastic Evaluation Model for Database Organization in Data Retrieval Systems. Commun. ACM 19(2): 84-95(1976) BibTeX
[Teorey and Das76]
Toby J. Teorey, K. Sundar Das: Application of an Analytical Model to Evaluate Storage Structures. SIGMOD Conference 1976: 9-19 BibTeX
[Teorey and Oberlander78]
...
[Tsichritzis and Christodoulakis83]
Dennis Tsichritzis, Stavros Christodoulakis: Message Files. ACM Trans. Inf. Syst. 1(1): 88-98(1983) BibTeX
[Yao77a]
S. Bing Yao: An Attribute Based Model for Database Access Cost Analysis. ACM Trans. Database Syst. 2(1): 45-67(1977) BibTeX
[Yao77b]
S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977) BibTeX
[Zahorian et al.83]
John Zahorjan, Barbara J. Bell, Kenneth C. Sevcik: Estimating Block Transfers When Record Access Probabilities are Non-Uniform. Inf. Process. Lett. 16(5): 249-252(1983) BibTeX

Referenced by

  1. A. Prasad Sistla, Ouri Wolfson, Yelena Yesha, Robert H. Sloan: Towards a Theory of Cost Management for Digital Libraries and Electronic Commerce. ACM Trans. Database Syst. 23(4): 411-452(1998)
  2. Banchong Harangsri, John Shepherd, Anne H. H. Ngu: Query Size Estimation Using Machine Learning. DASFAA 1997: 97-106
  3. Yannis E. Ioannidis, Viswanath Poosala: Balancing Histogram Optimality and Practicality for Query Result Size Estimation. SIGMOD Conference 1995: 233-244
  4. Chengwen Liu, I-Ping Chu: Load Balancing in Distributed Query Processing. DASFAA 1995: 256-263
  5. Chung-Min Chen, Nick Roussopoulos: Adaptive Selectivity Estimation Using Query Feedback. SIGMOD Conference 1994: 161-172
  6. Arun N. Swami, K. Bernhard Schiefer: On the Estimation of Join Result Sizes. EDBT 1994: 287-300
  7. Yannis E. Ioannidis, Stavros Christodoulakis: Optimal Histograms for Limiting Worst-Case Error Propagation in the Size of Join Results. ACM Trans. Database Syst. 18(4): 709-748(1993)
  8. Yannis E. Ioannidis: Universality of Serial Histograms. VLDB 1993: 256-267
  9. Wei Sun, Yibei Ling, Naphtali Rishe, Yi Deng: An Instant and Accurate Estimation Method for Joins and Selection in a Retrieval-Intensive Environment. SIGMOD Conference 1993: 79-88
  10. Nabil Kamel, Roger King: Intelligent Database Caching Through the Use of Page-Answers and Page-Traces. ACM Trans. Database Syst. 17(4): 601-646(1992)
  11. Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992)
  12. Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider: Practical Selectivity Estimation through Adaptive Sampling. SIGMOD Conference 1990: 1-11
  13. Richard J. Lipton, Jeffrey F. Naughton: Query Size Estimation by Adaptive Sampling. PODS 1990: 40-46
  14. Saumya K. Debray, Nai-Wei Lin: Static Estimation of Query Sizes in Horn Programs. ICDT 1990: 514-528
  15. Yannis Manolopoulos, John G. Kollias: Performance of a Two-Headed Disk System when Serving Database Queries Under the Scan Policy. ACM Trans. Database Syst. 14(3): 425-442(1989)
  16. Lothar F. Mackert, Guy M. Lohman: Index Scans Using a Finite LRU Buffer: A Validated I/O Model. ACM Trans. Database Syst. 14(3): 401-424(1989)
  17. Richard J. Lipton, Jeffrey F. Naughton: Estimating the Size of Generalized Transitive Closures. VLDB 1989: 165-171
  18. Goetz Graefe, Karen Ward: Dynamic Query Evaluation Plans. SIGMOD Conference 1989: 358-366
  19. David A. Bell, D. H. O. Ling, Sally I. McClean: Pragmatic Estimation of Join Sizes and Attribute Correlations. ICDE 1989: 76-84
  20. Michael V. Mannino, Paicheng Chu, Thomas Sager: Statistical Profile Estimation in Database Systems. ACM Comput. Surv. 20(3): 191-221(1988)
  21. Ming-Chien Shan: Optimal Plan Search in a Rule-Based Query Optimizer. EDBT 1988: 92-112
  22. Jane Fedorowicz: Database Performance Evaluation in an Indexed File Environment. ACM Trans. Database Syst. 12(1): 85-110(1987)
  23. Stavros Christodoulakis: Analysis of Retrieval Performance for Records and Objects Using Optical Disk Technology. ACM Trans. Database Syst. 12(2): 137-169(1987)
  24. Brad T. Vander Zanden, Howard M. Taylor, Dina Bitton: Estimating Block Accessses when Attributes are Correlated. VLDB 1986: 119-127
  25. Clement T. Yu, Leszek Lilien, Keh-Chang Guh, Marjorie Templeton, David Brill, Arbee L. P. Chen: Adaptive Techniques for Distributed Query Optimization. ICDE 1986: 86-93
  26. Clement T. Yu, C. H. Chen: Adaptive Information System Design: One Query at a Time. SIGMOD Conference 1985: 280-290
  27. Nabil Kamel, Roger King: A Model of Data Distribution Based on Texture Analysis. SIGMOD Conference 1985: 319-325
  28. Stavros Christodoulakis: Implications of Certain Assumptions in Database Performance Evaluation. ACM Trans. Database Syst. 9(2): 163-186(1984)
  29. Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
  30. Stavros Christodoulakis, J. Vanderbroek, J. Li, T. Li, S. Wan, Y. Wang, M. Papa, Elisa Bertino: Development of a Multimedia Information System for an Office Environment. VLDB 1984: 261-271
  31. Gregory Piatetsky-Shapiro, Charles Connell: Accurate Estimation of the Number of Tuples Satisfying a Condition. SIGMOD Conference 1984: 256-276
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:39:34 2009