Reading a Set of Disk Pages.

Bernhard Seeger, Per-Åke Larson, Ron McFadyen: Reading a Set of Disk Pages. VLDB 1993: 592-603

@inproceedings{DBLP:conf/vldb/SeegerLM93,
  author    = {Bernhard Seeger and
               Per-{\AA}ke Larson and
               Ron McFadyen},
  editor    = {Rakesh Agrawal and
               Se{\'a}n Baker and
               David A. Bell},
  title     = {Reading a Set of Disk Pages},
  booktitle = {19th International Conference on Very Large Data Bases, August
               24-27, 1993, Dublin, Ireland, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1993},
  isbn      = {1-55860-152-X},
  pages     = {592-603},
  ee        = {db/conf/vldb/SeegerLM93.html},
  crossref  = {DBLP:conf/vldb/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The problem studied in this paper is as follows. Consider a file stored in continuous space on disk. Given a list of pages to be retrieved from the file, whatis the fastest way of retrieving them? It is assumed that adjacent pages on disk can be read with a single read request. The straightforward solution is to read the desired pages one by one. However, if two or more pages are located close to each other it may be faster to read them with a single read request, possibly even reading some intervening"empty" pages. It is shown that finding an optimal read schedule is equivalent to finding the shortest path in a certain graph. A very simple approximate algorithm is then introduced and (experimentally) shown to produce schedules that are close to optimal. The expected cost of schedules produced by this algorithm is derived. It is found that significant speed-up can he achieved by the simple mechanism of using additional buffer space and issuing "large reads" whenever it is advantageous to do so.

Copyright © 1993 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" 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/vldb8997 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

Rakesh Agrawal, Seán Baker, David A. Bell (Eds.): 19th International Conference on Very Large Data Bases, August 24-27, 1993, Dublin, Ireland, Proceedings. Morgan Kaufmann 1993, ISBN 1-55860-152-X
Contents

References

[HSW 88]: Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: Globally Order Preserving Multidimensional Linear Hashing. ICDE 1988: 572-579
[McF 90]: ...
[Pal 85]: Prashant Palvia: Expressions for Batched Searching of Sequential and Hierarchical Files. ACM Trans. Database Syst. 10(1): 97-106(1985)
[Pal 88]: Prashant Palvia: The Effect of Buffer Size on Pages Accessed in Random Files. Inf. Syst. 13(2): 187-191,(1988)
[Smi 78]: Alan Jay Smith: Sequentiality and Prefetching in Database Systems. ACM Trans. Database Syst. 3(3): 223-247(1978)
[WWS 83]: Kyu-Young Whang, Gio Wiederhold, Daniel Sagalowicz: Estimating Block Accesses in Database Organizations: A Closed Noniterative Formula. Commun. ACM 26(11): 940-944(1983)
[Wei 89]: Gerhard Weikum: Set-Oriented Disk Access to Large Complex Objects. ICDE 1989: 426-433
[Yao 77]: S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977)