Title

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

Keywords

data skew; grid file; load balancing; Parallel query processing

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. © 1994.

Publication Date

1-1-1994

Publication Title

Information Systems

Volume

19

Issue

7

Number of Pages

549-567

Document Type

Article

Identifier

scopus

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/0306-4379(94)90014-0

Socpus ID

0000549068 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0000549068

This document is currently not available here.

Share

COinS