Providing a useable version of a data item
View Patent ↗Techniques are provided for providing a data item to a transaction in a multi-versioning system in which the data item may exist on multiple versions of a data block, and were versioning is performed at the granularity of the data block. According to one aspect of the invention, the technique involves locating, within volatile memory, a first version of a data block that includes a first version of the data item. It is then determined whether the first version of the data item is useable by the transaction without respect to whether the first version of the data block is generally useable by the transaction. If the first version of the data item is usable by the transaction, then the data item is established as a candidate that can be provided to the transaction. Thus, the data item within a block may be considered a candidate to be provided to a transaction even when the version of the data block on which the data item resides would otherwise disqualify the data block from being seen by that transaction. If the first version of the data item is not usable by the transaction, then a version of the data item that is usable by the transaction is obtained from a second version of the data block that is different from the first version.
1. A computer-implemented method for providing a data item to a transaction, the method comprising the steps of:
locating, within volatile memory, a first version of a data block that includes a first version of the data item;
determining whether the first version of the data item is useable by the transaction without respect to whether the first version of the data block is useable by the transaction;
if the first version of the data item is usable by the transaction, then establishing said data item as a candidate that can be provided to said transaction; and
if the first version of the data item is not usable by the transaction, then obtaining a version of the data item that is usable by the transaction from a second version of the data block that is different from said first version.
2. The method of claim 1 further comprising the step of generating the second version of the data block by modifying the first version of the data block.
3. The method of claim 1 wherein the step of obtaining a version of the data item that is usable by the transaction from a second version of the data block is performed by obtaining the version of the data item that is useable from a version of the data block that is maintained separate from the first version of the data block.
4. The method of claim 1 wherein the step of determining whether the first version of the data item is useable by the transaction includes the step of comparing version information associated with the data item with snapshot information associated with the transaction.
5. The method of claim 4 wherein the step of comparing version information associated with the data item with snapshot information associated with the transaction includes comparing version information associated with the data item with a snapshot time associated with the transaction.
6. The method of claim 4 wherein the step of comparing version information associated with the data item with snapshot information associated with the transaction includes comparing version information associated with the data item with a MUST-SEE time and a CANNOT-SEE time associated with the transaction.
7. The method of claim 4 wherein:
the step of comparing version information associated with the data item with snapshot information associated with the transaction includes comparing a freshness time associated with the data item with snapshot information associated with the transaction; and
the freshness time indicates a commit time of a committed transaction that most recently updated the first version of the data item within the first version of the data block.
8. The method of claim 7 further comprising the step of identifying the freshness time by performing the steps of:
determining whether the first version of the data item is locked;
if the first version of the data item is locked, then determining whether the transaction that holds a lock on the first version of the data item has actually committed; and
if the transaction that holds the lock on the first data item has actually committed, then using a commit time of said transaction that holds the lock as the freshness time of said data item.
9. The method of claim 7 further comprising the step of identifying the freshness time by performing the steps of:
determining whether the first version of the data item is locked;
if the first version of the data item is locked, then determining whether the transaction that holds a lock on the first version of the data item has actually committed; and
if the transaction that holds the lock on the first data item has not actually committed, then determining whether the transaction that holds the lock on the first data item is the transaction that requires the data item; and
if the transaction that holds the lock on the first data item is not the transaction that requires the data item, then determining that the first version of the data item is not useable by the transaction.
10. The method of claim 1 wherein:
the first version of the data item is established as one candidate of a plurality of candidates that are versions of the data item that are useable by the transaction; and
the method includes the step of selecting which candidate of the plurality of candidates to provide to said transaction.
11. The method of claim 1 wherein:
the transaction is a transaction performed within a multi-versioning database system; and
the data item is a row of a table within said database system.
12. The method of claim 10 wherein the step of selecting which candidate of the plurality of candidates to provide to said transaction is performed based on how the candidate affects a range associated with the transaction, wherein said range is bounded by a MUST-SEE time and a CANNOT-SEE time.
13. The method of claim 12 wherein the step of selecting which candidate of the plurality of candidates to provide is based on which candidate would result in the widest range for the transaction.
14. The method of claim 12 wherein the step of selecting which candidate of the plurality of candidates to provide is based on which candidate would result in the highest CANNOT-SEE time.
15. A computer-readable medium carrying instructions for providing a data item to a transaction, the instructions comprising instructions for performing the steps of:
locating, within volatile memory, a first version of a data block that includes a first version of the data item;
determining whether the first version of the data item is useable by the transaction without respect to whether the first version of the data block is useable by the transaction;
if the first version of the data item is usable by the transaction, then establishing said data item as a candidate that can be provided to said transaction; and
if the first version of the data item is not usable by the transaction, then obtaining a version of the data item that is usable by the transaction from a second version of the data block that is different from said first version.
16. The computer-readable medium of claim 15 further comprising instructions for performing the step of generating the second version of the data block by modifying the first version of the data block.
17. The computer-readable medium of claim 15 wherein the step of obtaining a version of the data item that is usable by the transaction from a second version of the data block is performed by obtaining the version of the data item that is useable from a version of the data block that is maintained separate from the first version of the data block.
18. The computer-readable medium of claim 15 wherein the step of determining whether the first version of the data item is useable by the transaction includes the step of comparing version information associated with the data item with snapshot information associated with the transaction.
19. The computer-readable medium of claim 18 wherein the step of comparing version information associated with the data item with snapshot information associated with the transaction includes comparing version information associated with the data item with a snapshot time associated with the transaction.
20. The computer-readable medium of claim 18 wherein the step of comparing version information associated with the data item with snapshot information associated with the transaction includes comparing version information associated with the data item with a MUST-SEE time and a CANNOT-SEE time associated with the transaction.
21. The computer-readable medium of claim 18 wherein:
the step of comparing version information associated with the data item with snapshot information associated with the transaction includes comparing a freshness time associated with the data item with snapshot information associated with the transaction; and
the freshness time indicates a commit time of a committed transaction that most recently updated the first version of the data item within the first version of the data block.
22. The computer-readable medium of claim 21 further comprising instructions for performing the step of identifying the freshness time by performing the steps of:
determining whether the first version of the data item is locked;
if the first version of the data item is locked, then determining whether the transaction that holds a lock on the first version of the data item has actually committed; and
if the transaction that holds the lock on the first data item has actually committed, then using a commit time of said transaction that holds the lock as the freshness time of said data item.
23. The computer-readable medium of claim 21 further comprising instructions for performing the step of identifying the freshness time by performing the steps of:
determining whether the first version of the data item is locked;
if the first version of the data item is locked, then determining whether the transaction that holds a lock on the first version of the data item has actually committed; and
if the transaction that holds the lock on the first data item has not actually committed, then determining whether the transaction that holds the lock on the first data item is the transaction that requires the data item; and
if the transaction that holds the lock on the first data item is not the transaction that requires the data item, then determining that the first version of the data item is not useable by the transaction.
24. The computer-readable medium of claim 15 wherein:
the first version of the data item is established as one candidate of a plurality of candidates that are versions of the data item that are useable by the transaction; and
the computer-readable medium includes instructions to perform the step of selecting which candidate of the plurality of candidates to provide to said transaction.
25. The computer-readable medium of claim 15 wherein:
the transaction is a transaction performed within a multi-versioning database system; and
the data item is a row of a table within said database system.
26. The computer-readable medium of claim 24 wherein the step of selecting which candidate of the plurality of candidates to provide to said transaction is performed based on how the candidate affects a range associated with the transaction, wherein said range is bounded by a MUST-SEE time and a CANNOT-SEE time.
27. The computer-readable medium of claim 26 wherein the step of selecting which candidate of the plurality of candidates to provide is based on which candidate would result in the widest range for the transaction.
28. The computer-readable medium of claim 26 wherein the step of selecting which candidate of the plurality of candidates to provide is based on which candidate would result in the highest CANNOT-SEE time.