Patent US6438562B1 successfully refreshed from Google Patents.
US6438562B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Parallel index maintenance
Assignee: Oracle International Corp
•
Filing: 1999-08-24
•
Granted: 2002-08-20
•
Expires: 2019-08-24
Abstract
Abstract A method, system and product for coordinating a parallel update for a global index of an indexed table involves a coordinator process and slave processes. The coordinator process receives index maintenance records from data manipulation slaves for an indexed table. Each index maintenance record includes a value for an index key of a global index of the table. The coordinator process computes index key value ranges and sends each range to an index update slave. Each slave updates the global index using just the index maintenance records with key values in its respective range, thus avoiding contention among the slaves and increasing clustering so that scaleable parallelism may be more closely attained. Techniques are also described for deferring the maintenance of global indexes relative to the time when the table on which they are built is changed.
Inventors
- 👤 Shivani Gupta
- 👤 William H. Waddington
- 👤 Benoit Dageville
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 23:13
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; G06F16/2228; G06F16/2272; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99952; Y10S707/99953
Claims Analysis
Total Claims: 55
Claim 1
Independent Claim
117 words
A method for coordinating an update to a global index of an indexed table, the method comprising the steps of: receiving index maintenance records from a plurality of data manipulation slaves for the indexed table, wherein each index maintenance record includes a value for an index key of the global index; computing a plurality of ranges for values of the index key received in the index maintenance records; assigning each range of the plurality of ranges to a respective index update slave of a plurality of index update slaves; and distributing work associated with said update to said plurality of index update slaves based on the plurality of ranges assigned to said plurality of index update slaves.
Claim 2
Independent Claim
117 words
A method for coordinating an update to a global index of an indexed table, the method comprising the steps of: receiving index maintenance records from a plurality of data manipulation slaves for the indexed table, wherein each index maintenance record includes a value for an index key of the global index; computing a plurality of ranges for values of the index key received in the index maintenance records; assigning each range of the plurality of ranges to a respective index update slave of a plurality of index update slaves; and distributing work associated with said update to said plurality of index update slaves based on the plurality of ranges assigned to said plurality of index update slaves.
Claim 3
Dependent Claim
61 words
The method of claim 1 , wherein: the index maintenance records cover a plurality of global indexes associated with said indexed table; each index maintenance record includes an index identification that identifies a particular index of said plurality of global indexes; and the step of computing the plurality of ranges is performed for each index of said plurality of global indexes.
Claim 4
Dependent Claim
55 words
The method of claim 1 , wherein the step of computing the plurality of ranges further comprises: sampling a set of the index maintenance records, wherein a number of records sampled is a sample size; and determining said plurality of ranges based upon index key values contained in said set of the index maintenance records.
Claim 5
Dependent Claim
95 words
The method of claim 3 , wherein the step of determining said plurality of ranges includes: determining a number of index update slaves, wherein the number of index update slaves is an index update degree of parallelism; sorting values of the index key in the set of the index maintenance records sampled; and defining a range using an index key value at a specified position of the values of the index key after sorting, wherein the specified position is related to a multiple of the sample size divided by the index update degree of parallelism.
Claim 6
Dependent Claim
27 words
The method of claim 4 , wherein, during the sampling, the sample size equals a total number of records received from said plurality of data manipulation slaves.
Claim 7
Dependent Claim
32 words
The method of claim 4 , wherein, during the sampling, the sample size is a specified quantity less than a total number of records received from said plurality of data manipulation slaves.
Claim 8
Dependent Claim
42 words
The method of claim 4 , wherein the specified position is also related to an affinity of the respective index update slave for leaf blocks in the global index, the leaf blocks containing the values of the index key in the range.
Claim 9
Dependent Claim
48 words
The method of claim 1 , the distributing further comprising: generating an index distribution table including a range and a slave identification for each range of the plurality of ranges; and replicating the index distribution table for each index update slave of the plurality of index update slaves.
Claim 10
Dependent Claim
42 words
The method of claim 8 , wherein the index distribution table includes an index identification associated with each range, wherein the index identification identifies which global index, of a plurality of global indexes built on said table, is associated with said range.
Claim 11
Dependent Claim
46 words
The method of claim 8 , further comprising, before the replicating, revising the index update distribution table based on an affinity of a respective index update slave for leaf blocks in the global index, the leaf blocks containing values of the index key in the range.
Claim 12
Dependent Claim
24 words
The method of claim 1 , further comprising, before receiving index maintenance records, distributing data manipulation operations among the plurality of data manipulation slaves.
Claim 13
Dependent Claim
29 words
The method of claim 11 , wherein the data manipulation operations are distributed based on partitions formed using a key other than the index key of said global index.
Claim 14
Dependent Claim
68 words
The method of claim 11 , wherein: the step of distributing data manipulation operations is performed by distributing data manipulation operations to a first number of data manipulation slaves; the step of distributing work associated with said update to said plurality of index update slaves is performed by distributing work to a second number of index update slaves; and the first number does not equal the second number.
Claim 15
Independent Claim
72 words
A method for updating a global index of an indexed table comprising: receiving data that identifies a value range, where the value range defines a range of values for an index key of the global index of the indexed table; reading an index key value from a current index maintenance record; and updating the global index using the current index maintenance record if the index key value falls within the value range.
Claim 16
Independent Claim
72 words
A method for updating a global index of an indexed table comprising: receiving data that identifies a value range, where the value range defines a range of values for an index key of the global index of the indexed table; reading an index key value from a current index maintenance record; and updating the global index using the current index maintenance record if the index key value falls within the value range.
Claim 17
Dependent Claim
65 words
The method of claim 14 , wherein said indexed table has a plurality of global indexes, the method further including: receiving an index identification associated with the value range; reading a current index identification from the current index maintenance record; and based on the current index identification, identifying which global index of the plurality of global indexes to update using said current index maintenance record.
Claim 18
Dependent Claim
193 words
The method of claim 14 wherein: a plurality of index update slaves is used to update said global index; each index update slave of said plurality of index update slaves has a slave identification; the steps of receiving data that identifies the value range, reading the index key value, and updating the global index, are performed by a particular index update slave of said plurality of index update slaves; the particular index update slave has a particular slave identification; the step of receiving data that identifies the value range includes receiving an index update distribution table from a coordinator process, wherein the index update distribution table maps value ranges for the index key of the global index to slave identifications; the method further includes the particular index update slave performing the steps of: locating the range in the index update distribution table that encompasses the index key value read from the current index maintenance record; determining if a slave identification associated with the range located corresponds to the particular slave identification; and if the slave identification corresponds to the particular slave identification, then updating the global index using the current index maintenance record.
Claim 19
Dependent Claim
35 words
The method of claim 16 , further comprising, if the slave identification does not correspond to the particular slave identification, then sending the current index maintenance record to a slave corresponding to the slave identification.
Claim 20
Dependent Claim
74 words
The method of claim 16 , wherein: the indexed table has a plurality of global indexes; the index update distribution table includes an index identification associated with each range; the method further comprises reading a current index identification from the current index maintenance record; and during said updating the global index, the particular index update slave determines which global index of the plurality of global indexes to update based on the current index identification.
Claim 21
Independent Claim
133 words
A method of parallelizing a data manipulation operation on an indexed table, the method comprising the steps of: based on a first partitioning criteria, dividing said data manipulation operation into a first set of work granules; distributing said first set of work granules to a first set of slaves; based on a second partitioning criteria, dividing a task of changing one or more indexes built on said indexed table into a second set of work granules; and distributing said second set of work granules to a second set of slaves; wherein said task of changing said one or more indexes includes updating said one or more indexes to reflect changes made to said indexed table by said data manipulation operation; and wherein said first partitioning criteria is different than said second partitioning criteria.
Claim 22
Independent Claim
133 words
A method of parallelizing a data manipulation operation on an indexed table, the method comprising the steps of: based on a first partitioning criteria, dividing said data manipulation operation into a first set of work granules; distributing said first set of work granules to a first set of slaves; based on a second partitioning criteria, dividing a task of changing one or more indexes built on said indexed table into a second set of work granules; and distributing said second set of work granules to a second set of slaves; wherein said task of changing said one or more indexes includes updating said one or more indexes to reflect changes made to said indexed table by said data manipulation operation; and wherein said first partitioning criteria is different than said second partitioning criteria.
Claim 23
Dependent Claim
22 words
The method of claim 19 wherein the task of changing one or more indexes is divided based on index key value ranges.
Claim 24
Dependent Claim
20 words
The method of claim 19 wherein the first set of slaves is not identical to said second set of slaves.
Claim 25
Dependent Claim
23 words
The method of claim 21 wherein the first set of slaves includes a different number of slaves than said second set of slaves.
Claim 26
Dependent Claim
30 words
The method of claim 21 wherein the first set of slaves includes a slave running on a node that does not execute any slaves of said second set of slaves.
Claim 27
Dependent Claim
30 words
The method of claim 21 wherein the second set of slaves includes a slave running on a node that does not execute any slaves of said first set of slaves.
Claim 28
Dependent Claim
31 words
The method of claim 20 further comprising the step of establishing the index key value ranges based on a sampling of index maintenance records generated by said first set of slaves.
Claim 29
Dependent Claim
122 words
A computer-readable medium bearing instructions arranged to cause one or more processors to perform: receiving index maintenance records from a plurality of data manipulation slaves for an indexed table of a database, wherein each index maintenance record includes a value for an index key of a global index for the indexed table; computing a plurality of ranges for values of the index key received in the index maintenance records; assigning each range of the plurality of ranges to a respective index update slave of a plurality of index update slaves; and distributing work associated with an update of said global index to said plurality of index update slaves based on the plurality of ranges assigned to said plurality of index update slaves.
Claim 30
Dependent Claim
122 words
A computer-readable medium bearing instructions arranged to cause one or more processors to perform: receiving index maintenance records from a plurality of data manipulation slaves for an indexed table of a database, wherein each index maintenance record includes a value for an index key of a global index for the indexed table; computing a plurality of ranges for values of the index key received in the index maintenance records; assigning each range of the plurality of ranges to a respective index update slave of a plurality of index update slaves; and distributing work associated with an update of said global index to said plurality of index update slaves based on the plurality of ranges assigned to said plurality of index update slaves.
Claim 31
Dependent Claim
74 words
A computer-readable medium bearing instructions arranged to cause one or more processors to perform: receiving data that identifies a value range, where the value range defines a range of values for an index key of a global index of an indexed table; reading an index key value from a current index maintenance record; and updating the global index using the current index maintenance record if the index key value falls within the value range.
Claim 32
Dependent Claim
74 words
A computer-readable medium bearing instructions arranged to cause one or more processors to perform: receiving data that identifies a value range, where the value range defines a range of values for an index key of a global index of an indexed table; reading an index key value from a current index maintenance record; and updating the global index using the current index maintenance record if the index key value falls within the value range.
Claim 33
Dependent Claim
129 words
A computer-readable medium bearing instructions arranged to cause one or more processors to perform: based on a first partitioning criteria, dividing a data manipulation operation into a first set of work granules; distributing said first set of work granules to a first set of slaves; based on a second partitioning criteria, dividing a task of changing one or more indexes built on an indexed table into a second set of work granules; and distributing said second set of work granules to a second set of slaves; wherein said task of changing said one or more indexes includes updating said one or more indexes to reflect changes made to said indexed table by said data manipulation operation; and wherein said first partitioning criteria is different than said second partitioning criteria.
Claim 34
Dependent Claim
129 words
A computer-readable medium bearing instructions arranged to cause one or more processors to perform: based on a first partitioning criteria, dividing a data manipulation operation into a first set of work granules; distributing said first set of work granules to a first set of slaves; based on a second partitioning criteria, dividing a task of changing one or more indexes built on an indexed table into a second set of work granules; and distributing said second set of work granules to a second set of slaves; wherein said task of changing said one or more indexes includes updating said one or more indexes to reflect changes made to said indexed table by said data manipulation operation; and wherein said first partitioning criteria is different than said second partitioning criteria.
Claim 35
Dependent Claim
67 words
A computer-readable medium bearing information for use by one or more processors that are participating in execution of a global index update, the information comprising: an index maintenance record; the index maintenance record including an index identification that identifies a global index requiring change; and an index key value of the global index, the index key value indicating an index entry requiring change within the global index.
Claim 36
Dependent Claim
67 words
A computer-readable medium bearing information for use by one or more processors that are participating in execution of a global index update, the information comprising: an index maintenance record; the index maintenance record including an index identification that identifies a global index requiring change; and an index key value of the global index, the index key value indicating an index entry requiring change within the global index.
Claim 37
Dependent Claim
95 words
A computer-readable medium bearing information for use by one or more processors that are participating in execution of a global index update, the information comprising: an index update distribution record; wherein the index update distribution record includes data that identifies a range of values, wherein the range of values is for an index key of a global index of an indexed table; and a slave identification, wherein said slave identification identifies a slave responsible for performing updates to said global index for index entries associated with key values that fall within said range of values.
Claim 38
Dependent Claim
95 words
A computer-readable medium bearing information for use by one or more processors that are participating in execution of a global index update, the information comprising: an index update distribution record; wherein the index update distribution record includes data that identifies a range of values, wherein the range of values is for an index key of a global index of an indexed table; and a slave identification, wherein said slave identification identifies a slave responsible for performing updates to said global index for index entries associated with key values that fall within said range of values.
Claim 39
Dependent Claim
28 words
The computer-readable medium of claim 30 , the index update distribution record further comprising an index identification for indicating one global index of a plurality of global indexes.
Claim 40
Independent Claim
260 words
A system for maintaining a global index of a database in response to parallel data manipulation operations, the system comprising: a plurality of processing nodes; a network connecting the plurality of nodes; an indexed table having a global index based on an index key residing on at least one of the plurality of nodes; a coordinator process running on a first node of the plurality of nodes; a plurality of data manipulation slaves, each data manipulation slave on a respective node of the plurality of nodes; and a plurality of index update slaves, each index update slave on a respective node of the plurality of nodes; wherein, the coordinator process is configured to distribute data manipulation operations among the plurality of data manipulation slaves, to receive index maintenance records from the plurality of data manipulation slaves, each record including an index key value, to compute a plurality of ranges for values of the index key received in the index maintenance records, and to send each range of the plurality of ranges to a respective index update slave; wherein each data manipulation slave is configured to perform a data manipulation operation on a row of the database and to send an index maintenance record to the coordinator process; and wherein each index update slave is configured to receive a respective range of the plurality of ranges, to read an index key value from a current index maintenance record, and to update the global index using the current index maintenance record if the index key value falls within the range of values.
Claim 41
Independent Claim
260 words
A system for maintaining a global index of a database in response to parallel data manipulation operations, the system comprising: a plurality of processing nodes; a network connecting the plurality of nodes; an indexed table having a global index based on an index key residing on at least one of the plurality of nodes; a coordinator process running on a first node of the plurality of nodes; a plurality of data manipulation slaves, each data manipulation slave on a respective node of the plurality of nodes; and a plurality of index update slaves, each index update slave on a respective node of the plurality of nodes; wherein, the coordinator process is configured to distribute data manipulation operations among the plurality of data manipulation slaves, to receive index maintenance records from the plurality of data manipulation slaves, each record including an index key value, to compute a plurality of ranges for values of the index key received in the index maintenance records, and to send each range of the plurality of ranges to a respective index update slave; wherein each data manipulation slave is configured to perform a data manipulation operation on a row of the database and to send an index maintenance record to the coordinator process; and wherein each index update slave is configured to receive a respective range of the plurality of ranges, to read an index key value from a current index maintenance record, and to update the global index using the current index maintenance record if the index key value falls within the range of values.
Claim 42
Independent Claim
105 words
A method of using a global index of an indexed table comprising: executing a query using an index key for the global index to provide a query result; determining whether an out-of-date flag indicates the global index is not current; if the out-of-date flag indicates the global index is not current, then searching through a set of sorted index maintenance records, each record containing a value of an index key for the global index and an index operation; and modifying the query result according to an index maintenance record that includes an index key value that matches the index key value used in the query.
Claim 43
Independent Claim
105 words
A method of using a global index of an indexed table comprising: executing a query using an index key for the global index to provide a query result; determining whether an out-of-date flag indicates the global index is not current; if the out-of-date flag indicates the global index is not current, then searching through a set of sorted index maintenance records, each record containing a value of an index key for the global index and an index operation; and modifying the query result according to an index maintenance record that includes an index key value that matches the index key value used in the query.
Claim 44
Dependent Claim
111 words
A computer-readable medium bearing instructions arranged to cause one or more processors to perform: executing a query using an index key for a global index of an indexed table to provide a query result; determining whether an out-of-date flag indicates the global index is not current; if the out-of-date flag indicates the global index is not current, then searching through a set of sorted index maintenance records, each record containing a value of an index key for the global index and an index operation; and modifying the query result according to an index maintenance record that includes an index key value that matches the index key values used in the query.
Claim 45
Dependent Claim
111 words
A computer-readable medium bearing instructions arranged to cause one or more processors to perform: executing a query using an index key for a global index of an indexed table to provide a query result; determining whether an out-of-date flag indicates the global index is not current; if the out-of-date flag indicates the global index is not current, then searching through a set of sorted index maintenance records, each record containing a value of an index key for the global index and an index operation; and modifying the query result according to an index maintenance record that includes an index key value that matches the index key values used in the query.
Claim 46
Dependent Claim
168 words
A computer-readable medium bearing instructions arranged to cause one or more processors to perform: distributing data manipulation operations among a plurality of data manipulation slaves, receiving index maintenance records from the plurality of data manipulation slaves, each record including an index key value for a global index of an indexed table, computing a plurality of ranges for values of the index key received in the index maintenance records, and sending each range of the plurality of ranges to a respective index update slave among a plurality of index update slaves, by a coordinator process; performing a data manipulation operation on a row of the database and sending an index maintenance record to the coordinator process, by a data manipulation slave; and receiving a respective range of the plurality of ranges, reading an index key value from a current index maintenance record, and updating the global index using the current index maintenance record if the index key value falls within the range of values, by an index update slave.
Claim 47
Dependent Claim
168 words
A computer-readable medium bearing instructions arranged to cause one or more processors to perform: distributing data manipulation operations among a plurality of data manipulation slaves, receiving index maintenance records from the plurality of data manipulation slaves, each record including an index key value for a global index of an indexed table, computing a plurality of ranges for values of the index key received in the index maintenance records, and sending each range of the plurality of ranges to a respective index update slave among a plurality of index update slaves, by a coordinator process; performing a data manipulation operation on a row of the database and sending an index maintenance record to the coordinator process, by a data manipulation slave; and receiving a respective range of the plurality of ranges, reading an index key value from a current index maintenance record, and updating the global index using the current index maintenance record if the index key value falls within the range of values, by an index update slave.
Claim 48
Dependent Claim
48 words
The method of claim 1 , the distribution further comprising: generating an index distribution table including a range and a slave identification for each range of the plurality of ranges; and replicating the index distribution table for each data manipulation slave of the plurality of data manipulation slaves.
Claim 49
Dependent Claim
64 words
The method of claim 1 , wherein: the step of receiving index maintenance records further comprises inserting maintenance records into a buffer for the global index so the records are in order of increasing key value in the buffer; and the step of computing the plurality of ranges further comprises determining said plurality of ranges based upon index key values contained in said buffer.
Claim 50
Dependent Claim
94 words
The method of claim 37 , wherein the step of determining said plurality of ranges includes: determining a number of index update slaves, wherein the number of index update slaves is an index update degree of parallelism; determining a sample size equal to a number of index maintenance records in the buffer; and defining a range using an index key value in a index maintenance record at a specified position of the buffer, wherein the specified position is related to a multiple of the sample size divided by the index update degree of parallelism.
Claim 51
Dependent Claim
133 words
The method of claim 14 , wherein: a plurality of index update slaves is used to update said global index; each index update slave of said plurality of index update slaves has a slave identification; the step of receiving data that identifies the value range includes receiving an index update distribution table from a coordinator process, wherein the index update distribution table maps value ranges for the index key of the global index to slave identifications; and the method further comprises locating the range in the index update distribution table that encompasses the index key value read from the current index maintenance record, determining an slave identification associated with the range located, and sending the current index maintenance record to an index update slave corresponding to the slave identification associated with the range.
Claim 52
Dependent Claim
56 words
The computer-readable medium of claim 26 bearing instructions arranged to cause one or more processors to further perform: generating an index distribution table including a range and a slave identification for each range of the plurality of ranges; and replicating the index distribution table for each data manipulation slave of the plurality of data manipulation slaves.
Claim 53
Dependent Claim
65 words
The computer-readable medium of claim 26 , wherein: the step of receiving index maintenance records further comprises inserting maintenance records into a buffer for the global index so the records are in order of increasing key value in the buffer; and the step of computing the plurality of ranges further comprises determining said plurality of ranges based upon index key values contained in said buffer.
Claim 54
Dependent Claim
95 words
The computer-readable medium of claim 41 , wherein the step of determining said plurality of ranges includes: determining a number of index update slaves, wherein the number of index update slaves is an index update degree of parallelism; determining a sample size equal to a number of index maintenance records in the buffer; and defining a range using an index key value in a index maintenance record at a specified position of the buffer, wherein the specified position is related to a multiple of the sample size divided by the index update degree of parallelism.
Claim 55
Dependent Claim
143 words
The computer-readable medium of claim 27 , wherein: a plurality of index update slaves is used to update said global index; each index update slave of said plurality of index update slaves has a slave identification; the step of receiving data that identifies the value range includes receiving an index update distribution table from a coordinator process, wherein the index update distribution table maps value ranges for the index key of the global index to slave identifications; and the instructions are arranged to cause one or more processors to further perform locating the range in the index update distribution table that encompasses the index key value read from the current index maintenance record, determining an slave identification associated with the range located, and sending the current index maintenance record to an index update slave corresponding to the slave identification associated with the range.
References Cited (Backward Citations)
US5204958A
Cited
US5551027A
Cited
US5440732A
Cited
US5991771A
Cited
US5960194A
Cited
US6014656A
Cited
US5899988A
Cited
US6278992B1
Cited
US6026406A
Cited
US6092061A
Cited
US6249784B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-08-19 | 2006-02-18 | 2006-08-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-08-19 | 2010-02-18 | 2010-08-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-08-19 | 2014-02-18 | 2014-08-20 | $7700.00 | Window Closed / Lapsed |