Paged inverted index

Patent metadata

Field	Value
Publication number	US-10140326-B2
Application number	US-201514954736-A
Country	US
Kind code	B2
Filing date	Nov 30, 2015
Priority date	Nov 30, 2015
Publication date	Nov 27, 2018
Grant date	Nov 27, 2018

Abstract

Disclosed herein are system and method embodiments for generating a paged inverted index. An embodiment is generated by storing a first data structure and the second data structure in a plurality of pages, where the plurality of pages are stored in the one or more memories. The first data structure is stored in the plurality of pages and includes a plurality of value identifiers, where a value identifier corresponds to an offset. The second data structure stored in the plurality of pages includes a plurality of row positions, wherein a row position is at a location that corresponds to the offset in the first data structure and identifies a position of row in a table that stores data associated with the value ID.

First claim

What is claimed is:

1. A system, comprising:
one or more memories;
an in-memory database management system coupled to the one or more memories and configured to:
store a paged inverted index as a plurality of pages comprising:
a first data structure,
wherein the first data structure stores a plurality of value identifiers and a plurality of offsets, and
wherein a value identifier of the plurality of value identifiers corresponds to an offset in the plurality of offsets, and

a second data structure,
wherein the second data structure stores a plurality of row positions,
wherein a row position in the plurality of row positions is at a location in the second data structure that corresponds to the offset stored in the first data structure, and
wherein the row position identifies a row position in a database table that stores data associated with the value identifier; and

an execution engine configured to:
execute on a processor coupled to the one or more memories;
access the paged inverted index; and
determine the row position in the database table that stores the data associated with the value identifier.

2. The system of claim 1 , wherein the paged inverted index further comprises:
a first block included in a first page in the plurality pages, wherein the first block stores the first data structure;
a second block included in a second page in the plurality of pages, wherein the second block stores the second data structure; and
a third block and a fourth block included in a third page in the plurality of pages, wherein the third block stores the first data structure and the fourth block stores the second data structure.

3. The system of claim 2 , wherein the paged inverted index further comprises:
a block header configured to store information associated with the first data structure stored in the first block, wherein the block header facilitates access to the plurality of value identifiers stored in first data structure.

4. The system of claim 2 , wherein the paged inverted index further comprises:
a block header associated with the first block, and configured to store a number of values in a portion of the first data structure stored in the first block.

5. The system of claim 1 , wherein data in the first data structure is compressed using binary compression that corresponds to a number of bits that encode a value of the largest offset.

6. The system of claim 1 , wherein data in the second data structure is compressed using binary compression that corresponds to a largest value in the second data structure.

7. The system of claim 1 , wherein the paged inverted index further comprises:
metadata configured to store a first logical page associated with the first data structure, wherein the first logical page corresponds to a block in the one or more blocks that stores a first page of the first data structure.

8. The system of claim 1 , wherein the one or more memories that store the plurality of pages include a memory of an in-memory database and a memory outside of the in-memory database, and wherein the execution engine is further configured to load a page in the plurality of pages that stores the offset of the first data structure or the row position in the second data structure into the memory of the in-memory database prior to accessing the page.

9. A method, comprising:
allocating memory space in one or more memories for a plurality of pages;
storing, by an in-memory database system coupled to the one or more memories, a paged inverted index in the plurality of pages, wherein the paged inverted index comprises:
a first data structure,
wherein the first data structure comprises a plurality of value identifiers and a plurality of offsets, and
wherein a value identifier of the plurality of value identifiers corresponds to an offset of the plurality of offsets; and

a second data structure,
wherein the second data structure stores a plurality of row positions,
wherein a row position in the plurality of row positions is at a location in the second data structure that corresponds to the offset stored in the first data structure and
wherein the row position identifies a row position in a database table stores data associated with the value identifier, and

wherein an execution engine accesses the paged inverted index and determines the row position in the database table that stores the data associated with the value identifier.

10. The method of claim 9 , further comprising:
storing a first block in a first page in the plurality of pages, wherein the first block stores the first data structure;
storing a second block in a second page in the plurality of pages, wherein the second block stores the second data structure; and
storing a third block and a fourth block in a third page in the plurality of pages, wherein the third block stores the first data structure and the fourth block stores the second data structure.

11. The method of claim 10 , further comprising:
storing a block header associated with the first block that stores the first data structure, wherein the block header facilitates access to the plurality of value identifiers stored in first data structure.

12. The method of claim 10 , further comprising:
storing in a block header associated with the first block, a number of values in a portion of the first data structure stored in the first block.

13. The method of claim 9 , further comprising:
compressing data in the first data structure using binary compression, wherein the binary compression corresponds to a number of bits that encode a value of the largest offset.

14. The method of claim 9 , further comprising:
compressing data in the second data structure using binary compression, wherein the binary compression corresponds to a largest value in the second data structure.

15. The method of claim 9 , further comprising:
storing in metadata associated with the paged inverted index, a first logical page associated with a first data structure, wherein the first logical page corresponds to a block in the one or more blocks that stores a first page of the first data structure.

16. The method of claim 9 , further comprising:
storing in metadata associated with the paged inverted index, a number of bits used to compress data in the first data structure.

17. A system, comprising:
an in-memory database management system coupled to one or more memories;
a paged inverted index stored in the one or more memories comprising a plurality of pages configured to store a first data structure and a second data structure,
wherein the first data structure stores a plurality of offsets and a plurality of value identifiers,
wherein a value identifier in the plurality of value identifiers corresponds to an offset in the plurality of offsets,
wherein the second data structure stores a plurality of row positions,
wherein a row position in the plurality of row positions is at a location in the second data structure that corresponds to the offset stored in the first data structure, and

a processor comprising operations configured to:
receive a query request for data stored in a database table;
determine, using the first data structure in the paged inverted index, a first offset and a second offset from the plurality of offsets;
determine a row position in the second data structure using the first offset and the second offset, wherein the row position identifies a row position in the database table that stores the data; and
access the data in the database table at the row position.

18. The

Assignees

• Sap Se

Inventors

• Sherkat Reza
• Schreter Ivan
• Schulze Robert
• Andrei Mihnea
• Florendo Colin
• Lemke Christian
• Seifert Sebastian

Classifications

• G06F17/30339 Primary

  Physics · mapped topic

• H03M7/60

  General implementation details not specific to a particular type of compression · CPC title

• G06F17/30336

  Physics · mapped topic

• G06F17/30622

  Physics · mapped topic

• G06F17/30424

  Physics · mapped topic