US6263345B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Histogram synthesis modeler for a database query optimizer
Assignee: Tandem Computers Inc
•
Filing: 1998-09-28
•
Granted: 2001-07-17
•
Expires: 2018-09-28
Abstract
Abstract The invention provides a mechanism for using statistics, in connection with various database query cost modeling techniques, to more accurately estimate the number of rows and UECs that will be produced by relational operators and predicates in database systems. The ability to accurately estimate the number of rows and UECs returned by a relational operator and/or a predicate is fundamental to computing the cost of a query execution plan. This, in turn, drives the optimizer's ability to select the query plan best suited for the desired performance goal. According to the present invention, histogram statistics are synthesized bottom up from the leaf nodes to the root node of a query tree. Given input statistics in the form of histograms for each operand of a relational operator or predicate, the present inventive method and apparatus merge the input statistics in a way that it simulates the effects of the run time operator on the actual data, so as to produce a predicted row count and UEC for each histogram interval representative of the data that actually will be produced by each such operator or predicate in the query tree. A database query optimizer may use these statistics to select and implement an optimal query plan.
Inventors
- 👤 Christopher M. Farrar
- 👤 Harry A. Leslie
- 👤 Pedro Celis
- 👤 Diana L. Shak
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 12:14
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2458; G06F16/2462; G06F16/2453; G06F16/24534; G06F16/24537; G06F16/24542; Y; Y10; Y10S; Y10S707/00; Y10S707/953; Y10S707/954; Y10S707/964; Y10S707/966; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99941; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
106 words
A process for producing predictive information about execution of an operation on data in a relational database, the process performed by a data processing system and comprising: receiving statistical information about rows of data in the relational database, the statistical information existing for each of a plurality of intervals of the data, wherein the statistical information includes a UEC (unique entry count) for certain of the plural intervals; and manipulating the statistical information, in accordance with the operation, on an interval by interval basis, to yield new statistical information also having a plurality of intervals and reflecting the predicted effect of the operation on the data.
Claim 2
Dependent Claim
106 words
A process for producing predictive information about execution of an operation on data in a relational database, the process performed by a data processing system and comprising: receiving statistical information about rows of data in the relational database, the statistical information existing for each of a plurality of intervals of the data, wherein the statistical information includes a UEC (unique entry count) for certain of the plural intervals; and manipulating the statistical information, in accordance with the operation, on an interval by interval basis, to yield new statistical information also having a plurality of intervals and reflecting the predicted effect of the operation on the data.
Claim 3
Dependent Claim
20 words
The process of claim 1 , wherein the statistical information includes a row count for certain of the plural intervals.
Claim 4
Dependent Claim
111 words
A process for producing predictive information about execution of an operation on data in a relational database, the process performed by a data processing system and comprising: receiving statistical information about rows of data in the relational database, the statistical information existing for each of a plurality of intervals of the data, wherein the statistical information includes at least one row count and at least one UEC for certain of the plural intervals; and manipulating the statistical information, in accordance with the operation, on an interval by interval basis, to yield new statistical information also having a plurality of intervals and reflecting the predicted effect of the operation on the data.
Claim 5
Dependent Claim
111 words
A process for producing predictive information about execution of an operation on data in a relational database, the process performed by a data processing system and comprising: receiving statistical information about rows of data in the relational database, the statistical information existing for each of a plurality of intervals of the data, wherein the statistical information includes at least one row count and at least one UEC for certain of the plural intervals; and manipulating the statistical information, in accordance with the operation, on an interval by interval basis, to yield new statistical information also having a plurality of intervals and reflecting the predicted effect of the operation on the data.
Claim 6
Dependent Claim
53 words
The process of claim 3 , wherein the operation includes the execution of a Join operator, and wherein the statistical information includes a first set of two histograms representing distributions of data in two database tables, each histogram having row counts and UECs reflecting the distribution of the data in the two databases.
Claim 7
Dependent Claim
42 words
The process of claim 4 wherein, if the original two histograms have different intervals, then the manipulating step further includes the step of normalizing the histograms to have the same number of intervals, each interval having the same lower and upper bounds.
Claim 8
Dependent Claim
33 words
The process of claim 4 , wherein the manipulating step further includes the step of producing a second set of two histograms resulting from a cross-product of the first set of two histograms.
Claim 9
Dependent Claim
37 words
The process of claim 6 , wherein the operator is an Inner Join and the manipulating step includes the application of the following formulas on each interval of the second set of two histograms: NumUec=MinOf(LeftUec, RightUec) NumRows=(LeftRowCount*RightRowCount)/MAXOF(LeftUec,RightUec)/XProwCount)
Claim 10
Dependent Claim
25 words
The process of claim 6 , wherein the operator is a Semi-Join and the following formulas are applied for each interval: NumUec=MINOF(LeftUec, RightUec) NumRows =LeftRowCount*(NumUec/LeftUec)
Claim 11
Dependent Claim
17 words
The process of claim 4 , wherein the new statistical information is passed to a parent operator.
Claim 12
Dependent Claim
26 words
The process of claim 3 , wherein the operator is a Scan and wherein all predicates on the base table are applied to the associated intervals.
Claim 13
Dependent Claim
140 words
A process for producing predictive information about execution of a query on data in a relational database, the process performed by a data processing system and comprising: creating a query data structure in memory for the query; selecting a current operation corresponding to a current node in the query data structure; receiving statistical information about rows of data in the relational database associated with at least one child of the current node, the statistical information existing for each of a plurality of intervals of the data, wherein the statistical information includes a UEC for certain of the plural intervals; and manipulating the statistical information, in accordance with the current operation, on an interval by interval basis, to yield statistical information for the current node, having a plurality of intervals and reflecting the predicted effect of the operation on the data.
Claim 14
Dependent Claim
140 words
A process for producing predictive information about execution of a query on data in a relational database, the process performed by a data processing system and comprising: creating a query data structure in memory for the query; selecting a current operation corresponding to a current node in the query data structure; receiving statistical information about rows of data in the relational database associated with at least one child of the current node, the statistical information existing for each of a plurality of intervals of the data, wherein the statistical information includes a UEC for certain of the plural intervals; and manipulating the statistical information, in accordance with the current operation, on an interval by interval basis, to yield statistical information for the current node, having a plurality of intervals and reflecting the predicted effect of the operation on the data.
Claim 15
Dependent Claim
15 words
The process of claim 11 , wherein the query data structure is a query tree.
Claim 16
Dependent Claim
143 words
A data processing apparatus for producing predictive information about execution of a query on data in a relational database, the apparatus comprising: means for creating a query data structure in memory for the query; means for selecting a current operation corresponding to a current node in the query data structure; means for receiving statistical information about rows of data in the relational database associated with at least one child of the current node, the statistical information existing for each of a plurality of intervals of the data, wherein the statistical information includes a UEC for certain of the plural intervals; and means for manipulating the statistical information, in accordance with the current operation, on an interval by interval basis, to yield statistical information for the current node, having a plurality of intervals and reflecting the predicted effect of the operation on the data.
Claim 17
Dependent Claim
143 words
A data processing apparatus for producing predictive information about execution of a query on data in a relational database, the apparatus comprising: means for creating a query data structure in memory for the query; means for selecting a current operation corresponding to a current node in the query data structure; means for receiving statistical information about rows of data in the relational database associated with at least one child of the current node, the statistical information existing for each of a plurality of intervals of the data, wherein the statistical information includes a UEC for certain of the plural intervals; and means for manipulating the statistical information, in accordance with the current operation, on an interval by interval basis, to yield statistical information for the current node, having a plurality of intervals and reflecting the predicted effect of the operation on the data.
Claim 18
Dependent Claim
160 words
A database apparatus for producing predictive information about execution of a query on data in the database, the apparatus having a memory and comprising: a portion configured to create a query data structure in the memory, wherein the query data structure includes parent and child nodes; a portion configured to select a current operation corresponding to a current node in the query data structure; a portion configured to receive statistical information about rows of data in the database associated with at least one child of the current node, the statistical information existing for each of a plurality of intervals of the data, wherein the statistical information includes a UEC for certain of the plural intervals; and a portion configured to manipulate the statistical information, in accordance with the current operation, on an interval by interval basis, to yield statistical information for the current node, having a plurality of intervals and reflecting the predicted effect of the operation on the data.
Claim 19
Dependent Claim
160 words
A database apparatus for producing predictive information about execution of a query on data in the database, the apparatus having a memory and comprising: a portion configured to create a query data structure in the memory, wherein the query data structure includes parent and child nodes; a portion configured to select a current operation corresponding to a current node in the query data structure; a portion configured to receive statistical information about rows of data in the database associated with at least one child of the current node, the statistical information existing for each of a plurality of intervals of the data, wherein the statistical information includes a UEC for certain of the plural intervals; and a portion configured to manipulate the statistical information, in accordance with the current operation, on an interval by interval basis, to yield statistical information for the current node, having a plurality of intervals and reflecting the predicted effect of the operation on the data.
References Cited (Backward Citations)
US5367675A
Cited
US5630120A
Cited
US5803914A
Cited
US5696686A
Cited
US5717911A
Cited
US5625815A
Cited
US5546570A
Cited
US5619692A
Cited
US5548755A
Cited
US5724570A
Cited
US5942986A
Cited
US5689696A
Cited
US5761654A
Cited
US5819255A
Cited
US5822747A
Cited
US6021405A
Cited
US5963957A
Cited
US5870752A
Cited
US6012054A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-07-16 | 2005-01-15 | 2005-07-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-07-16 | 2009-01-15 | 2009-07-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-07-16 | 2013-01-15 | 2013-07-17 | $7700.00 | Window Closed / Lapsed |