US4956774A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data base optimizer using most frequency values statistics
Assignee: International Business Machines Corp
•
Filing: 1988-09-02
•
Granted: 1990-09-11
•
Expires: 2008-09-02
Abstract
Abstract A method for more accurately estimating the time required to process a data base query using a selected index. A selected number of the most frequently occurring index key values (38) are collected during an index sequential scan. These most frequency occurring values are stored as percentage frequencies of occurrence in the data base system's catalog (42). Estimated access and processing times (NPAR, NPAS, NCPU) for a given query are calculated based on the stored frequencies where possible. Where the query's search criteria specify values other than the stored most frequently occurring values, those values are assumed to be uniformly distributed.
Inventors
- 👤 Akira Shibamiya
- 👤 Melvin R. Zimowski
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 17:42
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/901; G06F16/9017; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24534; G06F16/24549; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
128 words
In a method for accessing data of a relational data base management system having at least one index, the improvement characterized by the steps performed by a computer of: (a) selecting a number of most frequently occurring values of at least part of a key of the index, the number being greater than zero and less than a total number of such values; (b) collecting frequency of occurrence statistics for the selected most frequently occurring values of the index; (c) estimating a time required for using the index as the access path, based at least in part on the collected frequency of occurrence statistics; (d) selecting an access path based at least in part on the estimated time; and (e) accessing the data using the selected access path.
Claim 2
Dependent Claim
128 words
In a method for accessing data of a relational data base management system having at least one index, the improvement characterized by the steps performed by a computer of: (a) selecting a number of most frequently occurring values of at least part of a key of the index, the number being greater than zero and less than a total number of such values; (b) collecting frequency of occurrence statistics for the selected most frequently occurring values of the index; (c) estimating a time required for using the index as the access path, based at least in part on the collected frequency of occurrence statistics; (d) selecting an access path based at least in part on the estimated time; and (e) accessing the data using the selected access path.
Claim 3
Dependent Claim
26 words
The method of claim 1, wherein frequencies of occurrence of the values other than the collected most frequently occurring values are assumed to be uniformly distributed.
Claim 4
Dependent Claim
21 words
The method of claim 1, wherein the statistics comprise the most frequently occurring values, and their respective percentage frequencies of occurrence.
Claim 5
Dependent Claim
36 words
The method of claim 1, wherein the number of most frequently occurring values is selected so that a sum of frequencies of occurrence of the selected most frequently occurring values is greater than a selected threshold.
Claim 6
Dependent Claim
32 words
The method of claim 1, wherein the number of most frequently occurring values is selected to include all values occurring with more than a selected threshold frequency as most frequently occurring values.
Claim 7
Dependent Claim
17 words
The method of claim 1, wherein the collected statistics are stored within the data base management system.
Claim 8
Dependent Claim
15 words
The method of claim 6, wherein the collected statistics are stored in a system catalog.
Claim 9
Dependent Claim
30 words
The method of claim 1, wherein times required for random and sequential page accesses and for processing time are estimated separately, based at least in part on the index's statistics.
Claim 10
Independent Claim
138 words
A method for accessing data of a relational data base management system having at least one index, comprising the steps performed by a computer of: (a) selecting a number of most frequently occurring values of at least part of a key of the index, the number being greater than zero and less than a total number of values of said at least part of the key; (b) collecting frequency of occurrence statistics for the selected most frequently occurring values of the index; (c) storing the statistics in the system; (d) estimating a time required for using the index as the access path, based at least in part on the stored frequency of occurrence statistics; (e) selecting an access path based at least in part on the estimated time; and (f) accessing the data using the selected access path.
Claim 11
Independent Claim
138 words
A method for accessing data of a relational data base management system having at least one index, comprising the steps performed by a computer of: (a) selecting a number of most frequently occurring values of at least part of a key of the index, the number being greater than zero and less than a total number of values of said at least part of the key; (b) collecting frequency of occurrence statistics for the selected most frequently occurring values of the index; (c) storing the statistics in the system; (d) estimating a time required for using the index as the access path, based at least in part on the stored frequency of occurrence statistics; (e) selecting an access path based at least in part on the estimated time; and (f) accessing the data using the selected access path.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-09-10 | 1994-03-12 | 1994-09-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-09-10 | 1998-03-12 | 1998-09-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-09-10 | 2002-03-12 | 2002-09-11 | $7700.00 | Window Closed / Lapsed |