A Load Balancing Data Allocation for Parallel Query Processing

This paper presents a multidimensional schema, called the multidimensional range tree (MDR-tree), to manage multi dimensionally partitioned relational database tables in parallel database system environments. In order to support the speed-up and scalability for intensive data processing, the parallel data processing paradigm has been proved as being one of the best solutions for handling query processing. One of the most important issues in parallel data processing systems is the management of dynamic load balancing for partitioned relational database tables. In order to support the management of dynamic load balancing, we employ a dynamic multidimensional data structure, the multidimensional range tree (MDR-tree), and its associated operations such as insertion, deletion, split, merge, and tuning. The major purpose of operations such as splitting, merging, and tuning is to balance the distribution data records in each processor or network node. By using the tuning strategy, each processor or network node is initially assigned the partitioned data, with an equal load as the other processors. The equal load in each processor or network node is also maintained when the database undergoes frequent updates such as insertions and deletions. The application of multidimensional partitioning by using the MDR-tree is to support multidimensional query processing, such as OLAP (on-line analytic processing), in large database or data warehouse environments. Due to the nature of intensive data and real-time constraints in database and data warehouse applications, the issues of both speed-up and scalability do require finding good practical solutions to load-balanced partitioning and management of a huge volume of data. In the specific case of star queries in data warehouse applications, multidimensional joins can be processed effectively and in a parallel manner with the support of the MDR-tree. We believe that the multidimensional data partitioning and management can be one of the alternatives for these types of applications. We have performed simulation experiments to validate the effectiveness of the MDR-tree. All experimental results indicate that the MDR-tree is an effective index structure for multidimensional data partitioning