Tracking dependencies between transactions in a database

• US 5,806,076 A
• Filed: 10/29/1996
• Issued: 09/08/1998
• Est. Priority Date: 10/29/1996
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Bamford, Roger J., Swart, Garret, Ngai, Gary C.
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US08/740,544
• Time in Patent Office: 679 Days
• Field of Search: 707/203, 707/204, 707/201, 707/8, 707/103, 707/100, 707/500
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2329 using versioning
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

A method and an apparatus for tracking of the dependencies between transactions is provided. Every time a data item is updated, a record is made of the transaction that updated the data item. Before another transaction locks a data item previously locked by the transaction, the entry is updated to indicate that the transaction committed and the commit time of the transaction. These entries are contained in a list head that is maintained on the same block as the data item, and a list tail that is stored separate from the data block that contains the data item. A depends-on time is maintained for each transaction. Whenever the transaction updates a data item, the depends-on time is set to the greater of the current depends-on time and the commit time of the most recently committed transaction that updated the version of the data item. Whether a transaction depends on a committed transaction is then determined based on a simple comparison between the depends-on time associated with the transaction and the commit time of the committed transaction.

Claims

1. A method for tracking dependencies between transactions, the method comprising the steps of:

storing data that indicates which transactions have updated a data item, said data including commit times for those transactions that have committed after updating the data item;

storing a depends-on time associated with an active transaction;

accessing a version of the data item in response to executing said active transaction;

reading said data to determine a time value that represents a time that is at least as recent as a commit time of a committed transaction that most recently updated said version of the data item;

updating the depends-on time associated with the active transaction to said time value if said time value represents a time more recent than said depends-on time; and

approximating a determination of whether said active transaction depends on another transaction based on a comparison between a commit time for said other transaction and the depends-on time associated with the active transaction.

2. The method of claim 1 wherein the step of storing data that indicates which transactions have updated a data item includes the steps of:

storing in a data block with said data item a list head that includes a fixed number of entries for transactions that updated said data item; and

storing separate from said data item a list tail that includes additional entries for transactions that updated said data item.

3. The method of claim 2 wherein the step of reading data to determine a time value includes reading said data block without reading said list tail.

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

updating said data item in response to executing a second transaction;

writing over an entry in said list head in response to updating said data item, wherein said entry is the only entry in said list head for a committed transaction;

writing a include time value into the data block in response to writing over said entry, wherein said include time value represents a time that is at least as recent as the commit time of the transaction associated with said entry.

5. The method of claim 4 wherein, when all entries in said list head represent active transactions:

the step of reading said data to determine a time value includes reading said include time value; and

the step of updating the depends-on time associated with the active transaction includes updating the depends-on time to said include time value.

6. A method for tracking dependencies between transactions, the method comprising the steps of:

when a version of a data item is supplied to a transaction, determining an include-time value that represents a time at least as recent as a commit time of a transaction that most recently updated said version of said data item;

resetting depends-on time value associated with said transaction to said include time value if said include time value represents a time that is more recent that said depends-on time value; and

approximating a determination of whether said transaction depends on a committed transaction based on a comparison between a commit time for the committed transaction and the depends-on time of said transaction.

7. The method of claim 6 further comprising the steps of:

storing in a data block on a persistent storage device a stored version of said data item; and

wherein the step of determining said include-time value includes determining said include-time value based on data stored on said data block.

8. The method of claim 7 further comprising the steps of:

storing on said data block a list head that indicates commit times of transactions that have updated said data block; and

wherein the step of determining said include-time value based on data stored on said data block includes determining said include-time value based on said commit times of transactions that have updated said data block.

9. The method of claim 7 further comprising the steps of:

storing in said data block entries that identify a set of transactions that have updated said data block, said entries including commit times for any transaction in said set of transactions that is committed; and

storing in said data block a commit time value specified in an entry of said entries when the entry is to be overwritten;

wherein the step of determining said include-time value includes determining said include-time value based on said commit time value.

10. The method of claim 9 wherein:

the method further comprises the step of determining whether the entry to be overwritten is the only entry of said entries associated with a committed transaction; and

the step of storing in said data block a commit time value specified in an entry is performed in response to determining that the entry to be overwritten is the only entry of said entries associated with a committed transaction.

11. The method of claim 7 further comprising the steps of:

reconstructing said data block by applying one or more undo records to said data block;

wherein said version of said data item is the version of said data item in said reconstructed data block; and

wherein the step of determining said include-time value includes determining said include-time value based on data stored in said reconstructed data block.

12. A computer readable medium having stored thereon sequences of instructions, said sequences of instructions including sequences of instructions which, when executed by a processor, cause the processor to perform the steps of:

when a version of a data item is supplied to a transaction, determining an include-time value that represents a time at least as recent as a commit time of a transaction that most recently updated said version of said data item;

resetting a depends-on time value associated with said transaction to said include time value if said include time value represents a time that is more recent that said depends-on time value; and

approximating a determination of whether said transaction depends on a committed transaction based on a comparison between a commit time for the committed transaction and the depends-on time of said transaction.

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

storing in a data block on a persistent storage device a stored version of said data item; and

wherein the step of determining said include-time value includes determining said include-time value based on data stored on said data block.

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

storing on said data block a list head that indicates commit times of transactions that have updated said data block; and

wherein the step of determining said include-time value based on data stored on said data block includes determining said include-time value based on said commit times of transactions that have updated said data block.

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

storing in said data block entries that identify a set of transactions that have updated said data block, said entries including commit times for any transaction in said set of transactions that is committed; and

storing in said data block a commit time value specified in an entry of said entries when the entry is to be overwritten;

wherein the step of determining said include-time value includes determining said include-time value based on said commit time value.

16. The computer-readable medium of claim 15 wherein:

the computer-readable medium further includes sequences of instructions for performing the step of determining whether the entry to be overwritten is the only entry of said entries associated with a committed transaction; and

the step of storing in said data block a commit time value specified in an entry is performed in response to determining that the entry to be overwritten is the only entry of said entries associated with a committed transaction.

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

reconstructing said data block by applying one or more undo records to said data block;

wherein said version of said data item is the version of said data item in said reconstructed data block; and

wherein the step of determining said include-time value includes determining said include-time value based on data stored in said reconstructed data block.