Workload balance and page access scheduling for parallel joins in shared-nothing systems

This paper presents a methodology to resolve balancing and scheduling issues for parallel join execution in a shared-nothing multiprocessor environment. The past researches on parallel join methods mostly focused on the design of algorithms for partitioning (e.g., hashing) relations and distributing data buckets as evenly as possible to the processors. Once data are uniformly distributed to the processors, they assume that all processors will complete their tasks at about the same time. We stress that this is true if no further information such as page-level join index (to be discussed later) is available. Otherwise, the join execution can be further optimized and the workload in the processors may still be unbalanced. In this paper, we study such problems in a shared-nothing environment.