Accuracy testing of query optimizers
Query optimizer accuracy is tested by measuring the actual execution times on a database of each of a plurality of alternative query plans for each of a plurality of queries, first ranking the plans by the actual execution times, then ranking the plans by estimated execution times, and correlating the two rankings by computing a rank correlation metric. The rank correlation metric is normalized so that different optimizers can be objectively compared.
1. A computer-implemented method comprising:
obtaining, by a testing system comprising one or more computers, a plurality of query plans generated by a plurality of respective query optimizers, each query plan of the plurality of query plans being alternative query plans for computing results for a query;
computing, for each query plan of the plurality of query plans, a respective estimated cost to compute results for the query using the query plan;
executing each query plan of the plurality of query plans to compute a respective actual cost of executing the query plan;
performing a clustering algorithm on the plurality of query plans using the respective estimated cost and respective actual cost to classify each query plan as belonging to a cluster or as being an outlier;
computing, for each query optimizer from query plans generated by the optimizer, a respective rank correlation score, including:
selecting, by the testing system, no more than N different query plans generated by the query optimizer, including selecting at least one outlier according to the clustering algorithm;
generating, by the testing system, (i) a first ranking of query plans generated by the query optimizer, ordered according to the respective actual cost of each query plan generated by the query optimizer, and (ii) a second ranking of query plans generated by the query optimizer, ordered according to the respective estimated cost of each query plan generated by the query optimizer;
computing, by the testing system based at least on the first ranking of the different query plans and the second ranking of the different query plans, a first rank correlation score indicative of an accuracy of the query optimizer in estimating costs associated with executing query plans, wherein determining the first rank correlation score comprises performing a pair-wise comparison of each pair of plans that were incorrectly ranked in the second ranking, including iteratively:
computing a weight of each particular plan, the weight representing a comparison of an actual cost of a highest-ranked plan to an actual cost for the particular plan,
weighting a distance between each pair of incorrectly ranked plans according to a first weight for a first plan and a second weight for a second plan, and
adding the weighted distance for the pair of plans to the first rank correlation score for the query optimizer;
ranking the plurality of query optimizers according to the respective rank correlation score computed for each of the plurality of query optimizers; and
improving performance of a database system, including selecting, by the testing system, as a preferred query optimizer for generating query plans for the database system, a highest-ranked query optimizer according to the ranking of the plurality of query optimizers.
2. The method of claim 1 , wherein the first rank correlation score for each query optimizer represents a likelihood of the query optimizer making wrong optimization decisions.
3. The method of claim 2 , wherein computing the rank correlation score comprises penalizing ranking errors of good query plans more severely than ranking errors of bad query plans.
4. The method of claim 2 , wherein the weight of each particular plan is inversely relative to the actual cost of the plan.
5. The method of claim 1 , further comprising removing duplicate query plans before computing respective rank correlation scores.
6. The method of claim 5 , wherein computing a rank correlation score for each query optimizer comprises determining the rank correlation score for a first query optimizer and a second query optimizer over a same predetermined number of selected query plans.
7. The method of claim 6 , wherein the clustering algorithm is a k-medoids clustering algorithm.
8. A non-transitory computer-readable medium storing instructions that, when executed by one or more computers, cause the one or more computers to perform operations comprising:
obtaining a plurality of query plans generated by a plurality of respective query optimizers, each query plan of the plurality of query plans being alternative query plans for computing results for a query;
computing, for each query plan of the plurality of query plans, a respective estimated cost to compute result for the query using the query plan;
executing each query plan of the plurality of query plans to compute a respective actual cost of executing the query plan;
performing a clustering algorithm on the plurality of query plans using the respective estimated cost and respective actual cost to classify each query plan as belonging to a cluster or as being an outlier;
computing, for each query optimizer from query plans generated by the optimizer, a respective rank correlation score, including:
selecting no more than N different query plans generated by the query optimizer, including selecting at least one outlier according to the cluster algorithm;
generating (i) a first ranking of query plans generated by the query optimizer, ordered according to the respective actual cost of each query plan generated by the query optimizer, and (ii) a second ranking of query plans generated by the query optimizer, ordered according to the respective estimated cost of each query plan generated by the query optimizer;
computing, based at least on the first ranking of the different query plans and the second ranking of the different query plans, a first rank correlation score indicative of an accuracy of the query optimizer in estimating costs associated with executing query plans, wherein determining the first rank correlation score comprises performing a pair-wise comparison of each pair of plans that were incorrectly ranked in the second ranking, including iteratively:
computing a weight of each particular plan, the weight representing a comparison of an actual cost of a highest-ranked plan to an actual cost for the particular plan,
weighting a distance between each pair of incorrectly ranked plans according to a first weight for a first plan and a second weight for a second plan, and
adding the weighted distance for the pair of plans to the first rank correlation score for the query optimizer;
ranking the plurality of query optimizers according to the respective rank correlation score computed for each of the plurality of query optimizers; and
improving performance of a database system, including selecting, as a preferred query optimizer for generating query plans for the database system, a highest-ranked query optimizer according to the ranking of the plurality of query optimizers.
9. The non-transitory computer-readable medium of claim 8 , wherein the first rank correlation score for each query optimizer represents a likelihood of the first query optimizer making wrong optimization decisions.
10. The non-transitory computer-readable medium of claim 9 , wherein the weight of each particular plan is inversely relative to the actual cost of the plan.
11. The non-transitory computer-readable medium of claim 8 , further comprising removing duplicate query plans before computing respective rank correlation scores.
12. The non-transitory computer-readable medium of claim 8 , wherein computing a rank correlation score for each query optimizer comprises determining the rank correlation score for a first query optimizer and a second query optimizer over a same predetermined number of selected query plans.
13. The non-transitory computer-readable medium of claim 12 , wherein the clustering algorithm is a k-medoids clustering algorithm.
14. The non-transitory computer-readable medium of claim 8 , wherein the operations are repeated for each of a plurality of query optimizers to produce a normalized rank correlation metric for each query optimizer that indicates a respective accuracy of each query optimizer, and the operations further comprising generating a report that compares the accuracies of the query optimizers.
15. A system comprising:
one or more computer processors; and
a non-transitory computer-readable medium storing instructions that, when executed by the one or more computer processors, cause the one or more computer processors to perform operations comprising:
obtaining a plurality of query plans generated by a plurality of respective first query optimizers, each query plan of the plurality of query plans being alternative query plans for has generated as alternatives for executing computing results for a query;
computing, for each query plan of the plurality of query plans, a respective estimated cost to compute results for the query using the query plan;
executing each query plan of the plurality of query plans to compute a respective actual cost of executing the query plan;
performing a clustering algorithm on the plurality of query plans using the respective estimated cost and respective actual cost to classify each query plan as belong to a cluster or as being an outlier;
computing, for each query optimizer from query plans generated by the optimizer, a respective rank correlation score, including:
selecting no more than N different query plans generated by the query optimizer, including selecting at least one outlier according to the clustering algorithm;
generating (i) a first ranking of query plans generated by the query optimizers, ordered according to the respective actual cost of each query plan generated by the query optimizer, and (ii) a second ranking of query plans generated by the query optimizer, ordered according to the respective estimated cost of each query plan generated by the query optimizer;
computing, based at least on the first ranking of the different query plans and the second ranking of the different query plans, a first rank correlation score indicative of an accuracy of the query optimizer in estimating costs associated with executing query plans, wherein determining the first rank correlation score comprises performing a pair-wise comparison of each pair of plans that were incorrectly ranked in the second ranking, including iteratively:
computing a weight of each particular plan, the weight representing a comparison of an actual cost of a highest-ranked plan to an actual cost for the particular plan,
weighting a distance between each pair of incorrectly ranked plans according to a first weight for a first plan and a second weight for a second plan, and
adding the weighted distance for the pair of plans to the first rank correlation score for the query optimizer;
ranking the plurality of query optimizers according to the respective rank correlation score computed for each of the plurality of query optimizers; and
improving performance of a database system, including selecting, as a preferred query optimizer for generating query plans for the database system, a highest-ranked query optimizer according to the ranking of the plurality of query optimizers.
16. The system of claim 15 , wherein the first rank correlation score for each query optimizer represents a likelihood of the query optimizer making wrong optimization decisions.
17. The system of claim 16 , wherein the weight of each particular plan is inversely relative to the actual cost of the plan.
18. The system of claim 15 , wherein the operations further comprising removing duplicate query plans before computing respective rank correlation scores.
19. The system of claim 15 , wherein computing a rank correlation score for each query optimizer comprises determining the rank correlation score for a first query optimizer and a second query optimizer over a same predetermined number of query plans.
20. The system of claim 15 , the operations further comprising connecting the system to a plurality of different databases, each having a query optimizer, the system being operable to produce a normalized rank correlation metric for each query optimizer that indicates a respective accuracy of each query optimizer, for comparing the query optimizers of the databases to each other.