Decoupling load-balancing and optimization issues: A two-phase query processing framework for shared-nothing systems

Abstract

In this paper, we propose a two-phase query processing framework for shared-nothing systems. The framework decouples load-balancing and optimization issues. In the plan generation phase, a query is optimized without considering factors that may cause load imbalance during processing. In the plan execution phase, any form of load imbalance in the system is handled using a load-balancing algorithm. We study the effectiveness of the proposed framework for multi-join queries by comparing with "ideal" strategies that consider load-balancing issues during optimization. Our simulation study shows that the two-phase query processing framework performs nearly as well as the ideal integrated strategies. In the worst case, algorithms based on the two-phase framework generate plans whose elpased times are not more than 120% that of their ideal integrated counterparts.