Database management system with efficient version control

• US 20050033720A1
• Filed: 08/06/2003
• Published: 02/10/2005
• Est. Priority Date: 08/06/2003
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Timesten Performance Software Company
• Inventors: Listgarten, Sherry, Haldar, Sibsankar, Verma, Sanjay, McAuliffe, Mark L., Hoang, Chi-Kim
• Granted Patent: US 7,243,088 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 method for processing data, comprising:

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

providing a second transaction read access to the committed content item while providing the first transaction read/write access to the pending content item;

flagging the committed content item as deleted when the first transaction commits the pending content item; and

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

2. A method according to claim 1 including:

incrementing a reference count each time a read transaction accesses the committed content item;

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

initiating deallocation of the committed content item by the read transaction that decrements the reference count to zero.

3. A method according to claim 2 including:

flagging the committed content item for deletion when the first transaction commits the pending content item;

checking the committed content item for flagged deletion when a completed read transaction reduces the reference count to zero; and

deallocating the committed content item by the read transaction only when the committed content item has been flagged for deletion and has a zero reference count.

4. A method according to claim 1 including:

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

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

5. A method according to claim 4 including:

generating a logical tuple;

using the logical tuple to point directly to the committed content item when no write transaction is accessing the committed content item; and

using the logical tuple to point to the version-list when a write transaction is accessing the committed content item.

6. A method according to claim 4 including:

marking index entries in an index as committed or uncommitted;

providing an index map in the version-list that identifies indexes having committed and associated uncommitted dual entries;

scanning the index for index entries; and

returning a null value according to the index entry marking and the index contained in the index map.

7. A method according to claim 6 including returning a pointer to the pending content item when the index entry is not associated with the index map and an identifier (Id) for a transaction initiating the index scan matches the transaction Id in the third field of the version-list.

8. A method according to claim 7 including returning a pointer to the committed content item when the index entry is not associated with 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.

9. A method according to claim 2 including:

providing logical tuples;

copying a set of the logical tuples identified in a operation requiring “

snapshot”

of data;

incrementing a reference count for the physical content items associated with the copied set of logical tuples;

decrementing the reference count for the physical content items when that operation is completed; and

deallocating any of the physical content items that have a delete flag and have a zero reference count.

10. 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 read transaction access to the committed content item while providing the write transaction access to the pending content item, the processor flagging the committed content item as deleted when the write transaction commits the pending content item and deferring deallocation of the committed content item until the read transaction finishes accessing the committed content item.

11. A database system according to claim 10 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.

12. A database system according to claim 11 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.

13. A database system according to claim 12 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.

14. A database system according to claim 12 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.

15. A database system according to claim 14 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.

16. A database system according to claim 15 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.

17. A database system according to claim 10 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.