Optimizer dynamic sampling

• US 20040225639A1
• Filed: 05/09/2003
• Published: 11/11/2004
• Est. Priority Date: 05/09/2003
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: McKenna, William, Ziauddin, Mohamed, Jakobsson, Hakan
• Granted Patent: US 7,213,012 B2
• Time in Patent Office: Days
• US Class Current: 707/2
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24549 Run-time optimisation
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

Described herein are approaches to implementing dynamic sampling in a way that lessens or eliminates the additional overhead incurred to perform dynamic sampling. Also described are techniques for determining characteristics about predicates not previously determined by conventional techniques for dynamic sampling. Dynamic sampling is used by a query optimizer to dynamically estimate predicate selectivities and statistics. When a database statement is received by a database server, an initial analysis of the database statement is made to determine the efficacy of dynamic sampling, that is, to determine whether optimization of the query would benefit from dynamic sampling and whether performance is not excessively impacted by the dynamic sampling process. If this analysis determines dynamic sampling should be used, then dynamic sampling is undertaken.

Claims

1. A method used for optimizing queries, the method comprising the steps of:

receiving a first query that requires access to a first table;

generating a first execution plan for executing said first query;

based on a set of one or more factors, determining whether to execute another query to access a subset of rows as a sample from said first table and to generate results used to evaluate efficiency of execution plans for executing said first query;

wherein said one or more factors include at least one factor that reflects the efficacy of executing said other query to evaluate the efficiency of execution plans for executing said first query;

if, based on said one or more factors, it is determined the other query should be executed, then issuing said other query to generate first results; and

determining a second execution plan for executing said first query based on said first results.

2. The method of claim 1, wherein:

said first query includes a predicate; and

the step of issuing said first query includes issuing said other query to generate statistics that reflect application of said predicate to a portion of the rows in said first table.

3. The method of claim 2, wherein the step of generating statistics includes generating statistics that reflect the selectivity of said predicate.

4. The method of claim 2, wherein:

said predicate references join columns; and

the step of generating statistics includes generating statistics about at least one of said join columns.

5. The method of claim 1, wherein:

said first query requires access to a first column in said first table;

said first column contains unique values that are each unique relative to all other values in the first column;

said first query contains a predicate that is based on a first expression;

said first expression is based on said first column; and

the steps further include determining whether said first results indicate, for a subset of rows in the first table, whether said first expression is unique for each row of said subset relative to the other rows in said subset.

6. The method of claim 1,

wherein said other query accesses a first subset of the rows of said first table;

wherein said first results indicate the portion of rows in said first subset that satisfy a predicate in said first query; and

if said portion is greater than a threshold, then;

computing an estimate of the selectivity of the predicate based on the first results, and

performing the step of determining a second execution plan based on said estimate.

7. The method of claim 6, wherein the steps further include:

when said portion is not greater than said threshold;

establishing a default value as the estimate of the selectivity of the predicate; and

performing the step of determining a second execution plan based on said estimate.

8. The method of claim 6, wherein the steps further include:

when said portion is not greater than said threshold, generating a third query to evaluate the efficiency of execution plans for executing said first query, wherein said third query is generated to access a second subset of rows that contains more rows than said first subset.

9. The method of claim 6, wherein the steps further include:

when said portion is not greater than said threshold, causing traversing of an index to determine a number of rows in said first table that satisfy the predicate.

10. The method of claim 9, wherein the steps further include:

estimating a first amount of data that is accessed to perform the step of traversing;

determining that said first amount is less than an amount of data that would be accessed by executing a version of said other query that accesses a greater number of rows than the number of rows in said first subset; and

in response to determining that said first amount is less, performing the step of traversing.

11. The method of claim 1, wherein the one or more factors include one or more of the following:

the first query requires access to at least one table for which no persistently stored statistics are available;

the at least one table has no indexes;

the at least one table stores more database data than would be accessed by executing said other query; and

the first query includes two or more predicates that access said at least one table.

12. A method used for optimizing queries, the method comprising the steps of:

receiving a first query that requires access to a table;

in response to receiving said first query, generating another query to generate results that may be used to evaluate the efficiency of execution plans for executing said first query;

wherein said first query requires access to a first column in said table;

wherein said first column contains unique values that are each unique relative to all other values in the first column;

wherein said first query contains a predicate that is based on a expression;

wherein said expression is based on said first column; and

determining whether said results indicate, for a subset of rows in the table, whether said expression is unique for each row of said subset relative to the other rows in said subset.

13. A method used for optimizing queries, the method comprising the steps of:

receiving a first query that requires access to a table and that includes a predicate;

in response to receiving said first query, generating another query to generate results that may be used to evaluate the efficiency of execution plans for executing said first query;

wherein said other query accesses a subset of the rows of said table;

determining the portion of rows in said subset that satisfy said predicate; and

if said portion is not greater than a threshold, then;

establishing a default value as an estimate of the selectivity of the predicate; and

based on said estimate, determining an execution plan for executing said first query.

14. A method used for optimizing queries, the method comprising the steps of:

receiving a first query that requires access to a table and that includes a predicate;

in response to receiving said first query, generating another query to generate results that may be used to evaluate the efficiency of execution plans for executing said first query;

wherein said other query accesses a first subset of the rows of said table;

determining the portion of rows in said first subset that satisfy said predicate; and

if said portion is not greater than a threshold, then

establishing a default value as an estimate of selectivity of the predicate; and

based on said estimate, determining an execution plan for executing said first query.

15. A method used for optimizing queries, the method comprising the steps of:

receiving a first query that requires access to a table and that includes a predicate;

in response to receiving said first query, generating another query to generate results that may be used to evaluate the efficiency of execution plans for executing said first query;

wherein said other query accesses a first subset of the rows of said table;

determining the portion of rows in said first subset that satisfy said predicate; and

if said portion is not greater than a threshold, then causing traversal of an index to determine a number of rows in said table that satisfy the predicate.

16. A method used for performing dynamic sampling to optimize queries, the method comprising the steps of:

receiving a query that requires access to a table;

in response to receiving said first query, generating another query to generate results that may be used to evaluate the efficiency of execution plans for executing said first query;

wherein execution of said other query;

uses resources;

entails access to first data stored in said table and to metadata describing said table;

making a determination of how to divide said resources between accessing said first data and accessing said metadata; and

wherein the step of generating said other query includes generating said query so that said execution of said query uses said resources according to said determination.

17. The method of claim 16, wherein:

said table includes a plurality of table partitions;

said metadata includes partition metadata describing said table partitions;

the step of generating said other query includes;

determining a number of table partitions to access based on a number of accesses to the partition metadata expected during execution of said other query, and

generating said other query to cause said execution of said query to access said number of partitions.