Memory Management during Run Generation in External Sorting

Summary: Memory management for run generation via replacement selection in external sorts with variable-length records; compares workspace algorithms. Best-fit yields ~90% memory utilization and run lengths >1.8× workspace with no extra copying, showing replacement selection is viable for commercial DB systems. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3099
Venue: SIGMOD
Year: 1998
Pagerank: 9.7286236e-05
Overall Rank: 1,801 | 87.65%
DOI: 10.1145/276304.276346

Incoming Non-self Citations Over Time

Authors

1. Per-Åke Larson (Microsoft)
2. Goetz Graefe (Microsoft)

BibTeX Citation

@inproceedings{larson_sigmod98,
        title = {{Memory Management during Run Generation in External Sorting}},
        author = {Larson, Per-Åke and Graefe, Goetz},
        series = {{SIGMOD} '98},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/276304.276346},
        url = {https://dl.acm.org/doi/10.1145/276304.276346},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
109	DBMSs On A Modern Processor: Where Does Time Go?	1999	VLDB	0.000331207
523	Adaptive Self-Tuning Memory in DB2	2006	VLDB	0.00017133451
781	Self-tuning Database Technology and Information Services: from Wishful Thinking to Viable Engineering	2002	VLDB	0.00014085674
1,508	Sorting And Indexing With Partitioned B-Trees	2003	CIDR	0.00010540965
8,319	Two-way Replacement Selection	2010	VLDB	5.4548122e-05

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
844	Hash-Partitioned Join Method Using Dynamic Destaging Strategy	1988	VLDB	0.00013664056

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,996	Write-limited sorts and joins for persistent memory	2014	VLDB
2	12,723	Lower Bounds for Sorting with Few Random Accesses to External Memory	2005	PODS
3	3,842	FastSort: A Distributed Single-Input Single-Output External Sort	1990	SIGMOD
4	13,002	A Performance Study of Workfile Disk Management for Concurrent Mergesorts in a Multiprocessor Database System	1995	VLDB
5	8,451	Buffering and Read-Ahead Strategies for External Mergesort	1998	VLDB
6	7,705	A Study of Sort Algorithms for Multiprocessor Database Machines	1986	VLDB
7	12,033	A Study of Sorting Algorithms on Approximate Memory	2016	SIGMOD
8	4,708	Memory-Adaptive External Sorting	1993	VLDB
9	4,955	Dynamic Memory Adjustment for External Mergesort	1997	VLDB
10	8,319	Two-way Replacement Selection	2010	VLDB