DATABASE MANAGEMENT SYSTEM WITH EFFICIENT VERSION CONTROL

• US 20070233683A1
• Filed: 06/01/2007
• Published: 10/04/2007
• Est. Priority Date: 08/06/2003
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Listgarten, Sherry, Haldar, Sibsankar, Verma, Sanjay, Hoang, Chi-Kim, McAuliffe, Mark
• Granted Patent: US 8,010,497 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 an 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 computer readable medium having stored thereon computer-executable instructions that, when executed by a processor:

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

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

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

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

11. A computer readable medium according to claim 10 wherein the computer-executable instructions when executed by a processor further:

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

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

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

12. A computer readable medium according to claim 11 wherein the computer-executable instructions when executed by a processor further:

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

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

deallocate 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.

13. A method, comprising:

receiving a request to sort a set of physical content items;

creating a set of logical tuples that contain address values pointing to corresponding physical tuples in a table, the table containing a first set of data records identifying a current sorted order for the set of physical tuples and a second set of data records identifying a desired sorted order for the set of physical tuples;

creating a copy of the logical tuples; and

sorting the copy of the logical tuples according to the second set of data records.

14. The method according to claim 13 including:

incrementing a reference count for all of the physical tuples referenced by the sort operation, the incremented reference count preventing the referenced physical tuples from being deleted by other operations until the sort operation is completed; and

allowing the other operations to assign deferred deletes to selected ones of the referenced physical tuples.

15. The method according to claim 14 including:

decrementing the reference counts for each of the physical tuples after the sort operation has completed; and

using the sort operation to deallocate any of the previously referenced physical tuples that have assigned deferred deletes and a zero reference count.

16. The method according to claim 13 including:

assigning a reference count field to each of the physical tuples to track the number of operations referring to the physical tuples;

assigning a deferred delete field to each of the physical tuples to track the physical tuples assigned deferred deletes; and

assigning an allocated field to each of the physical tuples to notify a last operation accessing the physical tuples to deallocate the physical tuples.

17. An apparatus, comprising:

one or more processors;

a memory coupled to the one or more processors having stored thereon computer-executable instructions that, when executed by a processor;

receive a request to sort a set of physical content items;

create a set of logical tuples that contain address values pointing to corresponding physical tuples in a table, the table containing a first set of data records identifying a current sorted order for the set of physical tuples and a second set of data records identifying a desired sorted order for the set of physical tuples;

create a copy of the logical tuples; and

sort the copy of the logical tuples according to the second set of data records.

18. The apparatus according to claim 17 wherein the computer-executable instructions that, when executed by one of the processors, are further configured to:

increment a reference count for all of the physical tuples referenced by the sort operation, the incremented reference count preventing the referenced physical tuples from being deleted by other operations until the sort operation is completed; and

allow the other operations to assign deferred deletes to selected ones of the referenced physical tuples.

19. The apparatus according to claim 18 wherein the computer-executable instructions that, when executed by one of the processors, are further configured to:

decrement the reference counts for each of the physical tuples after the sort operation has completed; and

use the sort operation to deallocate any of the previously referenced physical tuples that have assigned deferred deletes and a zero reference count.

20. A method comprising:

performing a first operation that creates a logical tuple and a committed content item;

creating a first index entry for the first operation that causes the logical tuple to point to the committed content item;

performing a second operation that creates a pending content item from the committed content item;

creating a second index entry for the second operation that causes a read associated with the second operation to skip the first index entry and use the second index entry, the second index entry then causing the logical tuple to point to the pending content item.

21. The method according to claim 20 including creating an index map that causes the read to access the committed content item when a single index entry is associated with the logical tuple and causes the read to access the pending content item when multiple index entries are associated with the logical tuple.

22. The method according to claim 20 including:

creating a version-list having a first committed content item field that points to the committed content item and having a second pending content item field that points to the pending content item; and

having the logical tuple access the first committed content item field when only the first index entry exists and having the logical tuple access the second pending content item field when both the first and second index entries exist.

23. The method according to claim 20 where the first operation is an insert operation and the second operation is an update operation.