System and method for query optimization using quantile values of a large unordered data set

• US 5,664,171 A
• Filed: 04/14/1994
• Issued: 09/02/1997
• Est. Priority Date: 04/14/1994
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Agrawal, Rakesh, Swami, Arun Narasimha
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US08/227,428
• Time in Patent Office: 1,237 Days
• Field of Search: 395/600, 364/574, 364/300
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• 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
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

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.

Claims

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

2. The system of claim 1, wherein the test value is an element of one of the data records in the test set.

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

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

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

6. The method of claim 5, wherein the test value is an element of one of the records in the test set.

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

8. The method of claim 7, further comprising the step of returning upper and lower bounds between which the record lies.

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

10. The optimizer of claim 9, wherein the test value is an element of one of the tuples in the test set.

11. The optimizer of claim 10, further comprising means for selectively discarding the tuple from the test set in response to the quantile value.

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