Interval garbage collection for multi-version concurrency control in database systems

1. A method, implemented by a computing device, for performing interval garbage collection in a database environment using multi-version concurrency control (MVCC), the method comprising:

obtaining a set of active snapshot timestamps for corresponding active snapshots in the database environment;

obtaining a set of record version timestamps for corresponding record versions associated with a record in the database environment;

using the set of active snapshot timestamps and the set of record version timestamps, identifying one or more of the record versions that are not visible to any of the active snapshots, wherein the identified record versions have record version timestamps that are greater than a minimum of the set of active snapshot timestamps; and

collecting the identified record versions as garbage record versions.

2. The method of claim 1 , wherein identifying one or more of the record versions that are not visible to any of the set of active snapshots comprises:

determining a visible interval for a record version; and

determining whether there are any active snapshots that are within the visible interval.

3. The method of claim 2 , wherein the visible interval is from the record version timestamp for the record version up to, but not including, a next greater record version timestamp in the set of record version timestamps.

4. The method of claim 1 , wherein identifying one or more of the record versions that are not visible to any of the set of active snapshots comprises:

for each record version:

determining a visible interval for the record version, wherein the visible interval is from the record version timestamp for the record version up to, but not including, a next greater record version timestamp in the set of record version timestamps;

determining whether there are any active snapshots that are within the visible interval; and

when there are no active snapshots within the visible interval, determining that the record version is not visible to any of the active snapshots.

5. The method of claim 1 , wherein the method performs interval garbage collection without using a global minimum timestamp value.

6. The method of claim 1 , wherein the record versions that are identified as garbage record versions are deleted from a version space of the database environment.

7. The method of claim 1 , wherein identifying one or more of the record versions that are not visible to any of the set of active snapshots comprises:

calculating a subset of record versions, where T represents the set of record version timestamps and T∩ is the subset, that are not visible to any of the set of active snapshots, where S represents the set of active snapshot timestamps, satisfying an equation:

T∩={t|t∈T ,LGN( t+ 1, T )≤LGN( t,S )}.

8. The method of claim 1 , further comprising:

performing the method for one or more additional records in the database environment.

9. One or more computing devices operating a database environment using multi-version concurrency control (MVCC) configured to perform operations for interval garbage collection, the operations comprising:

obtaining a set of active snapshot timestamps for corresponding active snapshots in the database environment;

obtaining a set of record version timestamps for corresponding record versions associated with a record in the database environment;

using the set of active snapshot timestamps and the set of record version timestamps, identifying one or more of the record versions that are not visible to any of the set of active snapshots, wherein the identified record versions have record version timestamps that are greater than a minimum of the set of active snapshot timestamps; and

collecting the identified record versions as garbage record versions.

10. The one or more computing devices of claim 9 , wherein identifying one or more of the record versions that are not visible to any of the set of active snapshots comprises:

determining a visible interval for a record version; and

determining whether there are any active snapshots that are within the visible interval.

11. The one or more computing devices of claim 10 , wherein the visible interval is from the record version timestamp for the record version up to, but not including, a next greater record version timestamp in the set of record version timestamps.

12. The one or more computing devices of claim 9 , wherein identifying one or more of the record versions that are not visible to any of the set of active snapshots comprises:

for each record version:

determining a visible interval for the record version, wherein the visible interval is from the record version timestamp for the record version up to, but not including, a next greater record version timestamp in the set of record version timestamps;

determining whether there are any active snapshots that are within the visible interval; and

when there are no active snapshots within the visible interval, determining that the record version is not visible to any of the active snapshots.

13. The one or more computing devices of claim 9 , wherein the operations perform interval garbage collection without using a global minimum timestamp value.

14. The one or more computing devices of claim 9 , wherein the record versions that are identified as garbage record versions are deleted from a version space of the database environment.

15. The one or more computing devices of claim 9 , wherein identifying one or more of the record versions that are not visible to any of the set of active snapshots comprises:

calculating a subset of record versions, where T represents the set of record version timestamps and T∩ is the subset, that are not visible to any of the set of active snapshots, where S represents the set of active snapshot timestamps, satisfying an equation:

T∩={t|t∈T ,LGN( t+ 1, T )≤LGN( t,S )}.

16. A computer-readable storage medium storing computer-executable instructions for causing a computing device to perform operations for interval garbage collection in a database environment using multi-version concurrency control (MVCC), the operations comprising:

obtaining an ordered set of active snapshot timestamp values for corresponding active snapshots in the database environment;

obtaining an ordered set of record version timestamp values for corresponding record versions associated with a record in the database environment;

for each record version timestamp value in the ordered set of record version timestamp values:

determining a visible interval for the record version timestamp value, wherein the visible interval is from the record version timestamp value up to, but not including, a next greater record version timestamp value in the ordered set of record version timestamp values;

determining whether there are any active snapshot timestamp values that are within the visible interval; and

when there are no active snapshot timestamp values within the visible interval, adding the record version timestamp value to a garbage version set; and

deleting record versions with corresponding record version timestamp value entries in the garbage version set.

17. The computer-readable storage medium of claim 16 , wherein determining whether there are any active snapshot timestamp values that are within the visible interval comprises:

calculating a least greater number (LGN) for the record version timestamp with respect to the set of active snapshot timestamp values.

18. The computer-readable storage medium of claim 16 , wherein the operations implement a merge-based solution for performing interval garbage collection that comprises merging the two ordered sets.

19. The computer-readable storage medium of claim 16 , wherein the operations perform interval garbage collection to delete garbage record versions with record version timestamp values greater than a global minimum timestamp value.

20. The computer-readable storage medium of claim 16 , the operations further comprising:

performing the operations for interval garbage collection for one or more additional records in the database environment.