Garbage collection of versions driving the garbage collection of multi-version concurrency control timestamps

Patent metadata

Field	Value
Publication number	US-9953050-B2
Application number	US-201414579162-A
Country	US
Kind code	B2
Filing date	Dec 22, 2014
Priority date	Nov 25, 2014
Publication date	Apr 24, 2018
Grant date	Apr 24, 2018

Abstract

Disclosed herein are system, method, and computer program product embodiments for performing garbage collection on a multi-version concurrency control information in the database management system. An embodiment operates by determining, using multi-version concurrency control (MVCC) information, when a row manipulated by a write transaction is visible to a plurality of readers accessing a table that includes the row. The MVCC information for the row includes at least a creation timestamp, a destruction timestamp and a row state. Once the row is visible to the plurality of readers, garbage collecting at least the creation timestamp or the destruction timestamp in the MVCC information. After the creation timestamp or destruction timestamp have been garbage collected, the plurality of readers use the row state to determine accessibility of the row in the table.

First claim

What is claimed is:

1. A computer implemented method, comprising:
determining, using multi-version concurrency control (MVCC) information, when a row manipulated by a write transaction is visible to a plurality of readers accessing a table that includes the row, wherein the row is not visible to at least one reader, wherein the MVCC information for the row includes at least a creation timestamp and a row state;
determining that the MVCC information includes the creation timestamp and that the row is visible to the plurality of readers including the one reader; and
garbage collecting the creation timestamp based on the determination that the row is visible to the plurality of readers including the one reader, wherein subsequent to the garbage collecting the plurality of readers use the row state to determine accessibility of the row in the table, wherein a memory space occupied by the garbage collected creation timestamp is available for a newly created row that is not visible to one or more of the plurality of readers.

2. The method of claim 1 , further comprising:
generating an association in a transaction storage, wherein the association associates the write transaction with the row acted on by the write transaction; and
the determining further comprises accessing the MVCC information for the row using the association.

3. The method of claim 2 , wherein the association identifies a type of an instruction, wherein the type of the instruction identifies whether the write transaction created or destroyed the row in the table.

4. The method of claim 2 , further comprising:
determining a commit timestamp of the write transaction, wherein the commit timestamp is a system timestamp when the write transaction commits;
accessing, using the association, the MVCC information of the row;
storing the commit timestamp as the creation timestamp when the write transaction created the row or as a destruction timestamp when the write transaction deleted the row; and
indicating in the row state to a reader in the plurality of readers to access the creation timestamp or the destruction timestamp to determine accessibility of the row.

5. The method of claim 1 , wherein the determining further comprises:
determining a read timestamp of an oldest reader in the plurality of readers, wherein the oldest reader began executing before remaining readers in the plurality of readers; and
comparing the read timestamp to the creation timestamp when the write transaction creates the row or comparing the read timestamp to a destruction timestamp when the write transaction destroys the row.

6. The method of claim 5 , where the garbage collecting further comprises:
garbage collecting the creation timestamp when the read timestamp is greater than the creation timestamp; or
garbage collecting the destruction timestamp when the read timestamp is greater than the destruction timestamp.

7. The method of claim 1 , wherein the determining further comprises:
identifying a minimum read timestamp, wherein the minimum read timestamp is a read timestamp of an oldest reader;
identifying a new minimum read timestamp, wherein the new minimum read timestamp is a read timestamp of a next oldest reader once the oldest reader completes execution;
determining, using a commit timestamp of the write transaction, that the write transaction committed between the minimum read timestamp and the new minimum read timestamp; and
wherein the garbage collecting further comprises:
garbage collecting the creation timestamp or the destruction timestamp of the write transaction; and
setting the row state to indicate visibility of the row to the plurality of readers.

8. The method of claim 1 , wherein the garbage collecting further comprises:
replacing the creation timestamp with a timestamp that indicates that the row is visible to the plurality of readers; and
setting visibility of the row in the row state, wherein the plurality of readers subsequently use the row state to determine visibility of the row.

9. The method of claim 1 , wherein the garbage collecting further comprises:
replacing a destruction timestamp with a timestamp that indicates that the row is invisible to the plurality of readers; and
setting visibility of the row in the row state, wherein the plurality of readers subsequently use the row state to determine visibility of the row.

10. The method of claim 1 , wherein the row state indicates that the row is visible to the plurality of readers, invisible to the plurality of readers, or visible to a subset of readers in the plurality of readers.

11. A system. comprising:
a memory; and
at least one processor coupled to the memory and configured to:
determine, using multi-version concurrency control (MVCC) information, when a row manipulated by a write transaction is visible to a plurality of readers accessing a table that includes the row, wherein the row is not visible to at least one reader, wherein the MVCC information for the row includes at least a creation timestamp and a row state;
determine that the MVCC information includes the creation timestamp and that the row is visible to the plurality of readers and including the one reader; and
garbage collect the creation timestamp based on the determination that the row is visible to the plurality of readers including the one reader, wherein subsequent to the garbage collecting the plurality of readers use the row state to determine accessibility of the row in the table, wherein a memory space occupied by the garbage collected creation timestamp is available for a newly created row that is not visible to one or more of the plurality of readers.

12. The system of claim 11 , wherein the at least one processor is further configured to:
generate an association in a transaction storage, wherein the association associates the write transaction with the row acted on by the write transaction; and
wherein to determine whether the row is visible to the plurality of readers, the at least one processor is further configured to access the MVCC information for the row using the association.

13. The system of claim 12 , wherein the association identifies a type of an instruction, wherein the type of the instruction identifies whether the write transaction created or destroyed the row in the table.

14. The method of claim 12 , wherein the at least one processor is further configured to:
determine a commit timestamp of the write transaction, wherein the commit timestamp is a system timestamp when the write transaction commits;
access, using the association, the MVCC information of the row;
store the commit timestamp as the creation timestamp when the write transaction created the row or as a destruction timestamp when the write transaction deleted the row; and
indicate in the row state to a reader in the plurality of readers to access the creation timestamp or the destruction timestamp to determine accessibility of the row.

15. The system of claim 11 , wherein to determine whether to row is visible to the plurality of readers the at least one processor is further configured to:
determine a read timestamp of an oldest reader in the plurality of readers, wherein the oldest reader began executing before remaining readers in the plurality of readers; and
compare the read timestamp to the creation timestamp when the write transaction creates the row or comparing the read timestamp to a destruction timestamp when the write transaction destroys the row.

16. The system of claim 15 , where to garbage collect the at least one processor is further configured to:
garbage col

Assignees

• Andrei Mihnea
• Schreter Ivan
• Eluri Amarnadh
• Glebe Thorsten
• Kim Eunsang
• Sap Se

Inventors

• Andrei Mihnea
• Schreter Ivan
• Eluri Amarnadh
• Glebe Thorsten
• Kim Eunsang

Classifications

• G06F16/2322 Primary

  using timestamps · CPC title

• G06F17/30353 Primary

  Physics · mapped topic