Determining a density of a key value referenced in a database query over a range of rows
AssigneeInternational Business Machines Corporation
InventorsPaul R. Day, Randy L. Egan, Roger A. Mittelstadt
Life of this patent
Estimating the term…
Abstract
A method, apparatus and program product that determine a density of a key value referenced in a database query over at least one range of rows, and utilize the determined density to optimize the database query. By doing so, the density of various key values may be determined and compared, and a bit map may be generated over the range of rows of the key value that is denser, resulting in a reduction of resources to build and use the bit map. Moreover, from the bit map over the range of rows to be selected after using the determined density, dense regions may be identified that can be used to optimize block I/O's according to the number of rows to be selected based on the query.
Claims20
A method of processing a database query, the method comprising:
- determining a density of a key value referenced in the database query over at least one range of rows in a database table referenced by the database query;
- and
- utilizing the determined density to optimize the database query,
- wherein determining the density of the key value includes determining a first row of the range of rows in the database table that contains the key value, wherein the first row of the range of rows is representative of a location of the first row in the database table, determining a last row of the range of rows in the database table that contains the key value, wherein the last row of the range of rows is representative of a location of the last row in the database table, and determining a count that is representative of a number of times that the key value appears in the range of rows, wherein determining the density further comprises utilizing at least a portion of a first formula, wherein the first formula comprises:
- (the last row of the range of rows−the first row of the range of rows+one)/(the count).
An apparatus comprising:
- a processor;
- a memory;
- and
- program code resident in the memory and configured to be executed by the processor to process a database query by determining a density of a key value referenced in the database query over at least one range of rows in a database table referenced by the database query, and utilizing the determined density to optimize the database query, wherein the program code is further configured to determine the density by determining a first row of the range of rows in the database table that contains the key value, wherein the first row of the range of rows is representative of a location of the first row in the database table, determining a last row of the range of rows in the database table that contains the key value, wherein the last row of the range of rows is representative of a location of the last row in the database table, and determining a count that is representative of a number of times that the key value appears in the range of rows, and wherein the program code is further configured to determine the density by utilizing at least a portion of a first formula, wherein the first formula comprises:
- (the last row of the range of rows−the first row of the range of rows+one)/(the count).
A program product, comprising:
- program code resident in a memory and configured to be executed by a processor to process a database query by determining a density of a key value referenced in the database query over at least one range of rows in a database table referenced by the database query, and utilizing the determined density to optimize the database query, wherein the program code is further configured to determine the density by determining a first row of the range of rows in the database table that contains the key value, wherein the first row of the range of rows is representative of a location of the first row in the database table, determining a last row of the range of rows in the database table that contains the key value, wherein the last row of the range of rows is representative of a location of the last row in the database table, and determining a count that is representative of a number of times that the key value appears in the range of rows, and wherein the program code is further configured to determine the density by utilizing at least a portion of a first formula, wherein the first formula comprises:
- (the last row of the range of rows−the first row of the range of rows+one)/(the count);
- and
- a non-transitory computer readable medium bearing the program code.
Dependencies are inferred from the claim text.