In-Memory Database System Providing Lockless Read and Write Operations for OLAP and OLTP Transactions

• US 20160147814A1
• Filed: 11/25/2014
• Published: 05/26/2016
• 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
• Granted Patent: US 10,127,260 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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;

compressing each fragment using dictionary compression and n-bits compression;

loading the fragments 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 the main system memory; and

concurrently performing a plurality of lockless read and write operations, 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.

2. The method of claim 1, wherein the snapshot isolation is provided using system-wide timestamps for each record in the delta fragment.

3. The method of claim 2, wherein the snapshot isolation makes rows visible within a transaction based on a consistent view that, in turn, is based on a current system timestamp when the transaction begins.

4. The method of claim 3, wherein the snapshot isolation generates a new system timestamp when the transaction commits, the new system timestamp becoming the commit identifier (ID) for the rows.

5. The method of claim 4, wherein multi-version concurrency control (MVCC) information is maintained for each row of each fragment as such rows are inserted, updated, and deleted.

6. The method of claim 5, wherein the MVCC information comprises at least both of a creation timestamp and a destruction timestamp for each row.

7. The method of claim 6, wherein, for overloading, a row created or destructed by an open transaction has a creation timestamp or a destruction timestamp which, in turn, contains a reference to a control block corresponding to the transaction which has created or destructed the row, instead of a commit ID.

8. The method of claim 7, 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 the control block of the transaction with the referenced transaction control block referred to by the creation or destruction timestamp within the MVCC information.

9. The method of claim 1 further comprising:

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

maintaining multi-version concurrency control 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.

10. 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.

11. The method of claim 1 further comprising:

storing table data, multi-version concurrency control (MVCC) information, and metadata in chains of pages in the on-disk storage.

12. 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.

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

14. The method of claim 13, 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.

15. The method of claim 14, 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, multi-version concurrency control (MVCC) information, and table schema metadata.

16. A method as in 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.

17. 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.

18. 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.

19. 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;

compressing each fragment using dictionary compression and n-bits compression;

loading the fragments 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 the main system memory; and

concurrently performing a plurality of lockless read and write operations, 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.

20. A system comprising:

at least one hardware data processor;

on-disk storage; and

in-memory storage;

wherein;

a plurality of data records that comprise a table are stored in a plurality of fragments comprising 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 is 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 the main system memory; and

a plurality of lockless read and write operations are performed concurrently, 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.