| This thesis presents a new approach to distributed query processing in locally distributed database systems, load-balanced query processing (LBQP), which integrates distributed query processing and load balancing. Several observations about previous research work in distributed query processing motivated this study. First, only a few query processing algorithms have been developed specifically for distributed databases based on local networks. Second, the use of multiple copies of data to improve performance in a distributed database system has not been addressed by most existing algorithms. Finally, and perhaps most importantly, existing query optimization algorithms have considered only the static characteristics of a distributed database. The algorithm reported here considers the dynamic load status of the system and the existence of multiple copies of data to provide better performance than is achievable with purely static planning techniques.;The dynamic query allocation problem for distributed database systems with fully-replicated data was studied first using simulation. Two new heuristic algorithms were proposed for dynamically choosing a processing site for a newly arrived query in a local network environment. In order to obtain empirical experience regarding distributed query processing in local area networks, a testbed was built to conduct experiments on the performance of distributed join algorithms. A three-phase load-balanced query processing algorithm, Algorithm LBQP, was then developed based on these experimental results and the results of the study of dynamic query allocation. This algorithm first statically generates a logical processing plan for a query. A dynamic query unit allocation algorithm is then applied to the plan to determine the processing sites for each relation. Finally, specific processing methods for the distributed joins in the resulting plan are selected. A model of distributed database systems with partially-replicated data was used to investigate the performance of the dynamic query unit algorithm of LBQP. The results showed significant improvements in both the mean waiting time for queries and the overall system throughput. |
