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: 8516
Venue: VLDB
Year: 1998
Pagerank: 4.6085722e-05
Overall Rank: 8,004 | 44.32%
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,524	Sorting And Indexing With Partitioned B-Trees	2003	CIDR	0.00011516282

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

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,218	Reading a Set of Disk Pages	1993	VLDB	5.1528637e-05
11,832	A Study of Sorting Algorithms on Approximate Memory	2016	SIGMOD	4.1945683e-05
6,174	Percentile Finding Algorithm for Multiple Sorted Runs	1989	VLDB	5.1696569e-05
5,511	On Producing Join Results Early	2003	PODS	5.4699346e-05
2,742	Cache-Efficient Aggregation: Hashing Is Sorting	2015	SIGMOD	8.1906104e-05
12,808	A Performance Study of Workfile Disk Management for Concurrent Mergesorts in a Multiprocessor Database System	1995	VLDB	4.1945683e-05
7,460	A Study of Sort Algorithms for Multiprocessor Database Machines	1986	VLDB	4.7241128e-05
2,666	FastSort: A Distributed Single-Input Single-Output External Sort	1990	SIGMOD	8.3422378e-05
4,741	Memory-Adaptive External Sorting	1993	VLDB	5.95905e-05
4,832	Dynamic Memory Adjustment for External Mergesort	1997	VLDB	5.8924168e-05