Rollover strategies in a N-bit dictionary compressed column store

• US 9,489,409 B2
• Filed: 10/17/2013
• Issued: 11/08/2016
• Est. Priority Date: 10/17/2013
• Status: Active Grant

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Andrei, Minhnea, Sharique, Muhammed, Goel, Anil Kumar
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Le, Jessica N
• Application Number:
  US14/056,454
• Publication Number:
  US 20150113026A1
• Time in Patent Office: 1,118 Days
• Field of Search: 707/812
• US Class Current: 1/1
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof

Abstract

Disclosed herein are system, method, and computer program product embodiments for rollover strategies in an n-bit dictionary compressed column store. An embodiment operates by receiving a new value for addition to a compressed column store, determining that a current memory block of a most recently added token to the compressed column store is the insertion block. It is determined that the maximum token value has been reached for the current memory block. A new virtual memory block is created using the current insertion block, and a token corresponding to the new value is stored in the new virtual memory block. In another embodiment, when it is determined a maximum number of token values that may be stored in a compressed column store has been reached for a data dictionary, the compressed column store is converted into a composite store include a flat store where the new value is stored.

Claims

1. A method, comprising:

receiving a new value for addition to a compressed column store, the compressed column store including a plurality of tokens, each token corresponding to a value in a data dictionary, and being associated with a row identifier (RID) in the compressed column store;

determining an insertion block of the compressed column store, the insertion block being a physical or virtual memory block where new tokens are inserted;

determining that a current memory block of a most recently added token to the compressed column store is the insertion block, the compressed column store including one or more memory blocks each with a maximum token value that indicates a storage capacity for tokens within a respective memory block based on an encoding of the respective memory block;

determining that the maximum token value has been reached for the current memory block based on type of encoding of the current memory block;

creating a new virtual memory block using the current memory block, wherein the new virtual memory block has an encoding greater than the encoding of the current memory block, wherein the new virtual memory is designated as the insertion block, and wherein the tokens of the current memory block remain in the current memory block while new tokens are stored in the virtual memory block; and

storing a token corresponding to the new value in the new virtual memory block, wherein the token corresponding to the new value in the new virtual memory block is accessed in a same manner as existing tokens in the current memory block.

2. The method of claim 1, wherein the current memory block is a first virtual memory block.

3. The method of claim 1, wherein the creating comprises:

determining that the current memory block is at full capacity;

creating a new physical memory block; and

storing the token corresponding to the new value in the new physical memory block, wherein the new physical memory block is assigned an encoding based on the token corresponding to the new value.

4. The method of claim 1, wherein each physical and virtual memory block includes a header comprising a start Rip, an end RID, and an encoding value corresponding to encoding of a respective memory block.

5. The method of claim 4, wherein each of two or more virtual or physical memory blocks of the compressed column store have different encoding values.

6. The method of claim 1, wherein the new value is stored in the data dictionary, and wherein the token corresponding to the new value is used to access a data value corresponding to the new value from the data dictionary.

7. The method of claim 1, wherein a write operation for writing the token into the new virtual memory block is identical to a write operation for writing the token into the physical memory block.

8. The method of claim 1, wherein a read operation for reading the token from the new virtual memory block is identical to a read operation for reading the token from the physical memory block.

9. The method of claim 1, wherein the creating comprises:

creating a new virtual memory block using the current memory block based on the determination that the maximum token value has been reached for the type of encoding of the current memory block.

10. The method of claim 1, further comprising:

receiving, subsequent to the creating, a second new value, wherein the second new value is stored in the virtual memory block.

11. A system comprising:

a processor; and

a tangible memory communicatively coupled to the processor including instructions thereon that when executed by the processor cause the processor to;

receive a new value for addition to a compressed column store, the compressed column store including a plurality of tokens, each token corresponding to a value in a data dictionary, and being associated with a row identifier (RID) in the compressed column store,

determine an insertion block of the compressed column store, the insertion block being a physical or virtual memory block where new tokens are inserted,

determine that a current memory block of a most recently added token to the compressed column store is the insertion block, the compressed column store including one or more memory blocks each with a maximum token value that indicates a storage capacity for tokens within a respective memory block based on an encoding of the respective memory block,

determine that the maximum token value has been reached for the current memory block based on type of encoding of the current memory block

create a new virtual memory block using the current memory block, wherein the new virtual memory block has an encoding greater than the encoding of the current memory block, wherein the new virtual memory is designated as the insertion block, and wherein the tokens of the current memory block remain in the current memory block while new tokens are stored in the virtual memory block, and

store a token corresponding to the new value in the new virtual memory block, wherein the token corresponding to the new value in the new virtual memory block is accessed in a same manner as existing tokens in the current memory block.

12. The system of claim 11, wherein the current memory block is a first virtual memory block.

13. The system of claim 11, wherein the instructions that cause the processor to create comprise instructions that cause the processor to:

determining that the current memory block is at full capacity;

create a new physical memory block; and

storing the token corresponding to the new value in the new physical memory block, wherein the new physical memory block is assigned an encoding based on the token corresponding to the new value.

14. The system of claim 11, wherein each of two or more virtual or physical memo˜

7 blocks of the compressed column store have different encoding values.

15. The system of claim 11, wherein the new value is stored in the data dictionary, and wherein the token corresponding to the new value is used to access a data value corresponding to the new value from the data dictionary.

16. The system of claim 11, wherein a write operation for writing the token into the new virtual memory block is identical to a write operation for writing the token into the physical memory block.

17. The system of claim 11, wherein a read operation for reading the token from the new virtual memory block is identical to a read operation for reading the token from the physical memory block.