Method and apparatus for optimizing data retrieval using index scanning

Claim 1

A method for operating a data processing system 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, the method comprising the steps performed by said processing unit of: (a) 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; (b) storing a description of said relationship; and (c) selecting an index to be used for a database query based on said description.

Claim 2

A method for operating a data processing system 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, the method comprising the steps performed by said processing unit of: (a) 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; (b) storing a description of said relationship; and (c) selecting an index to be used for a database query based on said description.

Claim 3

A method for operating a data processing system 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, the method comprising the steps performed by said processing unit of: (a) 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; (b) for a query submitted by a data base user determining the number of page transfers required to scan a whole table of interest, and; (c) for each index of said table relevant to said query: (1) 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; (2) scaling down the number of page transfers required in proportion to a selectivity factor of any starting and stopping conditions present in search criteria in said query; (3) applying a suitable correction factor to said number of page transfers if any of the following conditions are found: (i) very few rows of data remain to be transferred after applying said search criteria; (ii) said buffer pool to table size ratio is large, or; (iii) an index being used has a low degree of clustering (4) accounting for the effect on said number of page transfers by any remaining index sargable search criteria; (5) comparing the number of page transfers required for scanning of said relevant indexes and for scanning said entire table; and (6) selecting a search procedure from among said index scanning or table scanning that results in the least number of page transfers.

Claim 4

A method for operating a data processing system 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, the method comprising the steps performed by said processing unit of: (a) 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; (b) for a query submitted by a data base user determining the number of page transfers required to scan a whole table of interest, and; (c) for each index of said table relevant to said query: (1) 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; (2) scaling down the number of page transfers required in proportion to a selectivity factor of any starting and stopping conditions present in search criteria in said query; (3) applying a suitable correction factor to said number of page transfers if any of the following conditions are found: (i) very few rows of data remain to be transferred after applying said search criteria; (ii) said buffer pool to table size ratio is large, or; (iii) an index being used has a low degree of clustering (4) accounting for the effect on said number of page transfers by any remaining index sargable search criteria; (5) comparing the number of page transfers required for scanning of said relevant indexes and for scanning said entire table; and (6) selecting a search procedure from among said index scanning or table scanning that results in the least number of page transfers.

Claim 8

A method for operating a data processing system 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, (a) for a query submitted by a data base user determining the number of page transfers required to scan a whole table of interest, and; (b) for each index of said table relevant to said query: (1) 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; (2) scaling down the number of page transfers required in proportion to a selectivity factor of any starting and stopping conditions present in search criteria in said query; (3) applying a suitable correction factor to said number of page transfers if any of the following conditions are found: (i) very few rows of data remain to be transferred after applying said search criteria; (ii) said buffer pool to table size ratio is large, or; (iii) an index being used has a low degree of clustering (4) accounting for the effect on said number of page transfers by any remaining search criteria including index sargable search criteria; (5) comparing the number of page transfers required for scanning of said relevant indexes and for scanning said entire table; and (6) selecting a search procedure from among said index scanning or table scanning that results in the least number of page transfers.

Claim 9

A method for operating a data processing system 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, (a) for a query submitted by a data base user determining the number of page transfers required to scan a whole table of interest, and; (b) for each index of said table relevant to said query: (1) 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; (2) scaling down the number of page transfers required in proportion to a selectivity factor of any starting and stopping conditions present in search criteria in said query; (3) applying a suitable correction factor to said number of page transfers if any of the following conditions are found: (i) very few rows of data remain to be transferred after applying said search criteria; (ii) said buffer pool to table size ratio is large, or; (iii) an index being used has a low degree of clustering (4) accounting for the effect on said number of page transfers by any remaining search criteria including index sargable search criteria; (5) comparing the number of page transfers required for scanning of said relevant indexes and for scanning said entire table; and (6) selecting a search procedure from among said index scanning or table scanning that results in the least number of page transfers.

Claim 10

A method for operating a data processing system 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, the method comprising the steps performed by said processing unit of: (a) for a query submitted by a data base user determining the number of page transfers required to scan a whole table of interest, and; (b) for each index of said table relevant to said query: (1) 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; (2) comparing the number of page transfers required for scanning of said relevant indexes and for scanning said entire table; and (3) selecting a search procedure from among said index scanning or table scanning that results in the least number of page transfers.

Claim 11

A method for operating a data processing system 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, the method comprising the steps performed by said processing unit of: (a) for a query submitted by a data base user determining the number of page transfers required to scan a whole table of interest, and; (b) for each index of said table relevant to said query: (1) 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; (2) comparing the number of page transfers required for scanning of said relevant indexes and for scanning said entire table; and (3) selecting a search procedure from among said index scanning or table scanning that results in the least number of page transfers.

Claim 12

A method for operating a data processing system 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 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, the method comprising the steps performed by said processing unit of: (a) 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; (b) for a query submitted to said data base determining the number of page transfers required to scan a whole table of interest, and; (c) for each index of said table relevant to said query: (1) 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; (2) comparing the number of page transfers required for scanning of said relevant indexes and for scanning said entire table; and (3) selecting a search procedure from among said index scanning or table scanning that results in the least number of page transfers.

Claim 13

A method for operating a data processing system 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 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, the method comprising the steps performed by said processing unit of: (a) 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; (b) for a query submitted to said data base determining the number of page transfers required to scan a whole table of interest, and; (c) for each index of said table relevant to said query: (1) 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; (2) comparing the number of page transfers required for scanning of said relevant indexes and for scanning said entire table; and (3) selecting a search procedure from among said index scanning or table scanning that results in the least number of page transfers.

Claim 17

A method for operating a data processing system 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 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, the method comprising the steps performed by said processing unit of: (a) 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; and (b) for a query submitted to said data base, for each index of said table relevant to said query: (1) 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; (2) comparing the number of page transfers required for scanning of said relevant indexes; and (3) selecting a search procedure from among said index scanning that results in the least number of page transfers.

Claim 18

A method for operating a data processing system 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 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, the method comprising the steps performed by said processing unit of: (a) 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; and (b) for a query submitted to said data base, for each index of said table relevant to said query: (1) 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; (2) comparing the number of page transfers required for scanning of said relevant indexes; and (3) selecting a search procedure from among said index scanning that results in the least number of page transfers.