Index key range estimator

• US 4,774,657 A
• Filed: 06/06/1986
• Issued: 09/27/1988
• Est. Priority Date: 06/06/1986
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cole, Richard L., Anderson, Mark J., Ricard, Gary R., Lee, Wilson D., Youngren, Larry W., Davidson, William S., Passe, Peter B.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Nguyen, Viet Q.
• Application Number:
  US06/871,637
• Time in Patent Office: 844 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/300, 364/200, 364/300 MS File
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

A key estimator estimates the number of keys over a key range defined by key endpoints in an index to a data space. The number of keys in the key range required to be processed for a particular operation is estimated as a function of the number of pages referenced during a range level limited search. Two keys defining range endpoint keys are searched down to their lowest level in the tree. The level limit is then calculated as a function of desired granularity or accuracy of the estimate. The entire range of keys in the desired key range is then searched down to the level limit and the number of pages referenced during the search is counted and multiplied by an average key density per page to calculate the number of keys in the range.

Claims

1. A key estimator for estimating the number of keys over a key range defined by key endpoints in a tree-like index having a plurality of pages, comprising:

search means for searching the index for each of the key defining the key range and keeping track of the level of search required for each range endpoint key;

limiting means for providing a level limit as a function of the levels of search for each range endpoint key and a desired granularity of search;

range search means for searching the index between the range endpoint keys down to the level limit determined by the limiting means; and

key estimator means for counting the number of pages pointed to during such range search.

2. The key estimator of claim 1 wherein the limiting means provides the level limit as a function of the deeper level of the levels of search performed by the search mean for the range endpoint keys.

3. The key estimator of claim 1 wherein the tree-like index comprises a binary radix index having the capability of more than two page pointers per page of the index.

4. The key estimator of claim 3 wherein each page of the index contains up to 60 page pointers per page of the index.

5. The key estimator of claim 1 wherein the level limit is at least one level above the lowest level of the index.

6. The key estimator of claim 1 wherein the index comprises a header section which contains the number of keys and pages in the index and wherein the key estimator means multiplies the number of pages counted by the number of keys divided by the number of pages in the index to obtain an estimate of the number of keys in the key range.

7. The key estimator of claim 6 wherein the number of keys estimate is used to select an order of operation for certain functions.

8. The key estimator of claim 7 wherein the numbers of keys estimate is used to select the order of operations to be performed in a Join operation.

9. The key estimator of claim 8 wherein multiple collections of records are to be Joined, and an estimate of the number of keys contained in desired key ranges in indexes to each collection of records is performed.

10. The key estimator of claim 9 wherein the order in which collections of records are Joined is a function of the estimates of the number of keys in the desired key ranges in each index.

11. The key estimator of claim 10 wherein the collections of records are Joined in order of ascending numbers of keys, with the collection of records having the least number of keys having the Join operation performed first, and the collection of records having the greatest number of keys having the Join operation performed last.

12. The key estimator of claim 6 wherein the number of keys estimate is used to select an optimum index to employ in performing a query operation.

13. The key estimator of claim 1 and further comprising:

look ahead means for determining future pages required by the range search means to search an index; and

pre-bring means for pre-fetching the future pages such that they may be available for searching when required by the range search means such that minimal delay is encountered in searching the index.

14. The key estimator of claim 13 wherein the range search means continues searching of pages preceding the future pages while such future pages are being pre-fetched.

15. The key estimator of claim 13 wherein the look ahead means checks for further pages to pre-fetch prior to searching pre-fetched future pages.

16. A method of estimating the number of keys in a key range over an index wherein the index is stored in page form, said pages having page pointers to other pages in the index, the method, comprising the steps of:

(a) defining a left endpoint and a right endpoint in the key range;

(b) searching each endpoint of the key range to determine a maximum level for each endpoint;

(c) determining a lower level limit as a function of the maximum level for each endpoint;

(d) searching the key range between the ends of the key range and at, and above the lower level limit; and

(e) counting the number of page pointers, encountered during the range search, residing on pages not exceeding the lower level limit.

17. The method of claim 16 and further comprising the step of identifying a point of divergence of the searching of the endpoints of the key range such that the search follows different paths from the point of divergence.

18. The method of claim 17 wherein the key range search is divided into two searches, defined by the two paths from the point of divergence and the ends of the key range.

19. The method of claim 18 wherein the two searches each proceed from the respective ends of the key range toward the middle of the key range until they reach the point of divergence.

20. The method of claim 19 and further comprising the step of initiating a pair of parallel tasks to perform the two searches, one task assigned to each search.

21. A method of estimating the number of keys in a key range over an index wherein the index is stored in page form, said pages having page pointers to other pages in the index, the method, comprising the steps of:

(a) defining a left endpoint key and a right endpoint key of the key range;

(b) determinig a lower level limit;

(c) searching the key range between the endpoints of the key range, but not below the lower level limit;

(d) counting the number of page points, encountered during the search of the key range; and

(e) multiplying the number page points counter by an average number of keys per page value associated with said index to obtain an estimate of the number of keys in the index.