Database management system with efficient version control

• US 7,243,088 B2
• Filed: 08/06/2003
• Issued: 07/10/2007
• Est. Priority Date: 08/06/2003
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Listgarten, Sherry, Haldar, Sibsankar, Verma, Sanjay, McAuliffe, Mark L., Hoang, Chi-Kim
• Primary Examiner(s): Kindred; Alford W.
• Application Number:
  US10/636,361
• Publication Number:
  US 20050033720A1
• Time in Patent Office: 1,434 Days
• Field of Search: 707/1, 707/7, 718/1, 710/56
• US Class Current: 707/695
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2329 using versioning
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

A two copy versioning scheme is proposed. The scheme provides efficient implementation for a high read load database and eliminates read dependencies. The versioning scheme provides efficient implementation for transactions executing under ANSI READ COMMITTED isolation, and is extensible to serializable isolation. The two-copy versioning scheme is garbage free meaning that all versions of data records are used during execution and is adapted to index scanning operations. A “deferred delete” scheme allows read transactions to complete data deallocation operations. Statements that require “snapshots” are efficiently supported.

Claims

1. A database system, comprising:

a database containing physical content items; and

a processor creating a pending content item from a committed content item for a write transaction and providing a second read transaction read access only to the committed content item while providing the write transaction read and write access to the pending content item and ownership of both the committed content item and the pending content item, the processor creating a fake delete of the committed content item by flagging the committed content item as deleted when the write transaction commits the pending content item while the committed content item is still being accessed by the second read transaction and transferring ownership of the committed content item to the second read transaction causing the second read transaction to defer deallocation of the committed content item and then causing immediate deallocation of the committed content item when the read transaction finishes accessing the committed content item.

2. A database system according to claim 1 wherein the processor increments a reference count each time a read transaction accesses the committed content item and decrements the reference count each time the read transaction finishes accessing the committed content item, the processor deallocating the committed content item when the committed content item has been previously marked for deletion and the read transaction decrements the reference count to zero.

3. A database system according to claim 2 wherein the processor creates a version-list having a first field pointing to the committed content item, a second field pointing to the pending content item, and a third field storing a transaction Id for a transaction creating the pending content item, the processor supplying the second field in the version-list to transactions matching the transaction Id in the third field and providing the first field to transactions not matching the transaction Id in the third field.

4. A database system according to claim 3 wherein the processor uses a logical tuple to point directly to the committed content item when the write transaction is completed and uses the logical tuple to point to the version-list when the write transaction has created the pending content item.

5. A database system according to claim 3 wherein the processor marks index entries in an index as committed or non committed and provides an index map in the version-list that identifies committed and associated non committed dual entries in the index, the processor scanning the index for a first transaction and returning a null value when the scanned index entry is marked as committed and the index entry is referenced by the index map.

6. A database system according to claim 5 wherein the processor returns a pointer to the pending content item when the index entry is not referenced by the index map and an identifier (Id) for the transaction initiating the index scan matches the transaction Id in the third field of the version-list.

7. A database system according to claim 6 wherein the processor returns a pointer to the committed content item when the index entry is not referenced in the index map and an identifier (Id) for the transaction initiating the index scan does not match the transaction Id in the third field of the version-list.

8. A database system according to claim 1 wherein the processor provides logical tuples that point to physical content items and copies a set of the logical tuples identified in a sort transaction;

the processor incrementing reference counts for the physical content items associated with the copied set of logical tuples, decrementing the reference counts for the physical content items when the sort transaction is completed, and deallocating any of the physical content items that have a delete flag and a zero reference count.

9. The database system according to claim 3 wherein the write transaction performs the fake delete by setting a deleted bit for the committed content item and then deallocating the version-list as if the delete of the committed content item was actually performed irrespective of what other transactions are reading the committed content item while at the same time maintaining an allocation bit for the committed content item in a state that prevents the committed content item from being recycled by the processor.

10. The database system according to claim 9 wherein the read transaction upon completion checks when a reference count for the committed data item previously marked for deletion by the write transaction is decremented to zero and then resets an allocation bit for the committed content item making the committed content item available for recycling without having to write any log records.

11. A computer-readable medium containing code that when executed operates as part of a database management system, the computer-readable medium comprising:

code for managing a database containing physical content items;

code for creating a pending content item from a committed content item for a write transaction;

code for providing a read transaction access to the committed content item while providing the write transaction access to the pending content item;

code for flagging the committed content item as deleted when the write transaction commits the pending content item;

code for deferring deallocation of the committed content item until the read transaction finishes accessing the committed content item; and

code for deallocating a version-list as if the delete of the committed content item was actually performed irrespective of what other transactions are reading the committed content item while at the same time maintaining an allocation bit for the committed content item in a state that prevents the committed content item from being recycled by the processor.

12. A computer-readable medium according to claim 11 including:

code for incrementing a reference count each time a read transaction accesses the committed content item and decrementing the reference count each time the read transaction finishes accessing the committed content item; and

code for deallocating the committed content item when the committed content item has been previously marked for deletion and the read transaction decrements the reference count to zero.

13. A computer-readable medium according to claim 12 including:

code for creating a version-list having a first field pointing to the committed content item, a second field pointing to the pending content item, and a third field storing a transaction Id for a transaction creating the pending content item; and

code for supplying the second field in the version-list to transactions matching the transaction Id in the third field and providing the first field to transactions not matching the transaction Id in the third field.

14. A computer-readable medium according to claim 13 including:

code for using a logical tuple to point directly to the committed content item when the write transaction is completed and using the logical tuple to point to the version-list when the write transaction has created the pending content item.

15. A computer-readable medium according to claim 13 including:

code for marking index entries in an index as committed or non committed and providing an index map in the version-list that identifies committed and associated non committed dual entries in the index;

code for scanning the index for a first transaction and returning a null value when the scanned index entry is marked as committed and the index entry is referenced by the index map;

code for returning a pointer to the pending content item when the index entry is not referenced by the index map and an identifier (Id) for the transaction initiating the index scan matches the transaction Id in the third field of the version-list; and

code for returning a pointer to the committed content item when the index entry is not referenced in the index map and an identifier (Id) for the transaction initiating the index scan does not match the transaction Id in the third field of the version-list.

16. A database management system, comprising:

means for managing a database containing physical content items;

means for creating a pending content item from a committed content item for a write transaction;

means for providing a read transaction access to the committed content item while providing the write transaction access to the pending content item;

means for flagging the committed content item as deleted when the write transaction commits the pending content item; and

means for deferring deallocation of the committed content item until the read transaction finishes accessing the committed content item;

means for incrementing a reference count each time a read transaction accesses the committed content item and decrementing the reference count each time the read transaction finishes accessing the committed content item; and

means for deallocating the committed content item when the committed content item has been previously marked for deletion and the read transaction decrements the reference count to zero.

17. The database management system according to claim 16 including:

means for creating a version-list having a first field pointing to the committed content item, a second field pointing to the pending content item, and a third field storing a transaction Id for a transaction creating the pending content item; and

means for supplying the second field in the version-list to transactions matching the transaction Id in the third field and providing the first field to transactions not matching the transaction Id in the third field.

18. The database management system according to claim 17 including:

means for using a logical tuple to point directly to the committed content item when the write transaction is completed and using the logical tuple to point to the version-list when the write transaction has created the pending content item.

19. The database management system according to claim 17 including:

means for marking index entries in an index as committed or non committed and providing an index map in the version-list that identifies committed and associated non committed dual entries in the index;

means for scanning the index for a first transaction and returning a null value when the scanned index entry is marked as committed and the index entry is referenced by the index map;

means for returning a pointer to the pending content item when the index entry is not referenced by the index map and an identifier (Id) for the transaction initiating the index scan matches the transaction Id in the third field of the version-list; and

means for returning a pointer to the committed content item when the index entry is not referenced in the index map and an identifier (Id) for the transaction initiating the index scan does not match the transaction Id in the third field of the version-list.

20. A method for managing a database, comprising:

managing the database containing physical content items;

creating a pending content item from a committed content item for a write transaction;

providing a read transaction access to the committed content item while providing the write transaction read and write access to the pending content item and control over both the committed content item and the pending content item;

flagging the committed content item as deleted when the write transaction commits the pending content item even though the committed content item is not currently available for deletion and still being accessed by the read transaction, the flagging of the committed content item transferring deallocation control of the committed content item from the write transaction to the read transaction; and

deferring deallocation of the committed content item until the read transaction finishes accessing the committed content item.

21. The method according to claim 20 including:

incrementing a reference count each time a read transaction accesses the committed content item and decrementing the reference count each time the read transaction finishes accessing the committed content item; and

deallocating the committed content item when the committed content item has been previously marked for deletion and the read transaction decrements the reference count to zero.

22. The method according to claim 21 including:

creating a version-list having a first field pointing to the committed content item, a second field pointing to the pending content item, and a third field storing a transaction Id for a transaction creating the pending content item; and

supplying the second field in the version-list to transactions matching the transaction Id in the third field and providing the first field to transactions not matching the transaction Id in the third field.

23. The method according to claim 22 including using a logical tuple to point directly to the committed content item when the write transaction is completed and using the logical tuple to point to the version-list when the write transaction has created the pending content item.

24. The method according to claim 22 including:

marking index entries in an index as committed or non committed and providing an index map in the version-list that identifies committed and associated non committed dual entries in the index;

scanning the index for a first transaction and returning a null value when the scanned index entry is marked as committed and the index entry is referenced by the index map;

returning a pointer to the pending content item when the index entry is not referenced by the index map and an identifier (Id) for the transaction initiating the index scan matches the transaction Id in the third field of the version-list; and

returning a pointer to the committed content item when the index entry is not referenced in the index map and an identifier (Id) for the transaction initiating the index scan does not match the transaction Id in the third field of the version-list.