Design and evaluation of efficient parellel join algorithms for multiprocessor database computers

Abstract

During the past decade, there have been constant efforts toward creating more powerful database systems, especially focusing on the relational database system and as a result, several relational database system have appeared. However, most of these systems exhibit poor performance in supporting a large class of database operations, since they are too large and complex to run on a conventional general purpose von Neumann computer which is particularly not suitable for database management. In order to overcome the drawbacks of the conventional database systems, the database computer approach has been inspired by parallel processing to support some or all of the functions of the relational database system, in particular to efficiently support the relational join operation because the join operation is the most important limiting factor on the performance of the relational database system. In this thesis, we extensively investigate the join processing algorithms under multiprocessor database computer environments. first, the problems of the existing join algorithms are addressed, and then we propose a new join algorithm referred to as hybrid join, which improves both the sort-merge and the hash-partitioned join algorithms by completely sorting only the smaller relation and partitioning the other one into ranged buckets according to the order statistics of the sorted relation. The key idea in the hybrid join is to determine the bound on the bucket sizes during the sort of the smaller relation. This guarantees a nice bound on the number of buffers necessary for any smaller relation bucket. Accordingly, the hybrid join requires relatively less sorting cost than that of the sort-merge join and also can prevent the bucket overflows which appear in the hash-partitioned join. Second, we extend this result to develop efficient parallel join algorithms on two types of multiprocessor database computers: a shared-memory multiprocessor and a distributed-memory multiprocessor. ...