Database lockless index for accessing multi-version concurrency control data

Patent metadata

Field	Value
Publication number	US-10552402-B2
Application number	US-201414553723-A
Country	US
Kind code	B2
Filing date	Nov 25, 2014
Priority date	Nov 25, 2014
Publication date	Feb 4, 2020
Grant date	Feb 4, 2020

Abstract

An operation on a row of a table of a database is initiated. Thereafter, a multi-version concurrency control (MVCC) object is accessed to identify blocks associated with the row position of the row using bitwise operations. Subsequently, a row state block computed based on the row position of the row is accessed to determine a row state for the row. At least one other block is accessed, based in part on the row state, to obtain at least one timestamp from the computed offset based on the row. Next, the at least one timestamp is stored or retrieved. Related apparatus, systems, techniques and articles are also described.

First claim

What is claimed is:

1. A method comprising:
executing a first query at a database by at least performing a first operation on a row of a table of the database, the performance of the first operation including:
accessing a multi-version concurrency control (MVCC) object to identify a row state block and a timestamp block associated with a row position of the row;
accessing the row state block to update a state of the row, the row state block being updated at a first offset computed based on the row position of the row; and
accessing the timestamp block to update at least one a commit timestamp and a delete timestamp associated with the row, the timestamp block being updated at a second offset computed based on the row position of the row; and

responding to the first query or a second query requiring a second operation to be performed on the row of the table concurrently with the first operation by at least:
accessing the MVCC object to retrieve the state of the row;
in response to the state of the row indicating that the row is visible, performing the second operation on the row concurrently with the first operation; and
in response to the state of the row indicating a check on at least one of the commit timestamp and the delete timestamp associated with the row, accessing the MVCC object to retrieve the at least one of the commit timestamp and the delete timestamp associated with the row, performing the second operation on the row concurrently with the first operation based on a timestamp of the second operation being at least one of greater than the commit timestamp associated with the row and less than the delete timestamp associated with the row, the timestamp of the second operation being greater than the commit timestamp of the row indicating that the first operation is committed prior to the second operation, and the timestamp of the second operation being less than the delete timestamp of the row indicating that the row is deleted subsequent to the second operation.

2. The method of claim 1 further comprising:
accessing a versioned vector at a slot computed using bit shift operations based on the row position of the row to obtain a block handle, the block handle comprising a pointer to the block and a handle to a page associated with the block.

3. The method of claim 1 , wherein the first offset and/or the second offset are computed using one or more bit shift operations.

4. The method of claim 2 further comprising:
registering the block handle in an index structure comprising a plurality of block handles.

5. The method of claim 4 , wherein there are two threads attempting the insert a block handle in the index structure such that a first thread inserts the block handle in the index structure using an atomic operation and the other thread will use the registered value by destroying its own allocated block.

6. The method of claim 2 , wherein the page is persisted.

7. The method of claim 1 , wherein the first operation comprises an insert operation and/or a delete operation, and wherein the second operation comprises a read operation.

8. The method of claim 1 , wherein the row state block comprises a row state vector encapsulating a plurality of row states associated with rows of the table.

9. The method of claim 1 , further comprising:
performing garbage collection to at least clear and free a memory associated with the row based at least on a minimum timestamp of one or more active read operations being greater than the delete timestamp of the row, the performing of the garbage collection further setting the state of the row to indicate the row as being invisible.

10. A non-transitory computer program product storing instructions which, when executed by at least one hardware data processor forming part of at least one computing device, results in operations comprising:
executing a first query at a database by at least performing a first operation on a row of a table of the database, the performance of the first operation including:
accessing a multi-version concurrency control (MVCC) object to identify a row state block and a timestamp block associated with a row position of the row;
accessing the row state block to update a state of the row, the row state block being updated at a first offset computed based on the row position of the row; and
accessing the timestamp block to update at least one a commit timestamp and a delete timestamp associated with the row, the timestamp block being updated at a second offset computed based on the row position of the row; and

responding to the first query or a second query requiring a second operation to be performed on the row of the table concurrently with the first operation by at least:
accessing the MVCC object to retrieve the state of the row;
in response to the state of the row indicating that the row is visible, performing the second operation on the row concurrently with the first operation; and
in response to the state of the row indicating a check on at least one of the commit timestamp and the delete timestamp associated with the row, accessing the MVCC object to retrieve the at least one of the commit timestamp and the delete timestamp associated with the row, performing the second operation on the row concurrently with the first operation based on a timestamp of the second operation being at least one of greater than the commit timestamp associated with the row and less than the delete timestamp associated with the row, the timestamp of the second operation being greater than the commit timestamp of the row indicating that the first operation is committed prior to the second operation, and the timestamp of the second operation being less than the delete timestamp of the row indicating that the row is deleted subsequent to the second operation.

11. The computer program product of claim 10 , wherein the operations further comprise:
accessing a versioned vector at a slot computed using bit shift operations based on the row position of the row to obtain a block handle, the block handle comprising a pointer to the block and a handle to a page associated with the block.

12. The computer program product of claim 10 , wherein the first offset and/or the second offset are computed using one or more bit shift operations.

13. The computer program product of claim 12 , wherein the operations further comprise:
registering the block handle in an index structure comprising a plurality of block handles.

14. The computer program product of claim 13 , wherein there are two threads attempting the insert a block handle in the index structure such that a first thread inserts the block handle in the index structure using an atomic operation and the other thread will use the registered value by destroying its own allocated block.

15. The computer program product of claim 10 , wherein the database operation comprises: inserting data, deleting data, or reading data.

16. The computer program product of claim 10 , wherein the first operation comprises an insert operation and/or a delete operation, and wherein the second operation comprises a read operation.

17. The computer program product of claim 10 , wherein the row state block comprises a row state vector encapsulating a plurality of row states associated with rows of the table.

18. A system comprising:
at least one data processor; and
at least one memory storing instructions which, when executed by the at least one data processor, results in operations comprising:
executing a first query at a database by at least performing a first operation

Assignees

• Eluri Amarnadh Sai
• Schreter Ivan
• Tonder Andreas

Inventors

• Eluri Amarnadh Sai
• Schreter Ivan
• Tonder Andreas

Classifications

• G06F16/2308 Primary

  Concurrency control (transaction processing G06F9/466) · CPC title

• G06F16/2228

  Indexing structures · CPC title

• G06F16/2322 Primary

  using timestamps · CPC title