Large string access and storage

• US 9,977,802 B2
• Filed: 10/27/2014
• Issued: 05/22/2018
• Est. Priority Date: 11/21/2013
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Florendo, Colin, Schreter, Ivan, Andrei, Mihnea
• Primary Examiner(s): ASPINWALL, EVAN S
• Application Number:
  US14/524,998
• Publication Number:
  US 20150142819A1
• Time in Patent Office: 1,303 Days
• Field of Search: 707741
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures

Abstract

Techniques for handling large string values in a string dictionary within an in-memory database system are presented. The string dictionary can be a paged-column main dictionary. For example, a value block of a dictionary may be loaded into memory, where the dictionary stores values for dictionary compression. The value block may include a first portion of a large string value and one or more logical pointers to one or more large string pages containing a remainder of the large string value. The large string value may be materialized into a contiguous location in memory, and a pointer to the materialized large string value may be created.

Claims

1. A method, implemented by a computing system comprising one or more processors coupled to one or more memories, comprising:

receiving a request to access a large string value, the request comprising a value ID;

with a value ID directory loaded into a memory of the one or more memories, determining a dictionary block ID of a dictionary block associated with the value ID, the dictionary storing string values for dictionary compression;

from a determined dictionary block, loaded into a memory of the one or more memories, having the determined dictionary block ID and comprising one or more value blocks having value block IDs, accessing a value block having a value block ID corresponding to the value ID, the accessed value block comprising a first portion of the requested large string value and one or more logical pointers to one or more large string pages containing a remainder of the large string value;

loading, with a processor of the one or more processors, the first portion of the large string value from the accessed value block, and loading the remainder of the large string value by dereferencing the one or more logical pointers to load from at least corresponding referenced large string pages the remainder of the large string value, providing the large string value;

storing, with a processor of the one or more processors, the loaded large string value into a contiguous memory location of the one or more memories, the contiguous memory location comprising a plurality of sequential, addressable memory locations, the contiguous memory location further comprising an addressable starting memory location having an address;

creating, with a processor of the one or more processors, a pointer to the starting memory address of the stored large string value;

storing, with a processor of the one or more processors, the pointer to the large string value; and

returning a pointer that can be dereferenced to access the stored large string value in response to the request.

2. The method of claim 1, further comprising:

constructing a large string map, wherein the large string map stores one or more pairs of values, one of the one or more pairs of values including (a) an index and (b) the large string value or the pointer to the stored large string value.

3. The method of claim 1, further comprising:

loading the one or more large string pages, each of the one or more large string pages comprising;

a header; and

a portion of the large string value.

4. The method of claim 1, wherein the dictionary is a paged dictionary that has multiple dictionary blocks, and wherein one of the multiple dictionary blocks containing the value block is loaded into memory in response to a request for a string value in the value block.

5. The method of claim 4, further comprising:

constructing a separator directory in memory, wherein the separator directory includes separators for the multiple dictionary blocks, wherein at least one the separators is mapped to an index of the one of the multiple dictionary blocks that includes the first portion of the large string value for that separator.

6. The method of claim 5, wherein the separator directory comprises one or more directory blocks that contain the separators for the multiple dictionary blocks and one or more directory blocks that contain logical pointers to the separators.

7. The method of claim 5, further comprising:

searching the separator directory using the large string value to determine the index of the one of the multiple dictionary blocks including the first portion of the large string value.

8. The method of claim 4, further comprising:

determining that the one of the multiple dictionary blocks that includes the value block has already been loaded into memory; and

searching the loaded dictionary block for the large string value.

9. The method of claim 1, wherein the large string value in the value block is represented using segments that comprise:

a first segment specifying a prefix length of a common prefix between the large string value and its predecessor string value;

a second segment specifying a length of the first portion of the large string value;

a third segment comprising the first portion of the large string value;

a fourth segment specifying zero or more logical pointers to the one or more large string pages containing the remainder of the large string value;

a fifth segment specifying number of the logical pointers in the fourth segment; and

a sixth segment specifying a total length of the large string value.

10. One or more computer-readable storage medium comprising computer-executable instructions usable by one or more processors of a computing system, the one or more processors in communication with the one or more computer-readable storage medium, to perform operations to support handling of large string values for a dictionary in memory, the operations comprising:

receiving a request to access a large string value, the request comprising a string value;

with a separator directory comprising one or more directory separator blocks, at least one of the one or more directory separator blocks comprising separators for multiple dictionary blocks of a dictionary, determining a dictionary block ID associated with the string value, wherein;

the multiple dictionary blocks store string values for dictionary compression;

a determined dictionary block of the multiple dictionary blocks has the determined dictionary block ID;

each of the one or more directory separator blocks stores at least some of the separators;

at least a portion of the multiple dictionary blocks store one or more large string values for dictionary compression;

the determined dictionary block stores part of a large string value corresponding to the string value of the request and one or more logical pointers for one or more large string blocks comprising a remainder of the large string value;

from the determined dictionary block, loaded into memory, accessing a first portion of the requested large string value and one or more logical pointers to at least one of one or more large string blocks containing a remainder of a large string value associated with the string value of the request;

loading the first portion of the large string value from the determined dictionary block, and loading the remainder of the large string value by following the one or more logical pointers to load from at least corresponding referenced large string blocks the remainder of the large string value, providing the large string value;

storing the loaded large string value into a contiguous memory location, the contiguous memory location comprising an addressable starting memory location having an address;

creating a pointer to the starting memory address of the stored large string value;

storing the pointer to the large string value; and

returning a pointer that can be followed to access the stored large string value in response to the request.

11. The computer-readable storage medium of claim 10, the operations further comprising:

accessing at least one of the separators using a separator logical pointer (LP) block for the separator directory, the separator LP block storing LPs to at least some of the separators.

12. The computer-readable storage medium of claim 10, the operations further comprising:

storing the pointer to the loaded large string value in a large string map, the large string map storing one or more pairs of values, one of the one or more pairs of values including (a) an index and (b) a given large string value among the one or more large string values or a pointer to the given large string value.

13. The computer-readable storage medium of claim 10, wherein a given large string value among the one or more string values is represented using segments that comprise:

a first segment specifying a prefix length of a common prefix between the given large string value and its predecessor string value;

a second segment specifying a length of a portion of the given large string value;

a third segment comprising the portion of the given large string value;

a fourth segment specifying zero or more logical pointers to large string pages;

a fifth segment specifying number of the logical pointers in the fourth segment; and

a sixth segment specifying a total length of the given large string value.

14. A database system comprising:

one or more processors; and

one or more memories in communication with the one or more processors, the one or more memories storing computer-executable instructions to perform operations comprising;

receiving a request to access a large string value, the request comprising a value ID or a value string;

searching a value block vector, the value block vector associated with a dictionary page for a dictionary block of a dictionary comprising multiple dictionary blocks, for a value block corresponding to the value ID, or a value ID corresponding to the value string, the value block comprising a first portion of the requested large string value and one or more physical or logical pointers to one or more large string blocks containing a remainder of the large string value;

loading the first portion of the large string value from the value block, and loading the remainder of the large string value by dereferencing the one or more physical or logical pointers to load from at least corresponding referenced large string blocks the remainder of the large string value, providing the large string value;

storing the loaded large string value in memory;

creating a pointer to the stored large string value;

storing the pointer to the large string value; and

returning a pointer that can be dereferenced to access the stored large string value in response to the request.

15. The database system of claim 14, the operations further comprising:

constructing a separator directory adapted to provide access to an entry of the string dictionary, given a string value.

16. The database system of claim 14, the operations further comprising:

receiving a request to access a large string value, the request comprising a string value;

searching a separator directory for a separator of one of the multiple dictionary blocks that contains at least a portion of the string value provided in the request, and

loading the one of the multiple dictionary blocks that contains the at least the portion of the string value provided in the request.

17. The database system of claim 14, the operations further comprising:

constructing a large string map associated with at least one of the multiple dictionary blocks, wherein the large string map stores one or more pairs of values, one of the one or more pairs of values including (a) an index and (b) a given large string value of the large string values or a pointer to the given large string value.

18. The database system of claim 14, the operations further comprising:

loading one or more intermediate dictionary blocks, each of the one or more intermediate dictionary blocks containing one or more logical pointers to one or more value blocks of one or more of the multiple dictionary blocks for normal string values and/or one or more logical pointers to one or more large string dictionary blocks for large string values.

19. The database system of claim 18, wherein the large string values are retrieved from the large string dictionary blocks.

20. The database system of claim 19, wherein after the large string values are retrieved, the large string dictionary blocks are marked as being removable from at least one memory of the one or more memories.