Optimal parallel scheduling of M-way join queries |
| |
Authors: | Farshad Fotouhi Jason Leigh Satyendra P. Rana |
| |
Affiliation: | Computer Science Department, Wayne State University, Detroit, MI 48202, U.S.A. |
| |
Abstract: | The problem of computing multirelation (M-way) join queries on uniprocessor architectures has been considered by many researchers in the past. This paper lays the necessary foundation for work involving optimization of M-way joins in parallel architectures. We explain the inadequacies of previous uniprocessor strategies and describe a more suitable formulation based on the concept of matching in graph theory to approach the problem in a parallel environment. It has been shown that the problem of optimizing M-way joins is an NP-hard problem and hence we would expect that in a parallel processing environment the search space of possible solutions (join schedules) would be enormous, especially when a variable number of processors are considered. Our strategy seeks to reduce the region to search by partitioning the search space according to the number of available processors. Based on this a significant portion of the search space, which will produce non-optimal join schedules, may be ignored. |
| |
Keywords: | Relational join join schedule parallel processing M-way join |
本文献已被 ScienceDirect 等数据库收录! |