Main memory database management using page index vectors
First Claim
Patent Images
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 includinga 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 Assignments
0 Petitions
Accused Products
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.
11 Citations
12 Claims
-
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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
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. - View Dependent Claims (8, 9)
-
-
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. - View Dependent Claims (11, 12)
-
Specification