US5884307A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Updating bitmapped indexes
Assignee: Oracle International Corp
•
Filing: 1997-02-28
•
Granted: 1999-03-16
•
Expires: 2017-02-28
Abstract
Abstract A method and apparatus for updating a segmented bitmapped index to reflect a change made to data upon which the segmented index is based. Change records specifying changes to bitmap segments contained in the segmented bitmapped index are sorted by key value (bitmap segment) and row ID (bit) before being applied to the segmented bitmapped index. When the change records are being applied to the bitmap segment contained in the segmented bitmapped index, the index entry containing the bitmap segment to be updated is locked. If a new bitmap segment must be generated, the index entry covering a row in the data having a row ID less than the row ID of the change is first locked. Then a new index entry is generated, stored in the segmented bitmapped index, and the locked index entry unlocked. If the segmented bitmapped index does not contain an index entry covering a row in the data having a row ID less than the row ID of the change, then a dummy index entry is generated, stored in the segmented bitmapped index, and locked. A new index entry is then generated and stored in the segmented bitmapped index, after which the dummy index entry is unlocked and deleted.
Inventors
- 👤 Michael Depledge
- 👤 Hakan Jakobsson
- 👤 Cetin Ozbutun
- 👤 Jeffrey I. Cohen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 06:55
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99935; Y10S707/99937; Y10S707/99941; Y10S707/99943
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
162 words
A method for updating a bitmapped index to reflect a change made to data upon which the bitmapped index is based, the method comprising the steps of: (a) sorting by key value and row ID a plurality of change records that reflect the change made to the data, the key value and row ID identifying bitmap segments contained in the bitmapped index to be updated, the plurality of change records reflecting the change made to the data, the plurality of change records further corresponding to the bitmap represented in the bitmapped index; and (b) applying in order the sorted plurality of change records to the bitmap represented in the bitmapped index by (i) locking a bitmapped index entry containing a bitmap segment corresponding to the change made to data; (ii) flipping a bitmap bit in the bitmapped index specified by the key value and row ID contained in the sorted plurality of change records; and (iii) unlocking the locked bitmapped index entry.
Claim 2
Independent Claim
162 words
A method for updating a bitmapped index to reflect a change made to data upon which the bitmapped index is based, the method comprising the steps of: (a) sorting by key value and row ID a plurality of change records that reflect the change made to the data, the key value and row ID identifying bitmap segments contained in the bitmapped index to be updated, the plurality of change records reflecting the change made to the data, the plurality of change records further corresponding to the bitmap represented in the bitmapped index; and (b) applying in order the sorted plurality of change records to the bitmap represented in the bitmapped index by (i) locking a bitmapped index entry containing a bitmap segment corresponding to the change made to data; (ii) flipping a bitmap bit in the bitmapped index specified by the key value and row ID contained in the sorted plurality of change records; and (iii) unlocking the locked bitmapped index entry.
Claim 3
Dependent Claim
139 words
The method of claim 1, further comprising the step of if the bitmapped index does not contain an entry with a bitmap segment corresponding to the changed data, then performing the steps of a) determining whether the bitmapped index contains an entry with a bitmap segment corresponding to a row number in the changed data which is less than a row number of the change, b) if the bitmapped index contains an entry with a bitmap segment preceding the key and row number in the changed data, then locking the preceding index entry, and c) if the bitmapped index does not contain an entry preceding the key and row number to be changed, i) creating a dummy bitmapped index entry, ii) storing the dummy bitmapped index entry in the bitmapped index, and iii) locking the dummy bitmapped index entry.
Claim 4
Independent Claim
87 words
A method for updating a bitmapped index to reflect a change made to data upon which the bitmapped index is based, the method comprising the steps of: sorting a plurality of change records based upon a bitmap represented in the bitmapped index, the plurality of change records reflecting the change made to the data, the plurality of change records further corresponding to the bitmap represented in the bitmapped index; and applying in order the sorted plurality of change records to the bitmap represented in the bitmapped index.
Claim 5
Independent Claim
87 words
A method for updating a bitmapped index to reflect a change made to data upon which the bitmapped index is based, the method comprising the steps of: sorting a plurality of change records based upon a bitmap represented in the bitmapped index, the plurality of change records reflecting the change made to the data, the plurality of change records further corresponding to the bitmap represented in the bitmapped index; and applying in order the sorted plurality of change records to the bitmap represented in the bitmapped index.
Claim 6
Dependent Claim
41 words
The method of claim 3, further comprising the step of sorting the plurality of change records based upon bits contained in the bitmap represented in the bitmapped index, each bit corresponding to the location of the change made to the data.
Claim 7
Dependent Claim
59 words
The method of claim 3, wherein the step of sorting the plurality of change records based upon a bitmap represented in the bitmapped index further comprises the step of sorting the plurality of change records based upon key values and row IDs, the key values and row IDs identifying bitmap segments contained in the bitmapped index to be updated.
Claim 8
Dependent Claim
55 words
The method of claim 5, wherein the step of applying in order the sorted plurality of change records to the bitmap represented in the bitmapped index further comprises the step of flipping a bitmap bit in the bitmapped index specified by the key value and row ID contained in the sorted plurality of change records.
Claim 9
Dependent Claim
80 words
The method of claim 3, wherein the step of applying in order the sorted plurality of change records to the bitmap represented in the bitmapped index further comprises the step of applying in order the sorted plurality of change records to bitmap segments contained in the bitmapped index and wherein the method further comprises the steps of locking a bitmapped index entry containing a bitmap segment corresponding to the change made to data, and unlocking the locked bitmapped index entry.
Claim 10
Dependent Claim
181 words
The method of claim 7, further comprising the step of if the bitmapped index does not contain an entry with a bitmap segment corresponding to the changed data, then performing the steps of determining whether the bitmapped index contains an entry with a bitmap segment corresponding to a row number in the changed data which is less than a row number of the change, if the bitmapped index contains an entry with a bitmap segment corresponding to a row number in the changed data which is less than the row number of the change, then locking the bitmapped index entry with a bitmap corresponding to a row number in the changed data which is less than the row number of the change, and if the bitmapped index does not contain an entry with a bitmap segment corresponding to a row number in the changed data which is less than the row number of the change, i) creating a dummy bitmapped index entry, ii) storing the dummy bitmapped index entry in the bitmapped index, and iii) locking the dummy bitmapped index entry.
Claim 11
Dependent Claim
104 words
A computer-readable medium carrying one or more sequences of one or more instructions, the one or more sequences of one or more instructions including instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of: sorting a plurality of change records based upon a bitmap represented in the bitmapped index, the plurality of change records reflecting the change made to the data, the plurality of change records further corresponding to the bitmap represented in the bitmapped index; and applying in order the sorted plurality of change records to the bitmap represented in the bitmapped index.
Claim 12
Dependent Claim
104 words
A computer-readable medium carrying one or more sequences of one or more instructions, the one or more sequences of one or more instructions including instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of: sorting a plurality of change records based upon a bitmap represented in the bitmapped index, the plurality of change records reflecting the change made to the data, the plurality of change records further corresponding to the bitmap represented in the bitmapped index; and applying in order the sorted plurality of change records to the bitmap represented in the bitmapped index.
Claim 13
Dependent Claim
45 words
The computer-readable medium of claim 9, wherein the computer-readable medium further includes instructions for sorting the plurality of change records based upon bits contained in the bitmap represented in the bitmapped index, each bit corresponding to the location of the change made to the data.
Claim 14
Dependent Claim
62 words
The computer-readable medium of claim 9, wherein the instructions for sorting the plurality of change records based upon a bitmap represented in the bitmapped index further include instructions for sorting the plurality of change records based upon a key value and a row ID, the key value and the row ID identifying bitmap segments contained in the bitmapped index to be updated.
Claim 15
Dependent Claim
55 words
The computer-readable medium of claim 11, wherein the instructions for applying in order the sorted plurality of change records to the bitmap represented in the bitmapped index further include instructions for flipping a bitmap bit in the bitmapped index specified by the key value and row ID contained in the sorted plurality of change records.
Claim 16
Dependent Claim
82 words
The computer-readable medium of claim 9, wherein the instructions for applying in order the sorted plurality of change records to the bitmap represented in the bitmapped index further include instructions for applying in order the sorted plurality of change records to bitmap segments contained in the bitmapped index and wherein the computer-readable medium further includes instructions for a) locking a bitmapped index entry containing a bitmap segment corresponding to the change made to data, and b) unlocking the locked bitmapped index entry.
Claim 17
Dependent Claim
205 words
The computer-readable medium of claim 13, wherein the instructions for applying in order the sorted plurality of change records to the bitmap represented in the bitmapped index further include instructions for if the bitmapped index does not contain an entry with a bitmap segment corresponding to the changed data, then performing the steps of a) determining whether the bitmapped index contains an entry with a bitmap segment corresponding to a row number in the changed data which is less than a row number of the change, b) if the bitmapped index contains an entry with a bitmap segment corresponding to a row number in the changed data which is less than the row number of the change, then locking the bitmapped index entry with a bitmap corresponding to a row number in the changed data which is less than the row number of the change, and c) if the bitmapped index does not contain an entry with a bitmap segment corresponding to a row number in the changed data which is less than the row number of the change, i) creating a dummy bitmapped index entry, ii) storing the dummy bitmapped index entry in the bitmapped index, and iii) locking the dummy bitmapped index entry.
Claim 18
Independent Claim
94 words
A method for updating a segmented bitmapped index to reflect a change made to data upon which the segmented bitmapped index is based, the method comprising the steps of: receiving a plurality of change records specifying changes to bitmap segments contained in the segmented bitmapped index; sorting the plurality of change records based upon the order of the bitmap segments contained in the segmented bitmapped index to generate a sorted plurality of change records; and applying in order the sorted plurality of change records to the bitmap segments contained in the segmented bitmapped index.
Claim 19
Independent Claim
94 words
A method for updating a segmented bitmapped index to reflect a change made to data upon which the segmented bitmapped index is based, the method comprising the steps of: receiving a plurality of change records specifying changes to bitmap segments contained in the segmented bitmapped index; sorting the plurality of change records based upon the order of the bitmap segments contained in the segmented bitmapped index to generate a sorted plurality of change records; and applying in order the sorted plurality of change records to the bitmap segments contained in the segmented bitmapped index.
Claim 20
Dependent Claim
49 words
The method of claim 15, wherein the plurality of change records further specify changes to bits in the bitmap segments and wherein the method further comprises the step of sorting the plurality of change records based upon the bits in the bitmap segments contained in the segmented bitmapped index.
Claim 21
Dependent Claim
59 words
The method of claim 15, wherein the plurality of change records specify key values and row IDs and wherein the step of sorting the plurality of change records based upon the order of bitmap segments contained in the segmented bitmapped index further comprises the step of sorting the plurality of change records based upon key value and row ID.
Claim 22
Dependent Claim
122 words
The method of claim 15, wherein the step of applying in order the sorted plurality of change records to the segmented bitmapped index further comprises the steps of selecting one of the plurality of change records; determining whether the selected change record specifies a change to a bitmapped segment contained in the bitmapped index; if the selected change record specifies a change to a bitmap segment contained in the segmented bitmapped index, then performing the steps of i) locking a bitmapped index entry containing the bitmap segment specified by the selected change record, ii) flipping a bit in the bitmap segment contained in the locked bitmapped index entry specified by the selected change record, and iii) unlocking the locked bitmapped index entry.
Claim 23
Dependent Claim
256 words
The method of claim 18, further comprising the step of if the selected change record does not specify a change to a bitmap segment contained in the segmented bitmapped index, then performing the steps of i) determining whether the bitmapped index contains a bitmap segment corresponding to a row in the change made to data having a row ID less than the row ID of the change, ii) if the bitmapped index contains a bitmap segment corresponding to a row in the changed data having a row ID less than the row ID of the change, then performing the steps of locking the bitmapped index entry containing the bitmap segment corresponding to a row in the changed data having a row ID less than the row ID of the change, generating a new bitmapped index entry reflecting the change contained in the selected change record, and unlocking the bitmapped index entry containing the bitmap segment corresponding to a row in the changed data having a row ID less than the row ID of the change, and iii) if the bitmapped index does not contain a bitmap segment corresponding to a row in the changed data having a row ID less than the row ID of the change, then performing the steps of creating a dummy bitmapped index entry, storing the dummy bitmapped index entry in the bitmapped index, locking the dummy bitmapped index entry, generating a new bitmapped index entry reflecting the change contained in the selected change record, and unlocking the dummy bitmapped index entry.
Claim 24
Dependent Claim
125 words
A computer system for updating a bitmapped index to reflect a change made to data upon which the bitmapped index is based, the computer system comprising: one or more processors; and a memory coupled to the one or more processors, the memory comprising: a) a first set of data of a first type, the first set of data specifying a bitmap segment contained in the bitmapped index to be updated; and b) a second set of data of a second type, the second set of data specifying a change to the bitmap segment specified by the first set of data, which, when applied to the bitmap segment, causes the bitmapped index to reflect a change made to data upon which the bitmapped index is based.
Claim 25
Dependent Claim
125 words
A computer system for updating a bitmapped index to reflect a change made to data upon which the bitmapped index is based, the computer system comprising: one or more processors; and a memory coupled to the one or more processors, the memory comprising: a) a first set of data of a first type, the first set of data specifying a bitmap segment contained in the bitmapped index to be updated; and b) a second set of data of a second type, the second set of data specifying a change to the bitmap segment specified by the first set of data, which, when applied to the bitmap segment, causes the bitmapped index to reflect a change made to data upon which the bitmapped index is based.
Claim 26
Dependent Claim
110 words
The computer system of claim 20, wherein the bitmapped index is a segmented bitmapped index built upon a key and wherein the first set of data further specifies a key value associated with a bitmap segment contained in the segmented bitmapped index to be updated, and wherein the second set of data specifies a row ID corresponding to both a row in the data upon which the segmented bitmapped index is based and a bit in the bitmap segment specified by the first set of data which when flipped, causes the segmented bitmapped index to reflect the change made to the data upon which the segmented bitmapped index is based.
References Cited (Backward Citations)
US5283894A
Cited
US5495608A
Cited
US5649181A
Cited
US5560007A
Cited
US5666528A
Cited
US5619226A
Cited
US5682179A
Cited
US5694149A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-03-15 | 2002-09-14 | 2003-03-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-03-15 | 2006-09-14 | 2007-03-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-03-15 | 2010-09-14 | 2011-03-16 | $7700.00 | Window Closed / Lapsed |