Database system with methods for performing cost-based estimates using spline histograms

Claim 2

In a computer system providing a database storing database objects, a method for improving modeling of cost estimates associated with data access occurring during execution of a database query, the method comprising: receiving a request to create a histogram for modeling data distribution of a particular database object; in response to said request, creating a histogram having a plurality of histogram cells for modeling occurrence of values in the database object, each cell being associated with a particular range of values from the particular database object, and each cell having a weighting for indicating how often values in the particular range occur in the database object relative to occurrence of other values in the database object; and for each particular histogram cell, determining selectivity of the cell by: applying interpolation to the cell for determining a spline weighting indicating how values are actually distributed within the particular range of the cell, and based on the determination, assigning said spline weighting to the cell for indicating how values are distributed within the cell itself.

Claim 3

The method of claim 1, wherein each spline weighting assigned to a cell comprises a floating-point quantity.

Claim 4

The method of claim 1, wherein a histogram cell is assigned a spline weighting of zero if values within the cell are uniformly distributed.

Claim 5

The method of claim 1, further comprising: receiving a request for access to items of the particular database object having a given value; based on said given value, determining a particular histogram cell having a particular range which includes the given value; and from the determined particular histogram cell, estimating selectivity of the particular value based on the cell weighting and spline weighting for the cell.

Claim 6

The method of claim 4, further comprising: formulating a query plan for providing access to the particular database object, said query plan including an access strategy based on the estimated selectivity of the given value.

Claim 7

The method of claim 1, wherein said database object comprises a database table.

Claim 8

The method of claim 1, wherein said database object comprises a database index.

Claim 9

The method of claim 1, wherein distribution within a particular cell is modeled as a linear spline by assigning a single spline weighting to the cell.

Claim 10

The method of claim 1, wherein distribution within a particular cell is modeled as a quadratic spline by assigning two spline weightings to the cell.

Claim 11

The method of claim 1, wherein distribution within a particular cell is modeled as a polynomial of n degree by assigning n number of spline weightings to the cell.

Claim 12

The method of claim 1, wherein spline weightings are only assigned to cells determined to have nonuniform distribution.

Claim 13

The method of claim 1, wherein values within the histogram are of a single data type.

Claim 14

The method of claim 12, wherein said single data type is a data type selected from integer, float, character string, date/time, and money data types.

Claim 15

The method of claim 1, wherein each cell's weighting comprises a floating-point value indicating relative selectivity of the cell.

Claim 16

The method of claim 1, further comprising: receiving a query predicate which requires an estimate of selectivity of a given value; based on said given value, determining a particular histogram cell having a particular range which includes the given value; and from the determined particular histogram cell, estimating selectivity of the given value.

Claim 17

The method of claim 15, wherein said estimating step includes calculating selectivity by: calculating a uniform component of weighting; calculating a spline component of weighting; and calculating selectivity by adding the uniform component to the spline component.

Claim 18

The method of claim 16, wherein the uniform component for the particular cell is determined, for a negative spline weighting, by subtracting the spline weighting from the cell weighting and multiplying that value by an interpolate fraction, which indicates what fraction of the cell is selected by the given value.

Claim 19

The method of claim 17, wherein the spline component for the particular cell is determined, for a negative spline weighting, by calculating a new interpolate fraction by subtracting the previously-calculated interpolate fraction from the value of 1, and thereafter multiplying the spline weighting by the quantity of 1 minus the interpolate fraction squared.

Claim 20

The method of claim 1, wherein said request to create a histogram occurs during conditions when the database object is scanned.

Claim 21

In a computer system providing a database storing database objects, a method for improving modeling of cost estimates associated with data access occurring during execution of a database query, the method comprising: receiving a request to create a histogram for modeling data distribution of a particular database object; in response to said request, creating a histogram having a plurality of histogram cells for modeling occurrence of values in the database object, each cell being associated with a particular range of values from the particular database object, and each cell having a weighting for indicating how often values in the particular range occur in the database object relative to occurrence of other values in the database object; and for each particular histogram cell, determining how values are actually distributed within the particular range of the cell, and based on the determination, assigning a spline weighting to the cell for indicating how values are distributed within the cell itself, wherein each range is defined by a lower boundary and an upper boundary, and wherein a histogram cell is assigned a positive spline weighting if values within the cell are distributed more densely near the upper boundary of the particular range for the cell.

Claim 22

In a computer system providing a database storing database objects, a method for improving modeling of cost estimates associated with data access occurring during execution of a database query, the method comprising: receiving a request to create a histogram for modeling data distribution of a particular database object; in response to said request, creating a histogram having a plurality of histogram cells for modeling occurrence of values in the database object, each cell being associated with a particular range of values from the particular database object, and each cell having a weighting for indicating how often values in the particular range occur in the database object relative to occurrence of other values in the database object; and for each particular histogram cell, determining how values are actually distributed within the particular range of the cell, and based on the determination, assigning a spline weighting to the cell for indicating how values are distributed within the cell itself, wherein each range is defined by a lower boundary and an upper boundary, and wherein a histogram cell is assigned a positive spline weighting if values within the cell are distributed more densely near the upper boundary of the particular range for the cell.

Claim 23

In a computer system providing a database storing database objects, a method for improving modeling of cost estimates associated with data access occurring during execution of a database query, the method comprising: receiving a request to create a histogram for modeling data distribution of a particular database object; in response to said request, creating a histogram having a plurality of histogram cells for modeling occurrence of values in the database object, each cell being associated with a particular range of values from the particular database object, and each cell having a weighting for indicating how often values in the particular range occur in the database object relative to occurrence of other values in the database object; and for each particular histogram cell, determining how values are actually distributed within the particular range of the cell, and based on the determination, assigning a spline weighting to the cell for indicating how values are distributed within the cell itself, wherein each range is defined by a lower and upper boundary, and wherein a histogram cell is assigned a negative spline weighting if values within the cell are distributed more densely near the lower boundary of the particular range for the cell.

Claim 24

In a computer system providing a database storing database objects, a method for improving modeling of cost estimates associated with data access occurring during execution of a database query, the method comprising: receiving a request to create a histogram for modeling data distribution of a particular database object; in response to said request, creating a histogram having a plurality of histogram cells for modeling occurrence of values in the database object, each cell being associated with a particular range of values from the particular database object, and each cell having a weighting for indicating how often values in the particular range occur in the database object relative to occurrence of other values in the database object; and for each particular histogram cell, determining how values are actually distributed within the particular range of the cell, and based on the determination, assigning a spline weighting to the cell for indicating how values are distributed within the cell itself, wherein each range is defined by a lower and upper boundary, and wherein a histogram cell is assigned a negative spline weighting if values within the cell are distributed more densely near the lower boundary of the particular range for the cell.

Claim 25

In a computer system providing a database storing database objects, a method for improving modeling of cost estimates associated with data access occurring during execution of a database query, the method comprising: receiving a request to create a histogram for modeling data distribution of a particular database object; in response to said request, creating a histogram having a plurality of histogram cells for modeling occurrence of values in the database object, each cell being associated with a particular range of values from the particular database object, and each cell having a weighting for indicating how often values in the particular range occur in the database object relative to occurrence of other values in the database object; and for each particular histogram cell, determining how values are actually distributed within the particular range of the cell, and based on the determination, assigning a spline weighting to the cell for indicating how values are distributed within the cell itself, receiving a query predicate which requires an estimate of selectivity of a given value; based on said given value, determining a particular histogram cell having a particular range which includes the given value; and from the determined particular histogram cell, estimating selectivity of the given value, wherein said estimating step includes calculating selectivity by (i) calculating a uniform component of weighting; (ii) calculating a spline component of weighting; and (iii) calculating selectivity by adding the uniform component to the spline component; wherein the uniform component for the particular cell is determined, for a positive spline weighting, by subtracting the spline weighting from the cell weighting and then multiplying that quantity by an interpolate fraction, which indicates what fraction of the cell is selected by the given value.

Claim 26

In a computer system providing a database storing database objects, a method for improving modeling of cost estimates associated with data access occurring during execution of a database query, the method comprising: receiving a request to create a histogram for modeling data distribution of a particular database object; in response to said request, creating a histogram having a plurality of histogram cells for modeling occurrence of values in the database object, each cell being associated with a particular range of values from the particular database object, and each cell having a weighting for indicating how often values in the particular range occur in the database object relative to occurrence of other values in the database object; and for each particular histogram cell, determining how values are actually distributed within the particular range of the cell, and based on the determination, assigning a spline weighting to the cell for indicating how values are distributed within the cell itself, receiving a query predicate which requires an estimate of selectivity of a given value; based on said given value, determining a particular histogram cell having a particular range which includes the given value; and from the determined particular histogram cell, estimating selectivity of the given value, wherein said estimating step includes calculating selectivity by (i) calculating a uniform component of weighting; (ii) calculating a spline component of weighting; and (iii) calculating selectivity by adding the uniform component to the spline component; wherein the uniform component for the particular cell is determined, for a positive spline weighting, by subtracting the spline weighting from the cell weighting and then multiplying that quantity by an interpolate fraction, which indicates what fraction of the cell is selected by the given value.

Claim 27

The method of claim 22, wherein the spline component for the particular cell is determined, for a positive spline weighting, by multiplying the spline weighting by the interpolate fraction squared.

Claim 28

A database system providing spline-based cost estimates comprising: a database storing database objects; an optimizer which employs a histogram for modeling data distribution of a particular database object; means for creating a histogram having a plurality of histogram cells for modeling occurrence of values in the database object, each cell being associated with a particular range of values from the particular database object, and each cell having a weighting for indicating how often values in the particular range occur in the database object relative to occurrence of other values in the database object; means for determining how values are actually distributed within each particular cell by calculating a spline weighting for each particular cell using interpolation; and means for assigning said spline weighting to each particular cell for indicating selectivity of each particular cell based on how values are actually distributed within each particular cell.

Claim 29

A database system providing spline-based cost estimates comprising: a database storing database objects; an optimizer which employs a histogram for modeling data distribution of a particular database object; means for creating a histogram having a plurality of histogram cells for modeling occurrence of values in the database object, each cell being associated with a particular range of values from the particular database object, and each cell having a weighting for indicating how often values in the particular range occur in the database object relative to occurrence of other values in the database object; means for determining how values are actually distributed within each particular cell by calculating a spline weighting for each particular cell using interpolation; and means for assigning said spline weighting to each particular cell for indicating selectivity of each particular cell based on how values are actually distributed within each particular cell.

Claim 30

The system of claim 24, wherein each spline weighting assigned to a cell comprises a floating-point quantity representing a slope of a linear spline.

Claim 31

The method of claim 24, further comprising: query means for receiving a request for access to items of the particular database object having a given value; means for determining, based on said given value, a particular histogram cell having a particular range which includes the given value; and means for estimating selectivity of the particular value based on the cell weighting and spline weighting for the determined particular histogram cell.

Claim 32

The system of claim 26, further comprising: access means for providing access to the particular database object, said query plan including an access strategy based on the estimated selectivity of the given value.

Claim 33

The system of claim 27, wherein said access means provides random access to the particular database object if the selectivity of the given value is estimated to be poor.

Claim 34

The system of claim 28, wherein said database object is a database table and said random access includes index-based access to the database table.

Claim 35

The system of claim 27, wherein said access means provides sequential access to the particular database object if the selectivity of the given value is estimated to be good.

Claim 36

The system of claim 30, wherein said database object is a database table and said sequential access includes scanning the database table.

Claim 37

A database system providing spline-based cost estimates comprising: a database storing database objects; an optimizer which employs a histogram for modeling data distribution of a particular database object; means for creating a histogram having a plurality of histogram cells for modeling occurrence of values in the database object, each cell being associated with a particular range of values from the particular database object, and each cell having a weighting for indicating how often values in the particular range occur in the database object relative to occurrence of other values in the database object; means for determining how values are actually distributed within each particular cell, and means for assigning a spline weighting to each particular cell for indicating how values are actually distributed within each particular cell; wherein each range is defined by a lower boundary and an upper boundary, and wherein a histogram cell is assigned a positive spline weighting if values within the cell are distributed more densely near the upper boundary of the particular range for the cell and is assigned a negative spline weighting if values within the cell are distributed more densely near the lower boundary of the particular range for the cell.

Claim 38

A database system providing spline-based cost estimates comprising: a database storing database objects; an optimizer which employs a histogram for modeling data distribution of a particular database object; means for creating a histogram having a plurality of histogram cells for modeling occurrence of values in the database object, each cell being associated with a particular range of values from the particular database object, and each cell having a weighting for indicating how often values in the particular range occur in the database object relative to occurrence of other values in the database object; means for determining how values are actually distributed within each particular cell, and means for assigning a spline weighting to each particular cell for indicating how values are actually distributed within each particular cell; wherein each range is defined by a lower boundary and an upper boundary, and wherein a histogram cell is assigned a positive spline weighting if values within the cell are distributed more densely near the upper boundary of the particular range for the cell and is assigned a negative spline weighting if values within the cell are distributed more densely near the lower boundary of the particular range for the cell.