| Author(s) | Khaled AISabti* and Sanjay Ranka** |
| Affiliation | Department of Computer Science, College of Computer & 1riformation Sciences King Saud University, P.D.Box 51178, Riyadh 11543, Saudi Arabia ** University of Florida, Florida, USA |
| Title | Skew-insensitive Parallel Algorithms for Relational Join |
| Source | Journal of King Saud University. Computer & Information Sciences. Volume 13, No 1. (2001/1421) |
| Abstract | Join is the most important and expensive operation in relational databases. The parallel join operation is very sensitive to the presence of the data skew. In this paper, we present two new parallel join algorithms for coarse-grained machines, which work optimally in presence of arbitrary amount of data skew. The first algorithm is sort-based and the second is hash-based. Both of these algorithms employ a preprocessing phase (prior to the redistribution phase) to equally partition the work among the processors. These algorithms are shown to be theoretically as well as practically scalable. Experimental results are provided on the IBM SP-2. |
