Generating and applying redo records

• US 8,977,597 B2
• Filed: 11/06/2013
• Issued: 03/10/2015
• Est. Priority Date: 05/21/2008
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Ganesh, Amit, Loaiza, Juan R., Kunchithapadam, Krishna
• Primary Examiner(s): DWIVEDI, MAHESH H
• Application Number:
  US14/073,832
• Publication Number:
  US 20140067767A1
• Time in Patent Office: 489 Days
• Field of Search: 707/675, 707/741
• US Class Current: 707/675
• CPC Class Codes: G06F 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor

Abstract

Techniques for maintaining a cascading index are provided. In one approach, one or more branch node compression techniques are applied to the main index of a cascading index. In an approach, a Bloom filter is generated and associated with, e.g., a branch node in the main index. The Bloom filter is used to determine whether, without accessing any leaf blocks, a particular key value exists, e.g., in leaf blocks associated with the branch node. In an approach, a new redo record is generated in response to a merge operation between two levels of the cascading index. The new redo record comprises (a) one or more addresses of blocks that are affected by the merge operation, (b) data is that being “pushed down” to a lower level of the cascading index, and (c) one or more addresses of blocks that are written to storage as a result of the merge operation.

Claims

1. A method comprising:

receiving a plurality of updates that affect a multi-level index that comprises a plurality of index levels that includes at least a journal index and a main index;

applying the plurality of updates to the journal index without applying the plurality of updates to the main index;

in response to determining that one or more criteria are satisfied, removing the plurality of updates from the journal index and applying the plurality of updates to the main index;

processing a transaction that will result in one or more particular changes to data in one or more original data blocks that are part of a leaf level of the main index;

before committing the transaction, generating and storing one or more redo records;

wherein each redo record of the one or more redo records indicates (a) a first address of at least one data block of the one or more original data blocks, (b) at least one of the one or more particular changes, and (c) a second address of at least one data block of one or more target data blocks that reflect the at least one of the one or more particular changes;

wherein the method is performed by one or more computing devices.

2. The method of claim 1, wherein:

a first redo record of the one or more redo records includes a length value that indicates how much data to read, when processing the first redo record as part of a database recovery process, beginning at the first address.

3. The method of claim 1, wherein:

the one or more original data blocks are a plurality of original data blocks;

the one or more target data blocks are a plurality of target data blocks;

each redo record indicates only one address associated with the plurality of original data blocks and only one address associated with the plurality of target data blocks.

4. The method of claim 1, further comprising, as part of a database recovery process, for each redo record of the one or more redo records:

identifying an original address indicated in said each redo record;

reading, based on the original address, first data from a data block located at the original address;

applying the one or more changes indicated in the redo record to the first data to create modified data;

identifying a target address indicated in said each redo record; and

writing the modified data to one or more data blocks beginning at the target address.

5. The method of claim 4, wherein applying the one or more changes comprises adding one or more values to the first data or deleting one or more values from the first data.

6. The method of claim 1, wherein the main index is stored in persistent storage while the journal index is stored in memory.

7. The method of claim 1, wherein the transaction involves merging changes reflected in the journal index with the main index.

8. The method of claim 7, wherein:

the one or more original data blocks are a plurality of original data blocks;

the one or more target data blocks are a plurality of target data blocks;

merging the changes comprises combining the changes with data contained in the plurality of original data block to produce combined data that is stored in the plurality of target data blocks.

9. One or more non-transitory storage media carrying instructions which, when executed by one or more processors, cause:

receiving a plurality of updates that affect a multi-level index that comprises a plurality of index levels that includes at least a journal index and a main index;

applying the plurality of updates to the main index;

in response to determining that one or more criteria are satisfied, removing the plurality of updates from the journal index and applying the plurality of updates to the main index;

processing a transaction that will result in one or more particular changes to data in one or more original data blocks that are part of a leaf level of the main index;

before committing the transaction, generating and storing one or more redo records;

wherein each redo record of the one or more redo records indicates (a) a first address of at least one data block of the one or more original data blocks, (b) at least one of the one or more particular changes, and (c) a second address of at least one data block of one or more target data blocks that reflect the at least one of the one or more particular changes.

10. The one or more non-transitory storage media of claim 9, wherein:

a first redo record of the one or more redo records includes a length value that indicates how much data to read, when processing the first redo record as part of a database recovery process, beginning at the first address.

11. The one or more non-transitory storage media of claim 9, wherein:

the one or more original data blocks are a plurality of original data blocks;

the one or more target data blocks are a plurality of target data blocks;

each redo record indicates only one address associated with the plurality of original data blocks and only one address associated with the plurality of target data blocks.

12. The one or more non-transitory storage media of claim 9, wherein the instructions, when executed by the one or more processors, further cause, as part of a database recovery process, for each redo record of the one or more redo records:

identifying an original address indicated in said each redo record;

reading, based on the original address, first data from a data block located at the original address;

applying the one or more changes indicated in the redo record to the first data to create modified data;

identifying a target address indicated in said each redo record; and

writing the modified data to one or more data blocks beginning at the target address.

13. The one or more non-transitory storage media of claim 12, wherein applying the one or more changes comprises adding one or more values to the first data or deleting one or more values from the first data.

14. The one or more non-transitory storage media of claim 9, wherein the main index is stored in persistent storage while the journal index is stored in memory.

15. The one or more non-transitory storage media of claim 9, wherein the transaction involves merging changes reflected in the journal index with the main index.

16. The one or more non-transitory storage media of claim 15, wherein:

the one or more original data blocks are a plurality of original data blocks;

the one or more target data blocks are a plurality of target data blocks;

merging the changes comprises combining the changes with data contained in the plurality of original data block to produce combined data that is stored in the plurality of target data blocks.

17. A system comprising:

one or more processors;

one or more non-transitory storage media carrying instructions which, when executed by one or more processors, cause;

receiving a plurality of updates that affect a multi-level index that comprises a plurality of index levels that includes at least a journal index and a main index;

applying the plurality of updates to the journal index without applying the plurality of updates to the main index;

in response to determining that one or more criteria are satisfied, removing the plurality of updates from the journal index and applying the plurality of updates to the main index;

processing a transaction that will result in one or more particular changes to data in one or more original data blocks that are part of a leaf level of the main index;

before committing the transaction, generating and storing one or more redo records;

wherein each redo record of the one or more redo records indicates (a) a first address of at least one data block of the one or more original data blocks, (b) at least one of the one or more particular changes, and (c) a second address of at least one data block of one or more target data blocks that reflect the at least one of the one or more particular changes.

18. The system of claim 17, wherein:

a first redo record of the one or more redo records includes a length value that indicates how much data to read, when processing the first redo record as part of a database recovery process, beginning at the first address.

19. The system of claim 17, wherein:

the one or more original data blocks are a plurality of original data blocks;

the one or more target data blocks are a plurality of target data blocks;

each redo record indicates only one address associated with the plurality of original data blocks and only one address associated with the plurality of target data blocks.

20. The system of claim 17, wherein the instructions, when executed by the one or more processors, further cause, as part of a database recovery process, for each redo record of the one or more redo records:

identifying an original address indicated in said each redo record;

reading, based on the original address, first data from a data block located at the original address;

applying the one or more changes indicated in the redo record to the first data to create modified data;

identifying a target address indicated in said each redo record; and

writing the modified data to one or more data blocks beginning at the target address.

21. The system of claim 20, wherein applying the one or more changes comprises adding one or more values to the first data or deleting one or more values from the first data.

22. The system of claim 17, wherein the main index is stored in persistent storage while the journal index is stored in memory.

23. The system of claim 17, wherein the transaction involves merging changes reflected in the journal index with the main index.

24. The system of claim 23, wherein:

the one or more original data blocks are a plurality of original data blocks;

the one or more target data blocks are a plurality of target data blocks;

merging the changes comprises combining the changes with data contained in the plurality of original data block to produce combined data that is stored in the plurality of target data blocks.