MAIN MEMORY DATABASE MANAGEMENT USING PAGE INDEX VECTORS

• US 20160012089A1
• Filed: 07/10/2014
• Published: 01/14/2016
• Est. Priority Date: 07/10/2014
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: Anil Kumar Goel, Guenter Radestock, Ivan Schreter, Mihnea Andrei, Reza Sherkat
• Inventors: SHERKAT, Reza, FLORENDO, Colin, ANDREI, Mihnea, GOEL, Anil Kumar, RADESTOCK, Guenter, SCHRETER, Ivan
• Granted Patent: US 10,089,342 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices

Abstract

A compression manager may store, within an index vector, a plurality of value identifiers (IDs), each value ID representing a value within a database. A page generator may designate a number of the value IDs as defining a page within the index vector, so that the index vector includes a plurality of pages, each page including the number of value IDs. The page generator may store the index vector in a secondary memory of a main memory database. An iterator may access a requested value ID, and a page loader may load a corresponding page of the index vector that contains the requested value ID into the main memory database.

Claims

1. A system including instructions recorded on a computer-readable medium, and executable by at least one processor, the system comprising:

a compression manager configured to cause the at least one processor to store, within an index vector, a plurality of value identifiers (IDs), each value ID representing a value within a database;

a page generator configured to cause the at least one processor to designate a number of the value IDs as defining a page within the index vector, so that the index vector includes a plurality of pages, each page including the number of value IDs, the page generator being further configured to cause the at least on processor to store the index vector in a secondary memory of a main memory database;

an iterator configured to cause the at least one processor to access a requested value ID; and

a page loader configured to cause the at least one processor to load a corresponding page of the index vector that contains the requested value ID into the main memory database.

2. The system of claim 1, wherein the compression manager is further configured to cause the at least one processor to implement a dictionary compression scheme in which the value is stored in a dictionary in the database.

3. The system of claim 1, wherein the compression manager is further configured to cause the at least one processor to calculate a number of bits required per value ID in order to store all the value IDs within the index vector, as part of an n-bit compression scheme.

4. The system of claim 1, wherein the values include column values of at least one columnar database.

5. The system of claim 4, further comprising a request handler configured to cause the at least one processor to receive a requested row position corresponding to a row of the columnar database.

6. The system of claim 5, further comprising an iterator configured to cause the at least one processor to locate the corresponding page, based on a size of each value ID in bits, and a size of each page in bytes.

7. The system of claim 5, further comprising an iterator configured to cause the at least one processor to locate the corresponding page, including performing division in modulo to find an end position of a preceding page immediately prior to the corresponding page.

8. The system of claim 5, wherein the request handler is configured to cause the at least one processor to receive a range of row positions, and wherein the system comprises an iterator configured to cause the at least one processor to identify and retrieve a range of value identifiers corresponding to the range of row positions.

9. The system of claim 1, wherein the number of value IDs per page is independent of a number of bits per value ID.

10. The system of claim 1, wherein each page includes only entire value IDs.

11. A computer-implemented method for executing instructions stored on a computer readable storage medium, the method comprising:

storing, within an index vector, a plurality of value IDs, each value ID representing a value within a database;

designating a number of the value IDs as defining a page within the index vector, so that the index vector includes a plurality of pages, each page including the number of value IDs;

storing the index vector in a secondary memory of a main memory database; and

accessing a requested value ID, including loading a corresponding page of the index vector that contains the requested value ID into the main memory database.

12. The method of claim 11, wherein the values include column values of at least one columnar database, the method further comprising receiving a requested row position corresponding to a row of the columnar database.

13. The method of claim 11, further comprising locating the corresponding page, based on a size of each value ID in bits, and a size of each page in bytes.

14. The method of claim 11, further comprising locating the corresponding page, including performing division in modulo to find an end position of a preceding page immediately prior to the corresponding page.

15. The method of claim 11, wherein each page includes only entire value IDs.

16. A computer program product, the computer program product being tangibly embodied on a non-transitory computer-readable storage medium and comprising instructions that, when executed by at least one computing device, are configured to cause the at least one computing device to:

store, within an index vector, a plurality of value IDs, each value ID representing a value within a database;

designate a number of the value IDs as defining a page within the index vector, so that the index vector includes a plurality of pages, each page including the number of value IDs;

store the index vector in a secondary memory of a main memory database; and

access a requested value ID, including loading a corresponding page of the index vector that contains the requested value ID into the main memory database.

17. The computer program product of claim 16, wherein the values include column values of at least one columnar database, and wherein the instructions, when executed, are configured to receive a requested row position corresponding to a row of the columnar database.

18. The computer program product of claim 16, wherein the instructions, when executed, are configured to locate the corresponding page, based on a size of each value ID in bits, and a size of each page in bytes.

19. The computer program product of claim 16, wherein the instructions, when executed, are configured to locate the corresponding page, including performing division in modulo to find an end position of a preceding page immediately prior to the corresponding page.

20. The computer program product of claim 16, wherein each page includes only entire value IDs.