# US 11,442,862 B2 · Fair prefetching in hybrid column stores > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,442,862 B2 - Document ID: US11442862B2 - Status: Granted - Kind: B2 - Application number: 16/850,310 - Filed: 2020-04-16 - Published: 2021-10-21 - Granted: 2022-09-13 - Earliest claimed: 2020-04-16 - Assignees: Sap SE - Applicants: Sap SE - Inventors: Robert Schulze; Adrian Dragusanu; Anup Ghatage; Colin Florendo; Mihnea Andrei; Randall Hammon; Sarika Iyer; Simhachala Sasikanth Gottapu; Yanhong Wang - Web page: https://patentgrep.com/patent/US11442862B2 ## CPC - G06F 12/0862: with prefetch - G06F 12/0882: Page mode - G06F 16/221: {Column-oriented storage; Management thereof} - G06F 16/2282: {Tablespace storage structures; Management thereof} - G06F 16/24: Querying - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Disclosed herein are system, method, and computer program product embodiments for performing fair prefetching. An embodiment operates by splitting a data vector into a first subrange and a second subrange. The embodiment performs a first chance prefetch operation on the first subrange based on a fixed number of pages, thereby loading a set of pages of the first subrange into a main memory. The embodiment performs the first chance prefetch operation on the second subrange based on the fixed number of pages, thereby loading a first set of pages of the second subrange into the main memory. The embodiment performs a second chance prefetch operation on the second subrange based on the performing the first chance prefetch operation on the second subrange, thereby loading a second set of pages of the second subrange into the main memory. The embodiment then executes the query. ## Claims ### Claim 1 A method for prefetching for a query, comprising: splitting, by at least one processor, a data vector associated with a column of a database table into a first subrange and a second subrange in response to the query; performing, by the at least one processor, a first chance prefetch operation on the first subrange based on a first number of rows to prefetch for the first subrange, wherein the first number of rows to prefetch for the first subrange is calculated based on a fixed number of pages, and wherein the performing the first chance prefetch operation on the first subrange loads a first set of pages of the first subrange into a main memory; performing, by the at least one processor, the first chance prefetch operation on the second subrange based on a second number of rows to prefetch for the second subrange, wherein the second number of rows to prefetch for the second subrange is calculated based on the fixed number of pages, and wherein the performing the first chance prefetch operation on the second subrange loads a second set of pages of the second subrange into the main memory; performing, by the at least one processor, a second chance prefetch operation on the second subrange based on the performing the first chance prefetch operation on the second subrange, thereby loading a third set of pages of the second subrange into the main memory; and executing, by the at least one processor, the query based on the first set of pages of the first subrange, the second set of pages of the second subrange, and the third set of pages of the second subrange. ### Claim 2 (depends on 1) The method of claim 1, further comprising: determining, by the at least one processor, all rows of the first subrange have been prefetched into the main memory; and skipping, by the at least one processor, performing the second chance prefetch operation on the first subrange based on the determination that all the rows of the first subrange have been prefetched into the main memory. ### Claim 3 (depends on 1) The method of claim 1, wherein the performing the second chance prefetch operation on the second subrange further comprises: determining, by the at least one processor, a current row associated with the second subrange is before an end row of the second subrange; determining, by the least one processor, the third set of pages of the second subrange based on the current row associated with the second subrange and the end row of the second subrange; and prefetching, by the at least one processor, the third set of pages for the second subrange into the main memory. ### Claim 4 (depends on 1) The method of claim 1, wherein the performing the first chance prefetch operation on the first subrange further comprises: determining, by the at least one processor, the first set of pages of the first subrange based on the number of rows to prefetch for the first subrange and a current row associated with the first subrange; incrementing, by the at least one processor, the current row associated with the first subrange based on the number of rows to prefetch for the first subrange; and prefetching, by the at least one processor, the first set of pages of the first subrange into the main memory; and further comprising repeating, by the at least one processor, the first chance prefetch operation until all rows of the first subrange have been prefetched or a prefetch limit is satisfied. ### Claim 5 (depends on 4) The method of claim 4, wherein the first set of pages of the first subrange comprises a set of rows in the first subrange, wherein the set of rows begins at the current row, and a size of the set of rows is equal to the number of rows to prefetch for the first subrange. ### Claim 6 (depends on 4) The method of claim 4, wherein the determining the first set of pages of the first subrange comprises: determining, by the at least one processor, the first set of pages of the first subrange using a persistence layer. ### Claim 7 (depends on 1) The method of claim 1, wherein the first number of rows to prefetch for the first subrange is calculated using the data vector. ### Claim 8 A system, comprising: a memory; and at least one processor coupled to the memory and configured to: split a data vector associated with a column of a database table into a first subrange and a second subrange in response to a query; perform a first chance prefetch operation on the first subrange based on a first number of rows to prefetch for the first subrange, wherein the first number of rows to prefetch for the first subrange is calculated based on a fixed number of pages, and wherein the performing the first chance prefetch operation on the first subrange loads a first set of pages of the first subrange into the memory; perform the first chance prefetch operation on the second subrange based on a second number of rows to prefetch for the second subrange, wherein the second number of rows to prefetch for the second subrange is calculated based on the fixed number of pages, and wherein the performing the first chance prefetch operation on the second subrange loads a second set of pages of the second subrange into the memory; perform a second chance prefetch operation on the second subrange based on the performing the first chance prefetch operation on the second subrange, thereby loading a second set of pages of the third subrange into the memory; and execute the query based on the first set of pages of the first subrange, the second set of pages of the second subrange, and the third set of pages of the second subrange. ### Claim 9 (depends on 8) The system of claim 8, the at least one processor further configured to: determine all rows of the first subrange have been prefetched into the memory; and skip performing the second chance prefetch operation on the first subrange based on the determination that all the rows of the first subrange have been prefetched into the memory. ### Claim 10 (depends on 8) The system of claim 8, wherein to perform the second chance prefetch operation on the second subrange the at least one processor is further configured to: determine a current row associated with the second subrange is before an end row of the second subrange; determine the second set of pages of the third subrange based on the current row associated with the second subrange and the end row of the second subrange; and prefetch the second set of pages for the third subrange into the memory. ### Claim 11 (depends on 8) The system of claim 8, wherein to perform the first chance prefetch operation on the first subrange the at least one processor is further configured to: determine the first set of pages of the first subrange based on the number of rows to prefetch for the first subrange and a current row associated with the first subrange; increment the current row associated with the first subrange based on the number of rows to prefetch for the first subrange; and prefetch the first set of pages of the first subrange into the memory; wherein the at least one processor is further configured to repeat the first chance prefetch operation until all rows of the first subrange have been prefetched or a prefetch limit is satisfied. ### Claim 12 (depends on 11) The system of claim 11, wherein the first set of pages of the first subrange comprises a set of rows in the first subrange, wherein the set of rows begins at the current row, and a size of the set of rows is equal to the number of rows to prefetch for the first subrange. ### Claim 13 (depends on 11) The system of claim 11, wherein to determine the first set of pages of the first subrange the at least one processor is further configured to: determine the first set of pages of the first subrange using a persistence layer. ### Claim 14 (depends on 8) The system of claim 8, wherein the first number of rows to prefetch for the first subrange is calculated using the data vector. ### Claim 15 A non-transitory computer-readable medium having instructions stored thereon that, when executed by at least one computing device, cause the at least one computing device to perform operations comprising: splitting a data vector associated with a column of a database table into a first subrange and a second subrange in response to a query; performing a first chance prefetch operation on the first subrange based on a first number of rows to prefetch for the first subrange, wherein the first number of rows to prefetch for the first subrange is calculated based on a fixed number of pages, and wherein the performing the first chance prefetch operation on the first subrange loads a first set of pages of the first subrange into a main memory; performing the first chance prefetch operation on the second subrange based on a second number of rows to prefetch for the second subrange, wherein the second number of rows to prefetch for the second subrange is calculated based on the fixed number of pages, and wherein the performing the first chance prefetch operation on the second subrange loads a a second set of pages of the second subrange into the main memory; performing a second chance prefetch operation on the second subrange based on the performing the first chance prefetch operation on the second subrange, thereby loading a second set of pages of the third subrange into the main memory; and executing the query based on the first set of pages of the first subrange, the second set of pages of the second subrange, and the third set of pages of the second subrange. ### Claim 16 (depends on 15) The non-transitory computer-readable medium of claim 15, the operations further comprising: determining all rows of the first subrange have been prefetched into the main memory; and skipping performing the second chance prefetch operation on the first subrange based on the determination that all the rows of the first subrange have been prefetched into the main memory. ### Claim 17 (depends on 15) The non-transitory computer-readable medium of claim 15, the performing the second chance prefetch operation on the second subrange further comprising: determining a current row associated with the second subrange is before an end row of the second subrange; determining the third set of pages of the second subrange based on the current row associated with the second subrange and the end row of the second subrange; and prefetching the third set of pages for the second subrange into the main memory. ### Claim 18 (depends on 15) The non-transitory computer-readable medium of claim 15, the performing the first chance prefetch operation on the first subrange further comprising: determining the first set of pages of the first subrange based on the number of rows to prefetch for the first subrange and a current row associated with the first subrange; incrementing the current row associated with the first subrange based on the number of rows to prefetch for the first subrange; and prefetching the first set of pages of the first subrange into the main memory; and the operations further comprising repeating the first chance prefetch operation until all rows of the first subrange have been prefetched or a prefetch limit is satisfied. ### Claim 19 (depends on 18) The non-transitory computer-readable medium of claim 18, wherein the first set of pages of the first subrange comprises a set of rows in the first subrange, wherein the set of rows begins at the current row, and a size of the set of rows is equal to the number of rows to prefetch for the first subrange. ### Claim 20 (depends on 18) The non-transitory computer-readable medium of claim 18, wherein the first number of rows to prefetch for the first subrange is calculated using the data vector.