US6067540A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Bitmap segmentation
Assignee: Oracle International Corp
•
Filing: 1997-02-28
•
Granted: 2000-05-23
•
Expires: 2017-02-28
Abstract
Abstract A method and apparatus for segmenting bitmaps in a bitmap index is provided. A segmented bitmap includes a plurality of bitmap segments that are used to indicate which records in a body of records that is associated with the segmented bitmap satisfy a particular criteria. Each bitmap segment contains a string of bits that correspond to a corresponding range of records in the body of records. There may be gaps between the ranges represented by the bitmap segments when, for example, the body of records does not contain records in a particular range. For the purposes of retrieval, compression, de-compression, locking and logging, the database system treats each bitmap segment as a distinct data item.
Inventors
- 👤 Cetin Ozbutun
- 👤 Jeffrey I. Cohen
- 👤 Hakan Jakobsson
- 👤 Mark Kremer
- 👤 Michael Depledge
- 👤 Quoc Tai Tran
- 👤 Alexander C. Ho
- 👤 Julian Hyde
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 02:55
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/20; G06F16/22; G06F16/2228; G06F16/2237; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934; Y10S707/99937
Claims Analysis
Total Claims: 38
Claim 1
Independent Claim
126 words
A method for indicating whether records in a body of data satisfy a particular criterion, the method comprising the steps of: establishing a plurality of ranges for identifiers assigned to records in said body of records; generating a plurality of bitmap segments that correspond to said plurality of ranges, wherein each bitmap segment includes data representing a sequence of bits that includes one bit for every record that has an identifier that falls within the range associated with said bitmap segment, wherein each bit in said sequence of bits is set to a value that indicates whether a record that corresponds to said bit satisfies said particular criterion; and storing data that indicates the range associated with each bitmap segment of said plurality of bitmap segments.
Claim 2
Independent Claim
126 words
A method for indicating whether records in a body of data satisfy a particular criterion, the method comprising the steps of: establishing a plurality of ranges for identifiers assigned to records in said body of records; generating a plurality of bitmap segments that correspond to said plurality of ranges, wherein each bitmap segment includes data representing a sequence of bits that includes one bit for every record that has an identifier that falls within the range associated with said bitmap segment, wherein each bit in said sequence of bits is set to a value that indicates whether a record that corresponds to said bit satisfies said particular criterion; and storing data that indicates the range associated with each bitmap segment of said plurality of bitmap segments.
Claim 3
Dependent Claim
96 words
The method of claim 1 further comprising the steps of: executing a transaction that affects whether a particular record in said body of records satisfies said particular criterion; determining which bitmap segment contains a bit that corresponds to said particular record; updating said bit in response to said transaction by performing the steps of obtaining a lock on the bitmap segment that contains said bit without obtaining a lock on the other of said plurality of bitmap segments; and after obtaining said lock, updating said bit to reflect whether said particular record satisfies said particular criterion.
Claim 4
Dependent Claim
103 words
The method of claim 1 further comprising the steps of: executing a transaction that affects whether a particular record in said body of records satisfies said particular criterion; determining which bitmap segment contains a bit that corresponds to said particular record; updating said bit in response to said transaction by performing the steps of loading the bitmap segment that contains said bit from a persistent storage to a dynamic memory without loading any other of said plurality of bitmap segments; and after loading the bitmap segment that contains said bit, updating said bit to reflect whether said particular record satisfies said particular criterion.
Claim 5
Dependent Claim
32 words
The method of claim 3 further comprising the step of, in response to updating said bit, generating a log that records an updated version of the bitmap segment that contains said bit.
Claim 6
Dependent Claim
120 words
The method of claim 1 further comprising the steps of: performing a logical operation that combines a first bitmap with a second bitmap, wherein the first bitmap is comprised of said plurality of bitmap segments, wherein said second bitmap indicates whether records in said body of records satisfy a second criterion; wherein the step of performing the logical operation includes the steps of: identifying a series of bits in said second bitmap that have a particular value; determining an identifier range associated with said series of bits; and loading into dynamic memory only those bitmap segments of said plurality of bitmap segments that are associated with ranges that correspond to at least one identifier that falls outside said identifier range.
Claim 7
Dependent Claim
67 words
The method of claim 1 wherein the step of generating a plurality of bitmap segments that correspond to said plurality of ranges includes the steps of: generating a first bitmap segment that corresponds to a first range; generating a second bitmap segment that corresponds to a second range; and generating no bitmap segment for a third range that falls between said first range and said second range.
Claim 8
Dependent Claim
54 words
The method of claim 6 wherein: records that have been assigned identifiers in said third range either all satisfy or all do not satisfy said particular criterion; and the method includes the step of storing data that indicates whether all records that have been assigned identifiers in said third range satisfy said particular criterion.
Claim 9
Dependent Claim
21 words
The method of claim 6 wherein no records within said body of records have been assigned identifiers in said third range.
Claim 10
Independent Claim
150 words
A method for indexing a body of records, wherein all records in said body of records fall within a particular range, the method comprising the steps of: generating a plurality of bitmap segments that indicate whether the records in said body of records contain a key value; wherein each bitmap segment of said plurality of bitmap segments corresponds to a subrange of said particular range; performing an update to a record in said body of records, wherein said update affects whether said record contains said key value; in response to performing said update, performing the steps of determining the subrange into which said record falls; loading into dynamic memory only the bitmap segment of said plurality of bitmap segments that corresponds to the subrange into which said record falls; and updating a bit in said bitmap that corresponds to said record to indicate whether said record contains said key value.
Claim 11
Independent Claim
150 words
A method for indexing a body of records, wherein all records in said body of records fall within a particular range, the method comprising the steps of: generating a plurality of bitmap segments that indicate whether the records in said body of records contain a key value; wherein each bitmap segment of said plurality of bitmap segments corresponds to a subrange of said particular range; performing an update to a record in said body of records, wherein said update affects whether said record contains said key value; in response to performing said update, performing the steps of determining the subrange into which said record falls; loading into dynamic memory only the bitmap segment of said plurality of bitmap segments that corresponds to the subrange into which said record falls; and updating a bit in said bitmap that corresponds to said record to indicate whether said record contains said key value.
Claim 12
Dependent Claim
26 words
The method of claim 9 further comprising the step of causing a plurality of processes to concurrently operate on different segments of said plurality of segments.
Claim 13
Dependent Claim
60 words
The method of claim 9 wherein the step of generating a plurality of bitmap segments includes generating a first bitmap segment for a first subrange of said particular range and a second bitmap segment for a second subrange of said particular range without generating any bitmap segment for a subrange that falls between said first subrange and said second subrange.
Claim 14
Dependent Claim
40 words
The method of claim 9 further comprising the step of generating a log in response to updating said bitmap segment, wherein said log indicates a version of said bitmap segment but not any other of said plurality of bitmap segments.
Claim 15
Dependent Claim
51 words
The method of claim 9 wherein the step of generating a plurality of bitmap segments includes generating, for each bitmap segment, data that indicates said subrange associated with said bitmap segment and a string of bits that includes one bit for every record in said subrange associated with said bitmap segment.
Claim 16
Dependent Claim
162 words
A computer-readable medium carrying one or more sequences of one or more instructions for indicating whether records in a body of data satisfy a particular criterion, 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: establishing a plurality of ranges for identifiers assigned to records in said body of records; generating a plurality of bitmap segments that correspond to said plurality of ranges, wherein each bitmap segment includes data representing a sequence of bits that includes one bit for every record that has an identifier that falls within the range associated with said bitmap segment, wherein each bit in said sequence of bits is set to a value that indicates whether a record that corresponds to said bit satisfies said particular criterion; and storing data that indicates the range associated with each bitmap segment of said plurality of bitmap segments.
Claim 17
Dependent Claim
162 words
A computer-readable medium carrying one or more sequences of one or more instructions for indicating whether records in a body of data satisfy a particular criterion, 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: establishing a plurality of ranges for identifiers assigned to records in said body of records; generating a plurality of bitmap segments that correspond to said plurality of ranges, wherein each bitmap segment includes data representing a sequence of bits that includes one bit for every record that has an identifier that falls within the range associated with said bitmap segment, wherein each bit in said sequence of bits is set to a value that indicates whether a record that corresponds to said bit satisfies said particular criterion; and storing data that indicates the range associated with each bitmap segment of said plurality of bitmap segments.
Claim 18
Dependent Claim
102 words
The computer-readable medium of claim 14 further comprising sequences of instructions for performing the steps of: executing a transaction that affects whether a particular record in said body of records satisfies said particular criterion; determining which bitmap segment contains a bit that corresponds to said particular record; updating said bit in response to said transaction by performing the steps of obtaining a lock on the bitmap segment that contains said bit without obtaining a lock on the other of said plurality of bitmap segments; and after obtaining said lock, updating said bit to reflect whether said particular record satisfies said particular criterion.
Claim 19
Dependent Claim
109 words
The computer-readable medium of claim 14 further comprising sequences of instructions for performing the steps of: executing a transaction that affects whether a particular record in said body of records satisfies said particular criterion; determining which bitmap segment contains a bit that corresponds to said particular record; updating said bit in response to said transaction by performing the steps of loading the bitmap segment that contains said bit from a persistent storage to a dynamic memory without loading any other of said plurality of bitmap segments; and after loading the bitmap segment that contains said bit, updating said bit to reflect whether said particular record satisfies said particular criterion.
Claim 20
Dependent Claim
38 words
The computer-readable medium of claim 16 further comprising sequences of instructions for performing the step of, in response to updating said bit, generating a log that records an updated version of the bitmap segment that contains said bit.
Claim 21
Dependent Claim
126 words
The computer-readable medium of claim 14 further comprising sequences of instructions for performing the steps of: performing a logical operation that combines a first bitmap with a second bitmap, wherein the first bitmap is comprised of said plurality of bitmap segments, wherein said second bitmap indicates whether records in said body of records satisfy a second criterion; wherein the step of performing the logical operation includes the steps of: identifying a series of bits in said second bitmap that have a particular value; determining an identifier range associated with said series of bits; and loading into dynamic memory only those bitmap segments of said plurality of bitmap segments that are associated with ranges that correspond to at least one identifier that falls outside said identifier range.
Claim 22
Dependent Claim
68 words
The computer-readable medium of claim 14 wherein the step of generating a plurality of bitmap segments that correspond to said plurality of ranges includes the steps of: generating a first bitmap segment that corresponds to a first range; generating a second bitmap segment that corresponds to a second range; and generating no bitmap segment for a third range that falls between said first range and said second range.
Claim 23
Dependent Claim
61 words
The computer-readable medium of claim 19 wherein: records that have been assigned identifiers in said third range either all satisfy or all do not satisfy said particular criterion; and the computer-readable medium includes sequences of instructions for performing the step of storing data that indicates whether all records that have been assigned identifiers in said third range satisfy said particular criterion.
Claim 24
Dependent Claim
22 words
The computer-readable medium of claim 19 wherein no records within said body of records have been assigned identifiers in said third range.
Claim 25
Dependent Claim
42 words
The method of claim 1, wherein the step of storing data that indicates the range associated with each bitmap segment of said plurality of bitmap segments includes storing in a bitmap segment data that indicates the range associated with the bitmap segment.
Claim 26
Dependent Claim
42 words
The method of claim 22, wherein the step of storing in a bitmap segment data that indicates the range associated with the bitmap segment includes storing in a bitmap segment data that indicates the beginning of the range associated with said bitmap.
Claim 27
Dependent Claim
57 words
The method of claim 23, wherein the step of storing in a bitmap segment data that indicates the beginning of the range associated with said bitmap segment includes storing in a bitmap segment data that indicates the beginning of the range associated with said bitmap segment and the end of the range associated with said bitmap segment.
Claim 28
Dependent Claim
63 words
The method of claim 1, wherein the step of storing data that indicates the range associated with each bitmap segment of said plurality of bitmap segments includes storing data that indicates the beginning of the range associated with each bitmap segment of said plurality of bitmap segments and the end of the range associated each bitmap segment of said plurality of bitmap segments.
Claim 29
Dependent Claim
43 words
The computer-readable medium of claim 14, wherein the step of storing data that indicates the range associated with each bitmap segment of said plurality of bitmap segments includes storing in a bitmap segment data that indicates the range associated with the bitmap segment.
Claim 30
Dependent Claim
43 words
The computer-readable medium of claim 26, wherein the step of storing in a bitmap segment data that indicates the range associated with the bitmap segment includes storing in a bitmap segment data that indicates the beginning of the range associated with said bitmap.
Claim 31
Dependent Claim
58 words
The computer-readable medium of claim 27, wherein the step of storing in a bitmap segment data that indicates the beginning of the range associated with said bitmap segment includes storing in a bitmap segment data that indicates the beginning of the range associated with said bitmap segment and the end of the range associated with said bitmap segment.
Claim 32
Dependent Claim
64 words
The computer-readable medium of claim 14, wherein the step of storing data that indicates the range associated with each bitmap segment of said plurality of bitmap segments includes storing data that indicates the beginning of the range associated with each bitmap segment of said plurality of bitmap segments and the end of the range associated each bitmap segment of said plurality of bitmap segments.
Claim 33
Dependent Claim
186 words
A computer-readable medium carrying one or more sequences of one or more instructions for indexing a body of records, wherein all records in said body of records fall within a particular range, 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: generating a plurality of bitmap segments that indicate whether the records in said body of records contain a key value; wherein each bitmap segment of said plurality of bitmap segments corresponds to a subrange of said particular range; performing an update to a record in said body of records, wherein said update affects whether said record contains said key value; in response to performing said update, performing the steps of determining the subrange into which said record falls; loading into dynamic memory only the bitmap segment of said plurality of bitmap segments that corresponds to the subrange into which said record falls; and updating a bit in said bitmap that corresponds to said record to indicate whether said record contains said key value.
Claim 34
Dependent Claim
186 words
A computer-readable medium carrying one or more sequences of one or more instructions for indexing a body of records, wherein all records in said body of records fall within a particular range, 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: generating a plurality of bitmap segments that indicate whether the records in said body of records contain a key value; wherein each bitmap segment of said plurality of bitmap segments corresponds to a subrange of said particular range; performing an update to a record in said body of records, wherein said update affects whether said record contains said key value; in response to performing said update, performing the steps of determining the subrange into which said record falls; loading into dynamic memory only the bitmap segment of said plurality of bitmap segments that corresponds to the subrange into which said record falls; and updating a bit in said bitmap that corresponds to said record to indicate whether said record contains said key value.
Claim 35
Dependent Claim
32 words
The computer-readable medium of claim 30 further comprising sequences of instructions for performing the step of causing a plurality of processes to concurrently operate on different segments of said plurality of segments.
Claim 36
Dependent Claim
61 words
The computer-readable medium of claim 30 wherein the step of generating a plurality of bitmap segments includes generating a first bitmap segment for a first subrange of said particular range and a second bitmap segment for a second subrange of said particular range without generating any bitmap segment for a subrange that falls between said first subrange and said second subrange.
Claim 37
Dependent Claim
46 words
The computer-readable medium of claim 30 further comprising sequences of instructions for performing the step of generating a log in response to updating said bitmap segment, wherein said log indicates a version of said bitmap segment but not any other of said plurality of bitmap segments.
Claim 38
Dependent Claim
52 words
The computer-readable medium of claim 30 wherein the step of generating a plurality of bitmap segments includes generating, for each bitmap segment, data that indicates said subrange associated with said bitmap segment and a string of bits that includes one bit for every record in said subrange associated with said bitmap segment.
References Cited (Backward Citations)
US5495608A
Cited
US5502804A
Cited
US5404411A
Cited
US5442715A
Cited
US5604850A
Cited
EP0606137A2
Cited
US5465322A
Cited
US5649181A
Cited
US5751921A
Cited
US5552898A
Cited
US5642473A
Cited
US5706495A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-05-23 | 2003-11-22 | 2004-05-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-05-23 | 2007-11-22 | 2008-05-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-05-23 | 2011-11-22 | 2012-05-23 | $7700.00 | Window Closed / Lapsed |