ACM SIGMOD Anthology TODS dblp.uni-trier.de

Performance of a Two-Headed Disk System when Serving Database Queries Under the Scan Policy.

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)
@article{DBLP:journals/tods/ManolopoulosK89,
  author    = {Yannis Manolopoulos and
               John G. Kollias},
  title     = {Performance of a Two-Headed Disk System when Serving Database
               Queries Under the Scan Policy},
  journal   = {ACM Trans. Database Syst.},
  volume    = {14},
  number    = {3},
  year      = {1989},
  pages     = {425-442},
  ee        = {http://doi.acm.org/10.1145/68012.68017, db/journals/tods/ManolopoulosK89.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Disk drives with movable two-headed arms are now commercially available. The two heads are separated by a fixed number of cylinders. A major problem for optimizing disk head movement, when answering database requests, is the specification of the optimum number of cylinders separating the two heads. An earlier analytical study assumed a FCFS model and concluded that the optimum separation distance should be equal to 0.44657 of the number of cylinders N of the disk. This paper considers that the SCAN scheduling policy is used in file access, and it applies combinatorial analysis to derive exact formulas for the expected head movement. Furthermore, it is proven that the optimum separation distance is N/2 - 1 (ceil(N/2 - 1) and floor(N/2 - 1)) if N is even (odd). In addition, a comparison with a single-headed disk system operating under the same scheduling policy shows that if the two heads are optimally spaced, then the mean seek distance is less than one-half of the value obtained with one head. In fact that the SCAN policy is used for many database applications (for example, batching and secondary key retrieval) demonstrates the potential of two-headed disk systems for improving the performance of database systems.

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

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[1]
Henry D. Anderson, P. Bruce Berra: Minimum Cost Selection of Secondary Indexes for Formatted Files. ACM Trans. Database Syst. 2(1): 68-90(1977) BibTeX
[2]
...
[3]
A. Robert Calderbank, Edward G. Coffman Jr., Leopold Flatto: Optimum Head Separation in a Disk System with Two Read/Write Heads. J. ACM 31(4): 826-838(1984) BibTeX
[4]
A. Robert Calderbank, Edward G. Coffman Jr., Leopold Flatto: Optimal directory placement on disk storage devices. J. ACM 35(2): 433-446(1988) BibTeX
[5]
Alfonso F. Cardenas: Analysis and Performance of Inverted Data Base Structures. Commun. ACM 18(5): 253-263(1975) BibTeX
[6]
To-Yat Cheung: Estimating Block Accesses and Number of Recorde in File Management. Commun. ACM 25(7): 484-487(1982) BibTeX
[7]
Stavros Christodoulakis: Estimating Block Transfers and Join Sizes. SIGMOD Conference 1983: 40-54 BibTeX
[8]
Stavros Christodoulakis: Implications of Certain Assumptions in Database Performance Evaluation. ACM Trans. Database Syst. 9(2): 163-186(1984) BibTeX
[9]
Stavros Christodoulakis: Analysis of Retrieval Performance for Records and Objects Using Optical Disk Technology. ACM Trans. Database Syst. 12(2): 137-169(1987) BibTeX
[10]
C. J. Date: An Introduction to Database Systems, 3rd Edition. Addison-Wesley 1981
BibTeX
[11]
...
[12]
Michael Hatzopoulos, John G. Kollias: The Determination of the Optimum Database Maintenance Points. Comput. J. 25(1): 126-129(1982) BibTeX
[13]
Micha Hofri: Should the Two-Headed Disk be Greedy? - Yes, it Should. Inf. Process. Lett. 16(2): 83-85(1983) BibTeX
[14]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[15]
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
[16]
John G. Kollias, Yannis Manolopoulos, Christos H. Papadimitriou: The Optimum Execution Order of Queries in Linear Storage. Inf. Process. Lett. 36(3): 141-145(1990) BibTeX
[17]
...
[18]
...
[19]
...
[20]
Ivor P. Page, R. T. Wood: Empirical Analysis of a Moving Head Disc Model with two Heads Separated by a Fixed Number of Tracks. Comput. J. 24(4): 339-342(1981) BibTeX
[21]
Ben Shneiderman: Optimum Data Base Reorganization Points. Commun. ACM 16(6): 362-365(1973) BibTeX
[22]
Ben Shneiderman, Victor Goodman: Batched Searching of Sequential and Tree Structured Files. ACM Trans. Database Syst. 1(3): 268-275(1976) BibTeX
[23]
William G. Tuel Jr.: Optimum Reorganization Points for Linearly Growing Files. ACM Trans. Database Syst. 3(1): 32-40(1978) BibTeX
[24]
S. J. Waters: Estimating Magnetic Disc Seeks. Comput. J. 18(1): 12-17(1975) BibTeX
[25]
Gio Wiederhold: File Organisation for Database Design. McGraw-Hill Book Company 1987, ISBN 0-07-100340-1
BibTeX
[26]
C. K. Wong: Minimizing Expected Head Movement in One-Dimensional and Two-Dimensional Mass Storage Systems. ACM Comput. Surv. 12(2): 167-178(1980) BibTeX
[27]
S. Bing Yao: An Attribute Based Model for Database Access Cost Analysis. ACM Trans. Database Syst. 2(1): 45-67(1977) BibTeX
[28]
S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977) BibTeX
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:07 2008