Database system with methods for performing cost-based estimates

Details Database system with methods for performing cost-based estimates Database system with methods for performing cost-based estimates

1997-10-23

2000-01-04

Fetting, Anton W.

Data processing: database and file management or data structures

Database design

Data structure types

707 1, 707 2, 704267, 704258, 704260, 39550002, 39550003, 39550023, 36447429, 36447431, 36446803, 36447402, G06F 1730

Patent

active

060120541

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.

REFERENCES:
patent: 4956774 (1990-09-01), Shibamiya et al.
patent: 5384893 (1995-01-01), Hutchins
patent: 5552995 (1996-09-01), Sebastian
patent: 5689696 (1997-11-01), Gibbons et al.
patent: 5732107 (1998-03-01), Phillips et al.
patent: 5778353 (1998-07-01), Schiefer et al.
patent: 5799311 (1998-08-01), Agrawal et al.
patent: 5822456 (1998-10-01), Reed et al.
patent: 5838579 (1998-11-01), Olson et al.
patent: 5903476 (1999-05-01), Mauskar et al.
Poosala, V., Ioannidis, Y., Haas, P., and Shekita, E., "Improved Histograms for Selectivity Estimation of Range Predicates," ACM SIGMOD '96, Montreal, Canada, 1996, pp. 294-305.
Piatetsky-Shapiro, G. and Connell, C., "Accurate Estimation of the Number of Tuples Satisfying A Condition," ACM, 1984, pp. 256-276.
Mannino, M., Chu, P., and Sager, T., "Statistical Profile Estimation in Database Systems," ACM Computing Surveys, vol. 20, No. 3, Sep. 1988, pp. 191-221.

Affiliated with

Also associated with

Rating

Database system with methods for performing cost-based estimates does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Database system with methods for performing cost-based estimates, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Database system with methods for performing cost-based estimates will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1080429