Main memory database algorithms for multiprocessors
William Carey Thompson · Medical Entomology and Zoology · 1986
The demand for more capable computers, despite the approach of basic physical limits to further increases in the speed of single processor systems, has engendered increasing interest in the use of multiple processors to simultaneously work on one problem. At the same time, decreasing memory costs have made it possible to consider keeping entire databases in a computer's primary memory. The combination of these concepts can provide the power necessary for future database systems. Only recently has the decrease in memory cost prompted the study of main memory databases. Databases contained in the main memory of powerful multiprocessors have received even less study. This dissertation investigates database operations on multiprocessors with very large main memories. Only closely coupled systems with powerful processors and shared memory are considered. Removed from this environment is the crushing burden of disk access times, prompting the development of new algorithms and methods to make efficient use of the available resources. Improved methods of performing the relational join, an expensive operation, are the first topic of investigation in this dissertation. A number of multiprocessor main memory join algorithms are developed and their costs analyzed. The cost analysis and a graphical comparison of the algorithms provides insight into both the effectiveness of these machines and the methods used to develop algorithms in this environment. Despite the absence of disks, the cost of access to data is still an important issue for databases on these systems. Hashing and index methods for data access, such as B-trees, T-trees and AVL trees, are studied and multiprocessor algorithms are developed for main memory database operations. A model of index and hashing methods based on the partitioning and location of the index and data in memory is used to analyze costs of the different algorithms. Algorithms for searching these data structures are implemented on a model machine so that their costs may be estimated in instructions per operation. The costs of different implementations are calculated for a varying range of database sizes and different numbers of processors and presented for comparison.