Method and mechanism for determining life intervals for a key in an index

• US 9,400,812 B2
• Filed: 08/12/2011
• Issued: 07/26/2016
• Est. Priority Date: 12/18/2002
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Sinha, Bipul, Raja, Vivekanandhan, Ganesh, Amit
• Primary Examiner(s): Kerzhner, Aleksandr
• Assistant Examiner(s): Levitian, Karina
• Application Number:
  US13/209,224
• Publication Number:
  US 20110302205A1
• Time in Patent Office: 1,810 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/219 Managing data history or versioning querying versioned data G06F16/2474; querying temporal data G06F16/2477

Abstract

Disclosed is a mechanism, system, interface, and process to determine one or more life intervals when given a key. In addition, one or more life intervals can be determined for each key within a range of keys. This type of process is useful for auditing purposes or if it is desire to implement a query upon past versions when a key or range of keys is specified for the data for which past versions is desired. This facilitates algorithms, mechanisms, and processes to implement a query upon past versions.

Claims

1. A method for determining one or more life intervals for a range of keys in a database system to retrieve one or more past versions of one or more data items corresponding to the range of keys in the database system, comprising:

using at least one computing system to execute a process, the process comprising;

receiving a range of keys for which it is desired to determine one or more life intervals;

determining whether the range of keys should be split into a first working range and a second working range based at least in part upon storage locations of the first working range and the second working range, wherein the first working range includes a first portion of keys, and the second working range-includes a second portion of keys, wherein determining whether the range of keys should be split into the first working range and the second working range is performed by determining whether the range of keys is situated within a single block on a physical, non-transitory computer usable storage medium for storing data in the database system, and wherein examination is performed on a branch between a first leaf block and a second leaf block and a determination is made whether the range of keys is over both the first leaf block and the second leaf block;

splitting, in response to the determination of whether the range of keys should be split, the range of keys into the first and second portion of keys; and

separately processing the first portion and the second portion to determine the one or more life intervals of one or more keys of the first and second portion of keys, wherein the determination of the life interval comprises applying a portion of an undo log record in a reverse temporal order to restore the one or more past versions by respectively re-generating the one or more past versions into a database table or one or more instances of the database table.

2. The method of claim 1, comprising:

determining whether a separator for a branch is within the range of keys.

3. The method of claim 1 in which the second portion of the range of keys associated with the second leaf block is after the first portion associated with the first leaf block.

4. The method of claim 1 in which a plurality of ranges are processed after the range of keys is processed.

5. The method of claim 1 in which the range is placed on a stack.

6. The method of claim 1 in which data for keys within the range are maintained for later processing, even after a split of the range into the first working range and the second working range.

7. The method of claim 1 in which data for keys within ranges are not maintained for later processing after a split.

8. The method of claim 1 in which the one or more life intervals are used to audit the database system.

9. The method of claim 1 in which the one or more life intervals are used to generate past versions of data associated with the range of keys.

10. The method of claim 1, wherein separately processing the first portion and the second portion comprises:

identifying at least some of the one or more life intervals for the first portion or the second portion by restoring a database table to one or more prior states using at least a portion of a log record to re-generate information for identification of the at least some of the one or more life intervals.

11. The method of claim 1, wherein a first storage unit associated with the first working range comprises the first block on the physical, non-transitory computer usable storage medium, and a second storage unit associated with the second working range comprises the second block on the physical, non-transitory computer usable storage medium.

12. A computer program product comprising a non-transitory computer usable medium having executable code to execute a process for determining one or more life intervals for a range of keys in a database system to retrieve one or more past versions for one or more data items corresponding to the range of keys in the database system, the process comprising:

receiving a range of keys for which it is desired to determine one or more life intervals;

determining whether the range of keys should be split into a first working range and a second working range based at least in part upon storage locations of the first working range and the second working range, wherein the first working range includes a first portion of keys, and the second working range-includes a second portion of keys, wherein determining whether the range of keys should be split into the first working range and the second working range is performed by determining whether the range of keys is situated within a single block on a physical, non-transitory computer usable storage medium for storing data in the database system, and wherein examination is performed on a branch between a first leaf block and a second leaf block and a determining is made whether the range of keys is over both the first leaf block and the second leaf block;

splitting, in response to the determination of whether the range of keys should be split, the range of keys into the first and second portion of keys; and

separately processing the first portion and the second portion to determine the one or more life intervals of one or more keys of the first and second portion of keys, wherein the determination of the life interval comprises applying a portion of an undo log record in a reverse temporal order to restore the one or more past versions by respectively re-generating the one or more past versions into a database table or one or more instances of the database table.

14. The computer program product of claim 12, wherein separately processing the first portion and the second portion comprises:

identifying at least some of the one or more life intervals for the first portion or the second portion by restoring a database table to one or more prior states using at least a portion of a log record to re-generate information for identification of the at least some of the one or more life intervals.

15. The computer program product of claim 12, wherein a first storage unit associated with the first working range comprises the first block on the physical, non-transitory computer usable storage medium, and a second storage unit associated with the second working range comprises the second block on the physical, non-transitory computer usable storage medium.

13. A system for determining one or more life intervals for a range of keys in a database system to retrieve one or more past versions for one or more data items corresponding to the range of keys in the database system, comprising:

a computer system which comprises at least one processor that is configured at least to;

receive a range of keys for which it is desired to determine one or more life intervals;

determine whether the range of keys should be split into a first working range and a second working range based at least in part upon storage locations of the first working range and the second working range, wherein the first working range includes a first portion of keys, and the second working range includes a second portion of keys, wherein determining whether the range of keys should be split into the first working range and the second working range is performed by determining whether the range of keys is situated within a single block on a physical, non-transitory computer usable storage medium for storing data in the database system, and wherein examination is performed on a branch between a first leaf block and a second leaf block and a determinion is made whether the range of keys is over both the first leaf block and the second leaf block;

split, in response to the determination of whether the range of keys should be split, the range of keys into the first and second portion of keys; and

separately process the first portion and the second portion to determine the one or more life intervals of one or more keys of the first and second portion of keys, wherein the determination of the life interval comprises applying a portion of an undo log record in a reverse temporal order to restore the one or more past versions by respectively re-generating the one or more past versions into a database table or one or more instances of the database table.

16. The system of claim 13, wherein the at least one processor that is to separately process the first portion and the second portion is further to:

identify at least some of the one or more life intervals for the first portion or the second portion by restoring a database table to one or more prior states using at least a portion of a log record to re-generate information for identification of the at least some of the one or more life intervals.

17. The system of claim 13, wherein a first storage unit associated with the first working range comprises the first block on the physical, non-transitory computer usable storage medium, and a second storage unit associated with the second working range comprises the second block on the physical, non-transitory computer usable storage medium.