Database system with methodology providing improved cost estimates for query strategies

• US 6,353,826 B1
• Filed: 08/27/1999
• Issued: 03/05/2002
• Est. Priority Date: 10/23/1997
• Status: Expired due to Term

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Seputis, Edwin Anthony
• Primary Examiner(s): Corrielus, Jean M.
• Application Number:
  US09/384,729
• Time in Patent Office: 921 Days
• Field of Search: 707/2, 707/1, 707/3, 707/4, 707/101, 707/200, 707/104, 707/10, 707/102, 707/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• 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
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

Database system and methods are described for improving execution speed of database queries (e.g., for decision support). A multi-attribute selectivity optimization methodology is described that provides a more accurate estimate of the cost of a query execution plan, so that the predicted performance of the final execution plan will be more accurate. The densities by how much the selectivity deviates from a single attribute density and by how much the multi-attribute densities differ from one another are used as a basis for multi-selectivity estimates. The multi-attribute densities are used to scale estimates between extremes of total independence and total dependence. By taking into account how well attributes are correlated, the approach is able to provide more accurate multi-selectivity estimates. As a result, the database system can formulate better query plans and, thus, provide better performance.

Claims

1. In a computer system providing a database storing database objects, a method for improving determination of cost estimates associated with data access occurring during execution of a database query, the method comprising:

receiving a database query specifying a database operation for at least one database object, said database query specifying a query condition for selecting particular rows based on multiple attributes of said at least one database object; and

determining an estimate for the cost associated with a query execution path for executing the database query by;

determining selectivity information providing a selectivity estimate for each of said multiple attributes,

determining correlation information providing a measure of how well at least some of said multiple attributes are correlated, and

combining said selectivity information together, based at least in part on said correlation information, for determining a multi-attribute selectivity estimate for the query condition.

2. The method of claim 1, wherein correlation between two attributes is determined based on how much a particular value specified in the database query for one attribute depends on a given value specified in the database query for another attribute.

3. The method of claim 2, wherein correlation between two attributes may very between total independence and total dependence.

4. The method of claim 1, wherein said combining step includes:

adding selectivity information for an attribute only if a particular value specified in the database query for the attribute is not totally dependent on a given value specified in the database query for another attribute whose selectivity information has been taken into account.

5. The method of claim 1, wherein said determined selectivity information provides a measure of the fraction of rows of said at least one database object that satisfy said query condition.

6. The method of claim 1, wherein each of said multiple attributes corresponds to a particular column of said at least one database object.

7. The method of claim 1, further comprising:

formulating a query execution plan for providing access to said a least one database object, said query execution plan including an access strategy based at least in part on the determined multi-attribute selectivity estimate.

8. The method of claim 1, wherein said formulating a query execution plan step includes determining a particular access path for use by access methods, for executing the database query.

9. The method of claim 1, wherein said at least one database object comprises a database table.

10. The method of claim 1, wherein said at least one database object comprises a database index.

11. A database system employing cost estimates comprising:

a database storing database objects;

an optimizer which employs cost estimates for formulating query access plans in response to receiving a database query specifying a database operation for at least one database object, said database query specifying a query condition for selecting particular rows based on multiple attributes of said at least one database object, wherein said optimizer determines an optimal execution path for executing the database query by;

determining selectivity information providing a selectivity estimate for each of said multiple attributes,

determining correlation information providing a measure of how well at least some of said multiple attributes are correlated, and

based at least in part on said correlation information, combining said selectivity information together for determining a multi-attribute selectivity estimate for the query condition; and

an execution unit for executing a query access plan for the database query, said query access plan including an access strategy based at least in part on the determined multi-attribute selectivity estimate.

12. The system of claim 11, wherein correlation between two attributes is determined based on how much a particular value specified in the database query for one attribute depends on a given value specified in the database query for another attribute.

13. The system of claim 12, wherein correlation between two attributes may very between total independence and total dependence.

14. The system of claim 11, wherein said optimizer combines selectivity information by adding selectivity information for an attribute only if a particular value specified in the database query for the attribute is not totally dependent on a given value specified in the database query for another attribute whose selectivity information has been taken into account.

15. The system of claim 11, wherein said determined selectivity information provides a measure of the fraction of rows of said at least one database object that satisfy said query condition.

16. The system of claim 11, wherein each of said multiple attributes corresponds to a particular column of said at least one database object.

17. The system of claim 11, wherein said execution unit formulates a query by determining a particular access path for use by access methods, for executing the database query.

18. The system of claim 11, wherein said at least one database object comprises a database table.

19. The system of claim 11, wherein said at least one database object comprises a database index.

20. The system of claim 11, wherein at least some of said correlation information is stored persistently for the database system.