US5675791A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for database load balancing
Assignee: International Business Machines Corp
•
Filing: 1996-08-07
•
Granted: 1997-10-07
•
Expires: 2016-08-07
Abstract
Abstract A method and system are provided for partitioning a database and for balancing the processing load among processing nodes in a data processing system. A database partition is stored at each node and a logical owner node is assigned to each partition. The logical owner becomes responsible for all database requests related to the corresponding partition. Techniques for optimally assigning logical owners to all partitions in a system are provided and are responsive to parameters such as the load at each node, the combined load of the system, and the total number of assignments allowed. Techniques are also provided to accomplish the transfer of partition ownership between processing nodes when multiple transactions related to the partition are simultaneously occurring.
Inventors
- 👤 Anupam Keshav Bhide
- 👤 Daniel Manuel Dias
- 👤 Ambuj Goyal
- 👤 Francis Nicholas Parr
- 👤 Joel Leonard Wolf
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 06:49
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/50; G06F9/5061; G06F16/00; G06F16/20; G06F16/27; G06F16/278; G06F9/5083; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99938; Y10S707/99951; Y10S707/99956
Claims Analysis
Total Claims: 32
Claim 1
Independent Claim
68 words
A method for partitioning a database in a data processing system, said method comprising the steps of: dividing the database into a plurality of data partitions, each of said plurality of data partitions having a physical owner associated therewith; and assigning to each of said plurality of data partitions a logical owner different from said physical owner, wherein said logical owner provides access to its corresponding data partition.
Claim 2
Independent Claim
68 words
A method for partitioning a database in a data processing system, said method comprising the steps of: dividing the database into a plurality of data partitions, each of said plurality of data partitions having a physical owner associated therewith; and assigning to each of said plurality of data partitions a logical owner different from said physical owner, wherein said logical owner provides access to its corresponding data partition.
Claim 3
Dependent Claim
52 words
The method of claim 1, wherein each physical owner comprises a physical processing node and each logical owner comprises a logical processing node, and wherein each of said plurality of data partitions corresponds to a physical processing node and each of said plurality of data partitions corresponds to a logical processing node.
Claim 4
Dependent Claim
46 words
The method of claim 2, further comprising the steps of: storing each of said plurality of data partitions at its corresponding physical processing node; and performing one or more database requests associated with each of said plurality of data partitions at its corresponding logical processing node.
Claim 5
Dependent Claim
42 words
The method of claim 3, wherein the step of performing comprises function shipping said one or more database requests associated with each of said plurality of data partitions to the logical processing node associated with each of said plurality of data partitions.
Claim 6
Dependent Claim
35 words
The method of claim 3, wherein the step of performing comprises I/O shipping blocks associated with one of said plurality of data partitions between its corresponding physical processing node and its corresponding logical processing node.
Claim 7
Dependent Claim
38 words
The method of claim 2, further comprising transferring ownership of one of said plurality of data partitions from said logical processing node corresponding to said one of said plurality of data partitions to a second logical processing node.
Claim 8
Dependent Claim
25 words
The method of claim 6, further comprising repeating the steps of assigning and transferring, thereby repeatedly balancing a processing load in said data processing system.
Claim 9
Dependent Claim
32 words
The method of claim 6, wherein the step of transferring comprises the step of maintaining one or more locks at one of said logical processing node and said second logical processing node.
Claim 10
Dependent Claim
39 words
The method of claim 8, further comprising the step of performing one or more subsequent transactions associated with said one of said plurality of data partitions at its corresponding second logical processing node subsequent to said step of transferring.
Claim 11
Dependent Claim
42 words
The method of claim 6, wherein the step of transferring comprises the steps of: maintaining a record of a transaction with interest in said one of said plurality of data partitions; and performing a two-phase commit cycle for said transaction with interest.
Claim 12
Dependent Claim
59 words
The method of claim 1, wherein one or more physical owners corresponds to said plurality of data partitions, and wherein one or more logical owners corresponds to said plurality of data partitions, and wherein said step of assigning comprises the step of: reassigning to one or more of the plurality of data partitions one or more next logical owners.
Claim 13
Dependent Claim
35 words
The method of claim 11, wherein said step of reassigning comprises reassigning to one or more of said plurality of data partitions one or more next logical owners according to at least one reassignment constraint.
Claim 14
Independent Claim
126 words
A method for balancing a processing load in a data processing system having a first physical processing node and a second physical processing node, said first physical processing node having a first data partition stored thereon and said second physical processing node having a second data partition stored thereon, said method comprising the steps of: assigning a first logical processing node to said first data partition, said first logical processing node performing one or more database requests using said first data partition; and reassigning to said first data partition a second logical processing node, said first logical processing node and said second logical processing node being different processing nodes, said second logical processing node performing one or more subsequent database requests using said first data partition.
Claim 15
Independent Claim
126 words
A method for balancing a processing load in a data processing system having a first physical processing node and a second physical processing node, said first physical processing node having a first data partition stored thereon and said second physical processing node having a second data partition stored thereon, said method comprising the steps of: assigning a first logical processing node to said first data partition, said first logical processing node performing one or more database requests using said first data partition; and reassigning to said first data partition a second logical processing node, said first logical processing node and said second logical processing node being different processing nodes, said second logical processing node performing one or more subsequent database requests using said first data partition.
Claim 16
Dependent Claim
31 words
The method of claim 13, wherein said step of reassigning comprises reassigning to said first data partition one or more second logical processing nodes according to at least one reassignment constraint.
Claim 17
Independent Claim
69 words
A system for partitioning a database in a data processing system, said system comprising: means for dividing the database into a plurality of data partitions, each of said plurality of data partitions having a physical owner associated therewith; and means for assigning to each of said plurality of data partitions a logical owner different from said physical owner, wherein said logical owner provides access to its corresponding data partition.
Claim 18
Independent Claim
69 words
A system for partitioning a database in a data processing system, said system comprising: means for dividing the database into a plurality of data partitions, each of said plurality of data partitions having a physical owner associated therewith; and means for assigning to each of said plurality of data partitions a logical owner different from said physical owner, wherein said logical owner provides access to its corresponding data partition.
Claim 19
Dependent Claim
52 words
The system of claim 15, wherein each physical owner comprises a physical processing node and each logical owner comprises a logical processing node, and wherein each of said plurality of data partitions corresponds to a physical processing node and each of said plurality of data partitions corresponds to a logical processing node.
Claim 20
Dependent Claim
47 words
The system of claim 16, further comprising: means for storing each of said plurality of data partitions at its corresponding physical processing node; and means for performing one or more database requests associated with each of said plurality of data partitions at its corresponding logical processing node.
Claim 21
Dependent Claim
43 words
The system of claim 17, wherein the performing means comprises means for function shipping said one or more database requests associated with each of said plurality of data partitions to the logical processing node associated with each of said plurality of data partitions.
Claim 22
Dependent Claim
36 words
The system of claim 17, wherein the performing means comprises means for I/O shipping blocks associated with one of said plurality of data partitions between its corresponding physical processing node and its corresponding logical processing node.
Claim 23
Dependent Claim
40 words
The system of claim 16, further comprising means for transferring ownership of one of said plurality of data partitions from said logical processing node corresponding to said one of said plurality of data partitions to a second logical processing node.
Claim 24
Dependent Claim
24 words
The system of claim 20, further comprising means for repeating assigning and transferring, thereby repeatedly balancing a processing load in said data processing system.
Claim 25
Dependent Claim
30 words
The system of claim 20, wherein the transferring means comprises means for maintaining one or more locks at one of said logical processing node and said second logical processing node.
Claim 26
Dependent Claim
36 words
The system of claim 22, further comprising means for performing one or more subsequent transactions associated with said one of said plurality of data partitions at its corresponding second logical processing node subsequent to said transferring.
Claim 27
Dependent Claim
42 words
The system of claim 20, wherein the transferring means comprises: means for maintaining a record of a transaction with interest in said one of said plurality of data partitions; and means for performing a two-phase commit cycle for said transaction with interest.
Claim 28
Dependent Claim
57 words
The system of claim 15, wherein one of more physical owners corresponds to said plurality of data partitions, and wherein one or more logical owners corresponds to said plurality of data partitions, and wherein said assigning means comprises: means for reassigning to one or more of the plurality of data partitions one or more next logical owners.
Claim 29
Dependent Claim
36 words
The system of claim 25, wherein said reassigning means comprises means for reassigning to one or more of said plurality of data partitions one or more next logical owners according to at least one reassignment constraint.
Claim 30
Independent Claim
127 words
A system for balancing a processing load in a data processing system having a first physical processing node and a second physical processing node, said first physical processing node having a first data partition stored thereon and said second physical processing node having a second data partition stored thereon, said system comprising: means for assigning a first logical processing node to said first data partition, said first logical processing node performing one or more database requests using said first data partition; and means for reassigning to said first data partition a second logical processing node, said first logical processing node and said second logical processing node being different processing nodes, said second logical processing node performing one or more subsequent database requests using said first data partition.
Claim 31
Independent Claim
127 words
A system for balancing a processing load in a data processing system having a first physical processing node and a second physical processing node, said first physical processing node having a first data partition stored thereon and said second physical processing node having a second data partition stored thereon, said system comprising: means for assigning a first logical processing node to said first data partition, said first logical processing node performing one or more database requests using said first data partition; and means for reassigning to said first data partition a second logical processing node, said first logical processing node and said second logical processing node being different processing nodes, said second logical processing node performing one or more subsequent database requests using said first data partition.
Claim 32
Dependent Claim
32 words
The system of claim 27, wherein said reassigning means comprises means for reassigning to said first data partition one or more second logical processing nodes according to at least one reassignment constraint.
References Cited (Backward Citations)
US5089956A
Cited
US4920487A
Cited
US5131087A
Cited
US5485610A
Cited
US5317728A
Cited
US5355475A
Cited
US5269013A
Cited
US5333315A
Cited
US5440727A
Cited
US5457793A
Cited
US5506986A
Cited
US5423018A
Cited
US5499354A
Cited
US5440737A
Cited
US5551020A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-10-06 | 2001-04-07 | 2001-10-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-10-06 | 2005-04-07 | 2005-10-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-10-06 | 2009-04-07 | 2009-10-07 | $7700.00 | Window Closed / Lapsed |