Forced ordering of a dictionary storing row identifier values

• US 10,725,987 B2
• Filed: 11/25/2014
• Issued: 07/28/2020
• Est. Priority Date: 11/25/2014
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Wein, David, Schreter, Ivan, Andrei, Mihnea, Heidel, Martin, Benkstein, Frank
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Mueller, Kurt A
• Application Number:
  US14/553,892
• Publication Number:
  US 20160147804A1
• Time in Patent Office: 2,072 Days
• Field of Search: None
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

The subject matter disclosed herein provides methods for the forced ordering of a dictionary based on row identifier values. A plurality of concurrent transactions can be handled in an in-memory database. At least one of the transactions can include at least one write operation to a dictionary. Each write operation can be assigned a row identifier (ID). At least one of the write operations can be written to the dictionary out of sequence. The sequence can be based on the row ID. Each row ID in the dictionary can be mapped to a corresponding value identifier in the dictionary. The dictionary can position the value identifiers so that the corresponding row IDs are in a sorted sequential order based on the row ID. Related apparatus, systems, techniques, and articles are also described.

Claims

1. A method for implementation by one or more data processors forming part of at least one computing system, the method comprising:

in response to an initiation of a first write operation to an in-memory database, writing, to a dictionary, the first write operation, the dictionary tracking transactions operating on the in-memory database by at least providing mappings between at least one row identifier (ID) and a corresponding value identifier (ID), the writing of the first write operation comprising;

assigning, to the first write operation, a first row identifier (ID);

determining that the first row ID is out of sequence relative to a second row ID in the dictionary, the second row ID being associated with a second write operation to the in-memory database; and

in response to the first row ID being determined to be out of sequence relative to the second row ID, mapping, based at least on a base row ID and a base value ID, the first row ID to a first value ID in the dictionary and the second row ID to a second value ID in the dictionary such that the first row ID and the second row ID are in a sorted sequential order in the dictionary, the base row ID and the base value ID corresponding to a row ID and value ID at a starting point of a sequence of consecutive row IDs following a committed write operation, the first value ID corresponding to a first sum of the base value ID and a first offset between the first row ID and the base row ID, and the second value ID corresponding to a second sum of the base value ID and a second offset between the second row ID and the base row ID; and

completing, based at least on the dictionary, one or more concurrent transactions operating on the in-memory database.

2. The method of claim 1, wherein the the sequence of consecutive row IDs comprises a transient portion of the dictionary, and wherein the base row ID and the base value ID are further representative of a starting point of the transient portion of the dictionary.

3. The method of claim 2, wherein the base row ID and the base value ID are persisted to the in-memory database, and wherein the remaining plurality of consecutive row IDs are not persisted to the in-memory database.

4. The method of claim 3, further comprising:

persisting a number of values in the transient portion to the in-memory database.

5. The method of claim 2, wherein the dictionary further comprises a persisted portion having a plurality of persisted row IDs.

6. The method of claim 5 further comprising searching the persisted portion for an incoming row ID using a search mechanism.

7. The method of claim 6, wherein the search mechanism is a binary search when the plurality of persisted row IDs are ordered, and wherein the search mechanism is a hash table search when the plurality of persisted row IDs are not ordered.

8. The method of claim 1, further comprising:

determining the first value ID by at least determining the first offset between the first row ID and the base row ID before adding the first offset to the base value ID; and

determining the second value ID by at least determining the second offset between the second row ID and the base row ID before adding the second offset to the base value ID.

9. The method of claim 1, further comprising:

inserting, into the dictionary, the first row ID and the first value ID based at least on the mapping.

10. The method of claim 1, further comprising:

obtaining a row position value for the first row ID by at least searching an index dictionary based on the first value ID, the index dictionary providing mappings between at least one value ID associated with a row ID and a corresponding row position value.

11. The method of claim 1 wherein the first write operation and/or the second write operation are associated with an insertion of data but not a deletion of data.

12. A non-transitory computer-readable medium containing instructions to configure a processor to perform operations comprising:

in response to an initiation of a first write operation to an in-memory database, writing, to a dictionary, the first write operation, the dictionary tracking transactions operating on the in-memory database by at least providing mappings between at least one row identifier (ID) and a corresponding value identifier (ID), the writing of the first write operation comprising;

assigning, to the first write operation, a first row identifier (ID);

determining that the first row ID is out of sequence relative to a second row ID in the dictionary, the second row ID being associated with a second write operation to the in-memory database; and

in response to the first row ID being determined to be out of sequence relative to the second row ID, mapping, based at least on a base row ID and a base value ID, the first row ID to a first value ID in the dictionary and the second row ID to a second value ID in the dictionary such that the first row ID and the second row ID are in a sorted sequential order in the dictionary, the base row ID and the base value ID corresponding to a row ID and value ID at a starting point of a sequence of consecutive row IDs following a committed write operation, the first value ID corresponding to a first sum of the base value ID and a first offset between the first row ID and the base row ID, and the second value ID corresponding to a second sum of the base value ID and a second offset between the second row ID and the base row ID; and

completing, based at least on the dictionary, one or more concurrent transactions operating on the in-memory database.

13. The non-transitory computer-readable medium of claim 12, wherein the the sequence of consecutive row IDs comprises a transient portion of the dictionary, and wherein the base row ID and the base value ID are further representative of a starting point of the transient portion of the dictionary.

14. The non-transitory computer-readable medium of claim 13, wherein the base row ID and the base value ID are persisted to the in-memory database, wherein the remaining plurality of consecutive row IDs are not persisted to the in-memory database, and wherein the dictionary further comprises a persisted portion having a plurality of persisted row IDs.

15. The non-transitory computer-readable medium of claim 12, further comprising:

determining the first value ID by at least determining the first offset between the first row ID and the base row ID before adding the first offset to the base value ID; and

determining the second value ID by at least determining the second offset between the second row ID and the base row ID before adding the second offset to the base value ID.

16. A system comprising:

at least one processor; and

at least one memory, wherein the at least one processor and the at least one memory are configured to perform operations comprising;

in response to an initiation of a first write operation to an in-memory database, writing, to a dictionary, the first write operation, the dictionary tracking transactions operating on the in-memory database by at least providing mappings between at least one row identifier (ID) and a corresponding value identifier (ID), the writing of the first write operation comprising;

assigning, to the first write operation, a first row identifier (ID);

determining that the first row ID is out of sequence relative to a second row ID in the dictionary, the second row ID being associated with a second write operation to the in-memory database; and

in response to the first row ID being determined to be out of sequence relative to the second row ID, mapping, based at least on a base row ID and a base value ID, the first row ID to a first value ID in the dictionary and the second row ID to a second value ID in the dictionary such that the first row ID and the second row ID are in a sorted sequential order in the dictionary, the base row ID and the base value ID corresponding to a row ID and value ID at a starting point of a sequence of consecutive row IDs following a committed write operation, the first value ID corresponding to a first sum of the base value ID and a first offset between the first row ID and the base row ID, and the second value ID corresponding to a second sum of the base value ID and a second offset between the second row ID and the base row ID; and

completing, based at least on the dictionary, one or more concurrent transactions operating on the in-memory database.

17. The system of claim 16, wherein the the sequence of consecutive row IDs comprises a transient portion of the dictionary, and wherein the base row ID and the base value ID are further representative of a starting point of the transient portion of the dictionary.

18. The system of claim 17, wherein the base row ID and the base value ID are persisted to the in-memory database, wherein the remaining plurality of consecutive row IDs are not persisted to the in-memory database, and wherein the dictionary further comprises a persisted portion having a plurality of persisted row IDs.

19. The system of claim 16, further comprising:

determining the first value ID by at least determining the first offset between the first row ID and the base row ID before adding the first offset to the base value ID; and

determining the second value ID by at least determining the second offset between the second row ID and the base row ID before adding the second offset to the base value ID.