Method and apparatus for adding data storage bins to a stored computer database while minimizing movement of data and balancing data distribution

• US 5,960,431 A
• Filed: 12/19/1996
• Issued: 09/28/1999
• Est. Priority Date: 12/19/1996
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Choy, David Mun-Hien
• Primary Examiner(s): Kulik, Paul V.
• Assistant Examiner(s): WALLACE, MICHAEL J
• Application Number:
  US08/770,207
• Time in Patent Office: 1,013 Days
• Field of Search: 707/1, 707/101, 707/7, 707/200, 707/2, 707/204, 707/205, 711/202, 711/209
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

In a database system that stores database objects in partitioned mode using bins to represent storage locations at which individual records of an object are stored, after they have been partitioned into logical buckets, a cascaded round-robin mapping method assigns buckets to bins evenly, while minimizing the movement of buckets when new bins are added and while minimizing memory overhead requirements. The method includes entering a do loop for an index counter variable j=m to 0 by -1, wherein "m" is the number of times new bins have been added since the last database reorganization. A variable y is set equal to x modulo n_j, wherein n_j is the number of bins after the j^th database expansion. If y≧n_j-1, y is established to be the bin identification. Buckets are moved to populate new bins based on modulo n+k, wherein k is the number of bins added in the current expansion.

Claims

1. In a database system having a stored database partitioned into a plurality of buckets initially distributed into storage in round robin fashion in n₀ bins and subsequently in n_j bins after a j^th time that new bins have been added to the stored database, each bucket being associated with a bucket identification "x", a database storage manager for generating a bin identification "y" for the buckets after the m^th addition of new bins, comprising:

a mapping module that includes;

first means for decrementing an index counter variable j=m to 0 by -1 ;

second means for defining a variable y=x mod n_j ;

third means for determining whether y is equal to or greater than n_j-1 ; and

fourth means responsive to the third means for establishing y as the bin identification when y is equal to or greater than n_j-1 and;

means for assigning the buckets to the n_m bins; and

means for obtaining from storage records in the stored database using the bin identification.

2. The database storage manager of claim 1, wherein the stored database contains "B" buckets, an integer "k" is defined to be a number of new bins being added, and the data records are clustered and accessible by bucket identification, and the database storage manager further comprises:

means for entering a do loop for a variable i=0 to B-1 to test each of the "n" existing bins;

means for determining whether the i^th bucket is in a bin being tested, and if not, retrieving the next i in the do loop;

means for defining a variable j=mode (n+k) when the i^th bucket is in the bin being tested; and

means for moving the i^th bucket to the j^th bin when j≧

n and then retrieving the next i in the do loop, and otherwise retrieving the next i in the do loop.

3. The database storage manager of claim 2, wherein the data records are not clustered or are not accessible by bucket identification, and the database storage manager further comprises:

means for defining j=x mod(n+k) to test each data record in each of the n existing bins, wherein "x" is the bucket identification for a record being tested; and

means for moving a record to the j^th bin when j≧

n.

4. The database storage manager of claim 1, wherein the stored database includes "n" bins, wherein "n" is a natural number, the database contains "B" buckets and the buckets are assigned to the bins using a mapping characterized by a defining sequence of integers, and wherein the database storage manager further comprises:

means for determining whether new bins have been added;

means for appending an integer to the defining sequence when new bins have been added;

means for determining a skew of the database and for returning the defining sequence with n appended thereto when the skew is less than a predetermined skew;

means for determining, when the skew is larger than the predetermined skew, whether n is a power of two and if so, returning "n" as the new defining sequence; and

means for returning, when n is not a power of two, the sequence of integers (2ⁱ, n) as the new defining sequence, wherein i=floor(log₂ (n)).

5. The database storage manager of claim 4, in combination with a digital computer.

6. A computer-implemented method for managing storage of a database, the storage being divided into a plurality of bins, the method comprising populating "k" newly added bins in the storage with records of the database partitioned among "n" preexisting bins, each record having a bucket identification signifying a bin of the plurality of bins, and moving a record to a newly added bin if the record'"'"'s bucket identification modulo the sum of "n" and "k" signifies the newly added bin, wherein the records are clustered in the database storage and accessible by respective logical bucket identifications, and the method further comprises:

for each of "n" existing bins, wherein "n" is a natural number, entering a do loop for an index counter variable "i"=0 to (B-1), wherein the database storage includes "B" buckets;

determining whether the i^th bucket is in the bin, and if so, setting an index counter variable "j" to be the index counter variable "i" modulo the sum of "n" and "k"; and

when the index counter variable "j" is at least as great as "n", moving the i^th bucket to the j^th bin, and otherwise not moving the i^th bucket.

7. A computer-implemented method for managing storage of a database the storage being divided into a plurality of bins, the method comprising populating "k" newly added bins in the storage with records of the database partitioned among "n" preexisting bins, each record having a bucket identification signifying a bin of the plurality of bins, and moving a record to a newly added bin if the record'"'"'s bucket identification modulo the sum of "n" and "k" signifies the newly added bin, wherein the records are not clustered or are not accessible by bucket identification, and the method further comprises:

for each of "n" existing bins, wherein "n" is a natural number, and for each record in the bin, defining an index counter variable "j" to be the bucket identification "x" associated with the record modulo the sum of "n" and "k";

determining whether the index counter variable "j" is at least as great as "n", and if so, moving the record to the j^th bin, and otherwise not moving the record to the j^th bin.

8. A computer-implemented method for managing storage of a database, the storage being divided into a plurality of bins, the method comprising populating "k" newly added bins in the storage with records of the database partitioned among "n" preexisting bins, each record having a bucket identification signifying a bin of the plurality of bins, and moving a record to a newly added bin if the record'"'"'s bucket identification modulo the sum of "n" and "k" signifies the newly added bin, wherein the database storage initially includes n₀ bins, further comprising the steps of:

(a) adding new bins "m" times to the database storage, wherein "m" is a natural number, and then initially defining an index counter variable "j" to be equal to "m";

(b) defining a variable "y" to be the bucket identification "x" modulo n_j ;

(c) determining whether the variable "y" is at least equal to n_j-1, and if so, defining the variable "y" to be the bin identification of the bucket having the bucket identification "x" and otherwise decrementing the index counter variable "j" by an integer number and repeating steps (b) and (c);

(d) subsequently accessing buckets using the variable "y" as the relevant bin identification;

(e) moving buckets to bins and mapping the buckets to the bins using steps (a)-(c).

9. The computer-implemented method of claim 8, wherein the database storage includes "n" bins, wherein "n" is a natural number, the database storage contains "B" buckets and the buckets are assigned to the bins using a mapping characterized by a defining sequence of integers, and wherein the method steps further comprise:

determining whether new bins have been added, and if so, appending "n" to the defining sequence;

determining whether the difference between the size of the largest bin and the ceiling of the quotient "B"/"n" exceeds a predetermined difference, and if not, returning the defining sequence with "n" appended thereto as a new defining sequence, and otherwise;

determining whether "n" is a power of two, and if so, returning "n" as the new defining sequence, and otherwise returning the sequence of integers (2ⁱ, n) as the new defining sequence, wherein "i" equals the integer portion of the logarithm of "n".

10. The computer-implemented method of claim 9, wherein performed in a combination that includes a digital computer.

11. A computer program device comprising:

a computer program storage device readable by a digital computer; and

a program means on the program storage device and including instructions executable by the digital computer for performing method steps for mapping to a bin in a database storage a data record bucket stored therein, the data record bucket containing data records of a database and having a bucket identification "x", while minimizing the movement of data when new bins are added to the database storage and while minimizing memory overhead, the method steps comprising;

(a) adding new bins "m" times to a database storage initially containing n₀ bins, wherein "m" is a natural number, and then initially defining an index counter variable "j" to be equal to "m";

(b) defining a variable "y" to be the bucket identification "x" modulo n_j ;

(c) determining whether the variable "y" is at least equal to n_j-1, and if so, defining the variable "y" to be the bin identification of the bucket having the bucket identification "x" and otherwise decrementing the index counter variable "j" by an integer number and repeating steps (b) and (c); and

(d) subsequently accessing the bucket using the variable "y" as the relevant bin identification.

12. The computer program device of claim 11, wherein the database contains "B" buckets, wherein an integer "k" is defined to be the number of new bins added in step (a), and wherein the method steps further comprise:

(e) moving buckets to bins and mapping the buckets to the bins using steps (a)-(c).

13. The computer program device of claim 12, wherein the data records are clustered and accessible by bucket identification, and the method step (e) further comprises the steps of:

(f) for each of the "n" existing bins, wherein "n" is a natural number, entering a do loop for an index counter variable "i"=0 to (B-1);

(g) determining whether the i^th bucket is in the bin, and if so, setting an index counter variable "j" to be the index counter variable "i" modulo the sum of "n" and "k"; and

(h) when the index counter variable "j" is at least as great as "n", moving the i^th bucket to the j^th bin, and otherwise not moving the i^th bucket.

14. The computer program device of claim 12, wherein the data records are not clustered or are not accessible by bucket identification, and the method step (e) further comprises the steps of:

(f) for each of the "n" existing bins, wherein "n" is a natural number, and for each data record in the bin, defining an index counter variable "j" to be the bucket identification "x" associated with the data record modulo the sum of "n" and "k";

(g) determining whether the index counter variable "j" is at least as great as "n", and if so, moving the record to the j^th bin, and otherwise not moving the record to the j^th bin.

15. The computer program device of claim 11, wherein the database storage includes "n" bins, wherein "n" is a natural number, the database storage includes "B" buckets and the buckets are assigned to the bins using a mapping characterized by a defining sequence of integers, and wherein the method steps further comprise:

determining whether new bins have been added to the database storage, and if so, appending "n" to the defining sequence;

determining whether the difference between the size of the largest bin and the ceiling of the quotient "B"/"n" exceeds a predetermined difference, and if not, returning the defining sequence with "n" appended thereto as a new defining sequence, and otherwise;

determining whether "n" is a power of two, and if so, returning "n" as the new defining sequence, and otherwise returning the sequence of integers (2ⁱ, n) as the new defining sequence, wherein "i" equals the integer portion of the logarithm of "n".

16. The computer program device of claim 15, wherein "i" equals the logarithm to the base (2) of "n".

17. The computer program device of claim 15, in combination with the digital computer.

18. In a computer database storage divided into a plurality of bins, in which buckets map data to bins, a computer-implemented bucket-to-bin mapping method characterized by a sequence of numbers, wherein the sequence is smaller in size than a stored directory having a bin identification or location for every bucket in the database, the method including:

adding new bins to the plurality of bins;

maintaining an even distribution of buckets to bins after each new bin addition, without requiring movement of data between bins other than populating new bins and without storing the bin identification or location for every bucket; and

,

populating "k" newly added bins in the database storage with records of the database partitioned among "n" preexisting bins, each record having a bucket identification signifying a bin, and moving a record to a newly added bin if the record'"'"'s bucket identification modulo the sum of "n" and "k" signifies the newly added bin;

wherein the records are clustered in the database storage and accessible by respective logical bucket identifications, and the method further comprises;

for each of "n" existing bins, wherein "n" is a natural number, entering a do loop for an index counter variable "i"=0 to (B-1), wherein the database storage includes "B" buckets;

determining whether the i^th bucket is in the bin, and if so, setting an index counter variable "j" to be the index counter variable "i" modulo the sum of "n" and "k"; and

when the index counter variable "j" is at least as great as "n", moving the i^th bucket to the j^th bin, and otherwise not moving the i^th bucket.

19. In a computer database storage divided into a plurality of bins, in which buckets map data to bins, a computer-implemented bucket-to-bin mapping method characterized by a sequence of numbers, wherein the sequence is smaller in size than a stored directory having a bin identification or location for every bucket in the database, the method including:

adding new bins to the plurality of bins;

maintaining an even distribution of buckets to bins after each new bin addition, without requiring movement of data between bins other than populating new bins and without storing the bin identification or location for every bucket; and

,

populating "k" newly added bins in the database storage with records of the database partitioned among "n" preexisting bins, each record having a bucket identification signifying a bin, and moving a record to a newly added bin if the record'"'"'s bucket identification modulo the sum of "n" and "k" signifies the newly added bin;

wherein the records are not clustered or are not accessible by bucket identification, and the method further comprises;

for each of "n" existing bins, wherein "n" is a natural number, and for each record in the bin, defining an index counter variable "j" to be the bucket identification "x" associated with the record modulo the sum of "n" and "k";

determining whether the index counter variable "j" is at least as great as "n", and if so, moving the record to the j^th bin, and otherwise not moving the record to the j^th bin.

20. In a computer database storage divided into a plurality of bins, in which buckets map data to bins, a computer-implemented bucket-to-bin mapping method characterized by a sequence of numbers, wherein the sequence is smaller in size than a stored directory having a bin identification or location for every bucket in the database, the method including:

adding new bins to the plurality of bins;

maintaining an even distribution of buckets to bins after each new bin addition, without requiring movement of data between bins other than populating new bins and without storing the bin identification or location for every bucket; and

,

populating "k" newly added bins in the database storage with records of the database partitioned among "n" preexisting bins, each record having a bucket identification signifying a bin, and moving a record to a newly added bin if the record'"'"'s bucket identification modulo the sum of "n" and "k" signifies the newly added bin;

wherein the database storage initially includes n₀ bins, and the method further comprises;

(a) adding new bins "m" times to the database storage, wherein "m" is a natural number, and then initially defining an index counter variable "j" to be equal to "m";

(b) defining a variable "y" to be the bucket identification "x" modulo n_j ;

(c) determining whether the variable "y" is at least equal to n_j-1, and if so, defining the variable "y" to be the bin identification of the bucket having the bucket identification "x" and otherwise decrementing the index counter variable "j" by an integer number and repeating steps (b) and (c);

(d) subsequently accessing buckets using the variable "y" as the relevant bin identification;

(e) moving buckets to bins and mapping the buckets to the bins using steps (a)-(c).

21. The computer-implemented method of claim 20, wherein the database storage includes "n" bins, wherein "n" is a natural number, the database storage contains "B" buckets and the buckets are assigned to the bins using a mapping characterized by a defining sequence of integers, and wherein the method steps further comprise:

determining whether new bins have been added, and if so, appending "n" to the defining sequence;

determining whether the difference between the size of the largest bin and the ceiling of the quotient "B"/"n" exceeds a predetermined difference, and if not, returning the defining sequence with "n" appended thereto as a new defining sequence, and otherwise;

determining whether "n" is a power of two, and if so, returning "n" as the new defining sequence, and otherwise returning the sequence of integers (2ⁱ, n) as the new defining sequence, wherein "i" equals the integer portion of the logarithm of "n".

22. The computer-implemented method of claim 21, performed in a combination that includes the database storage.

23. The computer-implemented method of claim 22, wherein the combination includes a digital computer.