Method and mechanism for pipelined prefetching

• US 7,610,351 B1
• Filed: 05/10/2002
• Issued: 10/27/2009
• Est. Priority Date: 05/10/2002
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Surlaker, Kapil, Saha, Debashis, Gollapudi, Sreenivas, Chidambaran, Lakshminarayanan
• Primary Examiner(s): Najjar; Saleh
• Assistant Examiner(s): NGUYEN, THUONG
• Application Number:
  US10/144,083
• Time in Patent Office: 2,727 Days
• Field of Search: 709/238, 709/217, 707 1- 3, 707/10
• US Class Current: 709/217
• CPC Class Codes: 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
• CPC Class Codes: H04L 67/2895 Intermediate processing functionally located close to the data provider application, e.g. reverse proxies
• CPC Class Codes: H04L 67/5681 Pre-fetching or pre-delivering data based on network characteristics
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

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

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.

2. 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.

3. 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.

4. 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.

5. 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.

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

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

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

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

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

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

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

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

14. 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.

15. 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.

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.

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

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

19. 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.

20. 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.

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

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

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

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

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

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

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

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

29. 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.

30. 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.

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.

32. 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.

33. 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.

34. 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.

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

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

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

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

39. 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.

40. 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.

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.

42. 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.

43. 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.

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

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

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

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

48. 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.

49. 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.