Parallel join for IBGF partitioned relational databases

This study is concerned with a parallel join operation where the subject relations are partitioned according to an interpolation based grid file (IBGF) scheme. The partitioned relations and directories are distributed over a set of independently accessible external storage units, together with the partitioning control data. The join algorithms executed by a mesh type parallel computing system allow handling of uniform as well as nonuniformly partitioned relations. Each processor locates and retrieves the data partitions it is to join at each step of the join process, in synchronisation with other processors. The approach is found to be feasible as the speedup and efficiency results found by simulation are consistent with theoretical bounds. The algorithms are tuned to join-key distributions, so that effective load balancing is achieved during the actual join.