Creating bitmaps from multi-level identifiers

• US 6,081,800 A
• Filed: 02/28/1997
• Issued: 06/27/2000
• Est. Priority Date: 02/28/1997
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Ozbutun, Cetin, Kremer, Mark, Jakobsson, Hakan, Cohen, Jeffrey I., Ho, Alexander C., Tran, Quoc Tai, Depledge, Michael
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): ALAM, SHAHID AL
• Application Number:
  US08/807,344
• Time in Patent Office: 1,215 Days
• Field of Search: 707/1, 707/8, 707/3, 707/10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A method and apparatus for generating and using bitmaps in a database system that employs multi-level identifiers is provided. The generated bitmaps include bits that correspond to the identifiers that have been assigned to existing records, as well as bits that correspond to all intervening multi-level identifiers that have not yet been assigned. Therefore, when new rows are inserted into the table associated with the bitmap, new bits do not have to be inserted into the existing bitmap. When existing rows are deleted, the bits that correspond to the deleted rows are not themselves deleted, but are simply set to a value that indicates that the corresponding row does not satisfy the criteria associated with the bitmap.

Claims

1. A method for generating a bitmap for a body of records, the method comprising the steps of:

identifying a plurality of levels of multilevel identifiers used to identify records in said body of records, wherein said plurality of levels includes a leading level and one or more non-leading levels;

determining a number of distinct values for each non-leading level of said plurality of levels;

determining a number of distinct combinations of non-leading level values based on said number of distinct values for each non-leading level; and

generating a bitmap that includes a bit sequence for every value of said leading level, wherein each bit sequence includes one bit for every distinct combination of said non-leading level values.

2. The method of claim 1 further comprising the steps of:

inserting a record into said body of data;

assigning said record a unique identifier;

locating an existing bit in said bitmap that corresponds to said unique identifier; and

setting the value of said existing bit based on whether said record satisfies a particular criteria associated with said bitmap.

3. The method of claim 1 wherein:

bits of said bitmap that correspond to records that satisfy a criteria associated with the bitmap have a first value;

bits of said bitmap that correspond to records that not satisfy said criteria associated with the bitmap have a second value;

the method further comprises the steps of;

deleting a record from said body of data, wherein said record had been assigned a particular identifier;

if said record satisfied said criteria associated with said bitmap, then performing the steps of

locating an existing bit in said bitmap that corresponds to said particular identifier; and

setting said existing bit to said second value.

4. The method of claim 1, wherein the step of determining a number of distinct combinations of non-leading level values based on said number of distinct values for each non-leading level includes determining, for a particular non-leading level, how many records can be stored in a predetermined amount of memory.

5. The method of claim 4 wherein:

said particular non-leading level indicates a slot number within a data block; and

the step of determining a maximum amount of records that can be stored in the predetermined amount of memory includes the step of

determining a maximum number of records that can be stored within a data block.

6. The method of claim 5 wherein the step of determining a maximum number of records that can be stored within a data block includes the steps of:

reading data that defines said body of records;

determining a minimum record size based on said data that defines said body of records; and

determining how many records having said minimum record size can be stored within a data block.

7. The method of claim 4, wherein the step of determining, for a particular non-leading level, how many records can be stored includes:

inspecting definition information that indicates data types of information stored in the records to determine a minimum size for said records; and

determining a maximum amount of records that can be stored in the predetermined amount of memory based on the minimum size for said records.

8. A database system comprising:

a body of records stored on one or more storage devices, wherein each record in said body of records is identified by a multi-level identifier that includes a leading level and one or more nonleading levels;

a bitmap associated with said body of records, the bitmap comprising a series of bit sequences;

wherein each distinct value of said leading level of said multi-level identifier corresponds to a distinct bit sequence in said series of bit sequences;

wherein each bit sequence includes one bit for every possible distinct combination of non-leading level values;

wherein bits in said bitmap that correspond to multi-level identifiers that are assigned to records that satisfy a criteria associated with said bitmap are set to a first value;

wherein bits in said bitmap that do not correspond to multi-level identifiers that are assigned to records that satisfy said criteria associated with said bitmap are not set to said first value;

a mechanism for identifying a bit within said bitmap that corresponds to a record based on the multi-level identifier assigned to the record; and

a mechanism for determining the identifier of a record associated with a bit in said bitmap based on the position of said bit within said bitmap.

9. The database system of claim 8 wherein:

each of said bit sequences has a fixed length; and

said fixed length is determined based on the maximum number of records that can be stored in a single data block.

10. The database system of claim 9 further including:

data that defines said body of records; and

a mechanism for determining the maximum number of records that can be stored in said single data block based on said data that defines said body of records.

11. The database system of claim 8 further including one or more mechanisms for:

inserting a record into said body of data;

assigning said record a unique multi-level identifier;

locating an existing bit in said bitmap that corresponds to said unique multi-level identifier; and

setting the value of said existing bit based on whether said record satisfies a criteria associated with said bitmap.

12. The database system of claim 8 further including one or more mechanisms for:

deleting a record from said body of data, wherein said record had been assigned a particular multi-level identifier;

if said record satisfied said criteria associated with said bitmap, then performing the steps of

locating an existing bit in said bitmap that corresponds to said particular multi-level identifier; and

setting said existing bit to a second value.

16. The computer readable medium of claim 9, wherein the step of determining a number of distinct combinations of non-leading level values based on said number of distinct values for each non-leading level includes determining, for a particular non-leading level, how many records can be stored in a predetermined amount of memory.

17. The computer readable medium of claim 16 wherein:

said particular non-leading level indicates a slot number within a data block; and

the step of determining a number of distinct values for each non-leading level includes the step of determining a maximum number of records that can be stored within a data block.

18. The computer readable medium of claim 17 wherein the step of determining a maximum number of records that can be stored within a data block includes the steps of:

reading data that defines said body of records;

determining a minimum record size based on said data that defines said body of records; and

determining how many records having said minimum record size can be stored within a data block.

19. The computer readable medium of claim 16, wherein the step of determining, for a particular non-leading level, how many records can be stored includes:

inspecting definition information that indicates data types of information stored in the records to determine a minimum size for said records; and

determining a maximum amount of records that can be stored in the predetermined amount of memory based on the minimum size for said records.

13. A computer readable medium having stored thereon sequences of instructions for generating a bitmap for a body of records, the sequences of instructions including instructions for performing the steps of:

identifying a plurality of levels of multilevel identifiers used to identify records in said body of records, wherein said plurality of levels includes a leading level and one or more non-leading levels;

determining a number of distinct values for each non-leading level of said plurality of levels;

determining a number of distinct combinations of non-leading level values based on said number of distinct values for each non-leading level; and

generating a bitmap that includes a bit sequence for every value of said leading level, wherein each bit sequence includes one bit for every distinct combination of said non-leading level values.

14. The computer readable medium of claim 13 further comprising instructions for performing the steps of:

inserting a record into said body of data;

assigning said record a unique identifier;

locating an existing bit in said bitmap that corresponds to said unique identifier; and

setting the value of said existing bit based on whether said record satisfies a particular criteria associated with said bitmap.

15. The computer readable medium of claim 13 wherein:

bits of said bitmap that correspond to records that satisfy a criteria associated with the bitmap have a first value;

bits of said bitmap that correspond to records that do not satisfy said criteria associated with the bitmap have a second value;

the computer readable medium further comprises sequences of instructions for performing the steps of;

deleting a record from said body of data, wherein said record had been assigned a particular identifier;

if said record satisfied said criteria associated with said bitmap, then performing the steps of

locating an existing bit in said bitmap that corresponds to said particular identifier; and

setting said existing bit to said second value.