US5664171A
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: 1994-04-14
•
Granted: 1997-09-02
•
Expires: 2014-04-14
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-10-30 04:21
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
182 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 executable 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 the data records in the set of data records to a test value of the condition in a single pass over the set of data records; means for selectively inserting a data record in a test set having a cardinality less than the cardinality of the set of data records based upon the comparison and the condition; and means for accessing the test set to generate a quantile value in response to a data record in the test set, the quantile value representative of a number of data records in the database satisfying the condition.
Claim 2
Dependent Claim
182 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 executable 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 the data records in the set of data records to a test value of the condition in a single pass over the set of data records; means for selectively inserting a data record in a test set having a cardinality less than the cardinality of the set of data records based upon the comparison and the condition; and means for accessing the test set to generate a quantile value in response to a data record in the test set, the quantile value representative of a number of data records in the database satisfying the condition.
Claim 3
Dependent Claim
22 words
The system of claim 1, wherein the test value is an element of one of the data records in the test set.
Claim 4
Dependent Claim
26 words
The system of claim 2, further comprising means for selectively discarding a data record from the test set in response to the comparison and the condition.
Claim 5
Dependent Claim
36 words
The system of claim 3, the database management system further including means for determining upper and lower bounds for a data record satisfying the condition, wherein the data record is between the upper and lower bounds.
Claim 6
Independent Claim
142 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 having 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 in said single pass and from a record in the test set 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
142 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 having 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 in said single pass and from a record in the test set 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
112 words
An optimizer including a quantile engine for estimating a 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 all tuples in the set of tuples to a test value; means for selectively inserting a tuple in the set of tuples 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 in said single pass a quantile value representative of the number of tuples of the test set satisfying the condition.
Claim 12
Dependent Claim
112 words
An optimizer including a quantile engine for estimating a 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 all tuples in the set of tuples to a test value; means for selectively inserting a tuple in the set of tuples 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 in said single pass 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) | 2000-09-01 | 2001-03-03 | 2001-09-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-09-01 | 2005-03-03 | 2005-09-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-09-01 | 2009-03-03 | 2009-09-02 | $7700.00 | Window Closed / Lapsed |