Title

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

Authors

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