Architecture-conscious storage management.

Abstract

Designers of database management systems (DBMS) have traditionally focussed on alleviating the disk I/O performance bottleneck. Because of the decreasing price and the increasing capacity of random access memory, systems with large main-memory configurations are becoming more prevalent. As the amount of main memory grows larger, data sets reside in main memory longer, and the disk I/O bottleneck shifts to the main-memory hierarchy. Because of this shift, DBMSs must become aware of the underlying architecture to maximize performance. This dissertation explores architecture-conscious design techniques that exploit the underlying architecture to improve DBMS performance. The first contribution of this thesis is an architecture-conscious data-storage technique, called Data Morphing (DM). The DM process dynamically analyzes the query workload and reorganizes the data to improve its spatial locality. The improved spatial locality reduces the number of processor cache misses that occur during query processing, thereby significantly improving performance. The second contribution of this thesis is an analysis of two architecture-conscious secondary index structures: the CSB<super>+</super>-tree and an extendible hash index. Analytical models based on the underlying microarchitectural behavior are developed for both indexes. Analysis of the CSB<super>+</super>-tree index shows that using a larger node size than originally proposed improves performance. Similar analysis of the extendible hash index shows that the overflow chain length is more critical than bucket size. Because of the tight coupling between DBMS performance and the underlying architecture, research for future processor design must take place in the simulation domain. Unfortunately, simulating large-scale database workloads is difficult due to their high complexity and cost. The third contribution of this thesis shows that the architectural behavior of a large scale database workload can be approximated by a much smaller workload. Using this smaller workload is much more conducive to simulation because of the reduced complexity and cost. This research is on the cusp of a new effort in main-memory database research. The techniques presented within are not only applicable on current DMBSs, but apply to future systems as well.