A Self-Adjusting Data Distribution Mechanism For Multidimensional Load Balancing In Multiprocessor-Based Database-Systems

    Authors

    C. Lee;K. A. Hua

    Comments

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

    Abbreviated Journal Title

    Inf. Syst.

    Keywords

    PARALLEL QUERY PROCESSING; LOAD BALANCING; DATA SKEW; GRID FILE; Computer Science, Information Systems

    Abstract

    With the advent of micro-processor, memory, and communication technology, it is economically feasible to develop a parallel database computer system to improve the performance of database systems. Relations in such an environment are usually partitioned and distributed across computing units. To achieve the optimal performance, it is essential for each unit to have a perfectly balanced load (i.e., identical amount of data). However, fragment sizes may vary due to insertions to and deletions from a relation. To retain good performance, the system needs to periodically rebalance the load of the processors by redistributing data among computing units. Traditionally, the redistribution is performed by reshuffling tuples among processors through a relation repartitioning (e.g., rehashing) process. The computation of this process is at the tuple level. In this paper, we present a self-adjusting data distribution scheme which balances computer workload at a cell (coarser grain than tuple) level during query processing to minimize redistribution cost. The entire scheme is built on top of the popular grid file structure. The adaptivity of the scheme and its relevant features are discussed. The cost of load rebalancing is estimated. The result shows that under our assumptions, it is always beneficial to rebalance computer workload before performing a join on skewed data.

    Journal Title

    Information Systems

    Volume

    19

    Issue/Number

    7

    Publication Date

    1-1-1994

    Document Type

    Article

    Language

    English

    First Page

    549

    Last Page

    567

    WOS Identifier

    WOS:A1994PP77200002

    ISSN

    0306-4379

    Share

    COinS