Buffering and Read-Ahead Strategies for External Mergesort.

Weiye Zhang, Per-Åke Larson: Buffering and Read-Ahead Strategies for External Mergesort. VLDB 1998: 523-533

@inproceedings{DBLP:conf/vldb/ZhangL98,
  author    = {Weiye Zhang and
               Per-{\AA}ke Larson},
  editor    = {Ashish Gupta and
               Oded Shmueli and
               Jennifer Widom},
  title     = {Buffering and Read-Ahead Strategies for External Mergesort},
  booktitle = {VLDB'98, Proceedings of 24rd International Conference on Very
               Large Data Bases, August 24-27, 1998, New York City, New York,
               USA},
  publisher = {Morgan Kaufmann},
  year      = {1998},
  isbn      = {1-55860-566-5},
  pages     = {523-533},
  ee        = {db/conf/vldb/ZhangL98.html},
  crossref  = {DBLP:conf/vldb/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The elapsed time for external mergesort is normally dominated by I/O time. This paper is focused on reducing I/O time during the merge phase. Three new buffering and read- ahead strategies are proposed, called equal buffering, extended forecasting and clustering. They exploit the fact that virtually all modern disks perform caching and sequential read- ahead. The latter two also collect information during run formation (the last keyof each run block) which is then used to preplan reading. For random input data, extended forecasting and clustering were found to reduce merge time by 30% compared with traditional double buffering. Clustering exploits any temporal skew in input runs to further reduce the number of seeks.

Copyright © 1998 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 DiSC

CDROM Version: Load the CDROM "DiSC, Volume 1 Number 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 CD and click on the path of your mount point:
/Anthology/Disc99_1 or /cdrom

ACM SIGMOD Anthology

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

Ashish Gupta, Oded Shmueli, Jennifer Widom (Eds.): VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York City, New York, USA. Morgan Kaufmann 1998, ISBN 1-55860-566-5
Contents

References

[Cor97]: ...
[ECW94]: Vladimir Estivill-Castro, Derick Wood: Foundations for Faster External Sorting (Extended Abstract). FSTTCS 1994: 414-425
[Gra93]: Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
[IBM95]: ...
[Knu73]: Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
[Sal89]: Betty Salzberg: Merging Sorted Runs Using Large Main Memory. Acta Inf. 27(3): 195-215(1989)
[Zha97]: ...
[Zhe92]: ...
[ZL96]: LuoQuan Zheng, Per-Åke Larson: Speeding up External Mergesort. IEEE Trans. Knowl. Data Eng. 8(2): 322-332(1996)
[ZL97]: Weiye Zhang, Per-Åke Larson: Dynamic Memory Adjustment for External Mergesort. VLDB 1997: 376-385