Optimizer-Assisted Load Balancing Techniques For Multicomputer Database-Management Systems

    Authors

    K. A. Hua; Y. L. Lo;H. C. Young

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    J. Parallel Distrib. Comput.

    Keywords

    JOIN ALGORITHM; MULTIPROCESSOR; Computer Science, Theory & Methods

    Abstract

    Although load balancing incurs processing costs, and therefore can have a profound influence on the optimized execution plan of a query, none of the existing parallelizing query optimizers consider this factor. In this paper, we address this issue by introducing the cost of load balancing as a new factor for query optimization. Specifically, we implemented three new optimizers for multiway join queries that take the load balancing issue into consideration. To evaluate the efficiency of these schemes, we also implemented a simulator for the parallel execution of multiway joins. To provide more faith, our simulation model was validated by comparing the simulation results to those produced by the actual implementation of the same algorithms running on a multicomputer system. This simulator was used in our study to compare the new techniques to a more conventional system in which load balancing is performed at runtime, but it is not a factor for query optimization. Our extensive simulation results confirm that the new methods, indeed, provide very significant savings. Most interestingly, the best scheme displays a performance which is essentially immune from the skew effect. Furthermore, we observed that these new optimizers can consistently achieve the same level of performance gain regardless of the CPU power, I/O, and communication capabilities of the computing system. This indicates that our approaches are generally useful for all hardware platforms. (C) 1995 Academic Press, Inc.

    Journal Title

    Journal of Parallel and Distributed Computing

    Volume

    25

    Issue/Number

    1

    Publication Date

    1-1-1995

    Document Type

    Article

    Language

    English

    First Page

    42

    Last Page

    57

    WOS Identifier

    WOS:A1995QP81400005

    ISSN

    0743-7315

    Share

    COinS