Computer program product for optimizing data retrieval using index scanning

Claim 2

A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps, the machine having a processing unit and physical storage in which data is stored, said storage being operably connected to said processing unit for transferring pages of data to said processing unit, said storage containing at least one data base table stored on a plurality of pages, each said data base table having a plurality of rows of data, and one or more indexes composed of a sequence of entries which reference said rows, said processing unit having a memory associated with it, a portion of said memory comprising a buffer pool for caching data pages from said table, said method steps comprising: scanning one or more selected indexes and determining the relationship between the number of data transfers required to traverse all or a portion of each selected index and a selected range of buffer pool sizes, and storing a description of said relationship; for a query submitted by a data base user, determining the number of page transfers required to scan a whole table of interest; for each index of said table relevant to said query, determining the number of page transfers required to scan each said relevant index in accordance with the size of buffer pool made available for said query, as determined from said relationship; scaling down the number of page transfers required in proportion to the selectivity of any starting and stopping conditions present in search criteria in said query; applying a suitable correction factor to said number of page transfers if any of the following conditions are found: very few rows of data remain to be transferred after applying said search criteria; said buffer pool to table size ratio is large; an index being used has a low degree of clustering; accounting for the effect on said number of page transfers by any remaining index search criteria; comparing the number of page transfers required for scanning of said relevant indexes and for scanning said entire table; and selecting a search procedure from among said index scanning or table scanning that results in the least number of page transfers.

Claim 3

The program storage device of claim 1, said method steps further including performing a search with said selected search procedure.

Claim 4

The program storage device of claim 1, wherein said relationship between the number of page transfers and the range of sizes of the buffer pool is modelled by line segment fitting, and wherein said methods steps further include: determining the number of page transfers required to scan said selected index by interpolating values of the relationship between the endpoints of the line segment which straddles the selected buffer pool size for the query.

Claim 5

The program storage device of claim 1, wherein said relationship between the number of page transfers and the range of sizes of the buffer pool is modelled by a polynomial equation.

Claim 6

A computer program product comprising a computer readable medium having computer program logic recorded thereon for controlling a processing unit in a data processing system having physical storage in which data is stored, said storage being operably connected to said processing unit for transferring pages of data to said processing unit, said storage containing at least one data base table stored on a plurality of pages, each said data base table having a plurality of rows of data, and a plurality of indexes composed of a sequence of entries which reference said rows, said processing unit having a memory associated with it, a portion of said memory comprising a buffer pool for caching data pages from said table, said computer program logic comprising: means for causing said processing unit to scan each said index and determine the relationship between the number of data transfers required to traverse each index and a selected range of buffer pool sizes; for a query submitted by a data base user, means for causing said processing unit to determine the number of page transfers required to scan each index relevant to said query in accordance with the size of buffer pool made available for said query, as determined by said relationship; means for causing said processing unit to scale down the number of page transfers required in proportion to the selectivity of any starting and stopping conditions present in search criteria in said query; means for causing said processing unit to account for the effect on said number of page transfers by any remaining search criteria including index sargable search criteria; means for causing said processing unit to compare the number of page transfers required for scanning of said relevant indexes; and means for causing said processing unit to select a search procedure from among said index scanning or table scanning that results in the least number of page transfers.

Claim 7

A computer program product comprising a computer readable medium having computer program logic recorded thereon for controlling a processing unit in a data processing system having physical storage in which data is stored, said storage being operably connected to said processing unit for transferring pages of data to said processing unit, said storage containing at least one data base table stored on a plurality of pages, each said data base table having a plurality of rows of data, and a plurality of indexes composed of a sequence of entries which reference said rows, said processing unit having a memory associated with it, a portion of said memory comprising a buffer pool for caching data pages from said table, said computer program logic comprising: means for causing said processing unit to scan each said index and determine the relationship between the number of data transfers required to traverse each index and a selected range of buffer pool sizes; for a query submitted by a data base user, means for causing said processing unit to determine the number of page transfers required to scan each index relevant to said query in accordance with the size of buffer pool made available for said query, as determined by said relationship; means for causing said processing unit to scale down the number of page transfers required in proportion to the selectivity of any starting and stopping conditions present in search criteria in said query; means for causing said processing unit to account for the effect on said number of page transfers by any remaining search criteria including index sargable search criteria; means for causing said processing unit to compare the number of page transfers required for scanning of said relevant indexes; and means for causing said processing unit to select a search procedure from among said index scanning or table scanning that results in the least number of page transfers.

Claim 8

A computer program product comprising a computer readable medium having computer program logic recorded thereon for controlling a processing unit in a data processing system having physical storage in which data is stored, said storage being operably connected to said processing unit for transferring pages of data to said processing unit, said storage containing at least one data base table stored on a plurality of pages, each said data base table having a plurality of rows of data, and one or more indexes composed of a sequence of entries which reference said rows, said processing unit having a memory associated with it, a portion of said memory comprising a buffer pool for caching data pages from said table, said computer program logic comprising: means for causing said processing unit to scan each said index and determine a relationship between the number of data transfers required to traverse each index and selected range of buffer pool sizes; for a query submitted by a data base user, means for causing the processing unit to determine the number of page transfers required to scan a whole table of interest; for each index of said table relevant to said query, means for causing the processing unit to determine the number of page transfers required to scan each said relevant index in accordance with the size of buffer pool made available for said query, as determined by said relationship; means for causing the processing unit to scale down the number of page transfers required in proportion to the selectivity of any starting and stopping conditions present in search criteria in said query; means for causing the processing unit to apply an heuristic correction factor to said number of page transfers if any of the following conditions are found: very few rows of data remain to be transferred after applying said search criteria; said buffer pool to table size ratio is large; an index being used has a low degree of clustering; means for causing the processing unit to account for the effect on said number of page transfers by any remaining search criteria including index sargable search criteria; means for causing the processing unit to compare the number of page transfers required for scanning of said relevant indexes and for scanning said entire table; and means for causing the processing unit to select a search procedure from among said index scanning or table scanning that results in the least number of page transfers.

Claim 9

A computer program product comprising a computer readable medium having computer program logic recorded thereon for controlling a processing unit in a data processing system having physical storage in which data is stored, said storage being operably connected to said processing unit for transferring pages of data to said processing unit, said storage containing at least one data base table stored on a plurality of pages, each said data base table having a plurality of rows of data, and one or more indexes composed of a sequence of entries which reference said rows, said processing unit having a memory associated with it, a portion of said memory comprising a buffer pool for caching data pages from said table, said computer program logic comprising: means for causing said processing unit to scan each said index and determine a relationship between the number of data transfers required to traverse each index and selected range of buffer pool sizes; for a query submitted by a data base user, means for causing the processing unit to determine the number of page transfers required to scan a whole table of interest; for each index of said table relevant to said query, means for causing the processing unit to determine the number of page transfers required to scan each said relevant index in accordance with the size of buffer pool made available for said query, as determined by said relationship; means for causing the processing unit to scale down the number of page transfers required in proportion to the selectivity of any starting and stopping conditions present in search criteria in said query; means for causing the processing unit to apply an heuristic correction factor to said number of page transfers if any of the following conditions are found: very few rows of data remain to be transferred after applying said search criteria; said buffer pool to table size ratio is large; an index being used has a low degree of clustering; means for causing the processing unit to account for the effect on said number of page transfers by any remaining search criteria including index sargable search criteria; means for causing the processing unit to compare the number of page transfers required for scanning of said relevant indexes and for scanning said entire table; and means for causing the processing unit to select a search procedure from among said index scanning or table scanning that results in the least number of page transfers.