 |
|
|
Buffering and Read-Ahead Strategies for External Mergesort |
Full Paper (PDF)
|
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.
|
@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},
crossref = {DBLP:conf/vldb/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
