# US 7,610,351 B1 · Method and mechanism for pipelined prefetching

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 7,610,351 B1
- Document ID: US7610351B1
- Status: Granted
- Kind: B1
- Application number: 10/144,083
- Filed: 2002-05-10
- Granted: 2009-10-27
- Earliest claimed: 2002-05-10
- Assignees: Oracle International Corporation
- Inventors: Sreenivas Gollapudi; Lakshminarayanan Chidambaran; Debashis Saha; Kapil Surlaker
- Web page: https://patentgrep.com/patent/US7610351B1

## CPC

- H04L 67/5681: Pre-fetching or pre-delivering data based on network characteristics
- H04L 67/289: Intermediate processing functionally located close to the data consumer application, e.g. in same machine, in same home or in same sub-network
- H04L 67/2895: Intermediate processing functionally located close to the data provider application, e.g. reverse proxies
- Y10S 707/99932: Access augmentation or optimizing
- Y10S 707/99933: Query processing, i.e. searching
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

## Abstract

A method and mechanism for implementing pipelined prefetching in a computer system is disclosed. Data prefetching is utilized to predictably retrieve information between multiple levels of nodes in the computer system, in which a first server may receive prefetched data from a second server, the second server receives prefetched data from a third server, with the chain of prefetching extending as long as needed/desired to effect efficient data transfers between the nodes.

## Claims

### Claim 1

A computer implemented method for prefetching data in a database system using multiple levels of prefetching to retrieve data between networked machines, comprising:
at a first prefetching level,
receiving a client request for a data item to be sent from a first database server to a client, the first database server executing database query operations against data in a database to satisfy the client request;
determining by using a first processor, a first prefetch condition for the first prefetching level to satisfy the client request, wherein the first prefetch condition is used to control what data items to prefetch on the first prefetching level; and
sending at least part of the data item from the first database server to the client;
prefetching, based at least upon the first prefetch condition, a second data item from the first database server to the client in anticipation of a future request from the client and storing, by using a bus, the second data item in a first data structure on a tangible computer readable medium or a storage device;
at a second prefetching level,
in response to the client request, receiving a first server request for a server data item to be sent from a second database server to the first database server, the first server request is to satisfy the client request;
receiving the server data item from the second database server to the first database server;
determining, by using a second processor, a second prefetch condition of the first prefetch condition for the second prefetching level to service the first server request, wherein the second prefetch condition is used to control what data items to prefetch on the second prefetching level;
determining existence of data redundancies when prefetching the second server data item by calculating row differences between successive rows in the second server data item by consulting a bitmap corresponding to changes between a first row and a second row of data; and
prefetching, based at least upon the second prefetch condition, a second server data item from the second database server to the first database server in anticipation of a future request from the first database.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
transmitting a reduced set of the second server data item, said reduced set comprising a smaller memory footprint when compared to the second server data item.

### Claim 3 (depends on 2)

The method of claim 2 in which determining the existence of the data redundancies is performed by identifying multiple copies of information; and the act of transmitting a reduced set of prefetch data comprises sending a single copy of the information that has not changed between a first row and a second row.

### Claim 4 (depends on 1)

The method of claim 1 in which calculating the row differences between successive rows is performed by identifying identical column values for the successive rows.

### Claim 5 (depends on 1)

The method of claim 1 in which determining the existence of the data redundancies is performed by creating a bitmap corresponding to changes between a first row and a second row of data, the bitmap containing bit values for differences in column values between the first and second rows.

### Claim 6 (depends on 1)

The method of claim 1 in which the bitmap is a multidimensional bitmap.

### Claim 7 (depends on 1)

The method of claim 1 in which a prefetch count is employed to identify quantity of data to prefetch.

### Claim 8 (depends on 7)

The method of claim 7, wherein the prefetch count indicates a number of rows of a table to prefetch.

### Claim 9 (depends on 7)

The method of claim 7, wherein the prefetch count is a tunable value, further comprising adjusting the prefetch count.

### Claim 10 (depends on 1)

The method of claim 1 in which website data is prefetched.

### Claim 11 (depends on 1)

The method of claim 1 in which prefetching is performed in response to a scrolling request for a scrollable cursor.

### Claim 12 (depends on 11)

The method of claim 11 in which the scrolling request moves a position for the scrollable cursor corresponding to the data item.

### Claim 13 (depends on 12)

The method of claim 12 in which the scrolling request is in the reverse direction.

### Claim 14 (depends on 1)

The method of claim 1, further comprising at a third prefetching level;
issuing a third server request for a second server data item to be sent from a third database server to the second database server, the third database server performing additional database query operations to satisfy the second server request;
sending the requested third server data item from the third database server to the second database server; and
prefetching a fourth server data item from the third database server to the second database server in anticipation of a future request from the second database server, wherein the prefetched fourth server data item is not explicitly requested by the second database server.

### Claim 15 (depends on 1)

The method of claim 1, wherein the prefetched second data item is not explicitly requested by the client request, and the prefetched second server data item is not explicitly requested by the first database server.

### Claim 16

A system for prefetching data in a database system using multiple levels of prefetching to retrieve data between networked machines, comprising:
a client device comprising a client cache and a first data structure, wherein the client device issues a client request for a data item;
at a first prefetching level,
a first database server device comprising a server cache;
the first database server device determining, by using a first processor, a first prefetch condition for the first prefetching level to satisfy the client request, wherein the first prefetch condition is used to control what data items to prefetch on the first prefetching level;
the first database server performing database query operations to send the data item, to satisfy the client request and to prefetch, based at least upon the first prefetch condition, a second data item that is transmitted from the first database server to the client device and stored in the client cache; and
at a second prefetching level, a second server device configured for receiving a first server request for a requested server data item, wherein the first server request is to satisfy the client requests;
determining, by using a second processor, a second prefetch condition for the second prefetching level to service the first server request, wherein the second prefetch condition is determined independently of the first prefetch condition, and the second prefetch condition is used to control what data items to prefetch on the second prefetching levels;
determining existence of data redundancies when prefetching, the second server data item by calculating row differences between successive rows in the second, server data item by consulting a bitmap corresponding to changes between a first row and a second row of data; and
performing second server database query operations to send the requested server data item from the second database server to the first database sever and to prefetch, based at least in part upon the second prefetch condition, a second server data item that is transmitted from the second database server device to the first database server device and stored in the server cache.

### Claim 17 (depends on 16)

The system of claim 16 in which the first and second database server devices determine the existence of data redundancies.

### Claim 18 (depends on 17)

The system of claim 17 in which a reduced set of data is sent if the data redundancies are identified.

### Claim 19 (depends on 18)

The system of claim 18 in which determining the existence of the data redundancies is performed by calculating row differences between successive rows of prefetched data.

### Claim 20 (depends on 18)

The system of claim 18 in which determining the existence of the data redundancies is performed by consulting a bitmap corresponding to changes between's first row and a second row of data.

### Claim 21 (depends on 20)

The system of claim 20 in which the bitmap is a multi dimensional bitmap.

### Claim 22 (depends on 16)

The system of claim 16 in which a prefetch count is employed to identify quantity of data to prefetch.

### Claim 23 (depends on 22)

The system of claim 22, wherein the prefetch count indicates a number of rows of a table to prefetch.

### Claim 24 (depends on 22)

The system of claim 22, wherein the prefetch count is a tunable value.

### Claim 25 (depends on 16)

The system of claim 16 in which website data is prefetched.

### Claim 26 (depends on 16)

The system of claim 16 in which prefetching is performed in response to a scrolling request for a scrollable cursor.

### Claim 27 (depends on 26)

The system of claim 26 in which the scrolling request moves a position for the scrollable cursor corresponding to the data item.

### Claim 28 (depends on 26)

The system of claim 26 in which the scrolling request is in the reverse direction.

### Claim 29 (depends on 16)

The system of claim 16, the second database server device comprising a second server cache, further comprising:
at a third prefetching level,
a third database server device, the third database server device performing database query operations to send a third requested server data item from the third database server to the second database sever and prefetch a fourth server data item that is transmitted from the third database server device to the second database server device and stored in the second server cache, wherein the prefetched fourth server data item is not explicitly requested by the second database server.

### Claim 30 (depends on 16)

The system of claim 16, wherein the prefetched second data item is not explicitly requested by the client request, and the prefetched second server data item is not explicitly requested by the first database server.

### Claim 31

A system for prefetching data in a database system using multiple is of prefetching to retrieve data between networked machines, comprising:
at a first prefetching level,
means for receiving a client request for a data item to be sent from a first database server to a client, the first database server executing database query operations against data in a database to satisfy the client request;
a first processor configured for determining a first prefetch condition for the first prefetching level to service the client request, wherein the means for determining the first prefetch condition comprises a first processor, and the first prefetch condition is used to control what data items to prefetch on the first prefetching level; and
means for sending part of the data item from the first database server to the client based at least in part upon the first prefetch condition;
means for prefetching, based at least in part on the first prefetch condition, a second data item from the first database server to the client-in anticipation of a future request from the client and a tangible computer readable medium or a storage device configured for storing at least part of the second data item in a first data structure;
at a second prefetching level,
means for, in response to the client request, receiving a first server request for a server data item to be sent from a second database server to the first database server, the first server request is to satisfy the client request;
means for receiving the server data item from the second database server 1 o the first database server;
a second processor configured for determining, by using a second processor, a second prefetch condition independently of the first prefetch condition for the second level to service the first server request, wherein the second prefetch condition is used to control what data items to prefetch on the second prefetching level;
means for determining existence of data redundancies when prefetching the second server data item by calculating row differences between successive rows in the second server data item by consulting a bitmap corresponding to changes between a first row and a second row of data; and
means for prefetching, based at least in part on the second prefetch condition, a second server data item from the second database server to the first database server-in anticipation of a future request from the first database server.

### Claim 32 (depends on 31)

The system of claim 31, further comprising:
means for transmitting a reduced set of the second server data item, said reduced set comprising a smaller memory footprint when compared to the second server data item.

### Claim 33 (depends on 31)

The system of claim 31 in which the means for determining the existence of the data redundancies comprises means for consulting a bit nap corresponding to changes between a first row and a second row of data.

### Claim 34 (depends on 31)

The system of claim 31 in which the means for determining the existence of the data redundancies comprises means for identifying multiple copies of information; and the act of transmitting a reduced set of prefetch data comprises sending a single copy of the information that has not changed between a first row and a second row.

### Claim 35 (depends on 31)

The system of claim 31 in which a prefetch count is employed to identify quantity of data to prefetch.

### Claim 36 (depends on 35)

The system of claim 35, wherein the prefetch count indicates a number of rows of a table to prefetch.

### Claim 37 (depends on 35)

The system of claim 35, wherein the prefetch count is a tunable value.

### Claim 38 (depends on 31)

The system of claim 31 in which prefetching is performed in response to a scrolling request for a scrollable cursor.

### Claim 39 (depends on 31)

The system of claim 31, further comprising at a third prefetching level,
means for issuing a second, server request for a third server data item to be sent from a third database server to the second database server, the third database server performing additional database query operations to satisfy the second server request;
means for sending the requested third server data item from the third database server to the second database server; and
means for prefetching a fourth server data item from the third database server to the second database server in anticipation of a future request from the second database server, wherein the prefetched fourth server data item is not explicitly requested by the second database server.

### Claim 40 (depends on 31)

The system of claim 31, wherein the prefetched second data item is not explicitly requested by the client request, and the prefetched second server data item is not explicitly requested by the first database server.

### Claim 41

A computer program product comprising a computer usable medium embedded executable code to execute a process for prefetching data in a database system using multiple levels of prefetching to retrieve data between networked machines, the process comprising:
at a first prefetching level,
receiving a client request for a data item to he sent from a first database server to a client, the first database server executing database query operations against data in a database to satisfy the client request;
determining, by using a first processor, a first prefetch condition for the first prefetching level to satisfy the client request, wherein the first prefetch condition is used to control what data items to prefetch on the first prefetching level;
sending part of the data item from the first database server to the client;
prefetching, based at least in part on the first prefetch condition, a second data item from the first database server to the client in anticipation of a future request from the client and storing, by using a bus, the second data item in a first data structure on a tangible computer usable medium or a storage device;
at a second prefetching level,
in response to the client request, receiving a first server request for a server data item to be sent from a second database server to the first database server, the first server request is to satisfy the client request;
receiving the server data item from the second database server to the first database server;
determining, by using a second processor, a second prefetch condition independently of the first prefetch condition for the second prefetching level to service the first server request, wherein the second prefetch condition is used to control what data items to prefetch on the second prefetching level;
determining existence of data redundancies when prefetching the second server data item by calculating row differences between successive rows in the second server data item by consulting a bitmap corresponding to changes between a first row and a second row of data; and
prefetching, based at least on the second prefetch condition, a second server data item from the second database server to the first database server in anticipation of a future request from the first database server.

### Claim 42 (depends on 41)

The computer program product of claim 41 further comprising:
transmitting a reduced set of the second server data item, said reduced set comprising a smaller memory footprint when compared to the second server data item.

### Claim 43 (depends on 41)

The computer program product of claim 41 in which determining the existence of the data redundancies is performed by identifying multiple copies of information; and the act of transmitting a reduced set of prefetch data comprises sending a single copy of the information that has not changed between a first row and a second row.

### Claim 44 (depends on 41)

The computer program product of claim 41 in which a prefetch count is employed to identify quantity of data to prefetch.

### Claim 45 (depends on 44)

The computer program product of claim 44, wherein the prefetch count indicates a number of rows of a table to prefetch.

### Claim 46 (depends on 44)

The computer program product of claim 44, wherein the prefetch count is a tunable value.

### Claim 47 (depends on 41)

The computer program product of claim 41 in which prefetching is performed in response to a scrolling request for a scrollable cursor.

### Claim 48 (depends on 41)

The computer program product of claim 41, wherein the executable code executes a process further comprising:
issuing a second server request for a third server data item to be sent from a third database server to the second database server, the third database server performing additional database query operations to satisfy the second server request; sending the third server data item from the third database server to the second database server; and
prefetching a fourth server data item from the third database server to the second database server in anticipation of a future request from the second database server, wherein the prefetched fourth server data item is not explicitly requested by the second database server.

### Claim 49 (depends on 41)

The computer program product of claim 41, wherein the prefetched second data item is not explicitly requested by the client request; and the prefetched second server data item is not explicitly requested by the first database server.