Consistent read in a distributed database environment

• US 20020194206A1
• Filed: 04/09/2002
• Published: 12/19/2002
• Est. Priority Date: 06/01/2001
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Ganesh, Amit, Bamford, Roger J.
• Granted Patent: US 7,334,004 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2474 Sequence data queries, e.g. querying versioned data
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

Techniques are provided for determining which data item version to supply to a query. According to the techniques, the determination is made by associating a new field, which indicates the time a data item version was current, with each data item version; associating a new field with each query, which indicates the last change that the query must see made by the transaction to which the query belongs; and determining which data item version to use to answer the query based, in part, on a comparison between the values of the two new fields.

Claims

1. A method for determining which version of a data item to supply to a session, the method comprising the computer-implemented steps of:

maintaining a LAST-TO-SEE-TIMESTAMP, associated with the session, which indicates a time of a last change made in the session that must be seen by the session;

maintaining with a data item version a CLONE-TIME that indicates a time at which the data item version was current; and

determining that the data item version is to be supplied to the session based, at least in part, on a comparison between the CLONE-TIME and the LAST-TO-SEE-TIMESTAMP.

2. The method of claim 1 wherein the step of determining includes selecting, based on said comparison between the CLONE-TIME and the LAST-TO-SEE-TIMESTAMP, the data item version from a plurality of data item versions that qualify to be supplied to the session.

3. The method of claim 1 wherein

a transaction that includes a query is executing in the session;

the LAST-TO-SEE-TIMESTAMP is associated with the query and indicates a time of a last change made by the transaction that must be seen by the query; and

the step of determining that the data item version is to be supplied to the session is performed by determining that the data item version is to be used to answer the query.

4. The method of claim 1 further comprising the step of setting said CLONE-TIME based on a global clock when said data item version is cloned from a current version.

5. The method of claim 1 further comprising the step of setting said CLONE-TIME based on a CLONE-TIME of a non-current data item version when said data item version is cloned from said non-current data item version.

6. The method of claim 1 wherein:

a plurality of nodes in a cluster have data item versions for said data item; and

the method further includes the steps of

maintaining, for each node of said plurality of nodes, CLONE-TIME information for said data item; and

selecting which node to send a request for said data item to based on said CLONE-TIME information.

7. The method of claim 6 wherein the step of maintaining CLONE-TIME information includes maintaining, for said data item, a vector that associates nodes with CLONE-TIMES, wherein the CLONE-TIMES that are associated with a given node in the vector are CLONE-TIMES associated with data item versions that reside in the given node.

8. The method of claim 1 wherein the step of determining includes:

determining, based on removed-data information, whether changes that must be seen have been removed from said data item version; and

determining, based on said CLONE-TIME, whether it is possible that information that must be seen was made to a current version of the data item after creation of the data item version.

9. A method of supplying a data item to a query that must see a particular snapshot of a database, the method comprising the steps of:

maintaining, for a plurality of data item versions that reside in a plurality of nodes, CLONE-TIME information that indicates when the data item versions were current;

determining which data item versions of said plurality of data items versions contain all changes that must be seen by said query based, at least in part, on said CLONE-TIME information; and

selecting a data item version to supply to said query from those data item versions that contain all changes that must be seen by said query.

10. The method of claim 9 wherein the step of determining includes:

determining, based on a CLONE-TIME associated with a data item version, whether changes that must be seen by said query may have been made to said data item after creation of said data item version; and

determining, based on a MOST-RECENT-INCLUSION-TIME associated with said data item version, whether changes that must be seen by said query may have been removed from said data item version.

11. The method of claim 10 wherein the step of selecting includes using the CLONE-TIME information to select a candidate that requires fewer changes to be removed than other candidates.

13. The computer-readable medium of claim 12 wherein the step of determining includes selecting, based on said comparison between the CLONE-TIME and the LAST-TO-SEE-TIMESTAMP, the data item version from a plurality of data item versions that qualify to be supplied to the session.

14. The computer-readable medium of claim 12 wherein a transaction that includes a query is executing in the session;

the LAST-TO-SEE-TIMESTAMP is associated with the query and indicates a time of a last change made by the transaction that must be seen by the query; and

the step of determining that the data item version is to be supplied to the session is performed by determining that the data item version is to be used to answer the query.

15. The computer-readable medium of claim 12 further comprising instructions for performing the step of setting said CLONE-TIME based on a global clock when said data item version is cloned from a current version.

16. The computer-readable medium of claim 12 further comprising instructions for performing the step of setting said CLONE-TIME based on a CLONE-TIME of a non-current data item version when said data item version is cloned from said non-current data item version.

17. The computer-readable medium of claim 12 wherein:

a plurality of nodes in a cluster have data item versions for said data item; and

the computer-readable medium further includes instructions for performing the steps of

maintaining, for each node of said plurality of nodes, CLONE-TIME information for said data item; and

selecting which node to send a request for said data item to based on said CLONE-TIME information.

18. The computer-readable medium of claim 17 wherein the step of maintaining CLONE-TIME information includes maintaining, for said data item, a vector that associates nodes with CLONE-TIMES, wherein the CLONE-TIMES that are associated with a given node in the vector are CLONE-TIMES associated with data item versions that reside in the given node.

19. The computer-readable medium of claim 12 wherein the step of determining includes:

determining, based on removed-data information, whether changes that must be seen have been removed from said data item version; and

determining, based on said CLONE-TIME, whether it is possible that information that must be seen was made to a current version of the data item after creation of the data item version.

12. A computer-readable medium carrying instructions for determining which version of a data item to supply to a session, the instructions comprising instructions for performing the steps of:

maintaining a LAST-TO-SEE-TIMESTAMP, associated with the session, which indicates a time of a last change made in the session that must be seen by the session;

maintaining with a data item version a CLONE-TIME that indicates a time at which the data item version was current; and

determining that the data item version is to be supplied to the session based, at least in part, on a comparison between the CLONE-TIME and the LAST-TO-SEE-TIMESTAMP.

20. A computer-readable medium carrying instructions for supplying a data item to a query that must see a particular snapshot of a database, the instructions comprising instructions for performing the steps of:

maintaining, for a plurality of data item versions that reside in a plurality of nodes, CLONE-TIME information that indicates when the data item versions were current;

determining which data item versions of said plurality of data items versions contain all changes that must be seen by said query based, at least in part, on said CLONE-TIME information; and

selecting a data item version to supply to said query from those data item versions that contain all changes that must be seen by said query.

21. The computer-readable medium of claim 20 wherein the step of determining includes:

determining, based on a CLONE-TIME associated with a data item version, whether changes that must be seen by said query may have been made to said data item after creation of said data item version; and

determining, based on a MOST-RECENT-INCLUSION-TIME associated with said data item version, whether changes that must be seen by said query may have been removed from said data item version.

22. The computer-readable medium of claim 21 wherein the step of selecting includes using the CLONE-TIME information to select a candidate that requires fewer changes to be removed than other candidates.