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: 8517
Venue: VLDB
Year: 1998
Pagerank: 5.5063131e-05
Overall Rank: 8,331 | 42.10%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Weiye Zhang
2. Per-Åke Larson

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

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

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,884	Dynamic Memory Adjustment for External Mergesort	1997	VLDB	6.5256146e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,539	Lower Bounds for Sorting with Few Random Accesses to External Memory	2005	PODS	5.1725247e-05
11,840	A Study of Sorting Algorithms on Approximate Memory	2016	SIGMOD	5.1725247e-05
6,603	Percentile Finding Algorithm for Multiple Sorted Runs	1989	VLDB	5.8857499e-05
5,403	On Producing Join Results Early	2003	PODS	6.300328e-05
2,245	Cache-Efficient Aggregation: Hashing Is Sorting	2015	SIGMOD	8.9438948e-05
12,817	A Performance Study of Workfile Disk Management for Concurrent Mergesorts in a Multiprocessor Database System	1995	VLDB	5.1725247e-05
7,577	A Study of Sort Algorithms for Multiprocessor Database Machines	1986	VLDB	5.6502196e-05
3,774	FastSort: A Distributed Single-Input Single-Output External Sort	1990	SIGMOD	7.1880753e-05
4,645	Memory-Adaptive External Sorting	1993	VLDB	6.6522279e-05
4,884	Dynamic Memory Adjustment for External Mergesort	1997	VLDB	6.5256146e-05