Buffering and Read-Ahead Strategies for External Mergesort

Summary: Buffering/read-ahead strategies for external mergesort: equal buffering, extended forecasting, clustering. They exploit disk caching and last-key run-block data to preplan I/O, yielding ~30% merge-time reductions over double buffering, with clustering reducing seeks under skew. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8707
Venue: VLDB
Year: 1998
Pagerank: 5.4230411e-05
Overall Rank: 8,451 | 42.02%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Weiye Zhang (University of Waterloo)
2. Per-Åke Larson (Microsoft)

BibTeX Citation

@article{zhang_vldb98,
        title = {{Buffering and Read-Ahead Strategies for External Mergesort}},
        author = {Zhang, Weiye and Larson, Per-Åke},
        journal = {PVLDB},
        series = {{VLDB} '98},
        pages = {523--534},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,508	Sorting And Indexing With Partitioned B-Trees	2003	CIDR	0.00010540965

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
4,955	Dynamic Memory Adjustment for External Mergesort	1997	VLDB	6.4297637e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,723	Lower Bounds for Sorting with Few Random Accesses to External Memory	2005	PODS
2	12,033	A Study of Sorting Algorithms on Approximate Memory	2016	SIGMOD
3	6,699	Percentile Finding Algorithm for Multiple Sorted Runs	1989	VLDB
4	5,467	On Producing Join Results Early	2003	PODS
5	2,250	Cache-Efficient Aggregation: Hashing Is Sorting	2015	SIGMOD
6	13,002	A Performance Study of Workfile Disk Management for Concurrent Mergesorts in a Multiprocessor Database System	1995	VLDB
7	7,705	A Study of Sort Algorithms for Multiprocessor Database Machines	1986	VLDB
8	3,842	FastSort: A Distributed Single-Input Single-Output External Sort	1990	SIGMOD
9	4,708	Memory-Adaptive External Sorting	1993	VLDB
10	4,955	Dynamic Memory Adjustment for External Mergesort	1997	VLDB