Prefetch performance of index access by look-ahead prefetch

• US 20060212658A1
• Filed: 03/18/2005
• Published: 09/21/2006
• Est. Priority Date: 03/18/2005
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hrle, Namik, Fuh, You-Chin, Tsuji, Yoichi, Xia, Li
• Application Number:
  US11/083,289
• Publication Number:
  US 20060212658A1
• Time in Patent Office: Days
• US Class Current: 711/137
• CPC Class Codes: G06F 12/0862 with prefetch

Abstract

Embodiments of the present invention provide a “look-ahead” form prefetch. Look-ahead prefetch may utilize a look-ahead queue to prefetch multiple pages asynchronously. The look-ahead queue may hold a plurality of search keys that are related to a transaction. When accessing a table, an index manager may retrieve the table'"'"'s index and scan the index based on the search keys from the look-ahead queue to find the RIDs in the table that match the search keys. The index manager may then accumulate these RIDs into a prefetch list. A prefetch manager may read the prefetch list, determine locations for the pages of the table that contain the records identified by the RIDs, and dispatch prefetch tasks to the appropriate storage device for these pages.

Claims

1. A method of prefetching records of a table before they are requested by a transaction, wherein said transaction is based on a set of keys, said method comprising:

queuing a plurality of the set of keys of the transaction;

scanning an index of the table based on the queued set of keys;

accumulating locations of records in the table based on the scan of the index;

determining respective pages that include the accumulated records; and

fetching the pages that include the accumulated records before they are requested , by the transaction.

2. The method of claim 1, wherein queuing the plurality of the set of keys of the transaction comprises:

queuing the plurality of the set of keys of the transaction, when a pipelined index access plan has been specified for the transaction.

3. The method of claim 1, wherein queuing the plurality of the set of keys of the transaction comprises:

determining when the queue of the plurality of keys is empty; and

refilling the queue of the plurality of keys when the queue is empty.

4. The method of claim 1, wherein scanning the index of the table based on the queued set of keys comprises:

scanning the index based on all of the queued set of keys.

5. The method of claim 4, wherein the index comprises a B-tree structure and wherein scanning the index of the table based on the queued set of keys comprises retrieving index leaf pages in the B-tree structure for all the queued set of keys.

6. The method of claim 1, wherein accumulating locations of records in the table based on the scan of the index comprises accumulating all the record identifiers in the table that satisfy the queued set of keys.

7. The method of claim 6, wherein determining respective pages that include the accumulated records comprises determining the respective pages that include the records based on a portion of the record identifier.

8. The method of claim 1, wherein determining respective pages that include the accumulated records comprises determining a list of unique pages that include the accumulated records.

9. The method of claim 8, wherein fetching the pages that include the accumulated records comprises fetching the unique pages from at least one storage device into a memory unless they are already cached in the memory.

10. A system that processes transactions, wherein the system is configured to prefetch records of a table before they are requested by the transactions, said system comprising:

at least one look-ahead queue having entries for search keys specified in a transaction;

a buffer pool that comprises at least a portion of a table and an index of the table, wherein the index comprises a set of entries each having an index key that indicates a value for a field of the table and a record identifier that indicates a location of a record that has the value in the field;

an index manager that is configured to scan the index based on the search keys in the entries in the look-ahead queue and write the record identifiers of the records in the table that satisfy the search keys into a prefetch list; and

a prefetcher that is configured to read the prefetch list, determine a set of pages that contain the records that satisfy the search keys, and fetch the set of pages before they are requested by the transaction.

11. The system of claim 10, wherein the prefetcher is configured to empty the prefetch list asynchronously from when the index manager writes to the prefetch list.

12. A computer readable medium having program code that configures a processor to prefetch records of a table before they are requested by a transaction, wherein said transaction is based on a set of keys, said medium comprising:

program code for queuing a plurality of the set of keys of the transaction;

program code for scanning an index of the table based on the queued set of keys;

program code for accumulating locations of records in the table based on the scan of the index;

program code for determining respective pages that include the accumulated records; and

program code for fetching the pages that include the accumulated records before they are requested by the transaction.

13. The computer readable medium of claim 12, wherein the program code for queuing the plurality of the set of keys of the transaction comprises:

program code for queuing the plurality of the set of keys of the transaction, when a pipelined index access plan has been specified for the transaction.

14. The computer readable medium of claim 12, wherein the program code for queuing the plurality of the set of keys of the transaction comprises:

program code for determining when the queue of the plurality of keys is empty; and

program code for refilling the queue of the plurality of keys when the queue is empty.

15. The computer readable medium of claim 12, wherein the program code for scanning the index of the table based on the queued set of keys comprises:

program code for scanning the index based on all of the queued set of keys.

16. The computer readable medium of claim 12, wherein the index comprises a B-tree structure and wherein the program code for scanning the index of the table based on the queued set of keys comprises program code for retrieving index leaf pages in the B-tree structure for all the queued set of keys.

17. The computer readable medium of claim 12, wherein the program code for accumulating locations of records in the table based on the scan of the index comprises program code for accumulating all the record identifiers in the table that satisfy the queued set of keys.

18. The computer readable medium of claim 12, wherein the program code for determining respective pages that include the accumulated records comprises program code for determining the respective pages that include the records based on a portion of the record identifier.

19. The computer readable medium of claim 12, wherein the program code for determining respective pages that include the accumulated records comprises program code for determining a list of unique pages that include the accumulated records.

20. The computer readable medium of claim 12, wherein the program code for fetching the pages that include the accumulated records comprises program code for fetching the unique pages from at least one storage device into a memory unless they are already cached in the memory.