Fast row to page lookup of data table using capacity index

Patent metadata

Field	Value
Publication number	US-9898551-B2
Application number	US-201414553878-A
Country	US
Kind code	B2
Filing date	Nov 25, 2014
Priority date	Nov 25, 2014
Publication date	Feb 20, 2018
Grant date	Feb 20, 2018

Abstract

The subject matter disclosed herein provides methods for determining the page on which a desired row position value is located. A table having a plurality of rows can be accessed. The rows can be distributed across one or more pages in an in-memory database. Each row can be associated with a unique row position value. Each page can be associated with a capacity that is representative of an amount of data stored on the page. A capacity index having a plurality of entries can be created to record changes in capacity between pages. Neighboring entries in the capacity index can have a different capacity. Each entry in the capacity index can correspond to a page. A page directory can be created based on the capacity index. The page directory can indicate all possible row position values associated with each page. Related apparatus, systems, techniques, and articles are also described.

First claim

What is claimed is:

1. A method for implementation by one or more data processors forming part of at least one computing system, the method comprising:
accessing a table stored in an in-memory database, the table having a plurality of rows distributed across one or more pages in the in-memory database, each of the plurality of rows associated with a unique row position value, and each of the one or more pages associated with a capacity representative of an amount of data stored on the page;
creating, based at least on capacities of each of the plurality of pages in the in-memory database, a capacity index having a plurality of entries, the creation of the capacity index comprising:
inserting, into the capacity index, an entry corresponding to a first capacity of a first page, in response to the first capacity being different than a second capacity of a second page that precedes the first page;

creating a page directory based on the capacity index, the page directory indicating a plurality of row position values included in each of the one or more pages in the in-memory database; and
executing, based at least on the page directory, a database query on the in-memory database, the execution of the query comprising:
identifying, based at least on the page directory, a page that includes a row having a target row position value; and
loading, from the in-memory database, the page that includes the row having the target row position value.

2. The method of claim 1 , wherein the identifying of the page comprises searching the page directory for the target row position value.

3. The method of claim 2 , wherein the searching is performed by a binary search, a linear search, or a reverse linear search.

4. The method of claim 1 , wherein the creating the capacity index comprises:
comparing a capacity of a first page with a capacity of a second page; and
adding the capacity of the second page to the capacity index if the capacity of the second page is different than the capacity of the first page.

5. The method of claim 1 , wherein the change in capacity is due to one or more of an adjustment in a size of the data stored on the page, an adjustment in a number of rows used on the page, and an adjustment in a number of columns used on the page.

6. The method of claim 1 , wherein the page directory is an array having a plurality of cells, each cell associated with a page in the table.

7. The method of claim 1 further comprising:
persisting the page directory to the in-memory database.

8. A non-transitory computer-readable medium containing instructions to configure a processor to perform operations comprising:
accessing a table stored in an in-memory database, the table having a plurality of rows distributed across one or more pages in the in-memory database, each of the plurality of rows associated with a unique row position value, and each of the one or more pages associated with a capacity representative of an amount of data stored on the page;
creating, based at least on capacity of each of the plurality of pages in the in-memory database, a capacity index having a plurality of entries, the creation of the capacity index comprising:
inserting, into the capacity index, an entry corresponding to a first capacity of a first page, in response to the first capacity being different than a second capacity of a second page that precedes the first page;

creating a page directory based on the capacity index, the page directory indicating a plurality of row position values included in each of the one or more pages in the in-memory database; and
executing, based at least on the page directory, a database query on the in-memory database, the execution of the query comprising:
identifying, based at least on the page directory, a page that includes a row having-a target row position value; and
loading, from the in-memory database, the page that includes the row having the target row position value.

9. The non-transitory computer-readable medium of claim 8 , wherein the identifying of the page comprises searching the page directory for the target row position value in any of the one or more pages.

10. The non-transitory computer-readable medium of claim 9 , wherein the searching is performed by a binary search, a linear search, or a reverse linear search.

11. The non-transitory computer-readable medium of claim 8 , wherein the creating the capacity index comprises:
comparing a capacity of a first page with a capacity of a second page; and
adding the capacity of the second page to the capacity index if the capacity of the second page is different than the capacity of the first page.

12. The non-transitory computer-readable medium of claim 8 , wherein the change in capacity is due to one or more of an adjustment in a size of the data stored on the page, an adjustment in a number of rows used on the page, and an adjustment in a number of columns used on the page.

13. The non-transitory computer-readable medium of claim 8 , wherein the page directory is an array having a plurality of cells, each cell associated with a page in the table.

14. The non-transitory computer-readable medium of claim 8 , the operations further comprising:
persisting the page directory to the in-memory database.

15. A system comprising:
at least one processor; and
at least one memory, wherein the at least one processor and the at least one memory are configured to perform operations comprising:
accessing a table stored in an in-memory database, the table having a plurality of rows distributed across one or more pages in the in-memory database, each of the plurality of rows associated with a unique row position value, and each of the one or more pages associated with a capacity representative of an amount of data stored on the page;
creating, based at least on capacities of each of the plurality of pages in the in-memory database, a capacity index having a plurality of entries, the creation of the capacity index comprising:
inserting, into the capacity index, an entry corresponding to a first capacity of a first page, in response to the first capacity being different than a second capacity of a second page that precedes the first page;

creating a page directory based on the capacity index, the page directory indicating a plurality of row position values included in each of the one or more pages in the in-memory database; and
executing, based at least on the page directory, a database query on the in-memory database, the execution of the query comprising:
identifying, based at least on the page directory, a page that includes a row having a target row position value; and
loading, from the in-memory database, the page that includes the row having the target row position value.

16. The system of claim 15 , wherein the identifying of the page comprises searching the page directory for the target row position value, the searching comprising a binary search, a linear search, or a reverse linear search.

17. The system of claim 15 , wherein the creating the capacity index comprises:
comparing a capacity of a first page with a capacity of a second page; and
adding the capacity of the second page to the capacity index if the capacity of the second page is different than the capacity of the first page.

18. The system of claim 15 , wherein the change in capacity is due to one or more of an adjustment in a size of the data stored on the page, an adjustment in a number of rows used on the page, and an adjustment in a number of columns used on the page.

19. The sy

Assignees

• Wein David
• Schreter Ivan
• Sap Se

Inventors

• Wein David
• Schreter Ivan

Classifications

• G06F12/0817

  using directory methods · CPC title

• G06F16/9017 Primary

  using directory or table look-up (use of a directory or look-up table in file systems G06F16/13) · CPC title

• G06F16/284

  Relational databases · CPC title

• G06F16/245

  Query processing · CPC title

• G06F16/2246

  Trees, e.g. B+trees · CPC title