System load based adaptive prefetch

• US 7,359,890 B1
• Filed: 05/08/2002
• Issued: 04/15/2008
• Est. Priority Date: 05/08/2002
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Mozes, Ari W., Nithrakashyap, Arvind, Ku, Chi
• Primary Examiner(s): Wu; Yicun
• Application Number:
  US10/142,257
• Time in Patent Office: 2,169 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 707/6, 707/7, 707/8, 707/9, 707/10, 707/100, 707/101, 707/102, 707/103, 707/104.1, 707/200, 711/150, 711/113
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

A number, of the blocks of data to be prefetched into a buffer cache, is determined dynamically at run time (e.g. during execution of a query), based at least in part on the load placed on the buffer cache. An application program (such as a database) is responsive to the number (also called “prefetch size”), to determine the amount of prefetching. A sequence of instructions (also called “prefetch size daemon”) computes the prefetch size based on, for example, the number of prefetched blocks aged out before use. The prefetch size daemon dynamically revises the prefetch size based on usage of the buffer cache, thereby to form a feedback loop. Depending on the embodiment, at times of excessive use of the buffer cache, prefetching may even be turned off. Although in one embodiment described herein the prefetch size daemon is implemented in a database, in other embodiments other kinds of applications and/or the operating system itself can use a prefetch size daemon of the type described herein to dynamically determine and change prefetch behavior.

Claims

1. A method implemented in a computer, the method comprising:

determining usage of a buffer cache;

prefetching into the buffer cache, blocks of data equal in number to a prefetch size; and

changing said prefetch size depending at least partially on a fraction of said prefetched blocks that are wasted without use.

2. The method of claim 1 wherein:

the determining is done periodically.

3. The method of claim 1 wherein:

the determining is done in response to an asynchronous event.

4. The method of claim 1 wherein:

said changing of prefetch size further depends at least partially on a number of clients; and

said clients receive at least some data in said prefetched blocks from said computer.

5. The method of claim 1 wherein:

the prefetching is performed only on satisfaction of a condition based on at least one of the following;

(a) cache miss rate and (b) clustering.

6. A method implemented in a computer that supports a plurality of clients, the method comprising:

determining usage of a buffer cache;

prefetching into the buffer cache, blocks of data equal in number to a prefetch size; and

changing said prefetch size at least partially dependent inversely on a number of clients;

wherein said computer currently prefetches data blocks into the buffer cache in response to said clients.

7. The method of claim 6 wherein:

the determining is done periodically.

8. The method of claim 6 wherein:

the determining is done in response to an asynchronous event.

9. The method of claim 6 wherein:

the prefetching is performed only on satisfaction of a condition based on at least one of the following;

(a) cache miss rate and (b) clustering.

10. A method implemented in a computer, said computer comprising a database, the method comprising:

determining usage of a buffer cache; and

prefetching into the buffer cache, blocks of data whose number depends at least in part on usage of the buffer cache;

wherein the prefetching is performed at least when a clustering factor is high, with a low clustering factor indicating that individual rows being fetched are concentrated within fewer blocks in a table of said database, and a high clustering factor indicating that individual rows are scattered rather than being collocated.

11. The method of claim 10 wherein:

the determining is done periodically.

12. The method of claim 10 wherein:

the determining is done in response to an asynchronous event.

13. A method implemented in a computer that supports a plurality of clients, the method comprising:

prefetching into a buffer cache, at least one block of data in response to at least one request from one client;

determining a fraction of a set of blocks in said buffer cache that have been prefetched and later aged out before use; and

prefetching an additional number of blocks into said buffer cache, said additional number depending at least in part on said fraction.

14. The method of claim 13 wherein:

said prefetching of additional number of blocks is performed in response to an additional request.

15. The method of claim 14 wherein:

said computer comprises a database, said database comprising a table, said table comprising a plurality of rows;

said additional number further depends on a number of said rows identified in said additional request.

16. The method of claim 15 wherein:

said prefetchings are performed at least when a predetermined condition is satisfied indicating that individual rows are scattered rather than being collocated.

17. The method of claim 13 wherein:

said additional number further depends on a number of said plurality of clients.

18. The method of claim 13 wherein:

said computer comprises an operating system; and

said determining and said prefetchings are performed by said operating system.

19. The method of claim 13 wherein:

said computer comprises a browser; and

said determining and said prefetchings are performed for said browser.

20. A computer-readable storage medium encoded with a plurality of instructions, said plurality of instructions comprising:

instructions to determine usage of a buffer cache;

instructions to prefetch into the buffer cache, a number of blocks of data;

wherein said number depends on a prefetch size; and

instructions to change said prefetch size depending at least partially on a fraction of said blocks that are prefetched, by said instructions to prefetch, and are wasted without use.

21. A computer-readable storage medium encoded with a plurality of instructions, said plurality of instructions comprising:

instructions to determine usage of a buffer cache of a computer;

instructions to prefetch into the buffer cache, a number of blocks of data;

wherein said number depends on a prefetch size; and

instructions to change said prefetch size at leats partially dependent inversely on a number of clients, which clients receive data from the computer based on said prefetching.

22. A computer-readable storage medium encoded with a plurality of instructions to be executed by a computer, said plurality of instructions comprising:

instructions to determine usage of a buffer cache; and

instructions to prefetch into the buffer cache, blocks of data whose number depends at least in part on usage of the buffer cache;

wherein the instructions to prefetch are executed at least when a clustering factor is high, with a low clustering factor indicating that individual rows being fetched are concentrated within fewer blocks in a table of a database in said computer, and a high clustering factor indicating that individual rows are scattered rather than being collocated.

23. A computer comprising:

a storage medium containing data;

means, coupled to the storage medium, for determining usage of a buffer cache for data in the storage medium; and

means, coupled to the determining means and coupled to the storage medium, for prefetching from the storage medium into the buffer cache, blocks of data equal in number to a prefetch size;

wherein the means for determining includes a storage location indicative of a fraction of said prefetched blocks that are wasted without use.

24. The computer of claim 23 wherein:

the means for determining further comprises another storage location encoded with a number of clients;

the computer prefetching data blocks into the buffer cache in response to requests from said clients.

25. A computer comprising:

a storage medium containing data;

means, coupled to the storage medium, for determining usage of a buffer cache for data in the storage medium; and

means, coupled to the determining means and coupled to the storage medium, for prefetching from the storage medium into the buffer cache, blocks of data whose number depends at least in part on usage of the buffer cache;

wherein the means for determining includes a storage location encoded with a number of clients that currently prefetch data blocks into the buffer cache.

26. A computer comprising:

a storage medium containing data of a database;

means, coupled to the storage medium, for determining usage of a buffer cache for data in the storage medium; and

means, coupled to the determining means and coupled to the storage medium, for prefetching from the storage medium into the buffer cache, blocks of data whose number depends at least in part on usage of the buffer cache;

wherein the means for prefetching performs prefetching at least when a clustering factor is high, with a low clustering factor indicating that individual rows being fetched are concentrated within fewer blocks in a table of said database, and a high clustering factor indicating that individual rows are scattered rather than being collocated.

27. A computer-readable storage medium encoded with a plurality of instructions, said plurality of instructions comprising:

instructions to prefetch into a buffer cache, at least one block of data in response to at least one request from one client;

instructions to determine a count of blocks in said buffer cache that have been prefetched and later aged out before use; and

instructions to prefetch an additional number of blocks into said buffer cache, said additional number depending at least in part on said count.