LARGE JOIN OPTIMIZATION ON A HYPERCUBE MULTIPROCESSOR

Optimizing large join queries that consist of many joins has been reco gnized as NP-hard. Most of the previous work focuses on a uniprocessor environment. In a multiprocessor, the location of each join adds anot her dimension to the complexity of the problem. In this paper, we exam ine the feasibility of exploiting the inherent parallelism in optimizi ng large join queries on a hypercube multiprocessor. This includes usi ng the multiprocessor not only to answer the large join query but also to optimize it. We propose an algorithm to estimate the cost of a par allel large join plan. Three heuristics are provided for generating an initial solution, which is further optimized by an iterative local-im provement method. The entire process of parallel query optimization an d execution is simulated on an Intel iPSC/2 hypercube machine. Our exp erimental results show that the performance of each heuristic depends on the characteristics of the query.