Cache efficient reading of result values in a column store database

• US 10,445,076 B1
• Filed: 05/07/2018
• Issued: 10/15/2019
• Est. Priority Date: 05/07/2018
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Legler, Thomas
• Primary Examiner(s): Nguyen, Than
• Application Number:
  US15/973,058
• Publication Number:
  US 20190339954A1
• Time in Patent Office: 526 Days
• CPC Class Codes: G06F 12/0844 Multiple simultaneous or quasi-simultaneous cache accessing
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/163 Server or database system
• CPC Class Codes: G06F 2212/463 File
• CPC Class Codes: G06F 8/4442 Reducing the number of cache misses; Data prefetching cache prefetching G06F12/0862

Abstract

A system for cache efficient reading of column values in a database is provided. In some aspects, the system performs operations including pre-fetching, asynchronously and in response to a request for data in a column store database system, a plurality of first values associated with the requested data. The request may identify a row of the column store database system associated with the requested data. The plurality of first values may be located in the row. The operations may further include storing the plurality of first values in a cache memory. The operations may further include pre-fetching, asynchronously and based on the plurality of first values, a plurality of second values. The operations may further include storing the plurality of second values in the cache memory. The operations may further include reading, in response to the storing the plurality of second values, the requested data from the cache memory.

Claims

1. A system, comprising:

at least one data processor; and

at least one memory storing instructions which, when executed by the at least one data processor, cause operations comprising;

pre-fetching, asynchronously and in response to a request for data in a column store database system, a plurality of first values associated with the requested data, the request identifying a row of the column store database system associated with the requested data, the plurality of first values located in the row;

storing the plurality of first values in a cache memory;

pre-fetching, asynchronously and based on the plurality of first values, a plurality of second values;

storing the plurality of second values in the cache memory; and

reading, in response to the storing the plurality of second values, the requested data from the cache memory.

2. The system of claim 1, the operations further comprising:

reading the plurality of first values, wherein the plurality of second values are associated with the plurality of first values in a dictionary.

3. The system of claim 1, the operations further comprising:

determining a first value of the plurality of first values is associated with a second value in the plurality of second values, the first value and the second value associated with an attribute of the column store database system,

wherein the pre-fetching the plurality of second values is based on the determining.

4. The system of claim 1, the operations further comprising:

receiving the request, the request identifying the row, the plurality of first columns, and the plurality of second columns of the column store database system associated with the requested data.

5. The system of claim 1, wherein the pre-fetching the plurality of first values comprises retrieving the plurality of first values from a main memory of the at least one memory.

6. The system of claim 1, wherein the pre-fetching the plurality of first values comprises retrieving each of the plurality of first values from a different database table of the column store database system.

7. The system of claim 6, wherein the pre-fetching the plurality of second values comprises retrieving each of the plurality of second values from a database table associated with one of the plurality of first values.

8. The system of claim 1, wherein the pre-fetching the plurality of second values comprises retrieving dictionary entries associated with the plurality of first values, wherein the plurality of first values comprise value identifiers of the dictionary entries.

9. The system of claim 1, wherein the pre-fetching the plurality of first values comprises:

triggering a first pre-fetch call and a second pre-fetch call sequentially;

executing the first pre-fetch call in parallel with the second pre-fetch call.

10. The system of claim 9, wherein the pre-fetching the plurality of second values comprises:

triggering a third pre-fetch call and a fourth pre-fetch call sequentially;

executing the third pre-fetch call in parallel with the fourth pre-fetch call.

11. A method comprising:

pre-fetching, by at least one processor, asynchronously and in response to a request for data in a column store database system, a plurality of first values associated with the requested data, the request identifying a row of the column store database system associated with the requested data, the plurality of first values located in the row;

storing, by at the least one processor, the plurality of first values in a cache memory;

pre-fetching, by at the least one processor, asynchronously and based on the plurality of first values, a plurality of second values;

storing, by at the least one processor, the plurality of second values in the cache memory; and

reading, by at the least one processor and in response to the storing the plurality of second values, the requested data from the cache memory.

12. The method of claim 11, further comprising:

reading the plurality of first values, wherein the plurality of second values are associated with the plurality of first values in a dictionary.

13. The method of claim 11, the operations further comprising:

determining a first value of the plurality of first values is associated with a second value in the plurality of second values, the first value and the second value associated with an attribute of the column store database system,

wherein the pre-fetching the plurality of second values is based on the determining.

14. The method of claim 11, the operations further comprising:

receiving the request, the request identifying the row, the plurality of first columns, and the plurality of second columns of the column store database system associated with the requested data.

15. The method of claim 11, wherein the pre-fetching the plurality of first values comprises retrieving the plurality of first values from a main memory of the at least one memory.

16. The method of claim 11, wherein the pre-fetching the plurality of first values comprises retrieving each of the plurality of first values from a different database table of the column store database system.

17. The method of claim 11, wherein the pre-fetching the plurality of second values comprises retrieving dictionary entries associated with the plurality of first values, wherein the plurality of first values comprise value identifiers of the dictionary entries.

18. The method of claim 11, wherein the pre-fetching the plurality of first values comprises:

triggering a first pre-fetch call and a second pre-fetch call sequentially; and

executing the first pre-fetch call in parallel with the second pre-fetch call.

19. The method of claim 18, wherein the pre-fetching the plurality of second values comprises:

triggering a third pre-fetch call and a fourth pre-fetch call sequentially; and

executing the third pre-fetch call in parallel with the fourth pre-fetch call.

20. A non-transitory computer readable medium storing instructions which, when executed by at least one processor, cause operations comprising:

pre-fetching, asynchronously and in response to a request for data in a column store database system, a plurality of first values associated with the requested data, the request identifying a row of the column store database system associated with the requested data, the plurality of first values located in the row;

storing the plurality of first values in a cache memory;

pre-fetching, asynchronously and based on the plurality of first values, a plurality of second values;

storing the plurality of second values in the cache memory; and

reading, in response to the storing the plurality of second values, the requested data from the cache memory.