EP0351388A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Access path optimization using degrees of clustering
Assignee: International Business Machines Corp
•
Filing: 1989-06-14
•
Granted: —
•
Expires: 2009-06-14
Abstract
Abstract This invention measures the degree of clustering of an index for a relational data base table, estimates the number of physical page accesses required to access the table using a partial index scan using the index, and selects the index providing the fastest access path to the table. The degree of clustering is measured as follows: DC = Number of clustered rows (NCR) / Total rows (NR) A multiplier greater than 1 can be applied to the degree of clustering to reflect the benefit of having consecutively accessed rows on adjacent or nearby data pages. The degree of clustering so calculated is used to estimate the number of random and sequential page accesses required for a partial index scan. These numbers of accesses are then multiplied by the unit time required for each, and added to the total CPU processing time required to arrive at the estimated total time for the scan. The total time is calculated for each index which could be used as an access path for the query or other operation being optimized, and the index with the shortest overall time is selected as the access path.
Inventors
- 👤 Josephine Miu-Kung Cheng
- 👤 Yun Wang
- 👤 Akira Shibamiya
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-23 17:08
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; G06F16/2228; G06F16/2246; G06F16/2272; G06F16/24; G06F16/245; G06F16/2453; G06F16/24534; G06F16/24542; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
97 words
A method for estimating the number of pages to be accessed when records of a data processing system are scanned in a selected sequence other than the sequence in which they were stored, comprising the steps of: (a) calculating a degree of clustering which is proportional to the number of records which when in the selected sequence are in a sequence which is the same as the sequence in which they are stored on the data pages; and (b) estimating the number of pages to be accessed based on the degree of clustering calculated in step (a).
Claim 2
Independent Claim
97 words
A method for estimating the number of pages to be accessed when records of a data processing system are scanned in a selected sequence other than the sequence in which they were stored, comprising the steps of: (a) calculating a degree of clustering which is proportional to the number of records which when in the selected sequence are in a sequence which is the same as the sequence in which they are stored on the data pages; and (b) estimating the number of pages to be accessed based on the degree of clustering calculated in step (a).
Claim 3
Dependent Claim
27 words
The method of claim 1, wherein the data processing system is a relational data base management system, and wherein the selected sequence is determined by an index.
Claim 4
Dependent Claim
63 words
The method of claim 2, wherein the step (a) of calculating degree of clustering comprises the steps of: (a1) performing an index scan; (a2) counting the number of rows stored on the same data page as their respective preceeding rows during the index scan; and (a3) dividing the number of rows from step (a2) by the total number of rows in the table.
Claim 5
Dependent Claim
32 words
The method of claim 1, wherein the degree of clustering is multiplied by a factor greater than 1, and wherein the degree of clustering is limited to a maximum value of 1.
Claim 6
Independent Claim
133 words
A method for selecting an indexed access path through a table of a relational data base management system, the table including rows stored on data pages, comprising the steps of: (a) calculating a degree of clustering for an index of the table, the degree of clustering being proportional to the number of rows which when in index order are in the same sequence as that in which they are stored on the data pages; (b) estimating a number of pages to be accessed, the estimate being based on the degree of clustering calculated in step (a); (c) estimating an access time for the index scan, the access time being based on the estimated page accesses of step (b); and (d) selecting an index access path based on the time estimated in step (c).
Claim 7
Independent Claim
133 words
A method for selecting an indexed access path through a table of a relational data base management system, the table including rows stored on data pages, comprising the steps of: (a) calculating a degree of clustering for an index of the table, the degree of clustering being proportional to the number of rows which when in index order are in the same sequence as that in which they are stored on the data pages; (b) estimating a number of pages to be accessed, the estimate being based on the degree of clustering calculated in step (a); (c) estimating an access time for the index scan, the access time being based on the estimated page accesses of step (b); and (d) selecting an index access path based on the time estimated in step (c).
Claim 8
Dependent Claim
63 words
The method of claim 5, wherein the step (a) of calculating degree of clustering comprises the steps of: (a1) performing an index scan; (a2) counting the number of rows stored on the same data page as their respective preceeding rows during the index scan; and (a3) dividing the number of rows from step (a2) by the total number of rows in the table.
Claim 9
Dependent Claim
28 words
The method of claim 5, wherein the access path is selected from two or more indexes, and wherein steps (a) through (c) are repeated for each such index.
Claim 10
Dependent Claim
23 words
The method of claim 5, wherein the number of page accesses calculated in step (b) is proportional to the selectivity of the index.
Claim 11
Dependent Claim
22 words
The method of claim 5, wherein the number of page accesses calculated in step (b) includes the number of index pages accessed.
Claim 12
Dependent Claim
21 words
The method of claim 9, wherein the number of pages accessed is based on the number of levels of the index.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.