×

Access path optimization using degrees of clustering

  • US 5,043,872 A
  • Filed: 07/15/1988
  • Issued: 08/27/1991
  • Est. Priority Date: 07/15/1988
  • Status: Expired due to Fees
First Claim
Patent Images

1. A method for operating a data processing system having a processing unit and a physical storage device in which a plurality of pages of data are stored in a physical sequence wherein each page other than a last page has a sequential page which follows it, the physical storage device being operably connected to the processing unit for transferring pages of data to the processing unit, the physical storage device containing a data base table which is stored on a plurality of pages, the data base table having a plurality of rows of data and a plurality of indexes composed of a sequence of entries which reference the rows, the method comprising the steps performed by the processing unit of:

  • (a) obtaining a data base operation command specifying search criteria;

    (b) selecting a plurality of indexes which correspond to the search criteria;

    (c) determining a degree of clustering for each selected index which is calculated by dividing the number of clustered rows referenced in the selected index by the number of rows in the data base table, clustered rows being those rows which are stored in the physical storage device in the same page or a sequential page of the physical storage device as the row referenced by the preceding entry in the index, divided by the total number of rows in the table, wherein the degree of clustering is directly proportional to the number of rows referenced by the selected index which are stored on a page of the physical storage device which is the same page on which the row referenced by the preceding index entry is stored;

    (d) determining, using the degree of clustering for each selected index and the search criteria, a total expected time required for transferring the pages from the physical storage device if the selected index is used to specify the order in which to transfer the pages from the physical storage device; and

    (e) transferring the pages containing the rows of the data base table from the physical storage device to the processing unit in the sequence specified in the selected index having the lowest total expected time from step (d), thereby obtaining the data matching the search criteria in an efficient manner.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×