Patent ID: 8275761

Claim:
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).