Paged column dictionary

• US 9,977,801 B2
• Filed: 07/16/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, Thiel, Carsten, Schreter, Ivan, Andrei, Mihnea, Goel, Anil Kumar
• Primary Examiner(s): Ly, Cheyne D
• Application Number:
  US14/333,224
• Publication Number:
  US 20150142818A1
• Time in Patent Office: 1,406 Days
• Field of Search: 707693
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures

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.

Claims

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 blocks of the string dictionary, each of the multiple dictionary blocks comprising one or more value blocks;

a value ID directory providing access to an entry of the string dictionary given a value ID;

a separator directory providing access to an entry of the string dictionary given a string value; and

a large string handler providing access to large string values; and

a basis storing 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; and

computer executable instructions for, with the dictionary storage component, performing operations comprising;

receiving a request for an entry of the string 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.

16. The database system of claim 15, wherein, when a value ID is provided in the request, as part of the selecting the dictionary block, the dictionary storage component:

searches the value ID directory for a last value ID of one of the multiple dictionary blocks that contains the value ID provided in the request, and

selects the dictionary block that contains the value ID provided in the request.

17. The database system of claim 15, wherein, when a string value is provided in the request, as part of the selecting the dictionary block, the dictionary storage component:

searches the separator directory for a separator of one of the multiple dictionary blocks that contains the string value provided in the request, and

selects the dictionary block that contains the string value provided in the request.

18. One or more non-transitory computer-readable media having stored thereon computer-executable instructions for causing a database system comprising one or more processors and memory, when programmed thereby, to perform operations comprising:

receiving a request for an entry of a dictionary having multiple dictionary blocks, wherein the dictionary stores string values associated with corresponding value identifiers (IDs) for dictionary compression, and wherein each of the multiple dictionary blocks comprises;

a variable dictionary block header comprising information that indicates a number of value blocks in the dictionary block;

one or more value blocks, each value block comprising a value ID and a plurality of string values, wherein a string value in a given value block of the one or more value blocks is represent 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, a length of the segments of the given value block, or a total length of the string; and

a third segment comprising a remainder string of the string; and

offset values for accessing the one or more value blocks in the dictionary block;

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.

19. The one or more computer-readable media of claim 18, wherein each of the one or more value blocks contains a fixed number of string values.

20. The one or more computer-readable media of claim 18, wherein a string value in a given value block of the one or more value blocks is represented using segments that further comprise:

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

21. The one or more computer-readable media of claim 18, wherein each of the offset values specifies how many bytes from a beginning of the dictionary block a corresponding one of the one or more value blocks begins.

22. The one or more computer-readable media of claim 18, wherein the operations further comprise:

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.

29. The one or more non-transitory computer-readable media of claim 18, wherein the second segment specifies a remainder length of the string and the segments further comprise a fourth segment specifying a length of the segments of the given value block.

30. The one or more non-transitory computer-readable media of claim 18, wherein the second segment specifies a total length of the string and the segments further comprise a fourth segment specifying a length of the segments of the given value block.

31. The one or more non-transitory computer-readable media of claim 20, the segments further comprising a fifth segment specifying a number of the logical pointers in the fourth segment.

23. In a database system comprising one or more processors and memory, a method of managing a string dictionary, the method comprising:

constructing in memory a value identifier (ID) directory, a separator directory, and a large string handler, wherein;

the value ID directory provides access to an entry of the dictionary given a value ID;

the separator directory provides access to an entry of the dictionary given a string value; and

the large string handler provides access to large string values; and

with a dictionary storage component;

receiving a request for an entry of the string dictionary;

using a value ID or string value associated with the request, selecting a dictionary block of multiple dictionary blocks as responsive to the request, each of the multiple dictionary blocks comprising one or more value blocks;

selectively loading the selected dictionary block into memory; and

searching the selected dictionary block that has been loaded into memory;

storing value block vectors as part of a basis, each of the value block vectors storing pointers to the one or more value blocks for one of the multiple dictionary blocks; and

with an attribute engine, providing access to the dictionary.

24. The method of claim 23, wherein the selecting the dictionary block with the dictionary storage component comprises, when a value ID is provided in the request:

searching the value ID directory for a last value ID of one of the multiple dictionary blocks that contains the value ID provided in the request, and

selecting the dictionary block that contains the value ID provided in the request.

25. The method of claim 23, wherein the selecting the dictionary block with the dictionary storage component comprises, when a string value is provided in the request:

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

selecting the dictionary block that contains the string value provided in the request.

26. One or more non-transitory computer-readable media having stored thereon computer-executable instructions for causing a database system comprising one or more processors and memory, when programmed thereby, to perform operations to manage a string dictionary, the operations comprising:

constructing in memory a value identifier (ID) directory, a separator directory, and a large string handler, wherein;

the value ID directory provides access to an entry of the dictionary given a value ID;

the separator directory provides access to an entry of the dictionary given a string value; and

the large string handler provides access to large string values; and

with a dictionary storage component;

receiving a request for an entry of the string dictionary;

using a value ID or string value associated with the request, selecting a dictionary block of multiple dictionary blocks as responsive to the request, each of the multiple dictionary blocks comprising one or more value blocks;

selectively loading the selected dictionary block into memory; and

searching the selected dictionary block that has been loaded into memory;

storing value block vectors as part of a basis, each of the value block vectors storing pointers to the one or more value blocks for one of the multiple dictionary blocks; and

with an attribute engine, providing access to the dictionary.

27. The one or more computer-readable media of claim 26, wherein the selecting the dictionary block with the dictionary storage component comprises, when a value ID is provided in the request:

searching the value ID directory for a last value ID of one of the multiple dictionary blocks that contains the value ID provided in the request, and

selecting the dictionary block that contains the value ID provided in the request.

28. The one or more computer-readable media of claim 26, wherein the selecting the dictionary block with the dictionary storage component comprises, when a string value is provided in the request:

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

selecting the dictionary block that contains the string value provided in the request.