Bitmapped indexing with high granularity locking

• US 5,899,988 A
• Filed: 02/28/1997
• Issued: 05/04/1999
• 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,451
• Time in Patent Office: 795 Days
• Field of Search: 707/3, 707/10, 707/7, 707/202
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method and apparatus provide bitmapped indexing with high granularity locking. Whenever a change is made to a data table upon which a bitmapped index is based, two differential entries are generated and stored as index entries in the bitmapped index. Each differential entry identifies a bit to be flipped in the corresponding bitmap index entry. When applied to corresponding bitmap index entry, the changes are reflected in the appropriate bitmaps. Whenever a bitmap is read from the bitmapped index, any corresponding differential entries are applied so that the resulting bitmap reflects the change made to the data table.

Claims

1. A method for allowing a bitmapped index to reflect a change made to data associated with the bitmapped index, the method comprising the steps of:

a) generating a change entry identifying a bitmap change which, when applied to a bitmap contained in the bitmapped index, causes the bitmap to reflect the change made to the data; and

b) saving the change entry.

2. The method of claim 1, wherein the step of saving the change entry includes the step of storing the change entry as an index entry in the bitmapped index.

3. The method of claim 1, further comprising the steps of

a) when a first bitmap associated with the prior value of the changed data is read from the bitmapped index, applying the bitmap change to the first bitmap causing the first bitmap to reflect the change made to the data, and

b) when a second bitmap associated with the new value of the changed data is read from the bitmapped index, applying the bitmap change to the second bitmap causing the second bitmap to reflect the change made to the data.

4. The method of claim 3, wherein the step of applying the bitmap change to the first bitmap further comprises the step of flipping a bit in the first bitmap specified in the bitmap change causing the first bitmap to indicate that the changed data no longer contains the value associated with the first bitmap, and

wherein the step of applying the bitmap change to the second bitmap further comprises the step of flipping a bit in the second bitmap specified in the bitmap change causing the second bitmap to indicate that the changed data contains the value associated with the second bitmap.

5. The method of claim 1, wherein the data is a data table, the change includes changing an old value to a new value in the data table and, the method further comprises the steps of:

a) when the old value is changed to the new value

i) generating a first change entry specifying a change to a first bitmap in the bitmapped index, the first bitmap being associated with the old value, and

ii) generating a second change entry specifying a change to a second bitmap in the bitmapped index, the second bitmap being associated with the new value;

b) when the first bitmap is read from the bitmapped index, applying the change specified in the first change entry to the first bitmap causing the first bitmap to reflect the change of the old value to the new value; and

c) when the second bitmap is read from the bitmapped index, applying the change specified in the second change entry to the second bitmap causing the second bitmap to reflect the change of the old value to the new value.

6. The method of claim 5, wherein the step of generating a first change entry further comprises the step of generating a first differential entry specifying a bit in the first bitmap to be flipped, and

wherein the step of generating a second change entry further comprises the step of generating a second differential entry specifying a bit in the second bitmap to be flipped.

7. The method of claim 6, wherein the step of applying the change to the first bitmap further comprises the step of flipping the bit in the first bitmap specified in the first differential entry, and

wherein the step of applying the change to the second bitmap further comprises the step of flipping the bit in the second bitmap specified in the second differential entry.

8. The method of claim 5, further comprising the step of storing the first and second change entries in the bitmapped index, the first and second change entries being stored with a key value identical to the key value of bitmapped index entries with which the first and second change entries are associated.

9. The method of claim 8, further comprising the step of if existing change entries specifying the same changes as the first and second change entries already exist in the bitmapped index, then deleting the first and second change entries and deleting the existing change entries specifying the same changes as the first and second change entries.

10. The method of claim 5, wherein the step of generating a first change entry further comprises the step of generating flag information to distinguish the first change entry from other index entries in the bitmapped index, and

wherein the step of generating a second change entry further comprises the step of generating flag information to distinguish the second change entry from other index entries in the bitmapped index.

11. The method of claim 5, further comprising the steps of:

a) applying the changes specified in the first and second change entries to the first and second bitmaps respectively,

b) saving the changed first and second bitmaps, and

c) deleting the first and second change entries.

12. A computer-readable medium having stored thereon a plurality of sequences of instructions, the plurality of sequences of instructions including sequences of instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of:

a) generating a change entry identifying a bitmap change which, when applied to a bitmap contained in the bitmapped index, causes the bitmap to reflect the change made to the data; and

b) saving the change entry.

13. The computer-readable medium of claim 12, wherein the computer-readable medium further includes instructions for storing the change entry as an index entry in the bitmapped index.

14. The computer-readable medium of claim 12, wherein the computer-readable medium further includes instructions for

a) when a first bitmap associated with the prior value of the changed data is read from the bitmapped index, applying the bitmap change to the first bitmap causing the first bitmap to reflect the change made to the data, and

b) when a second bitmap associated with the new value of the changed data is read from the bitmapped index, applying the bitmap change to the second bitmap causing the second bitmap to reflect the change made to the data.

15. The computer-readable medium of claim 14, wherein the instructions for applying the bitmap change to the first bitmap further comprise instructions for flipping a bit in the first bitmap specified in the bitmap change causing the first bitmap to indicate that the changed data no longer contains the value associated with the first bitmap, and

wherein the instructions for applying the bitmap change to the second bitmap further include instructions for flipping a bit in the second bitmap specified in the bitmap change causing the second bitmap to indicate that the changed data contains the value associated with the second bitmap.

16. The computer-readable medium of claim 12, wherein the computer-readable medium further includes instructions for

a) when the old value is changed to the new value

i) generating a first change entry specifying a change to a first bitmap in the bitmapped index, the first bitmap being associated with the old value, and

ii) generating a second change entry specifying a change to a second bitmap in the bitmapped index, the second bitmap being associated with the new value,

b) when the first bitmap is read from the bitmapped index, applying the change specified in the first change entry to the first bitmap causing the first bitmap to reflect the change of the old value to the new value, and

c) when the second bitmap is read from the bitmapped index, applying the change specified in the second change entry to the second bitmap causing the second bitmap to reflect the change of the old value to the new value.

17. The computer-readable medium of claim 16, wherein the instructions for generating a first change entry further include instructions for generating a first differential entry specifying a bit in the first bitmap to be flipped, and

wherein the instructions for generating a second change entry further include instructions for generating a second differential entry specifying a bit in the second bitmap to be flipped.

18. The computer-readable medium of claim 17, wherein the instructions for applying the change to the first bitmap further include instructions for flipping the bit in the first bitmap specified in the first differential entry, and

wherein the instructions for applying the change to the second bitmap further include instructions for flipping the bit in the second bitmap specified in the second differential entry.

19. The computer-readable medium of claim 16, wherein the computer-readable medium further includes instructions for storing the first and second change entries in the bitmapped index, the first and second change entries being stored with a key value identical to the key value of bitmapped index entries with which the first and second change entries are associated.

20. The computer-readable medium of claim 19, wherein the computer-readable medium further includes instructions for if existing change entries specifying the same changes as the first and second change entries already exist in the bitmapped index, then deleting the first and second change entries and deleting the existing change entries specifying the same changes as the first and second change entries.

21. The computer-readable medium of claim 16, wherein the instructions for generating a first change entry further include instructions for generating flag information to distinguish the first change entry from other index entries in the bitmapped index, and

wherein the instructions for generating a second change entry further include instructions for generating flag information to distinguish the second change entry from other index entries in the bitmapped index.

22. The computer-readable medium of claim 16, wherein the computer-readable medium further includes instructions for

a) applying the changes specified in the first and second change entries to the first and second bitmaps respectively,

b) saving the changed first and second bitmaps, and

c) deleting the first and second change entries.

23. A computer system having a storage medium with an index stored thereon, the index comprising:

a) a first set of index entries of a first type; and

b) a second set of index entries of a second type, the second set of index entries specifying changes to the first set of index entries to make the first set of index entries reflect changes made to data upon which the index is based.

24. The computer system of claim 23, wherein the index is a bitmapped index,

wherein the bitmapped index is built on a key contained in a plurality of records contained in the data, and

wherein each of the first set of index entries contains bitmap information, and

wherein each of the second set of index entries specifies at least one change to the bitmap information contained in at least one of the first set of index entries causing the bitmap information in the first set of index entries to reflect changes made to the plurality of records.

25. The computer system of claim 24, wherein the bitmap information includes a string of bits, each bit corresponding to one of said plurality of records, and

wherein the at least one change to the bitmap information contained in the at least one of the first set of index entries includes a change to a bit in the string of bits.

26. The computer system of claim 23, wherein

a) the index is a bitmapped index built on a data table,

b) each index entry in the first set of index entries contains a key value and a bitmap, the bitmap containing a string of bits where each bit indicates whether a corresponding data record in the data table contains the key value in the index entry, and

c) each index entry in the second set of index entries includes a key value and a bit identifier, the bit identifier specifying a bit in the bitmap of one of the index entries in the first set of index entries having the same key value, which when the bit is changed, causes the index entry in the first set of index entries to reflect the change made to the data table.

27. The computer system of claim 26, wherein each index entry in the first set of index entries further includes a starting record identifier and an ending record identifier for mapping each index entry in the first set of index entries to one of the data records in the data table, and

wherein each index entry in the second set of index entries further includes an entry identifier for identifying each of the index entries in the second set of entries.