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

• US 20050120064A1
• Filed: 09/03/2004
• Published: 06/02/2005
• Est. Priority Date: 09/06/2003
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Sinha, Bipul, Ganesh, Amit, Raja, Vivekanandhan
• Granted Patent: US 8,015,161 B2
• Time in Patent Office: Days
• 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 key in a database system, comprising:

(a) receiving a key for which it is desired to determine one or more life intervals;

(b) walking an index structure to identify a location where the key exists or should exist;

(c) reviewing past versions of the location associated with the key;

(d) determining if a structural change has occurred to the location, and if so, accessing as of a time prior to the structural change; and

(e) determining the one or more life intervals for the key based upon analysis of type of operation detected against the key and whether the key existed prior to the operation.

4. The method of claim 1, in which the action of reviewing past versions of the location associated with the key is performed by applying one or more undo records, in which the context object is updated based upon identification of an undo record having a different transaction identifier.

6. The method of claim 1 in which the key is a primary key.

7. The method of claim 1 in which the location is an index block.

8. The method of claim 1 in which the action of reviewing past versions of the location associated with the key is performed by applying one or more undo records, in which the undo records are applied until a low point of a range interval has been reached or until there are no further undo records to apply.

9. The method of claim 1 in which the structural change comprises a block split or a block coalesce.

11. The method of claim 1 in which the action of accessing the location as of a time prior to the structural change comprises:

applying undo records to a portion of an index tree associated with the location.

12. The method of claim 11 in which the index tree is re-walked as of the time prior to the structural change and continue applying undo records.

13. The method of claim 1 in which the type of operation detected is an insert operation.

14. The method of claim 13 further comprising:

determining a commit time for the transaction that performed the insert operation;

searching for the key prior to the commit time.

15. The method of claim 13 in which it is determined that the key did not exist before the transaction, and the start point of the presently detected life interval is based upon the commit time of the transaction that performed the insert operation to the end-life-interval time for the present analysis.

16. The method of claim 13 in which it is determined that the key existed before the transaction that performed the insert operation.

17. The method of claim 16 in which a present insert has occurred and the presently detected life interval is based upon the commit time of the transaction that performed the insert operation to the end-life-interval time for the present analysis.

18. The method of claim 16 in which a delete has occurred, and the presently detected life interval is based upon the commit time of the transaction that performed the insert operation to the current time or a subsequent transaction commit.

19. The method of claim 16 in which further undo records are applied to identify start point to the presently detected life interval.

20. The method of claim 1 in which the type of operation detected is a delete operation.

21. The method of claim 20 in which it is determined that the key existed before the transaction that performed the delete operation.

22. The method of claim 21 in which the presently detected life interval is based upon the commit time of the transaction that performed the delete operation to the current time or a subsequent transaction commit.

23. The method of claim 20 in which it is determined that the key did not exist before the transaction that performed the delete operation, wherein no present life interval is detected.

24. The method of claim 1 in which (a) through (e) are performed for each key in a range of keys.

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

26. The method of claim 25 in which an audit trail is created based upon the one or more life intervals.

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

2. (canceled)

3. (canceled)

5. (canceled)

10. (canceled)

28. A method for determining one or more life intervals for a range of keys in a database system, comprising:

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

(b) determining if a working range should be split;

(c) splitting the working range if required, making a first portion of the working range into the new working range and placing a second portion of the working range on hold for later processing;

(d) if the working range is not split, then processing the working range to determine one or more life intervals for keys within the working range; and

(e) after the working range has been processed, taking a range portion from hold and making it the new working range and continuing to process from (b).

29. The method of claim 28 in which the act of determining whether the working range should be split is performed by determining whether the range of keys is within a single block.

30. The method of claim 29, comprising:

examining a branch between a first leaf block and a second leaf block;

determining whether the range of keys is over both the first leaf block and the second leaf block.

31. The method of claim 29, comprising:

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

32. The method of claim 29 in which the range associated with the second leaf block is put on hold and the range associated with the first leaf block becomes the new working range.

33. The method of claim 28 in which a plurality of ranges are placed on hold.

34. The method of claim 28 in which the range put on hold is placed on a stack.

35. The method of claim 28 in which data for keys within ranges are maintained for later processing, even after a split.

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

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

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

37. (canceled)

38. (canceled)

39. (canceled)

41. (canceled)

43. (canceled)

44. (canceled)

45. A computer program product comprising a 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, the process comprising:

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

(b) determining if a working range should be split;

(c) splitting the working range if required, making a first portion of the working range into the new working range and placing a second portion of the working range on hold for later processing;

(d) if the working range is not split, then processing the working range to determine one or more life intervals for keys within the working range; and

(e) after the working range has been processed, taking a range portion from hold and making it the new working range and continuing to process from (b).

46. A system for determining one or more life intervals for a range of keys in a database system, comprising:

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

(b) logic for determining if a working range should be split;

(c) logic for splitting the working range if required, making a first portion of the working range into the new working range and placing a second portion of the working range on hold for later processing;

(d) logic for processing the working range to determine one or more life intervals for keys within the working range if the working range is not split; and

(e) logic for, after the working range has been processed, taking a range portion from hold and making it the new working range and continuing to process from (b).

47. A computer program product comprising a computer usable medium having executable code to execute a process for determining one or more life intervals for a key in a database system, the process comprising:

(a) receiving a key for which it is desired to determine one or more life intervals;

(b) walking an index structure to identify a location where the key exists or should exist;

(c) reviewing past versions of the location associated with the key;

(d) determining if a structural change has occurred to the location, and if so, accessing as of a time prior to the structural change; and

(e) determining the one or more life intervals for the key based upon analysis of type of operation detected against the key and whether the key existed prior to the operation.

48. A system for determining one or more life intervals for a key in a database system, comprising:

(a) logic for receiving a key for which it is desired to determine one or more life intervals;

(b) logic for walking an index structure to identify a location where the key exists or should exist;

(c) logic for reviewing past versions of the location associated with the key;

(d) logic for determining if a structural change has occurred to the location, and if so, accessing as of a time prior to the structural change; and

(e) logic for determining the one or more life intervals for the key based upon analysis of type of operation detected against the key and whether the key existed prior to the operation.