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: h7372507509225c68
Venue: SIGMOD
Year: 1998
Pagerank: 9.5606648e-05
Overall Rank: 1,823 | 87.75%
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 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
110	DBMSs On A Modern Processor: Where Does Time Go?	1999	VLDB	0.00032700879
508	Adaptive Self-Tuning Memory in DB2	2006	VLDB	0.00017089907
780	Self-tuning Database Technology and Information Services: from Wishful Thinking to Viable Engineering	2002	VLDB	0.00014025444
1,539	Sorting And Indexing With Partitioned B-Trees	2003	CIDR	0.00010316015
8,412	Two-way Replacement Selection	2010	VLDB	5.335329e-05
10,840	CrocSort: Resource-Efficient, Skew-Resilient Parallel External Merge Sort	2026	VLDB	4.9793485e-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
853	Hash-Partitioned Join Method Using Dynamic Destaging Strategy	1988	VLDB	0.00013444911

Semantically Similar Papers

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