Patent US6026406A successfully refreshed from Google Patents.
US6026406A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Batch processing of updates to indexes
Assignee: Oracle International Corp
•
Filing: 1997-06-04
•
Granted: 2000-02-15
•
Expires: 2017-06-04
Abstract
Abstract A method and apparatus for batch processing of updates to indexes is provided. A plurality of index update records are generated that identify a plurality of index update operations to be made to an index. The plurality of index entry records are sorted and then applied, in an order that corresponds to the sort order, in batches to their respective indexes. As a result of performing batch processing of updates to indexes, the number of disk I/Os will be greatly reduced, freeing database system resources to perform other tasks. The overall efficiency of index maintenance is also improved, as is the recovery of the database system after a failure, resultant from an ordering of the index maintenance operations and a partial ordering of the persistent redo log file.
Inventors
- 👤 Wei Huang
- 👤 Gianfranco Putzolu
- 👤 William H. Waddington
- 👤 Jonathan D. Klein
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 19:06
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/23; G06F16/2308; G06F16/2336; G06F16/2343; G06F16/22; G06F16/2228; G06F16/2246; G06F16/2379; G06F16/2386; G06F11/00; G06F11/07; G06F11/14; G06F11/1471; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99937
Claims Analysis
Total Claims: 32
Claim 1
Independent Claim
86 words
A method for batch processing of updates to an index, the method comprising the steps of: generating a plurality of index update records that identify a plurality of index update operations to be made to said index; sorting said plurality of index update records; and applying said plurality of index update operations to said index in an order that corresponds to the order of said sorted plurality of index update record, said index update operations being applied in batches of two or more index update operations.
Claim 2
Independent Claim
86 words
A method for batch processing of updates to an index, the method comprising the steps of: generating a plurality of index update records that identify a plurality of index update operations to be made to said index; sorting said plurality of index update records; and applying said plurality of index update operations to said index in an order that corresponds to the order of said sorted plurality of index update record, said index update operations being applied in batches of two or more index update operations.
Claim 3
Dependent Claim
97 words
The method of claim 1, wherein said index is a B-tree, and wherein said step of applying said plurality of index update operations to said index further comprises the steps of: fetching an index update record from said sorted plurality of index update records; retrieving a key value from said index update record; traversing said B-tree based on said key value to find a target leaf node; storing said index update record in an update buffer; and performing an index update operation based on said target leaf node and said index update record in said update buffer.
Claim 4
Dependent Claim
95 words
The method of claim 2, wherein said method further comprises the steps of: fetching a next index update record; retrieving a next key value from said next index update record; comparing said next key value with a plurality of boundary values associated with said target leaf node; if said next key value does not fall within said plurality of boundary values, then traversing said B-tree based on said next key value; and if said next key value does fall within said target leaf node, then storing said next index update record in said update buffer.
Claim 5
Dependent Claim
79 words
The method of claim 2, wherein said method further comprises the steps of: testing said target leaf node for available storage space; if there is not enough storage space in said target leaf node to perform said index update operation, then splitting said target leaf node to create a new leaf node; and if there is enough room in said target leaf node to perform said index update operation, then storing said index update record in said update buffer.
Claim 6
Dependent Claim
31 words
The method of claim 2, wherein the method further comprises the step of creating a single redo log record for said plurality of index update operations applied from said update buffer.
Claim 7
Dependent Claim
84 words
The method of claim 1, wherein said index is a B-tree, and wherein said step of applying said plurality of index update operations to said index further comprises the steps of: fetching an index update record from said sorted plurality of index update records; retrieving a key value from said index update record; traversing said B-tree based on said key value to find a target leaf node; and performing an index update operation based on said target leaf node and said index update record.
Claim 8
Dependent Claim
98 words
The method of claim 6, wherein said method further comprises the steps of: fetching, a next index update record; retrieving a next key value from said next index update record; comparing said next key value with a plurality of boundary values associated with said target leaf node; if said next key value does not fall within said plurality of boundary values, then traversing said B-tree based on said next key value; and if said next key value does fall within said target leaf node, then performing a next index update operation based on said next index update record.
Claim 9
Dependent Claim
81 words
The method of claim 6, wherein said method further comprises the steps of: testing said target leaf node for available storage space; if there is not enough storage space in said target leaf node to perform said index update operation, then splitting said target leaf node to create a new leaf node; and if there is enough room in said target leaf node to perform said index update operation, then performing said index update operation based on said index update record.
Claim 10
Dependent Claim
32 words
The method of claim 1, wherein said step of sorting further comprises the step of sorting said plurality of index update records by a type of index update operation to be performed.
Claim 11
Dependent Claim
26 words
The method of claim 1, wherein said step of sorting further comprises the step of sorting said plurality of index update records by a key value.
Claim 12
Dependent Claim
29 words
The method of claim 1, wherein the method further comprises the step of creating a single redo log record for said plurality of-index update operations applied to said index.
Claim 13
Dependent Claim
29 words
The method of claim 1, wherein the method further comprises the step of performing a cost based analysis to determine whether to perform batch processing of updates to indexes.
Claim 14
Dependent Claim
99 words
A computer readable medium having stored thereon sequences of instructions for batch processing of updates to an index, said sequences of instructions including instructions for performing the steps of: generating a plurality of index update records that identify a plurality of index update operations to be made to said index; sorting said plurality of index update records; and applying said plurality of index update operations to said index in an order that corresponds to the order of said sorted plurality of index update records, said index update operations being performed in batches of two or more index update operations.
Claim 15
Dependent Claim
99 words
A computer readable medium having stored thereon sequences of instructions for batch processing of updates to an index, said sequences of instructions including instructions for performing the steps of: generating a plurality of index update records that identify a plurality of index update operations to be made to said index; sorting said plurality of index update records; and applying said plurality of index update operations to said index in an order that corresponds to the order of said sorted plurality of index update records, said index update operations being performed in batches of two or more index update operations.
Claim 16
Dependent Claim
99 words
The computer readable medium of claim 13, wherein said index is a B-tree, and wherein said step of applying said plurality of index update operations to said index further comprises the steps of: fetching an index update record; from said sorted plurality of index update records; retrieving a key value from said index update record; traversing said B-tree based on said key value to find a target leaf node; storing said index update record in an update buffer; and performing an index update operation based on said target leaf node and said index update record in said update buffer.
Claim 17
Dependent Claim
97 words
The computer readable medium of claim 14, wherein said method further comprises the steps of: fetching a next index update record; retrieving a next key value from said next index update record; comparing said next key value with a plurality of boundary values associated with said target leaf node; if said next key value does not fall within said plurality of boundary values, then traversing said B-tree based on said next key value; and if said next key value does fall within said target leaf node, then storing said next index update record in said update buffer.
Claim 18
Dependent Claim
81 words
The computer readable medium of claim 14, wherein said method further comprises the steps of: testing said target leaf node for available storage space; if there is not enough storage space in said target leaf node to perform said index update operation, then splitting said target leaf node to create a new leaf node; and if there is enough room in said target leaf node to perform said index update operation, then storing said index update record in said update buffer.
Claim 19
Dependent Claim
33 words
The computer readable medium of claim 14, wherein the method further comprises the step of creating a single redo log record for said plurality of index update operations applied from said update buffer.
Claim 20
Dependent Claim
81 words
The computer readable medium of claim 13, wherein said index is a B-tree, and wherein said step of applying said plurality of index update operations to said index further comprises the steps of: fetching an index update record from said sorted plurality of index update records; retrieving a key value from said index update record; traversing said B-tree based on said key value to find a target leaf node; and performing an index update operation based on said index update record.
Claim 21
Dependent Claim
100 words
The computer readable medium of claim 18 wherein said method further comprises the steps of: fetching a next index update record; retrieving a next key value from said next index update record; comparing said next key value with a plurality of boundary values associated with said target leaf node; if said next key value does not fall within said plurality of boundary values, then traversing said B-tree based on said next key value; and if said next key value does fall within said target leaf node, then performing a next index update operation based on said next index update record.
Claim 22
Dependent Claim
83 words
The computer readable medium of claim 18, wherein said method further comprises the steps of: testing said target leaf node for available storage space; if there is not enough storage space in said target leaf node to perform said index update operation, then splitting said target leaf node to create a new leaf node; and if there is enough room in said target leaf node to perform said index update operation, then performing said index update operation based on said index update record.
Claim 23
Dependent Claim
34 words
The computer readable medium of claim 13, wherein said step of sorting further comprises the step of sorting said plurality of index update records by a type of index update operation to be performed.
Claim 24
Dependent Claim
28 words
The computer readable medium of claim 13, wherein said step of sorting further comprises the step of sorting said plurality of index update records by a key value.
Claim 25
Dependent Claim
32 words
The computer readable medium of claim 13, wherein said method further comprises the step of creating a single redo log record for said plurality of index update operations applied to said index.
Claim 26
Dependent Claim
31 words
The computer readable medium of claim 13, wherein said method further comprises the step of performing a cost based analysis to determine whether to perform batch processing of updates to indexes.
Claim 27
Independent Claim
182 words
A method for batch processing of updates to an index, the method comprising the steps of: fetching an index update record from a sorted plurality of index update records; retrieving a key value from said index update record; traversing said index base upon said key value to a target leaf node, said key value being a value between two boundary values of said target leaf node; fetching a next index update record from said sorted plurality of index update records; retrieving a next key value from said next index update record; comparing said next key value to said two boundary values of said target leaf node; if said next key value does fall within said two boundary values, then repeating said step of fetching a next index update record; and if said next key value does not fall within said two boundary values, then applying a plurality of index update operations corresponding to two or more fetched index update records falling within said boundary values, and re-traversing said index based upon said next key value not falling within said two boundary values.
Claim 28
Independent Claim
182 words
A method for batch processing of updates to an index, the method comprising the steps of: fetching an index update record from a sorted plurality of index update records; retrieving a key value from said index update record; traversing said index base upon said key value to a target leaf node, said key value being a value between two boundary values of said target leaf node; fetching a next index update record from said sorted plurality of index update records; retrieving a next key value from said next index update record; comparing said next key value to said two boundary values of said target leaf node; if said next key value does fall within said two boundary values, then repeating said step of fetching a next index update record; and if said next key value does not fall within said two boundary values, then applying a plurality of index update operations corresponding to two or more fetched index update records falling within said boundary values, and re-traversing said index based upon said next key value not falling within said two boundary values.
Claim 29
Dependent Claim
71 words
The method of claim 25, further comprising the steps of; storing two or more of said sorted plurality of index update records in an update buffer; performing said plurality of index update operations from said two or more index update records stored in said update buffer to said index; generating a single redo log record to describe said plurality of index update operations performed from said update buffer to said index.
Claim 30
Dependent Claim
194 words
A computer readable medium having stored thereon sequences of instructions for batch processing of updates to an index, said sequence of instructions including instructions for performing the steps of: fetching an index update record from a sorted plurality of index update records; retrieving a key value form said index update record; transversing said index based upon said key value to a target leaf node, said key value being a value between two boundary values of said target leaf node; fetching a next index update record from said sorted plurality of index update records; retrieving a next key value from said next index update record; comparing said next key value to said two boundary values of said target leaf node; if said next key value does fall within said boundary values, then repeating said step of fetching a next index update record; and if said next key value does not fall within said two boundary values, then performing a plurality of index update operations corresponding to two or more fetched index update records falling within said boundary values, and re-traversing said index based upon said next key value not falling within said two boundary values.
Claim 31
Dependent Claim
194 words
A computer readable medium having stored thereon sequences of instructions for batch processing of updates to an index, said sequence of instructions including instructions for performing the steps of: fetching an index update record from a sorted plurality of index update records; retrieving a key value form said index update record; transversing said index based upon said key value to a target leaf node, said key value being a value between two boundary values of said target leaf node; fetching a next index update record from said sorted plurality of index update records; retrieving a next key value from said next index update record; comparing said next key value to said two boundary values of said target leaf node; if said next key value does fall within said boundary values, then repeating said step of fetching a next index update record; and if said next key value does not fall within said two boundary values, then performing a plurality of index update operations corresponding to two or more fetched index update records falling within said boundary values, and re-traversing said index based upon said next key value not falling within said two boundary values.
Claim 32
Dependent Claim
73 words
A computer readable medium of claim 27, further comprising the steps of; storing two or more of said sorted plurality of index update records in an update buffer; performing said plurality of index update operations from said two or more index update records stored in said update buffer to said index; generating a single redo log record to describe said plurality of index update operations performed from said update buffer to said index.
References Cited (Backward Citations)
US4933848A
Cited
US5276872A
Cited
US5717921A
Cited
US5288894A
Cited
US5563997A
Cited
US5758356A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-02-14 | 2003-08-16 | 2004-02-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-02-14 | 2007-08-16 | 2008-02-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-02-14 | 2011-08-16 | 2012-02-15 | $7700.00 | Window Closed / Lapsed |