Fast row to page lookup of data table using capacity index

• US 9,898,551 B2
• Filed: 11/25/2014
• Issued: 02/20/2018
• Est. Priority Date: 11/25/2014
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Wein, David, Schreter, Ivan
• Primary Examiner(s): CHANNAVAJJALA, SRIRAMA T
• Application Number:
  US14/553,878
• Publication Number:
  US 20160147904A1
• Time in Patent Office: 1,183 Days
• CPC Class Codes: G06F 12/0817 using directory methods
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/9017 using directory or table look-up use of a directory or look-up table in file systems G06F16/13

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.

Claims

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 system of claim 15, wherein the page directory is an array having a plurality of cells, each cell associated with a page in the table.

20. The system of claim 15, the operations further comprising:

persisting the page directory to the in-memory database.