Method and apparatus for analyzing data retrieval using index scanning

• US 6,549,895 B1
• Filed: 07/05/2000
• Issued: 04/15/2003
• Est. Priority Date: 12/22/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lai, Tony Wen Hsun
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): Liang, Gwen
• Application Number:
  US09/609,887
• Time in Patent Office: 1,014 Days
• Field of Search: 707/2, 707/5, 707/100, 707/8, 707/201, 707/7, 707/1, 707/10, 707/3, 711/160
• US Class Current: 707/742
• CPC Class Codes: G06F 16/24524 Access plan code generation and invalidation; Reuse of access plans
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A method and computer program product for analyzing data retrieval using index scanning in a database management system. The method involves scanning an index associated with a table in the database management system and selecting pages in the index. For each of the selected pages, the index entries are extracted and ranked. A distance parameter is then determined for each of the ranked index entries. The number of page transfers is estimated based on the distance parameters and the number of consecutive index entries which can be stored in the buffer pool.

Claims

1. A method for data retrieval using index scanning in a database management system, the database management system including a processing unit operably coupled to physical storage for storing data, the physical storage containing at least one database table stored in a plurality of pages, each database table having a plurality of rows, and one or more indexes composed of a sequence of entries referencing the rows, and the processing unit having a buffer pool for caching data pages from the database table, said method comprising the steps of:

(a) ranking selected entries of an index;

(b) determining a distance parameter for each of said ranked index entries, wherein said distance parameter is derived from the relationship between said index and an index of lesser rank;

(c) determining the number of consecutive index entries that can be stored in the buffer pool; and

(d) estimating the number of page transfers based on the distance parameters and the number of consecutive index entries.

2. The method as claimed in claim 1, further including after said step (a) the steps of selecting pages for the database table according to a sampling criterion and storing respective page numbers for said selected pages, and wherein said step (b) comprises determining distance parameters for ranked index entries associated with said page numbers.

3. The method as claimed in claim 1, wherein said step (d) comprises estimating the number of page transfers based on the distance parameters exceeding the number of consecutive index entries determined in step (c).

4. The method as claimed in claim 1, wherein said distance parameters comprise counts of distance ranges for the index entries.

5. The method as claimed in claim 1, wherein said step (b) comprises determining distance parameters for one or more subsets of said index entries.

6. A computer program product for use on a computer for data retrieval using index scanning in a database management system, the database management system including a processing unit operably coupled to physical storage for storing data, the physical storage containing at least one database table stored in a plurality of pages, each database table having a plurality of rows, and one or more indexes composed of a sequence of entries referencing the rows, and the processing unit having a buffer pool for caching data pages from the database table, said computer program product comprising:

a recording medium;

means recorded on said medium for instructing said computer to perform the steps of,

(a) ranking selected entries of an index;

(b) determining a distance parameter for each of said ranked index entries, wherein said distance parameter is derived from the relationship between said index and an index of lesser rank;

(c) determining the number of consecutive index entries that can be stored in the buffer pool; and

(d) estimating the number of page transfers based on the distance parameters and the number of consecutive index entries.

7. The computer program product as claimed in claim 6, further including after said step (a) the steps of selecting pages for the database table according to a sampling criterion and storing respective page numbers for said selected pages, and wherein said step (b) comprises determining distance parameters for ranked index entries associated with said page numbers.

8. The computer program product as claimed in claim 6, wherein said step (d) comprises estimating the number of page transfers based on the distance parameters exceeding the number of consecutive index entries determined in step (c).

9. The computer program product as claimed in claim 6, wherein said distance parameters comprise counts of distance ranges for the index entries.

10. The computer program product as claimed in claim 6, wherein said step (b) comprises determining distance parameters for one or more subsets of said index entries.

11. A computer program product for use on a computer for data retrieval using index scanning in a database management system, the database management system including a processing unit operably coupled to physical storage for storing data, the physical storage containing at least one database table stored in a plurality of pages, each database table having a plurality of rows, and one or more indexes composed of a sequence of entries referencing the rows, and the processing unit having a buffer pool for caching data pages from the database table, said computer program product comprising:

a recording medium;

means recorded on said medium for instructing said computer to perform the steps of,

(a) ranking selected entries of an index;

(b) selecting pages for the database table according to a sampling criterion and storing respective page numbers for said selected pages;

(c) determining a distance parameter for each of said ranked index entries associated with said page numbers, wherein said distance parameter is derived from the relationship between said index and an index entry of lesser rank;

(d) determining the number of consecutive index entries that can be stored in the buffer pool;

(e) estimating the number of page transfers based on the distance parameters and the number of consecutive index entries.

12. The computer program product as claimed in claim 11, wherein said step (e) comprises estimating the number of page transfers based on the distance parameters exceeding the number of consecutive index entries determined in step (d).

13. A relational database management system for use with a computer system wherein queries are entered by a user for retrieving data from tables, the relational database management system including a processing unit operably coupled to physical storage for storing data, the physical storage containing at least one database table stored in a plurality of pages, each database table having a plurality of rows, and one or more indexes composed of a sequence of entries referencing the rows, and the processing unit a buffer pool for caching data pages from the database table, said relational database management system comprising:

(a) means for ranking selected entries of an index;

(b) means for determining a distance parameter for each of said ranked index entries, wherein said distance parameter is derived from the relationship between said index and an index entry of lesser rank;

(c) means for determining the number of consecutive index entries that can be stored in the buffer pool; and

(d) means for estimating the number of page transfers based on the distance parameters and the number of consecutive index entries.

14. The relational database management system as claimed in claim 13, wherein said means for ranking selected entries include means for selecting pages according to a predetermined criterion and means for storing page numbers for said selected pages.

15. The relational database management system as claimed in claim 13, wherein said means for estimating comprises means for estimating the number of page transfers based on the distance parameters exceeding the number of consecutive index entries.

16. The relational database management system as claimed in claim 13, wherein said means for determining distance parameters includes means for generating counts of distance ranges for the index entries.

17. The relational database management system as claimed in claim 13, wherein said means for determining distance parameters includes means for generating distance parameters for one or more subsets of said index entries.

18. Data storage media recorded with a computer program which, in combination with a general purpose computer configured for a database management system and equipped to read into memory and execute program data from the data storage media, the program data for:

(a) ranking selected entries of an index;

(b) determining a distance parameter for each of said ranked index entries, wherein said distance parameter is derived from the relationship between said index and an index of lesser rank;

(c) determining the number of consecutive index entries that can be stored in the buffer pool; and

(d) estimating the number of page transfers based on the distance parameters and the number of consecutive index entries.

19. The data storage media as claimed in claim 18, further including after said step (a) the steps of selecting pages for the database table according to a sampling criterion and storing respective page numbers for said selected pages, and wherein said step (b) comprises determining distance parameters for ranked index entries associated with said page numbers.

20. The data storage media as claimed in claim 18, wherein said step (d) comprises estimating the number of page transfers based on the distance parameters exceeding the number of consecutive index entries determined in step (c).

21. The data storage-media as claimed in claim 18, wherein said distance parameters comprise counts of distance ranges for the index entries.

22. The data storage media as claimed in claim 18, wherein said step (b) comprises determining distance parameters for one or more subsets of said index entries.