Method and apparatus for achieving uniform data distribution in a parallel database system

• US 5,970,495 A
• Filed: 06/10/1996
• Issued: 10/19/1999
• Est. Priority Date: 09/27/1995
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Baru, Chaitanya K., Koo, Fred
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): RONES, CHARLES
• Application Number:
  US08/665,031
• Time in Patent Office: 1,226 Days
• Field of Search: 395/618, 395/13, 395/200.44, 395/674, 395/800, 395/675, 395/200.45, 395/677, 707/205, 707/101, 707/100, 707/102, 707/104, 711/1, 370/85
• US Class Current: 1/1
• CPC Class Codes: G06F 9/5088 involving task migration
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

The invention provides a method and apparatus for distributing data of a table substantially uniformly across a parallel database system having a plurality of interlinked database nodes. Data of the table is distributed across a group of nodes (nodegroup) in accordance with a partitioning arrangement. Resource loading, for example, the workload or storage volume of the nodes is monitored. Data is moved from one or more nodes having higher resource loading to nodes having lower resource loading to achieve a substantially uniform distribution of the resource loading across the group of nodes concerned. In the course of moving data the selection of groups of data to be moved is performed in a manner to reduce the amount of data movement.

Claims

1. A method of distributing data of a table partitioned across a parallel database system having a number of nodes comprising:

determining the data volume for nodes of said system associated with said table;

comparing said data volume stored among said nodes;

identifying groups of data in nodes having higher data volumes which may be distributed to nodes having lower data volumes to obtain a more uniform data distribution with minimum required data movement activity;

moving said identified data to said nodes having lower data volumes to balance the data volumes of said nodes across which said data is partitioned;

obtaining file size information for table partitions of said nodes by reading file attributes for said files and obtaining database statistics on data group volume and volume of data group usage;

generating a distribution listing file depicting current data distribution;

selecting one or more data groups for redistribution among selected nodes to which data is to be redistributed;

generating a partitioning map for redistribution of said groups of data in which a best fit method has been applied to select data groups and a redistribution plan for redistribution according to descending weight of said data groups in which data will be substantially uniformly distributed among said nodes; and

redistributing said data groups among said selected nodes in accordance with said partition map.

2. A method of distributing data of a table partitioned across a parallel database system having a number of nodes comprising:

determining resource loading at nodes of the system associated with said table;

comparing resource loading among said nodes;

if said resource loading is distributed in a significantly unbalanced manner;

(a) selecting subpartitions contained within partitions of said table at said nodes having heavy loading for movement to nodes having lower resource loading to obtain a more uniform distribution;

(b) selecting subpartitions for retention at said nodes having heavy loading;

moving said subpartitions selected for movement to said nodes having lower resource loading to balance the resource loading among said nodes containing partitions of said table;

wherein transaction activity information is obtained for all table partitions in said nodes by reading transaction logs of said database system;

generating a current workload distribution file;

selecting data groups from nodes having excessive workload distribution for redistribution among selected nodes to which data is to be distributed;

generating a partitioning map describing a plan of redistribution of said groups to achieve uniformity of workload while minimizing the amount of data transferred between said nodes to achieve said redistribution; and

redistributing said selected data groups.

3. A system of distributing data of a table partitioned across a parallel database system having a number of nodes comprising:

means for determining the data volume for nodes of said system associated with said table;

means for comparing said data volume stored among said nodes;

means for identifying groups of data in nodes having higher data volumes which may be distributed to nodes having lower data volumes to obtain a more uniform data distribution with minimum required data movement activity;

means for moving said identified data to said nodes having lower data volumes to balance the data volumes of said nodes across which said data is partitioned;

means for obtaining file size information for table partitions of said nodes by reading file attributes for said files and obtaining database statistics on data group volume and volume of data group usage;

means for generating a distribution listing file depicting current data distribution;

means for selecting one or more of data groups for redistribution among selected nodes to which data is to be redistributed;

means for generating a partitioning map for redistribution of said groups of data in which a best fit method has been applied to select data groups and a redistribution plan for redistribution according to descending weight of said data groups in which data will be uniformly distributed among said nodes; and

means for redistributing said data groups among said selected nodes in accordance with said partition map.

4. A system of distributing data of a table partitioned across a parallel database system having a number of nodes comprising:

means for determining resource loading at nodes of the svstem associated with said table;

means for comparing resource loading among said nodes;

(a) means for selecting subpartitions contained within partitions of said table at said nodes having heavy loading for movement to nodes having lower resource loading;

(b) means for selecting subpartitions for retention at said nodes having heavy loading;

means for moving said subpartitions selected for movement to said nodes having lower resource loading to balance the resource loading among said nodes containing partitions of said table;

means for obtaining transaction activity information for all table partitions in said nodes by reading transaction logs of said database system;

means for generating a current workload distribution file;

means for selecting data groups from nodes having excessive workload distribution for redistribution among selected nodes to which data is to be distributed;

means for generating a partitioning map describing a plan of redistribution of said groups to achieve uniformity of workload while minimizing the amount of data transferred between said nodes to achieve said redistribution; and

means for redistributing said selected data groups.

5. A computer product for use on a computer system for distributing data of a table partitioned across a parallel database system having a number of nodes comprising:

program code means recorded on said medium for instructing said computer system to perform the steps of;

determining the data volume for nodes of said system associated with said table;

comparing said data volume stored among said nodes;

identifying groups of data in nodes having higher data volumes which may be distributed to nodes having lower data volumes to obtain a more uniform data distribution with minimum required data movement activity;

moving said identified data to said nodes having lower data volumes to balance the data volumes of said nodes across which said data is partitioned;

wherein the smallest group of data identified for redistribution from one node to another comprises a subpartition of said data in said node;

obtaining file size information for table partitions of said nodes by reading file attributes for said files and obtaining database statistics on data group volume and volume of data group usage;

generating a distribution listing file depicting current data distribution;

selecting one or more data groups for redistribution among selected nodes to which data is to be redistributed;

generating a partitioning map for redistribution of said groups of data in which a best fit method has been applied to select data groups and a redistribution plan for redistribution according to descending weight of said data groups;

a redistribution plan in which data will be uniformly distributed among said nodes; and

redistributing said data groups among said selected nodes in accordance with said partition map.

6. A computer program product for use on a computer system for distributing data of a table partitioned across a parallel database system having a number of nodes comprising;

a recording medium;

means recorded on said medium for instructing said computer system to perform the steps of;

determining resource loading at nodes of the system associated with said table;

comparing resource loading among said nodes;

if said resource loading is distributed in a significantly unbalanced manner;

(a) selecting subpartitions contained within partitions of said table at said nodes having heavy loading for movement to nodes having lower resource loading;

(b) selecting subpartitions for retention at said nodes having heavy loading;

moving said subpartitions selected for movement to said nodes having lower resource loading to balance the resource loading among said nodes containing partitions of said table;

wherein transaction activity information is obtained for all table partitions in said nodes by reading transaction logs of said database system;

generating a current workload distribution file;

selecting data groups from nodes having excessive workload distribution for redistribution among selected nodes to which data is to be distributed;

generating a partitioning map describing a plan of redistribution of said groups to achieve uniformity of workload while minimizing the amount of data transferred between said nodes to achieve said redistribution; and

redistributing said selected data groups.