Parallel data base record distribution method and parallel data base management system

• US 5,987,462 A
• Filed: 04/25/1997
• Issued: 11/16/1999
• Est. Priority Date: 04/26/1996
• Status: Expired due to Term

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd., Hitachi Software Engineering Co., Ltd. (Hitachi, Ltd.)
• Inventors: Yamaguchi, Kota, Masai, Kazuo, Toda, Keisuke, Hirohata, Kiyomi, Kasao, Hideaki
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US08/840,643
• Time in Patent Office: 935 Days
• Field of Search: 364/200, 395/200.32, 395/477, 395/725, 395/441, 395/457, 707/2, 707/3, 707/10, 707/104, 707/7
• US Class Current: 707/698
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A parallel data base management system with a data base divided into a plurality of external memory units is disclosed. A control CPU, upon receipt of a request for access to the data base, decides whether the access request is for storing or searching a record. For a record storage request, the control CPU determines an external memory unit to store the record using a hash function. In the case of a record search request, on the other hand, all the external memory units are searched in parallel without using the hash function thereby to obtain the desired record. The hash function is altered upon addition of an external memory unit.

Claims

1. A method of dividing a database in parallel in a parallel database management system, wherein the database management system comprises:

a plurality of database units each having an external memory unit for storing a division of a database, and

a control CPU including means for registering, referencing and altering database configuration information including a number of divisions of the database among said external memory units, means for storing a record in any one of said external memory units, and means for searching and updating the record stored in any one of said external memory units, the database records being distributed among the external memory units associated with each database unit, the stored records being searched and updated in each database unit, thereby achieving a high processing speed;

said method of dividing a database in parallel, comprises the steps of, by said control CPU;

referencing said database configuration information;

calculating the value of a predetermined portion of the data of a record by a hash function;

uniquely determining an external memory unit to store said record to thereby realize the divided storage of the record when storing or adding said record;

searching and updating the external memory units associated with all the database units included in the database to thereby realize the desired record search without using the hash function when searching and updating a record;

said method further comprising the steps of;

storing in memory means an average record increment rate per unit time for the whole database and the number of records in each of said external memory units;

temporarily altering the hash function used for storing the records during a predetermined time proportional to the total number of records in said external memory units before addition divided by the average record increment rate per unit time for all of said external memory units when increasing the number of divisions of the database due to the addition of a database unit; and

selecting the added external memory unit in priority over the other external memory units as an external memory unit assigned for storage as a result of the calculation result using the hash function.

2. A method of dividing a database in parallel in a parallel database management system, wherein the database management system comprises:

a plurality of database units each having an external memory unit for storing a division of a database, and

a control CPU including means for registering, referencing and altering database configuration information including a number of divisions of the database among said external memory units, means for storing a record in any one of said external memory units, and means for searching and updating the record stored in any one of said external memory units, the database records being distributed among the external memory units associated with each database unit, the stored records being searched and updated in each database unit, thereby achieving a high processing speed;

said method of dividing a database in parallel, comprises the steps of, by said control CPU;

referencing said database configuration information;

calculating the value of a predetermined portion of the data of a record by a hash function;

uniquely determining an external memory unit to store said record to thereby realize the divided storage of the record when storing or adding said record;

searching and updating the external memory units associated with all the database units constituting the database to thereby realize the desired record search without using the hash function when searching and updating a record;

said method further comprising the steps of;

storing the number of records in each of said external memory units in memory means; and

moving the records from each of said external memory units before addition to the external memory unit associated with the added database unit by the number stored in each of said external memory units divided by the number of database divisions after addition when adding said database unit and thereby increasing the number of database divisions.

3. A parallel database management system comprising:

a plurality of database units each including an external memory unit for storing a division of a database;

a control CPU including;

means for registering, referencing and altering database configuration information including a number of divisions of the database among said external memory units,

storage position determining means for determining an external memory unit to store a record using the hash function for a predetermined portion of the data of each record with reference to said database configuration information,

means for storing and adding the record in the external memory unit determined by said storage position determining means, and

record search and update means for requesting all of said external memory units included in said database to search and update the records in parallel without using the hash function; and

record information storage means for storing the average record increment rate per unit time of the whole database and the number of records in each of said external memory units;

wherein said storage position determining means selects said newly-added external memory unit in priority over the remainder of said external memory units during a predetermined time proportional to the total number of records in said external memory units before addition divided by the average record increment rate per unit time for all of said external memory units when increasing the number of the database divisions due to the addition of said new database unit.

4. A parallel database management system, comprising:

a plurality of database units each including an external memory unit for storing a division of a database; and

a control CPU including;

means for registering, referencing and altering database configuration information including a number of divisions of the database among said external memory units,

storage position determining means for determining an external memory unit to store a record using the hash function for a predetermined portion of the data of each record with reference to said database configuration information,

means for storing and adding the record in the external memory unit determined by said storage position determining means, and

record search and update means for requesting all the external memory units constituting the database to search and update the records in parallel without using the hash function,

wherein said control CPU further includes;

means for storing the number of records in each of said external memory units, and

means for moving the records from each of said external memory units to said newly-added external memory unit by the number stored in each of said external memory units before addition divided by the number of database divisions after addition when increasing the number of the database divisions due to the addition of said database unit.

5. In a parallel data management system comprising a plurality of database units each including an external memory unit for storing a division of a database and a control CPU for determining an external memory unit associated with a destination database unit to store a record using a first hash function in response to a request for storing said record, a method for distributing the record by said control CPU comprising the steps of:

altering said first hash function to a second hash function based on the altered number of database divisions upon detection of said alteration of the number of database divisions;

determining a destination external memory unit to store said record on the basis of the hashing calculation using the prevailing hash function in response to a record storage request and instructing the database unit associated with said destination external memory unit to store said record; and

instructing all of said database units to search said record without using the first and second hash functions in response to a record search request.

6. A record distribution method according to claim 5, wherein said alteration of the number of database divisions is increasing the number of database divisions due to the addition of a database unit.

7. A record distribution method according to claim 5, wherein said alteration of the number of database divisions is decreasing the number of divisions due to the separation of a database unit.

8. In a parallel data management system comprising a plurality of database units each including an external memory unit for storing a division of a database and a control CPU for determining an external memory unit associated with a destination database unit to store a record using a first hash function in response to a request for storing said record, a method for distributing the record by said control CPU comprising the steps of:

temporarily altering said first hash function to a second hash function based on a number larger than the altered number of database divisions upon detection of an increase in the number of database divisions due to the addition of a database unit;

determining a destination external memory unit to store said record on the basis of the hashing calculation using said second hash function in response to a record storage request and instructing the database unit associated with said destination external memory unit to store said record;

altering said second hash function to a third hash function based on a number equal to the altered number of database divisions after the lapse of a predetermined length of time following said temporary alteration to said second hash function;

determining a destination external memory unit to store said record on the basis of the hash calculation using said third hash function in response to a record storage request and instructing the database unit associated with said destination external memory unit to store said record; and

instructing all of said database units to search said record without using said first, second or third function in response to a record search request.

9. A record distribution method according to claim 8, wherein a difference between the total record amount after addition and the total record amount before addition is divided by the average record increment rate per unit time for all the external memory units after addition thereby to determine said predetermined length of time.

10. A record distribution method according to claim 9, wherein the record increment rate for a given external memory unit before addition is used as the average record increment rate per unit time for all the external memory units after addition.

11. In a parallel data management system comprising a plurality of database units each including an external memory unit for storing a division of a database and a control CPU for determining an external memory unit associated with a destination database unit to store a record using a first hash function in response to a request for storing said record, a method for distributing the record by said control CPU comprising the steps of:

moving a part of the records stored in the external memory units already existing before a database unit addition to an added external memory unit thereby to distribute the records stored before addition equally among the external memory units after database unit addition, upon detection of an increase in the number of said database divisions due to the addition of said database unit;

altering said first hash function to a second hash function based on a number equal to the altered number of divisions after complete movement of said record;

determining a destination external memory unit to store said record on the basis of the hashing calculation using the prevailing hash function in response to a record storage request and instructing the database unit associated with said destination external memory unit to store said record; and

instructing all of said database units to search said record without using said first or second hash function in response to a record search request.

12. A parallel database management system, comprising:

a plurality of database units each including an external memory unit for storing a division of a database; and

a control CPU for determining a destination external memory unit associated with a database unit to store a record using a first hash function in response to a request for storing the particular record in said database, wherein said control CPU includes;

means for altering said first hash function to a second hash function based on the altered number of database divisions upon detection of the alteration of the number of divisions of said database,

means for determining a destination external memory unit to store said record on the basis of the hashing calculation using the prevailing hash function in response to a record storage request and instructing the database unit associated with said destination external memory unit to store said record, and

means for instructing all the database units to search said record without using said first or said second hash function in response to a record search request.

13. A parallel database management system according to claim 12, wherein the alteration of said number of database divisions is increasing the number of database divisions due to the addition of a database unit.

14. A parallel database management system according to claim 12, wherein said alteration of said number of database divisions is decreasing the number of database divisions due to the separation of a database unit.

15. A parallel database management system, comprising:

a plurality of database units each including an external memory unit for storing a division of a database; and

a control CPU for determining a destination external memory unit associated with a database unit to store a record using a first hash function in response to a request for storing the particular record in said database, wherein said control CPU includes;

means for temporarily altering said first hash function to a second hash function based on a number larger than the altered number of database divisions upon detection of an increase in the number of database divisions due to the addition of a database unit, and altering said second hash function to a third hash function based on the altered number of database divisions after the lapse of a predetermined time following said temporary alteration to said second hash function,

means for determining a destination external memory unit to store said record on the basis of the hashing calculation using the prevailing hash function in response to a record storage request and instructing the database unit associated which said destination external memory unit to store said record, and

means for instructing all the database units to search said record without using said first, said second or said third hash function in response to a record search request.

16. A parallel database management system according to claim 15, wherein said control CPU calculates a difference between the total record amount after database unit addition and the total record amount before database unit addition, calculates the average record increment rate per unit time for all the external memory units alter database unit addition and dividing said difference by said average record increment rate thereby to determine said predetermined length of time.

17. A parallel database management system according to claim 16, wherein each of said external memory units includes means for storing the record increment rate, and said control CPU uses the record increment rate stored in said memory means as the average increment rate per unit time for all the external memory units after database unit addition.

18. A parallel database management system, comprising:

a plurality of database units each including an external memory unit for storing a division of a database; and

a control CPU for determining a destination external memory unit associated with the database unit to store a record using a first hash function in response to a request for storing such a record in said database, wherein said control CPU includes;

means for moving a part of the records stored in the external memory units already existing before addition to an added external memory unit upon detection of an increase in the number of said database divisions due to the addition of a database unit thereby to distribute the records stored before database unit addition equally among the external memory units after addition,

means for altering said first hash function to a second hash function based on the altered number of database divisions after complete movement of said record,

means for determining a destination external memory unit to store said record on the basis of the hashing calculation using the prevailing hash function in response to a record storage request and instructing the database unit associated with said destination external memory unit to store said record, and

means for instructing all the database units to search said record without using said first or second hash function in response to a record search request.

19. A computer program stored on a storage medium in a parallel database management system including a plurality of database units each having an external memory unit for storing a division of a database and a control CPU, said computer program, when executed by said control CPU causes said parallel database management system to perform the steps of:

registering, referencing and altering database configuration information including the number of divisions of the database among said external memory units, determining one of said external memory units to store a record using a hash function for a predetermined portion of the data of each record with reference to said database configuration information,

storing and adding the record in the determined external memory unit,

requesting all of said external memory units in said database to search and update the records in parallel, and

storing an average record increment rate per unit time of the whole database and the number of records in each of said external memory units;

wherein said determining step selects said newly-added external memory unit in priority over the remainder of said external memory units during a predetermined time proportional to the total number of records in said external memory units before addition divided by the average record increment rate per unit time for all said external memory units when increasing the number of database divisions due to the addition of said new database unit.