PARALLELISM AND QUERY OPTIMIZATION

Query optimization for parallel execution is an open problem. However, Hong and Stonebraker showed that in the context of XPRS the two-phase hypothesis seems to be valid. In this paper, we clarify the domain of validity of this hypothesis which states that ''the best parallel pla n is a parallelization of the best sequential plan''. To do this, we f irst clarify the differences between sequential and execution plans an d make precise the decisions to be taken by a parallel optimizer. Our analysis suggests that the two-phase hypothesis is usually not valid i n DM. In SM it is true as long as disks are not involved. Finally, we used our parallel optimizer to make several experiments which confirme d some of our conclusions.