Deleting records in a multi-level storage architecture without record locks

• US 10,162,766 B2
• Filed: 03/15/2013
• Issued: 12/25/2018
• Est. Priority Date: 04/30/2012
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Faerber, Franz, Lee, Juchang, Schreter, Ivan
• Primary Examiner(s): Chan, Tracy C.
• Application Number:
  US13/844,044
• Publication Number:
  US 20140136788A1
• Time in Patent Office: 2,111 Days
• Field of Search: None
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/23 Updating

Abstract

The multi-level storage system and method of deleting first level storage structure pages or records without record locks. The method includes determining whether a record to be deleted from the first level storage structure has any uncommitted write operation, and if the record has an uncommitted write operation, the record is kept in the first level storage structure. Record-moved version information is added to the record to designate the record being moved from the first level storage structure to the second level storage structure. Data change operations are executed for the record based on the record-moved version information without waiting until the record'"'"'s movement from the first level storage structure to the second level storage structure finishes.

Claims

1. In a unified table architecture of an in-memory computing system having a multi-level storage architecture, the multi-level storage architecture having a first level storage structure to store incoming data requests in a logical row format as data records, a second level storage structure to encode and store the data records in a logical column format, and a main memory to compress and store the encoded data records for long-term storage, the main memory being partitioned into a passive main part and an active main part, a method comprising:

determining, by one or more processors, whether a record of the data records located in the first level storage structure has an uncommitted write operation;

if the record has the uncommitted write operation, keeping, by the one or more processors, the record in the first level storage structure;

if the record does not have the uncommitted write operation;

executing, by the one or more processors, data change operations on the record;

moving, by the one or more processors, the record from the first level storage to the second level storage;

adding, by the one or more processors, record-moved version information to the record to designate that the record has been moved from the first level storage structure to the second level storage structure; and

merging, by the one or more processors, the record in the second level storage structure into the active main part, the merging into the active main part being based on an encoding scheme specific to a dictionary of the active main part, the dictionary of the active main part being separate from and dependent on a dictionary of the passive main part.

2. The method in accordance with claim 1, further comprising:

if the record in the first level storage structure maintains the record-moved version information, deleting, by the one or more processors, data corresponding to the record-moved version information in the second level storage structure.

3. The method in accordance with claim 2, further comprising:

reviving, by the one or more processors and using data change information associated with the record-moved version information, data that is stored in the first level storage structure and is related to the record.

4. The computer implemented method in accordance with claim 1, wherein the one or more processors are configured to look up the record in the multi-level storage architecture prior to finding the record in the first level storage structure and the determining of whether the record the first level storage structure has an uncommitted write operation, the one or more processors configured to look up the record in the second level storage structure if the record would not have been found in the first level storage structure, the one or more processors configured to further look up the record in the main memory if the record would not have been found in one of the first level storage structure and the second level storage structure.

5. The computer implemented method in accordance with claim 4, wherein:

the first level storage structure, the second level storage structure and the main memory have different corresponding visibility information structures, at least one of the different visibility information structures being modified when a location of the record has been found after the looking up.

6. The computer implemented method in accordance with claim 1, wherein the data change operations manage a memory of the in-memory computing system.

7. The computer implemented method in accordance with claim 6, wherein the management of the memory is performed during a garbage collection phase.

8. The method of claim 1, wherein the data records stored in the first level storage structure are arranged in ten thousand to one hundred thousand rows per table of the first level storage structure.

9. The method of claim 1, wherein the data records stored in the first level storage structure are optimized for time taken to perform an insert operation, a delete operation, a field update operation, and a record projection operation associated with the first level storage structure.

10. The method of claim 1, wherein the second level storage structure performs the encoding of the data records by implementing an unsorted dictionary, the encoding using the unsorted dictionary conserving memory usage and optimizing execution of validation of unique constraints.

11. The method of claim 1, wherein:

the data records in the first level storage structure are compressed at a first rate; and

the main memory performs the compression at a second rate that is higher than the first rate.

12. A computer implemented method comprising:

providing a multi-level storage architecture having a first level storage structure to store incoming data requests in a logical row format as data records, a second level storage structure to encode and store the data records in a logical column format, and a main memory to compress and store the encoded data records for long-term storage, the main memory being partitioned into a passive main part and an active main part;

determining whether a record located in the first level storage structure has an uncommitted write operation;

if the record has the uncommitted write operation, keeping the record in the first level storage structure;

if the record does not have the uncommitted write operation;

executing data change operations on the record;

moving the record from the first level storage to the second level storage;

adding record-moved version information to the record to designate that the record has been moved from the first level storage structure to the second level storage structure; and

merging the record in the second level storage structure into the active main part, the merging into the active main part being based on an encoding scheme specific to a dictionary of the active main part, the dictionary of the active main part being separate from and dependent on a dictionary of the passive main part.

13. The computer implemented method in accordance with claim 12, further comprising:

if the record in the first level storage structure maintains the record-moved version information, deleting data corresponding to the record-moved version information in the second level storage structure.

14. The computer implemented method in accordance with claim 13, further comprising:

reviving, using data change information associated with the record-moved version information, data that is stored in the first level storage structure and is related to the record.

15. The computer implemented method in accordance with claim 12, wherein the determining, the keeping, the executing, the moving, and the adding are performed by one or more processors.

16. A system comprising:

at least one programmable processor;

a multi-level storage architecture, the multi-level storage architecture having a first level storage structure to store incoming data requests in a logical row format as data records, a second level storage structure to encode and store the data records in a logical column format, and a main memory to compress and store the encoded data records for long-term storage, the main memory being partitioned into a passive main part and an active main part; and

a machine-readable medium storing instructions that, when executed by the at least one processor, cause the at least one programmable processor to perform operations comprising;

determining whether a record of the data records located in the first level storage structure has an uncommitted write operation;

if the record has the uncommitted write operation, keeping the record in the first level storage structure;

if the record does not have the uncommitted write operation;

executing data change operations on the record;

moving the record from the first level storage to the second level storage;

adding record-moved version information to the record to designate has been moved from the first level storage structure to the second level storage structure; and

merging the record in the second level storage structure into the active main part, the merging into the active main part being based on an encoding scheme specific to a dictionary of the active main part, the dictionary of the active main part being separate from and dependent on a dictionary of the passive main part.

17. The system in accordance with claim 16, wherein the operations further comprise:

if the record in the first level storage structure maintains the record-moved version information, deleting data corresponding to the record-moved version information in the second level storage structure.

18. The system in accordance with claim 16, wherein the operations further comprise:

reviving, using data change information associated with the record-moved version information, data that is stored in the first level storage structure and is related to the record.