Access path optimization using degrees of clustering
US5043872A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Jul 15, 1988 |
| Grant date | Aug 27, 1991 |
| Priority date | — |
| Expiry date | Jul 15, 2008 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99932
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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: EQU 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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.