Large string access and storage

Patent metadata

Field	Value
Publication number	US-9977802-B2
Application number	US-201414524998-A
Country	US
Kind code	B2
Filing date	Oct 27, 2014
Priority date	Nov 21, 2013
Publication date	May 22, 2018
Grant date	May 22, 2018

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.

First claim

We claim:

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.

Assignees

• Florendo Colin
• Schreter Ivan
• Andrei Mihnea
• Sap Se

Inventors

• Florendo Colin
• Schreter Ivan
• Andrei Mihnea

Classifications

• G06F16/22 Primary

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F17/30312 Primary

  Physics · mapped topic