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

• US 6,012,054 A
• Filed: 10/23/1997
• Issued: 01/04/2000
• Est. Priority Date: 08/29/1997
• Status: Expired due to Term

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Seputis, Edwin Anthony
• Primary Examiner(s): Fetting, Anton W.
• Assistant Examiner(s): Corrielus, Jean M.
• Application Number:
  US08/956,631
• Time in Patent Office: 803 Days
• Field of Search: 707/3, 707/1, 707/2, 364/474.29, 364/474.31, 364/193, 364/474.02, 364/167.09, 364/468.03, 704/267, 704/258, 704/260, 395/500.03, 395/500.02, 395/500.23
• US Class Current: 702/180
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: Y10S 707/955 Object-oriented
• CPC Class Codes: Y10S 707/966 Distributed
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

Database system and methods are described for improving execution speed of database queries (e.g., for decision support) by provides methods employing spline histograms for improving the determination of selectivity estimates. The general approach improves histogram-based cost estimates as follows. The constant associated with a predicate (e.g., in r.a>5, the constant is "5") is used to do a binary search in an array of histogram boundary values, for determining a particular histogram cell. Once a cell has been found, the system employs interpolation to find out how much of the cell has been selected. Once this interpolation value is found, it is used with a cell weighting and a spline value or weighting to estimate the selectivity of the predicate value, which takes into account how data values are distributed within the cell. As a result of increased accuracy of estimates, the system can formulate better query plans and, thus, provides better performance.

Claims

1. 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.

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

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

4. 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.

5. 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.

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

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

8. 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.

9. 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.

10. 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.

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

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

13. 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.

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

15. 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.

16. 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.

17. 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.

18. 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.

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

20. 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.

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 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.

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,

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.

23. 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.

24. 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.

25. 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.

26. 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.

27. 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.

28. 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.

29. 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.

30. 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.

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

32. 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.