Partial merge

• US 10,534,764 B2
• Filed: 09/09/2016
• Issued: 01/14/2020
• 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): Gurmu, Muluemebet
• Application Number:
  US15/261,188
• Publication Number:
  US 20170004158A1
• Time in Patent Office: 1,222 Days
• Field of Search: 706607, 707607
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/24553 of query operations
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

A multi-level storage architecture and method of performing a partial merge are disclosed. A main store is partitioned into a passive main part and an active main part, the active main part being empty at a start of the partial merge, the passive main part storing encoded data records of the main store that are not subject to the partial merge. A values index corresponding to a sorted dictionary of the passive main part is set to a cardinality of n. The data records of a second level storage structure is merged into the active main part, the active main part having a dictionary that starts with a value of n+1, such that the merging into the active main part continues an encoding scheme according to the values index of the passive main part.

Claims

1. An in-memory computing system comprising:

a first level storage structure to store a first set of one or more data records in a logical row format;

a second level storage structure to encode and store a second set of one or more data records in a logical column format, the second level storage being operably coupled to the first level storage structure such that at least one of the first set of one or more data records propagates from the first level storage structure, pivots from the logical row format to the logical column format, and is stored in the second level storage structure; and

a main store partitioned into a passive part and an active part, the active part being empty at a start of a partial merging of the second set of one or more data records in the second level storage structure into the active part, the second set of one or more data records stored within the active part being encoded using a first dictionary, the passive part storing a third set of one or more data records that are not a part of the merging, the third set of one or more data records within the passive part being encoded using a second dictionary, the merging of the second set of one or more data records into the active part being the partial merge, wherein the second dictionary is searched for queried data upon receipt of a point query, the point query comprising the queried data, and wherein the first dictionary is not searched when the queried data is found in the second dictionary, a position of the queried data in the second dictionary being used as an encoding value for the second dictionary as well as the first dictionary, a parallel scan being executed in the active part and the passive part to find the queried data.

2. The in-memory computing system of claim 1, wherein the first level storage structure is configured to receive the first set of one or more data records, the first set of one or more data records being one or more data requests made using any querying language of a plurality of query languages.

3. The in-memory computing system of claim 1, wherein the first level storage structure is optimized for a quick insert, delete, field update, and record projection operations.

4. The in-memory computing system of claim 1, wherein the first level storage structure is configured to store between ten thousand and one hundred thousand rows per table.

5. The in-memory computing system of claim 1, wherein the second level storage structure is configured to store up to ten million rows of the first level storage structure.

6. The in-memory computing system of claim 1, wherein the second level storage structure stores fragments of multiple columns within a single page.

7. The in-memory computing system of claim 1, wherein the main store compresses data prior to storing the data, the compression being performed by a plurality of compression techniques.

8. The in-memory computing system of claim 1, wherein the encoding using the first dictionary and the encoding using the second dictionary is prevented from overlapping.

9. The in-memory computing system of claim 1, wherein:

the cardinality of the second dictionary is a first numerical value; and

the first dictionary starts with a dictionary position value of a second numerical value that is more than the first numerical value.

10. The in-memory computing system of claim 9, wherein a difference between the second numerical value and the first numerical value is one.

11. The in-memory computing system of claim 1, wherein:

the first dictionary is searched subsequent to the searching of the second dictionary when the queried data is not found in the second dictionary.

12. The in-memory computing system of claim 1, wherein upon receipt of a range query, a range specified by the range query is split into a first range associated with the first dictionary and a second range associated with the second dictionary, the first dictionary being searched for the first range, and the second dictionary being searched for the second range.

13. A method comprising:

partitioning, by one or more processors, a main store comprised within a multi-level storage architecture into a passive part and an active part, the multi-level storage architecture further comprising a first level storage structure storing a first set of one or more data records in a row format and a second level storage structure storing a second set of one or more data records in a columnar format, the second level storage being operably coupled to the first level storage structure such that at least one of the first set of one or more data records propagates from the first level storage structure, pivots from the logical row format to the logical column format, and is stored in the second level storage structure;

encoding, by the one or more processors, the first set of one or more data records according to a first dictionary;

encoding, by the one or more processors, the second set of one or more data records according to a second dictionary, the encoding by the second dictionary being non-overlapping with the encoding by the first dictionary;

receiving, by the one or more processors, a point query, the point query comprising queried data;

searching, by the one or more processors, the second dictionary for the queried data; and

when the queried data is found in the second dictionary;

abstaining, by the one or more processors, from searching the first dictionary, a position of the queried data in the second dictionary being used as an encoding value for the second dictionary as well as the first dictionary; and

executing, by the one or more processors, a parallel scan in the active part and the passive part to find the queried data.

14. The method of claim 13, further comprising:

when the queried data is not found in the second dictionary;

searching, by the one or more processors, the first dictionary subsequent to the searching of the second dictionary.

15. The method of claim 13, further comprising:

receiving, by the one or more processors, a range query, the range query specifying a range of values;

splitting, by the one or more processors, the range into a first range associated with the first dictionary and a second range associated with the second dictionary;

searching, by the one or more processors, the first dictionary for the first range; and

searching, by the one or more processors, the second dictionary for the second range.

16. The method of claim 13, further comprising:

assigning, by the one or more processors, a first numerical value for a cardinality of the second dictionary; and

starting, by the one or more processors, the first dictionary with a dictionary position value of a second numerical value that is more than the first numerical value.

17. A non-transitory computer program product storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising:

partitioning a main store comprised within a multi-level storage architecture into a passive part and an active part, the multi-level storage architecture further comprising a first level storage structure storing a first set of one or more data records in a row format and a second level storage structure storing a second set of one or more data records in a columnar format, the second level storage being operably coupled to the first level storage structure such that at least one of the first set of one or more data records propagates from the first level storage structure, pivots from the logical row format to the logical column format, and is stored in the second level storage structure;

encoding, the first set of one or more data records according to a first dictionary; and

encoding the second set of one or more data records according to a second dictionary, the encoding by the second dictionary being non-overlapping with the encoding by the first dictionary;

receiving a point query, the point query comprising queried data;

searching the second dictionary for the queried data; and

when the queried data is found in the second dictionary;

abstaining from searching the first dictionary, a position of the queried data in the second dictionary being used as an encoding value for the second dictionary as well as the first dictionary; and

executing a parallel scan in the active part and the passive part to find the queried data.

18. The non-transitory computer program product of claim 17, wherein the operations further comprise:

when the queried data is not found in the second dictionary;

searching the first dictionary subsequent to the searching of the second dictionary.

19. The non-transitory computer program product of claim 17, wherein the operations further comprise:

receiving a range query, the range query specifying a range of values;

splitting the range into a first range associated with the first dictionary and a second range associated with the second dictionary;

searching the first dictionary for the first range; and

searching the second dictionary for the second range.

20. The non-transitory computer program product of claim 17, wherein the operations further comprise:

assigning a first numerical value for a cardinality of the second dictionary; and

starting the first dictionary with a dictionary position value of a second numerical value that is more than the first numerical value.