EP0252234A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Index key range estimator
Assignee: International Business Machines Corp
•
Filing: 1987-04-28
•
Granted: —
•
Expires: 2007-04-28
Abstract
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.
Inventors
- 👤 Mark John Anderson
- 👤 Richard Lee Cole
- 👤 William Simpson Davidson
- 👤 Larry William Youngren
- 👤 Wilson Douglas Lee
- 👤 Peter Bernard Passe
- 👤 Gary Ross Ricard
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-26 03:21
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/901; G06F16/9027; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
120 words
The 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 keys defining the key range and keeping track of the level of search required for each range limiting key; limiting means for providing a level limit as a function of the levels of search for each range limiting key and a desired granularity of search; range search means for searching the index between the range limiting 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.
Claim 2
Dependent Claim
120 words
The 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 keys defining the key range and keeping track of the level of search required for each range limiting key; limiting means for providing a level limit as a function of the levels of search for each range limiting key and a desired granularity of search; range search means for searching the index between the range limiting 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.
Claim 3
Dependent Claim
30 words
The key estimator of claim 1 wherein the limiting means provides the level limit as a function of the deeper of the levels of search for the range limiting keys.
Claim 4
Dependent Claim
29 words
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.
Claim 5
Dependent Claim
23 words
The key estimator of claim 3 wherein each page of the index contains up to 60 page pointers per page of the index.
Claim 6
Dependent Claim
22 words
The key estimator of claim 1 wherein the level limit is at least one level above the lowest level of the index.
Claim 7
Dependent Claim
36 words
The key estimator of claim 1 wherein the key estimator multiplies the number of pages counted by an average key density per page to obtain an estimate of the number of keys in the key range.
Claim 8
Dependent Claim
21 words
The key estimator of claim 6 wherein the key estimate is used to select an order of operation for certain functions.
Claim 9
Dependent Claim
25 words
The key estimator of claim 7 wherein the key estimate is used to select the order of operations to be performed in a Join operation.
Claim 10
Dependent Claim
37 words
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.
Claim 11
Dependent Claim
34 words
The key estimator of claim 9 wherein the order in which data spaces are Joined is a function of the estimates of the number of keys in the desired key ranges in each index.
Claim 12
Dependent Claim
51 words
The key estimator of claim 10 wherein the data spaces are Joined in order of ascending number of keys, with the data space having the least number of keys having the Join operation performed first, and the data space having the greatest number of keys having the Join operation performed last.
Claim 13
Dependent Claim
24 words
The key estimator of claim 6 wherein the key estimate is used to select an optimum index to employ in performing a query operation.
Claim 14
Dependent Claim
59 words
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.
Claim 15
Dependent Claim
26 words
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.
Claim 16
Dependent Claim
23 words
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.
Claim 17
Independent Claim
135 words
A method of estimating the number of keys in a key range over an index stored in a storage system using pages which are paged in and out of a main memory, said pages having page pointers to other pages in the index, the method, comprising the steps of: a) searching each end of the key range to determine a maximum level for each end of the key range; b) determining a lower level limit as a function of the key range levels and a desired accuracy of the number of keys estimate; c) searching the key range between the ends of the key range and at and above the lower level limit; and d) counting the number of page pointers, encountered during the range search, residing on pages not exceeding the lower level limit.
Claim 18
Independent Claim
135 words
A method of estimating the number of keys in a key range over an index stored in a storage system using pages which are paged in and out of a main memory, said pages having page pointers to other pages in the index, the method, comprising the steps of: a) searching each end of the key range to determine a maximum level for each end of the key range; b) determining a lower level limit as a function of the key range levels and a desired accuracy of the number of keys estimate; c) searching the key range between the ends of the key range and at and above the lower level limit; and d) counting the number of page pointers, encountered during the range search, residing on pages not exceeding the lower level limit.
Claim 19
Dependent Claim
38 words
The method of claim 16 and further comprising the steps of identifying a point of divergence of the search of the ends of the key range such that the search follows different paths from the point of divergence.
Claim 20
Dependent Claim
32 words
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.
Claim 21
Dependent Claim
33 words
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.
Claim 22
Dependent Claim
28 words
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.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.