LARGE STRING ACCESS AND STORAGE

• US 20150142819A1
• Filed: 10/27/2014
• Published: 05/21/2015
• Est. Priority Date: 11/21/2013
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: Colin Florendo
• Inventors: Florendo, Colin, Schreter, Ivan, Andrei, Mihnea
• Granted Patent: US 9,977,802 B2
• Time in Patent Office: Days
• US Class Current: 707/741
• 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 comprising:

loading a value block of a dictionary into memory, the dictionary storing string values for dictionary compression, the value block comprising 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;

materializing the large string value into a contiguous memory location; and

creating a pointer to the materialized large string value.

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 materialized 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 is constructed using 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:

receiving a request for the large string value;

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. A computer-readable storage medium storing structured data usable by one or more processors to support handling of large string values for a dictionary in memory, the structured data stored on the computer-readable storage medium comprising:

multiple dictionary blocks for a dictionary adapted to store one or more large string values for dictionary compression, at least one of the multiple dictionary blocks storing at least part of one of the one or more large string values;

one or more directory separator blocks for a separator directory adapted to include separators for the multiple dictionary blocks, each of the one or more directory separator blocks storing at least some of the separators; and

one or more large string blocks for the one or more large string values.

11. The computer-readable storage medium of claim 10, wherein the structured data further comprises:

one or more separator logical pointer (LP) blocks for the separator directory, each of the one or more separator LP blocks storing LPs to at least some of the separators.

12. The computer-readable storage medium of claim 10, wherein a 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 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

memory storing;

an attribute engine adapted to provide access to a string dictionary;

a unified table component comprising;

a dictionary storage component adapted to load one or more of multiple dictionary blocks of the string dictionary using on-demand paging, each of the multiple dictionary blocks comprising one or more value blocks; and

a large string handler adapted to provide access to large string values; and

a basis adapted to store value block vectors, each of the value block vectors storing pointers to the one or more value blocks for one of the multiple dictionary blocks.

15. The database system of claim 14, wherein the unified table component further comprises:

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, wherein the dictionary storage component is further adapted to, when a string value is provided in a request:

search 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 load 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, wherein the basis further comprises:

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, wherein the dictionary storage component is further adapted to load 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 materialized from the large string dictionary blocks.

20. The database system of claim 19, wherein after the large string values are materialized, the large string dictionary blocks are unpinned.