Paged column dictionary

Patent metadata

Field	Value
Publication number	US-9977801-B2
Application number	US-201414333224-A
Country	US
Kind code	B2
Filing date	Jul 16, 2014
Priority date	Nov 21, 2013
Publication date	May 22, 2018
Grant date	May 22, 2018

Abstract

A request for an entry of a dictionary having multiple dictionary blocks may be received, where the dictionary stores string values associated with corresponding value identifiers (IDs) for dictionary compression. One of the dictionary blocks may be selectively loaded into memory, and the dictionary block that has been loaded into memory may be searched. A value ID directory may be constructed in memory, where the value ID directory includes last value IDs for the dictionary blocks, and each of the last value IDs is mapped to an index of one of the dictionary blocks that includes a string value for that last value ID. A separator directory may also be constructed in memory, where the separator directory includes separators for the dictionary blocks, and each of the separators is mapped to an index of one of the dictionary blocks that includes a string value for that separator.

First claim

We claim:

1. A method comprising:
constructing a value identifier (ID) directory in memory for a dictionary having multiple dictionary blocks, each dictionary block comprising a plurality of value blocks, each value block comprising a value ID and comprising a plurality of string values, wherein the value ID directory includes last value IDs for the multiple dictionary blocks, and wherein each of the last value IDs is mapped to an index of one of the multiple dictionary blocks that includes a string value for that last value ID;
receiving a request for an entry of the dictionary having multiple dictionary blocks, wherein the dictionary stores string values associated with corresponding value IDs for dictionary compression;
using the value ID directory and a value ID or string value associated with the request, selecting a dictionary block of the multiple dictionary blocks as responsive to the request;
selectively loading the selected dictionary block into memory;
constructing a large string map associated with the dictionary block that has been loaded into memory, wherein the large string map stores one or more pairs of values, each of the one or more pairs of values including (a) an index and (b) a large string value or pointer to the large string value, wherein the constructing the large string map includes, for one of the one or more pairs of values in the large string map, materializing the large string value, including:
loading part of the large string value from a value block of the dictionary block that has been loaded into memory; and
loading part of the large string value from one or more large string dictionary blocks, each of the one or more large string dictionary blocks comprising:
a header; and
one or more parts of large string values; and
searching the selected dictionary block that has been loaded into memory.

2. The method of claim 1 , further comprising:
constructing a separator directory in memory, wherein the separator directory includes separators for the multiple dictionary blocks, and wherein each of the separators is mapped to an index of one of the multiple dictionary blocks that includes a string value for that separator.

3. The method of claim 2 , wherein the value ID directory is constructed using one or more directory blocks that contain the last values IDs for the multiple dictionary blocks, and 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.

4. The method of claim 2 , wherein the request includes a value ID, and wherein the method further includes:
searching the value ID directory using the value ID of the request to determine an index of the one of the multiple dictionary blocks that is to be loaded into memory.

5. The method of claim 2 , wherein the request includes a string value, and wherein the method further includes:
searching the separator directory using the string value of the request to determine the index of the one of the multiple dictionary blocks that is to be loaded into memory.

6. The method of claim 1 , further comprising:
receiving a second request for an entry of the dictionary having multiple dictionary blocks;
determining that one of the multiple dictionary blocks that includes the entry for the second request has already been loaded into memory; and
searching the dictionary block that has been loaded into memory.

7. The method of claim 1 , wherein each value block comprises a fixed number of string values.

8. The method of claim 1 , wherein a string value in a given value block of the plurality of value blocks is represented using segments that comprise:
when the string value does not start the given value block, a first segment specifying a prefix length of a string;
a second segment specifying a remainder length of the string; and
a third segment comprising a remainder string of the string.

9. The method of claim 1 , wherein a string value in a given value block of the plurality of value blocks is represented using segments that comprise:
when the string value does not start the given value block, a first segment specifying a prefix length of a string;
a second segment specifying a length of the segments of the given value block;
a third segment comprising a portion of the string;
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 string.

10. The method of claim 1 , wherein each of the multiple dictionary blocks further comprises:
a variable dictionary block header comprising information that indicates a number of value blocks in the dictionary block; and
offset values for accessing the plurality value blocks in the dictionary block, each of the offset values specifying how many bytes from a beginning of the dictionary block a corresponding one of the one or more value blocks begins.

11. The method of claim 1 , further comprising:
constructing a value block vector associated with the dictionary block that has been loaded into memory, wherein the value block vector stores logical pointers, each of the logical pointers referencing a start of a value block of the dictionary block, and wherein the searching the dictionary block uses the value block vector.

12. One or more computer-readable storage media storing:
structured data usable by one or more processors to load dictionary blocks for a dictionary into memory, the structured data stored on the computer-readable storage medium comprising:
multiple dictionary blocks for a dictionary comprising string values associated with corresponding value identifiers (IDs) for dictionary compression, each of the multiple dictionary blocks storing at least some of the string values;
one or more directory value ID blocks for a value ID directory comprising last value IDs for the multiple dictionary blocks, each of the one or more directory value ID blocks storing at least some of the last value IDs; and
one or more directory separator blocks for a separator directory comprising separators for the multiple dictionary blocks, each of the one or more directory separator blocks storing at least some of the separators; and
computer executable instructions for performing operations comprising:
receiving a request for an entry of the dictionary;
using a value ID or string value associated with the request, selecting a dictionary block of the multiple dictionary blocks as responsive to the request;
selectively loading the selected dictionary block into memory and
searching the selected dictionary block that has been loaded into memory.

13. The one or more computer-readable storage media of claim 12 , wherein the structured data stored on the computer-readable storage media 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.

14. The one or more computer-readable storage media of claim 12 , wherein the structured data stored on the one or more computer-readable storage media further comprises:
one or more large string blocks for a large string map.

15. A database system comprising:
one or more processors; and
memory storing:
an attribute engine providing access to a string dictionary;
a unified table component comprising:
a dictionary storage component that loads one or more of multiple dictionary bl

Assignees

• Florendo Colin
• Thiel Carsten
• Schreter Ivan
• Andrei Mihnea
• Goel Anil Kumar
• Sap Se

Inventors

• Florendo Colin
• Thiel Carsten
• Schreter Ivan
• Andrei Mihnea
• Goel Anil Kumar

Classifications

• G06F16/22 Primary

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F17/30312 Primary

  Physics · mapped topic