Dynamic Load Balancing in Hierarchical Parallel Database Systems

We consider the execution of multi-join queries in a hierarchical parallel system, i.e., a shared-nothing system whose nodes are shared-memory multiprocessors. In this context, the problem of load balancing is magnified and must be addressed within and among shared-memory nodes. We propose a dynamic execution model that maximizes local load balancing within shared-memory nodes while minimizing the need for load sharing across nodes. We describe a performance evaluation using an implementation on a 72-processor KSR1 computer. The experiments with many queries and large relations show very good speedup results, even with highly skewed data. Our execution model performs as well as a dedicated model in shared-memory and can scale up very well to deal with multiple nodes. 1 Introduction Parallel system designers have long opposed sharedmemory versus shared-nothing architectures. Sharedmemory provides flexibility and performance for a restricted number of processors while shared-nothing can..