Sorting in a Memory Hierarchy with Flash Memory

Abstract

Flash memory continues to improve in price, capacity, reliability, durability, and performance. In addition to consumer and client devices, flash memory is also employed in many servers. Its optimal usage in various classes of server software, including web servers, file-and-print servers, and database servers, requires evaluation and analysis. The present paper analyzes the use of flash memory for database query processing including algorithms that combine flash memory and traditional disk drives.External merge sort serves as a prototypical query execution algorithm. The excellent access latency of flash memory promises substantially better sort performance than sorting with traditional disks. Surprisingly, this is true only in fairly limited cases. Flash memory as intermediate external storage improves performance in particular in situations with very limited memory.The most advantageous external sort algorithms combine flash memory and traditional disk, exploiting the fast access latency of flash memory as well as the fast transfer bandwidth and inexpensive capacity of traditional disks. Moreover, graceful degradation is required in multiple ways, both when spilling from memory to flash storage and when spilling from flash to disk. These algorithms are described in detail, including in particular their graceful transition from run generation to merging. Using such graceful degradation and incremental transitions, sorting in a three-level memory hierarchy of RAM, flash memory, and traditional disk can be generalized to database query processing with any number of levels.