Main memory database management using page index vectors

Patent metadata

Field	Value
Publication number	US-10089342-B2
Application number	US-201414328511-A
Country	US
Kind code	B2
Filing date	Jul 10, 2014
Priority date	Jul 10, 2014
Publication date	Oct 2, 2018
Grant date	Oct 2, 2018

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.

First claim

What is claimed is:

1. A system comprising:
at least one processor; and
a non-transitory computer-readable storage medium configured to store instructions executable by the at least one processor;
a main memory of a main memory database; and
a secondary memory of a main memory database, the system further including
a compression engine configured to cause the at least one processor to store, within an index vector and within the secondary memory, a plurality of value identifiers (IDs), each value ID representing a value within a database, wherein the compression engine 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, and an n-bit compression scheme in which a number of bits required per value ID in order to store all the value IDs within the index vector is calculated;
a page generation engine configured to cause the at least one processor to designate a number of the value IDs stored within the secondary memory 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, wherein the number of the value IDs corresponds to including only entire value IDs within the page;
an iteration engine configured to cause the at least one processor to access a requested value ID from within the secondary memory, including identifying the page from among the plurality of pages, based on the number of bits required per value ID according to the n-bit compression scheme, as well as a size of each page; and
a page loader configured to cause the at least one processor to load the page of the index vector that contains the requested value ID from the secondary memory into the main memory of the main memory database.

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

3. The system of claim 2 , 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 from a user of the main memory database by way of a user interface thereof.

4. The system of claim 3 , wherein the iteration engine is configured to cause the at least one processor to locate the page, including performing division in modulo to find an end position of a preceding page immediately prior to the page.

5. The system of claim 3 , wherein the request handler is configured to cause the at least one processor to receive a range of row positions, and wherein the iteration engine is further configured to cause the at least one processor to identify and retrieve a range of value identifiers corresponding to the range of row positions.

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

7. 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, including implementing a dictionary compression scheme in which the value is stored in a dictionary, and implementing an n-bit compression scheme in which a number of bits required per value ID in order to store all the value IDs within the index vector is calculated;
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, wherein the number of the value IDs corresponds to including only entire value IDs within each page;
storing the index vector in a secondary memory of a main memory database;
accessing a requested value ID, including identifying a corresponding page from among the plurality of pages, based on the number of bits required per value ID according to the n-bit compression scheme, as well as a size of each page; and
loading the corresponding page of the index vector that contains the requested value ID into the main memory database.

8. The method of claim 7 , 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.

9. The method of claim 7 , 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.

10. 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;
implement a dictionary compression scheme in which the value is stored in a dictionary, and an n-bit compression scheme in which a number of bits required per value ID in order to store all the value IDs within the index vector is calculated;
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, wherein the number of the value IDs corresponds to including only entire value IDs within each page;
store the index vector in a secondary memory of a main memory database;
access a requested value ID, including identifying a corresponding page from among the plurality of pages, based on the number of bits required per value ID according to the n-bit compression scheme, as well as a size of each page; and
the corresponding page of the index vector that contains the requested value ID into the main memory database.

11. The computer program product of claim 10 , 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.

12. The computer program product of claim 10 , 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.

Assignees

• Sherkat Reza
• Radestock Guenter
• Schreter Ivan
• Florendo Colin
• Andrei Mihnea
• Goel Anil Kumar
• Sap Se

Inventors

• Sherkat Reza
• Radestock Guenter
• Schreter Ivan
• Florendo Colin
• Andrei Mihnea
• Goel Anil Kumar

Classifications

• G06F16/2237 Primary

  Vectors, bitmaps or matrices · CPC title

• G06F16/221

  Column-oriented storage; Management thereof · CPC title

• G06F16/1744

  using compression, e.g. sparse files · CPC title

• G06F17/30153

  Physics · mapped topic

• G06F17/30315

  Physics · mapped topic