Patent US5864841A successfully refreshed from Google Patents.
US5864841A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for query optimization using quantile values of a large unordered data set
Assignee: International Business Machines Corp
•
Filing: 1997-08-28
•
Granted: 1999-01-26
•
Expires: 2017-08-28
Abstract
Abstract A database management system determines, in a single pass over an unordered database, the quantile information. The system sequentially compares each tuple in the data set to a test value, and then selectively inserts the tuple in a test set having a cardinality less than the cardinality of the data set based upon the comparison. The system next uses the quantile information to estimate the number of tuples in the database which satisfy a user-defined predicate to generate an efficient query plan.
Inventors
- 👤 Rakesh Agrawal
- 👤 Arun Narasimha Swami
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 19:20
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2458; G06F16/2462; G06F16/2453; G06F16/24534; G06F16/24542; G06F16/24545; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
159 words
A data storage system, comprising: a computer; one or more input devices electrically connected to the computer for generating a user request for data satisfying a predetermined condition; a database accessible by the computer for holding a set of data records; and a database management system executed by the computer, the database management system including a compiler, the compiler including: a query optimizer for generating a query plan in response to quantiles of the set of data records; comparator means in the query optimizer for sequentially comparing records in the data set to a test value of the condition in a single pass over the data set; means for selectively inserting a record in a test set having a cardinality less than the cardinality of the data set based upon the comparison and the condition; and means for accessing the test set to generate a quantile value representative of a number of records in the database satisfying the condition.
Claim 2
Dependent Claim
159 words
A data storage system, comprising: a computer; one or more input devices electrically connected to the computer for generating a user request for data satisfying a predetermined condition; a database accessible by the computer for holding a set of data records; and a database management system executed by the computer, the database management system including a compiler, the compiler including: a query optimizer for generating a query plan in response to quantiles of the set of data records; comparator means in the query optimizer for sequentially comparing records in the data set to a test value of the condition in a single pass over the data set; means for selectively inserting a record in a test set having a cardinality less than the cardinality of the data set based upon the comparison and the condition; and means for accessing the test set to generate a quantile value representative of a number of records in the database satisfying the condition.
Claim 3
Dependent Claim
21 words
The system of claim 1, wherein the test value is an element of one of the records in the test set.
Claim 4
Dependent Claim
25 words
The system of claim 2, further comprising means for selectively discarding a record from the test set in response to the comparison and the condition.
Claim 5
Dependent Claim
34 words
The system of claim 3, the database management system further including means for determining upper and lower bounds for a record satisfying the condition, wherein the record is between the upper and lower bounds.
Claim 6
Independent Claim
130 words
A method executed by a query optimizer for estimating a number of records containing a data field satisfying a predetermined query condition in a data set defining a data set cardinality in a single pass over the records of the set, comprising the steps of: generating a test set having a cardinality less than the data set cardinality; sequentially comparing each record in the data set to a test value and generating a first value in response thereto; generating a second value representative of the condition; selectively inserting the record in the test set in response to the first and second values; determining a quantile value representing a number of records in the data set which satisfy the condition; and generating a query plan in response to the quantile value.
Claim 7
Independent Claim
130 words
A method executed by a query optimizer for estimating a number of records containing a data field satisfying a predetermined query condition in a data set defining a data set cardinality in a single pass over the records of the set, comprising the steps of: generating a test set having a cardinality less than the data set cardinality; sequentially comparing each record in the data set to a test value and generating a first value in response thereto; generating a second value representative of the condition; selectively inserting the record in the test set in response to the first and second values; determining a quantile value representing a number of records in the data set which satisfy the condition; and generating a query plan in response to the quantile value.
Claim 8
Dependent Claim
21 words
The method of claim 5, wherein the test value is an element of one of the records in the test set.
Claim 9
Dependent Claim
26 words
The method of claim 6, further comprising the step of selectively discarding the element from the test set in response to the first and second values.
Claim 10
Dependent Claim
20 words
The method of claim 7, further comprising the step of returning upper and lower bounds between which the record lies.
Claim 11
Dependent Claim
102 words
An optimizer including a quantile engine for estimating the number of tuples satisfying a condition in a set of tuples having a cardinality in a single pass over the tuples of the set, the quantile engine characterized by: comparator means for sequentially comparing tuples in the set of tuples to a test value; means for selectively inserting a tuple in a test set having a cardinality less than the cardinality of the set of tuples based upon the comparison and the condition; and means for generating a quantile value representative of the number of tuples of the test set satisfying the condition.
Claim 12
Dependent Claim
102 words
An optimizer including a quantile engine for estimating the number of tuples satisfying a condition in a set of tuples having a cardinality in a single pass over the tuples of the set, the quantile engine characterized by: comparator means for sequentially comparing tuples in the set of tuples to a test value; means for selectively inserting a tuple in a test set having a cardinality less than the cardinality of the set of tuples based upon the comparison and the condition; and means for generating a quantile value representative of the number of tuples of the test set satisfying the condition.
Claim 13
Dependent Claim
21 words
The optimizer of claim 9, wherein the test value is an element of one of the tuples in the test set.
Claim 14
Dependent Claim
23 words
The optimizer of claim 10, further comprising means for selectively discarding the tuple from the test set in response to the quantile value.
Claim 15
Dependent Claim
30 words
The optimizer of claim 11, further comprising means for determining upper and lower bounds for the tuple satisfying the condition, wherein the tuple lies between the upper and lower bounds.
References Cited (Backward Citations)
US4379948A
Cited
US4530076A
Cited
US4829427A
Cited
US4817158A
Cited
US5091967A
Cited
US5018088A
Cited
US5105469A
Cited
US5379419A
Cited
US5345585A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-01-25 | 2002-07-27 | 2003-01-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-01-25 | 2006-07-27 | 2007-01-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-01-25 | 2010-07-27 | 2011-01-26 | $7700.00 | Window Closed / Lapsed |