Stavros Christodoulakis
Abstract
In this paper we provide estimates of the number of sequential and 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.
- {Aho et al. 74} Aho, A.V., Hopcroft, J.E. and Ullman, J.D.: "The Design and Analysis of Computer Algorithms", Addison-Wesley, 1974. Google Scholar
Digital Library
- {Batory81} Batory, D.S.: "An Analytic Model of Physical Databases", Ph.D. Thesis, Technical Report CSRG-124, University of Toronto, 1981. Google ScholarDigital Library
- {Bernstein et al.81} Bernstein, P.A., Goodman, N., Wong, E., Reeve, C., Rothnie, D.B.: "Query Processing in a System for Distributed Databases (SDD-1)", ACM TODS 6, 4, December 81, 602--625. Google ScholarDigital Library
- {Cardenas75} Cardenas, A.F.: "Analysis and Performance of Inverted Database Structures", CACM 18, 5, May 1975, 253--263. Google ScholarDigital Library
- {Cheung82} Cheung To-Yat: "Estimating Block Accesses and Number of Records in File Management", CACM 25, 7, 1982, 484--487. Google ScholarDigital Library
- {Christodoulakis81} Christodoulakis, S.: "Estimating Selectivities in Data Bases", Ph.D. Thesis, Technical Report CSRG-136, University of Toronto, 1981. Google ScholarDigital Library
- {Christodoulakis82a} Christodoulakis, S.: "Implications of Certain Assumptions in Data Base Performance Evaluation", submitted for publication, 1982.Google Scholar
- {Christodoulakis82b} Christodoulakis, S.: "Issues in Query Evaluation", IEEE Database Engineering 5, 3, 1982, 48--51.Google Scholar
- {Christodoulakis83} Christodoulakis, S.: "Estimating Record Selectivities", Information Systems 8, 2, 1983 (to appear).Google ScholarCross Ref
- {Christodoulakis and Faloutsos82} Christodoulakis, S., and Faloutsos, C.: "Performance Considerations for a Message File Server", in Alpha-Beta, Report CSRG#143, University of Toronto, 1982 (F. Lochovsky editor).Google Scholar
- {Gelenbe and Cardy82} Gelenbe, E. and Cardy, D.: "The Size of Projections of Relations Satisfying a Functional Dependency", VLDB 8, Mexico City, September 1982, 325--333. Google ScholarDigital Library
- {Gelenbe and Cardy83} Gelenbe, E. and Cardy, D.: "On the Size of Projections I", Information Processing Letters 1983 (to appear).Google Scholar
- {Kerschberg et al.80} Kerschberg, L. Ting, P.D., and Yao, S.B.: "Optimal Distributed Query Processing", Technical Report, Bell Labs Holmdel, 1980.Google Scholar
- {Kollias78} Kollias, J. B.: "An estimate of Seek Time for Batched Searching of Random or Index Sequential Structured Files", The Computer Journal 21, 2, May 78, 132--133.Google Scholar
- {Langer and Shum82} Langer, A. and Shum, A.: "The Distribution of Granule Accesses Made by Database Transactions", CACM 25, 11, November 82, 831--832. Google ScholarDigital Library
- {Marshall and Olkin79} Marshall, A. and Olkin, I.: "Inequalities" Theory of Majorisation and its Applications", Academic Press 1979.Google Scholar
- {Potier and Leblank80} Potier, D., and Leblank, P.: "Analysis of Locking Policies in Database Management Systems", CACM 29, 10, Oct. 80, 584--593. Google ScholarDigital Library
- {Rosenthal 81} Rosenthal, A.: "Note on the Expected Size of a Join", SIGMOD record, July 81. Google ScholarDigital Library
- {Ries79} Ries, D.: "The Effect of Concurrency Control on Database Management System Performance", Ph.D. Dissertation, Computer Science Department, University of California, Berkeley, April 1979. Google ScholarDigital Library
- {Riordan58} Riordan, J.: "An Introduction to Combinational Analysis". Wiley, New York, 1958.Google Scholar
- {Schneiderman and Goodman 76} Schneiderman, B. and Goodman, V.: "Batched Searching of Sequential and Tree Structured Files". ACM TODS 1, 3, Sept 76, 268--275. Google ScholarDigital Library
- {Sevcik81} Sevcik, K.: "Data Base System Performance Prediction Using an Analytic Model", Proc. VLDB 9181, 182--198.Google Scholar
- {Siler76} Siler, K.F.: "A Stochastic Evaluation Model for Database Organizations in Data Retrieval Systems", CACM 19, 2, February 76, 84--95. Google ScholarDigital Library
- {Teorey and Das76} Teorey, T.J. and Das, K.S.: "Application of an Analytical Model to Evaluate Storage Structures", Proc. ACM SIGMOD 1976, 9--19. Google ScholarCross Ref
- {Teorey and Oberlander78} Teorey, T.J. and Oberlander, L.B.: "Network Database Evaluation Using Analytical Modeling", Proc. NCC 1978, 833--842.Google Scholar
- {Tsichritzis and Christodoulakis83} Tsichritzis, D., and Christodoulakis, S.: Message Files", ACM Transactions on Office Information Systems 1, Jan. 1983, 88--98. Google ScholarDigital Library
- {Yao77a} Yao, S.B.: "An Attribute Based Model for Database Access Cost Analysis", ACM TODS 2, 1, March 77, 45--67. Google ScholarDigital Library
- {Yao77b} Yao, S.B.: "Approximating Block Accesses in Database Organizations", CACM 20, 4, April 77, 260--261. Google ScholarDigital Library
- {Zahorian et al.83} Zahorian, J., Bell, B., Sevcik, K.: "Estimating Block Transfers When Record Access Probabilities are non-uniform", Information Processing Letters, 1983, (to appear).Google Scholar
Recommendations
Estimating block transfers and join sizes
SIGMOD '83: Proceedings of the 1983 ACM SIGMOD international conference on Management of dataIn this paper we provide estimates of the number of sequential and 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 ...
Exploiting block co-occurrence to control block sizes for entity resolution
AbstractThe problem of identifying duplicated entities in a dataset has gained increasing importance during the last decades. Due to the large size of the datasets, this problem can be very costly to be solved due to its intrinsic quadratic complexity. ...
Multi-way spatial join selectivity for the ring join graph
Efficient spatial query processing is very important since the applications of the spatial DBMS (e.g. GIS, CAD/CAM, LBS) handle massive amount of data and consume much time. Many spatial queries contain the multi-way spatial join due to the fact that ...
Comments