Controlling visibility in multi-version database systems
First Claim
Patent Images
1. A method for controlling visibility of data during transaction processing in a multi-version database management system, comprising:
- receiving a request for a record stored in a multi-version database from a requesting transaction, the requesting transaction having an associated transaction identifier which uniquely identifies the requesting transaction, a transaction invisibility list which identifies other transactions whose effects are to be invisible to the requesting transaction, and an isolation level which describes whether changes made by other transactions are to be visible to the requesting transaction;
wherein the transaction identifier is a numeric value and transaction identifiers are assigned to transactions in increasing numerical order based on a start time of the transaction, such that a first transaction can be determined to start before a second transaction if the transaction identifier associated with the first transaction is numerically less than the transaction identifier associated with the second transaction; and
wherein transaction identifiers associated with transactions that operate in the present have an even numeric value, and transaction identifiers associated with transactions operating “
as-of”
a specified “
as-of”
time in the past have an odd numeric value;
wherein the specified “
as-of”
time is a time in the past that, when used as a argument in an “
as-of”
query, produces the same results as would have been produced if a query occurred in the past at the specified “
as-of”
time;
determining whether the record is visible to the requesting transaction based on the isolation level of the requesting transaction, the transaction identifier, the transaction invisibility list of the requesting transaction, and a creator transaction identifier in the requested record which identifies a transaction that created the record;
assigning a Record ID value to the record when the record is first created, the Record ID uniquely distinguishing the record from all other records, and the Record ID preserved across modifications of the record;
finding a transaction identifier for an earliest transaction that started on or after the specified “
as-of”
time;
creating a new transaction, the new transaction having a start-time equal to the specified “
as-of”
time, a transaction identifier equal to the transaction identifier for the earliest transaction, minus one, and an isolation level set to Read Committed;
initializing an invisibility list of the new transaction to include the transaction identifiers of all transactions having transaction identifiers less than the transaction identifier for the new transaction and end-times greater than the specified “
as-of”
time;
removing from the invisibility list of the new transaction, any transactions serialized before transactions visible to the new transaction; and
adding to a visibility list of the new transaction, any transactions with transaction identifiers greater than the transaction identifier of the new transaction, that are serialized before transactions visible to the new transaction.
8 Assignments
0 Petitions
Accused Products
Abstract
A multi-version database system controls visibility of data during transaction processing. A transaction includes a transaction identifier that identifies the transaction and an invisibility list of transactions whose effects are invisible to the transaction. Changes made by other transactions are visible to the transaction based on the isolation level of the transaction. Records are visible to a transaction based on a creator identifier stored in the record that identifies the transaction that created the record.
-
Citations
39 Claims
-
1. A method for controlling visibility of data during transaction processing in a multi-version database management system, comprising:
-
receiving a request for a record stored in a multi-version database from a requesting transaction, the requesting transaction having an associated transaction identifier which uniquely identifies the requesting transaction, a transaction invisibility list which identifies other transactions whose effects are to be invisible to the requesting transaction, and an isolation level which describes whether changes made by other transactions are to be visible to the requesting transaction; wherein the transaction identifier is a numeric value and transaction identifiers are assigned to transactions in increasing numerical order based on a start time of the transaction, such that a first transaction can be determined to start before a second transaction if the transaction identifier associated with the first transaction is numerically less than the transaction identifier associated with the second transaction; and wherein transaction identifiers associated with transactions that operate in the present have an even numeric value, and transaction identifiers associated with transactions operating “
as-of”
a specified “
as-of”
time in the past have an odd numeric value;wherein the specified “
as-of”
time is a time in the past that, when used as a argument in an “
as-of”
query, produces the same results as would have been produced if a query occurred in the past at the specified “
as-of”
time;determining whether the record is visible to the requesting transaction based on the isolation level of the requesting transaction, the transaction identifier, the transaction invisibility list of the requesting transaction, and a creator transaction identifier in the requested record which identifies a transaction that created the record; assigning a Record ID value to the record when the record is first created, the Record ID uniquely distinguishing the record from all other records, and the Record ID preserved across modifications of the record; finding a transaction identifier for an earliest transaction that started on or after the specified “
as-of”
time;creating a new transaction, the new transaction having a start-time equal to the specified “
as-of”
time, a transaction identifier equal to the transaction identifier for the earliest transaction, minus one, and an isolation level set to Read Committed;initializing an invisibility list of the new transaction to include the transaction identifiers of all transactions having transaction identifiers less than the transaction identifier for the new transaction and end-times greater than the specified “
as-of”
time;removing from the invisibility list of the new transaction, any transactions serialized before transactions visible to the new transaction; and adding to a visibility list of the new transaction, any transactions with transaction identifiers greater than the transaction identifier of the new transaction, that are serialized before transactions visible to the new transaction. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. A method for controlling visibility of data during transaction processing in a multi-version database management system, comprising:
-
receiving a request for a record stored in the multi-version database from a requesting transaction, the requesting transaction having an associated transaction identifier which uniquely identifies the transaction, a transaction invisibility list which identifies other transactions whose effects are to be invisible to the requesting transaction, and an isolation level which describes whether changes made by other transactions are to be visible to the transaction; determining whether the record is visible to the requesting transaction based on the isolation level of the requesting transaction, the transaction identifier, the invisibility list of the requesting transaction, and a creator transaction identifier in the requested record which identifies a transaction that created the record; and rolling back changes of a transaction, comprising; examining all records created, updated or deleted by the transaction; storing an aborted transaction identifier in a deleter transaction identifier field of records created by the requesting transaction, the aborted transaction identifier being less than a numeric value of any other non-NULL transaction identifier; storing a deletion descriptor in a list of deleted records the deletion descriptor including the aborted transaction identifier and information uniquely identifying an associated version of the record; storing a NULL transaction identifier in the deleter transaction identifier field of records deleted by the requesting transaction; removing the deletion descriptor from the list of deleted records, the deletion descriptor including the identifier of the requesting transaction; and writing records with a modified deleter transaction identifier field to a persistent storage device. - View Dependent Claims (15, 16, 17)
-
-
18. A method for controlling visibility of data during transaction processing in a multi-version database management system, comprising:
-
receiving a request for a record stored in the multi-version database from a requesting transaction, the requesting transaction having an associated transaction identifier which uniquely identifies the transaction, a transaction invisibility list which identifies other transactions whose effects are to be invisible to the requesting transaction, and an isolation level which describes whether changes made by other transactions are to be visible to the transaction; determining whether the record is visible to the requesting transaction based on the isolation level of the requesting transaction, the transaction identifier of the requesting transaction, the invisibility list of the requesting transaction, and a creator transaction identifier in the requested record which identifies a transaction that created the record; and retrieving visible records for a requesting transaction operating with Repeatable Read isolation comprising; reading a record from the database; ensuring that the creator transaction identifier of the record is not on the invisibility list of the requesting transaction and has a value less than or equal to the transaction identifier of the requesting transaction; ensuring that a deleter transaction identifier of the record is a NULL transaction identifier, or is greater than the transaction identifier of the requesting transaction, or is both less than the transaction identifier of the requesting transaction and is stored on the invisibility list of the requesting transaction; and ensuring that a list of deleted records does not include a description of the record, or that the record was deleted by a transaction whose transaction identifier was greater than the transaction identifier of the requesting transaction, or that the record was deleted by a transaction whose transaction identifier is both less than the transaction identifier of the requesting transaction and is stored on the invisibility list of the requesting transaction. - View Dependent Claims (19)
-
-
20. A computer readable storage medium containing instructions readable by a computer to configure the computer to control visibility of data during transaction processing in a multi-version database management system comprising:
-
a requesting transaction requesting a record stored in a multi-version database, comprising; an associated transaction identifier which uniquely identifies the requesting transaction; wherein the transaction identifier is a numeric value and transaction identifiers are assigned to transactions in increasing numerical order based on a start time of the transaction, such that a first transaction can be determined to start before a second transaction if the transaction identifier associated with the first transaction is numerically less than the transaction identifier associated with the second transaction; wherein transaction identifiers associated with transactions that operate in the present have an even numeric value, and transaction identifiers associated with transactions operating “
as-of”
a specified “
as-of”
time in the past have an odd numeric value;wherein the specified “
as-of”
time is a time in the past that, when used as a argument in an “
as-of”
query, produces the same results as would have been produced if a query occurred in the past at the specified “
as-of”
time;a transaction invisibility list which identifies other transactions whose effects are to be invisible to the requesting transaction; and an isolation level which describes whether changes made by other transactions are to be visible to the requesting transaction; a transaction manager which receives a request for a record from the requesting transaction and determines whether the record is visible to the requesting transaction based on the isolation level of the requesting transaction, the transaction identifier, the transaction invisibility list of the requesting transaction, and a creator transaction identifier in the requested record which identifies a transaction that created the record; a Record ID manager which assigns a Record ID value to the record when the record is first created, the Record ID uniquely distinguishing the record from all other records, and the Record ID preserved across modifications of the record; wherein the transaction manager finds a transaction identifier for an earliest transaction that started on or after the specified “
as-of”
time, creates a new transaction, the new transaction having a start-time equal to the specified “
as-of”
time, a transaction identifier equal to the transaction identifier for the earliest transaction, minus one, and an isolation level set to Read Committed; and
initializes an invisibility list of the new transaction to include the transaction identifiers of all transactions having transaction identifiers less than the transaction identifier for the new transaction and end-times greater than the specified “
as-of”
time; andwherein the transaction manager removes from the invisibility list of the new transaction, any transactions serialized before transactions visible to the new transaction and adds to a visibility list of the new transaction, any transactions with transaction identifiers greater than the transaction identifier of the new transaction, that are serialized before transactions visible to the new transaction. - View Dependent Claims (21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32)
-
-
33. A computer readable storage medium containing instructions readable by a computer to configure the computer to control visibility of data during transaction processing in a multi-version database management system comprising:
-
a requesting transaction requesting a record stored in a multi-version database comprising; an associated transaction identifier which uniquely identifies the requesting transaction; a transaction invisibility list which identifies other transactions whose effects are to be invisible to the requesting transaction; and an isolation level which describes whether changes made by other transactions are to be visible to the requesting transaction; a transaction manager which receives a request for a record from the requesting transaction and determines whether the record is visible to the requesting transaction based on the isolation level of the requesting transaction, the transaction identifier, the invisibility list of the requesting transaction, and a creator transaction identifier in the requested record which identifies a transaction that created the record. wherein to roll back changes of a transaction the transaction manager; wherein to roll back changes of a transaction the transaction manager; examines all records created, updated or deleted by the transactions; stores an aborted transaction identifier in a deleter transaction identifier field of records created by the requesting transaction, the aborted transaction identifier is less than a numeric value of any other non-NULL transaction identifier; stores a deletion descriptor in a list of deleted records the deletion descriptor including the aborted transaction identifier and information uniquely identifying an associated version of the record; stores a NULL transaction identifier in the deleter transaction identifier field of records deleted by the requesting transaction; removes the deletion descriptor from the list of deleted records, the deletion descriptor including the identifier of the requesting transaction; and writes records with a modified deleter transaction identifier field to a persistent storage device. - View Dependent Claims (34, 35, 36)
-
-
37. A computer readable storage medium containing instructions readable by a computer to configure the computer to control visibility of data during transaction processing in a multi-version database management system comprising:
a requesting transaction requesting a record stored in a multi-version database comprising; an associated transaction identifier which uniquely identifies the requesting transaction; a transaction invisibility list which identifies other transactions whose effects are to be invisible to the requesting transaction; and an isolation level which describes whether changes made by other transactions are to be visible to the requesting transaction; a transaction manager which receives a request for a record from the requesting transaction and determines whether the record is visible to the requesting transaction based on the isolation level of the requesting transaction, the transaction identifier of the requesting transaction, the invisibility list of the requesting transaction, and a creator transaction identifier in the requested record which identifies a transaction that created the record; wherein to retrieve visible records for a requesting transaction operating with Repeatable Read isolation, the transaction manager reads a record from the database and ensures that the creator transaction identifier of the record is not on the invisibility list of the requesting transaction and has a value less than or equal to the transaction identifier of the requesting transaction, ensures that a deleter transaction identifier of the record is a NULL transaction identifier, or is greater than the transaction identifier of the requesting transaction, or is both less than the transaction identifier of the requesting transaction and is stored on the invisibility list of the requesting transaction and ensures that a list of deleted records does not include a description of the record, or that the record was deleted by a transaction whose transaction identifier was greater than the transaction identifier of the requesting transaction, or that the record was deleted by a transaction whose transaction identifier is both less than the transaction identifier of the requesting transaction and is stored on the invisibility list of the requesting transaction. - View Dependent Claims (38)
-
39. A computer readable storage medium containing instructions readable by a computer to configure the computer to control visibility of data during transaction processing in a multi-version database management system comprising:
-
means for receiving a request for a record stored in a multi-version database from a requesting transaction, the requesting transaction having an associated transaction identifier which uniquely identifies the requesting transaction, a transaction invisibility list which identifies other transactions whose effects are to be invisible to the requesting transaction, and an isolation level which describes whether changes made by other transactions are to be visible to the requesting transaction; wherein the transaction identifier is a numeric value and transaction identifiers are assigned to transactions in increasing numerical order based on a start time of the transaction, such that a first transaction can be determined to start before a second transaction if the transaction identifier associated with the first transaction is numerically less than the transaction identifier associated with the second transaction; wherein transaction identifiers associated with transactions that operate in the present have an even numeric value, and transaction identifiers associated with transactions operating “
as-of”
a specified “
as-of”
time in the past have an odd numeric value;wherein the specified “
as-of”
time is a time in the past that, when used as a argument in an “
as-of”
query, produces the same results as would have been produced if a query occurred in the past at the specified “
as-off”
time;means for determining whether the record is visible to the requesting transaction based on the isolation level of the requesting transaction, the transaction identifier, the transaction invisibility list of the requesting transaction, and a creator transaction identifier in the requested record which identifies a transaction that created the record; means for assigning a Record ID value to the record when the record is first created, the Record ID uniquely distinguishing the record from all other records, and the Record ID preserved across modifications of the record; means for finding a transaction identifier for an earliest-transaction that started on or after the specified “
as-of”
time;means for creating a new transaction, the new transaction having a start-time equal to the specified “
as-of”
time;
a transaction identifier equal to the transaction identifier for the earliest transaction, minus one; and
an isolation level set to Read Committed;means for initializing an invisibility list of the new transaction to include the transaction identifiers of all transactions having transaction identifiers less than the transaction identifier for the new transaction and end-times greater than the specified “
as-of”
time;means for receiving a request for a record from a requesting transaction, the requesting transaction having an associated transaction identifier which uniquely identifies the transaction, an invisibility list which identifies other transactions whose effects are to be invisible to the requesting transaction, and an isolation level which describes whether changes made by other transactions are to be visible to the transaction; and means for determining whether the record is visible to the requesting transaction based on the isolation level of the requesting transaction, the transaction identifier, the invisibility list of the requesting transaction, and a creator transaction identifier in the requested record which identifies a transaction that created the record.
-
Specification