In-memory database system providing lockless read and write operations for OLAP and OLTP transactions

• US 10,127,260 B2
• Filed: 11/25/2014
• Issued: 11/13/2018
• Est. Priority Date: 11/25/2014
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Goel, Anil Kumar, Schreter, Ivan, Lee, Juchang, Andrei, Mihnea, Geissinger, Steffen, Legler, Thomas
• Primary Examiner(s): Channavajjala, Srirama T
• Application Number:
  US14/553,950
• Publication Number:
  US 20160147814A1
• Time in Patent Office: 1,449 Days
• CPC Class Codes: G06F 16/1774 Locking methods, e.g. locking methods for file systems allowing shared and concurrent access to files
• CPC Class Codes: G06F 16/219 Managing data history or versioning querying versioned data G06F16/2474; querying temporal data G06F16/2477
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: G06F 16/2322 using timestamps
• CPC Class Codes: G06F 16/2329 using versioning
• CPC Class Codes: G06F 16/2336 Pessimistic concurrency control approaches, e.g. locking or multiple versions without time stamps
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 16/2393 Updating materialised views
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

As part of a database system comprising a combination of on-disk storage and in-memory storage, a plurality of records that comprise a table are stored in a plurality of fragments that include at least a delta fragment and a main fragment retained in the on-disk storage. Each fragment has visibility data structures to enable multi-version concurrency control. Each fragment can be compressed using dictionary compression and n-bits compression. The fragments are loaded into main system memory in the in-memory storage from the on-disk storage if they are accessed for read operations or write operations and are not already in memory. A plurality of lockless read and write operations are concurrently performed, while providing snapshot isolation, on the at least one of the plurality of fragments while the at least one of the plurality of fragments is in the main system memory.

Claims

1. A method for implementation by a database system comprising a combination of on-disk storage and in-memory storage, the method comprising:

storing, in a plurality of fragments comprising at least a delta fragment and a main fragment retained in the on-disk storage, a plurality of data records that comprise a table, each fragment having visibility data structures to enable multi-version concurrency control (MVCC), the visibility data structures comprising at least one bit identifying a visibility of a row in the table, wherein MVCC information is maintained for each row of each fragment as such rows are inserted, updated, and deleted, the MVCC information comprising at least both of a creation timestamp and a destruction timestamp for each row;

compressing the delta fragment and the main fragment using n-bits compression to generate a compressed main fragment and a compressed delta fragment;

in response to operations comprising read and/or write operations on the row of the table, loading the compressed main fragment and the compressed delta fragment into main system memory in the in-memory storage from the on-disk storage when the compressed main fragment and the compressed delta fragment are accessed for the operations and are not already in the main system memory;

accessing a multi-version concurrency control object to obtain a current system timestamp for the row;

concurrently performing the operations on the row, while providing snapshot isolation, on the at least one of the compressed main fragment and the compressed delta fragment while the at least one of the compressed main fragment and the compressed delta fragment is in the main system memory, wherein the providing snapshot isolation comprises;

making the row visible for allowing changes during concurrent performing of the operations comprising a plurality of lockless read and/or write operations on the compressed delta fragment, the visibility of the row based on the current system timestamp corresponding to when the operations began, the making of the row visible comprising setting the at least one bit to identify the row as visible; and

generating a new system timestamp when the operations commit, such that the new system timestamp becomes a commit identifier for the row; and

wherein a transaction attempting to read rows in a fragment establishes the visibility of each row, optimally for data set reads with varying granularity levels ranging from single row to the whole table, by;

comparing a base timestamp of a consistent view of the transaction with the MVCC information for the row;

or

comparing a control block of the transaction with a referenced transaction control block referred to by the creation or destruction timestamp within the MVCC information.

2. The method of claim 1, wherein, for overloading, a row created or destructed by an open transaction having the creation timestamp or the destruction timestamp contains a reference to a control block corresponding to the transaction which has created or destructed the row, instead of the commit identifier.

3. The method of claim 1, further comprising:

generating log records for each inserted, updated, and deleted statement; and

maintaining the MVCC information of inserted, updated, and deleted rows, optimally for data set changes having varying granularities ranging from single row to the whole table for redo, undo, post-commit and cleanup actions based on the generated log records.

4. The method of claim 1, wherein the table stored in the on-disk storage comprises table schema metadata characterizing a schema for the table and enabling execution of redo, undo, post-commit and cleanup actions without accessing system catalogs.

5. The method of claim 1, further comprising:

storing table data, the MVCC information, and metadata in chains of pages in the on-disk storage.

6. The method of claim 1, wherein elements of column fragments of a delta fragment are loaded into memory by:

storing and directly loading a column data array and dictionary value array into memory; and

recomputing other components forming part of the delta fragment based on the column data array and the dictionary value array.

7. The method of claim 1, wherein the plurality of lockless read and write operations form part of both OLAP and OLTP transactions.

8. The method of claim 7, wherein the lockless read and write operations comprise:

allowing concurrent read operations and write operations such that they do not block each other;

writers applying, using versioned data structures that represent versions of data objects, changes to a latest version of a particular data object, and restarting a change operation in case of a conflict; and

readers concurrently reading from a stable older version of such data object.

9. The method of claim 8, where the versioned data structures are used for data in the in-memory storage including a column values array, an inverted index, a dictionary value array, a dictionary index, the MVCC information, and table schema metadata.

10. The method of claim 1, further comprising:

executing a merge of an existing delta fragment and the main fragment in the in-memory storage, the merge comprising;

creating a new delta fragment and a new main fragment, both in-memory and on-disk;

copying one or more uncommitted rows from the existing delta fragment to the new delta fragment;

copying one or more committed rows from the existing delta fragment and the existing main fragment to the new main fragment;

optionally re-sorting the new main fragment to allow achievement of maximal compression of the data records;

replacing with the new delta fragment and with the new main fragment the existing delta fragment and the existing main fragment; and

dropping the replaced delta fragment and main fragment.

11. The method of claim 1, further comprising:

initiating a database administration operation comprising at least one of;

altering the table, repartitioning the database, moving data from the table, or exporting data from the table.

12. The method of claim 1, wherein the storing, compressing, loading, and performing are implemented by at least one hardware data processor forming part of at least one computing system.

13. A non-transitory computer program product storing instructions for use by a database system comprising a processor and combination of on-disk storage and in-memory storage, the instructions, which when executed by the database system, result in operations comprising:

storing, in a plurality of fragments comprising at least a delta fragment and a main fragment retained in the on-disk storage, a plurality of data records that comprise a table, each fragment having visibility data structures to enable multi-version concurrency control (MVCC), the visibility data structures comprising at least one bit identifying a visibility of a row in the table, wherein MVCC information is maintained for each row of each fragment as such rows are inserted, updated, and deleted, the MVCC information comprising at least both of a creation timestamp and a destruction timestamp for each row;

compressing the delta fragment and the main fragment using n-bits compression to generate a compressed main fragment and a compressed delta fragment;

in response to operations comprising read and/or write operations on the row of the table, loading the compressed main fragment and the compressed delta fragment into main system memory in the in-memory storage from the on-disk storage when the compressed main fragment and the compressed delta fragment are accessed for the operations and are not already in the main system memory;

accessing a multi-version concurrency control object to obtain a current system timestamp for the row;

concurrently performing the operations on the row, while providing snapshot isolation, on the at least one of the compressed main fragment and the compressed delta fragment while the at least one of the compressed main fragment and the compressed delta fragment is in the main system memory, wherein the providing snapshot isolation comprises;

making the row visible for allowing changes during concurrent performing of the operations comprising a plurality of lockless read and/or write operations on the compressed delta fragment, the visibility of the row based on the current system timestamp corresponding to when the operations began, the making of the row visible comprising setting the at least one bit to identify the row as visible; and

generating a new system timestamp when the operations commit, such that the new system timestamp becomes a commit identifier for the row; and

wherein a transaction attempting to read rows in a fragment establishes the visibility of each row, optimally for data set reads with varying granularity levels ranging from single row to the whole table, by;

comparing a base timestamp of a consistent view of the transaction with the MVCC information for the row;

or

comparing a control block of the transaction with a referenced transaction control block referred to by the creation or destruction timestamp within the MVCC information.

14. The non-transitory computer program product of claim 13, wherein, for overloading, a row created or destructed by an open transaction having the creation timestamp or the destruction timestamp contains a reference to a control block corresponding to the transaction which has created or destructed the row, instead of the commit identifier.

15. The non-transitory computer program product of claim 13, wherein the instructions, when executed by the database system, result in operations further comprising:

generating log records for each inserted, updated, and deleted statement; and

maintaining the MVCC information of inserted, updated, and deleted rows, optimally for data set changes having varying granularities ranging from single row to the whole table for redo, undo, post-commit and cleanup actions based on the generated log records.

16. The non-transitory computer program product of claim 13, wherein the table stored in the on-disk storage comprises table schema metadata characterizing a schema for the table and enabling execution of redo, undo, post-commit and cleanup actions without accessing system catalogs.

17. A system comprising:

on-disk storage;

in-memory storage; and

at least one hardware data processor configured to perform operations comprising;

storing, in a plurality of fragments comprising at least a delta fragment and a main fragment retained in the on-disk storage, a plurality of data records that comprise a table, each fragment having visibility data structures to enable multi-version concurrency control (MVCC), the visibility data structures comprising at least one bit identifying a visibility of a row in the table, wherein MVCC information is maintained for each row of each fragment as such rows are inserted, updated, and deleted, the MVCC information comprising at least both of a creation timestamp and a destruction timestamp for each row;

compressing the delta fragment and the main fragment using n-bits compression to generate a compressed main fragment and a compressed delta fragment;

in response to operations comprising read and/or write operations on the row of the table, loading the compressed main fragment and the compressed delta fragment into main system memory in the in-memory storage from the on-disk storage when the compressed main fragment and the compressed delta fragment are accessed for the operations and are not already in the main system memory;

accessing a multi-version concurrency control object to obtain a current system timestamp for the row;

concurrently performing the operations on the row, while providing snapshot isolation, on the at least one of the compressed main fragment and the compressed delta fragment while the at least one of the compressed main fragment and the compressed delta fragment is in the main system memory, wherein the providing snapshot isolation comprises;

making the row visible for allowing changes during concurrent performing of the operations comprising a plurality of lockless read and/or write operations on the compressed delta fragment, the visibility of the row based on the current system timestamp corresponding to when the operations began, the making of the row visible comprising setting the at least one bit to identify the row as visible; and

generating a new system timestamp when the operations commit, such that the new system timestamp becomes a commit identifier for the row; and

wherein a transaction attempting to read rows in a fragment establishes the visibility of each row, optimally for data set reads with varying granularity levels ranging from single row to the whole table, by;

comparing a base timestamp of a consistent view of the transaction with the MVCC information for the row;

or

comparing a control block of the transaction with a referenced transaction control block referred to by the creation or destruction timestamp within the MVCC information.

18. The system of claim 17, wherein, for overloading, a row created or destructed by an open transaction having the creation timestamp or the destruction timestamp contains a reference to a control block corresponding to the transaction which has created or destructed the row, instead of the commit identifier.

19. The system of claim 17, wherein the at least one hardware data processor is configured to perform operations further comprising:

generating log records for each inserted, updated, and deleted statement; and

maintaining the MVCC information of inserted, updated, and deleted rows, optimally for data set changes having varying granularities ranging from single row to the whole table for redo, undo, post-commit and cleanup actions based on the generated log records.

20. The system of claim 17, wherein the table stored in the on-disk storage comprises table schema metadata characterizing a schema for the table and enabling execution of redo, undo, post-commit and cleanup actions without accessing system catalogs.