Predicting query execution time

• US 8,874,548 B2
• Filed: 12/11/2012
• Issued: 10/28/2014
• Est. Priority Date: 02/27/2012
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Wu, Wentao, Chi, Yun, Zhu, Shenghuo, Tatemura, Junichi, Hacigumus, Vahit Hakan
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): Perez-Arroyo, Raquel
• Application Number:
  US13/711,023
• Publication Number:
  US 20130226903A1
• Time in Patent Office: 686 Days
• Field of Search: 707/718, 707/719
• US Class Current: 707/719
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24549 Run-time optimisation

Abstract

There are provided a system and method for predicting query execution time in a database system. A cost model determination device determines a cost model of a database query optimizer for the database system. The cost model models costs of queries applied to the database system. A profiling device determines profiling queries for profiling input/output cost units and processor cost units relating to the database system, and profiles the cost units using the profiling queries to output profiled cost units. A calibrating device calibrates cost units in the cost model responsive to the profiled cost units to output calibrated cost units. A sampling re-estimator samples and re-estimates a cardinality estimation of a final query plan to output an updated cardinality estimation. A predictor applies the calibrated cost units and the updated cardinality estimation in the cost model to generate a prediction of an execution time of a given query.

Claims

1. A system for predicting query execution time in a database system, comprising:

a processor,

a cost model determination device for determining a cost model of a database query optimizer for the database system, the cost model for modeling costs of queries applied to the database system, wherein the optimizer estimates a cost of each operator as a vector of cost units c=(C_s;

C_r;

C_t;

C_i;

C_o)^T|, wherein

c_s;

seq_page_cost, I/O cost to sequentially scan a page;

c_r;

random_page_cost, I/O cost to randomly access a page;

c_t;

cpu_tuple_cost, CPU cost to process a tuple;

c_i;

cpu_index_tuple_cost, CPU cost to process a tuple via index access;

or

c_o;

cpu_operator_cost, CPU cost to perform an operation,

and where a cost C_O of an operator O in a query plan is represented as a linear combination as;

C_O=n^Tc=n_s·

c_s+n_r·

c_r+n_t·

c_t+n_i·

c_i+n_o·

c_o.;

a profiling device for determining a group of profiling queries for profiling input/output cost units and processor cost units relating to the database system, and for profiling the input/output cost units and the processor cost units using one or more of the profiling queries in the group to output profiled input/output cost units and profiled processor cost units;

a calibrating device for calibrating cost units in the cost model responsive to the profiled input/output cost units and the profiled processor cost units to output calibrated cost units;

a sampling re-estimator for sampling and re-estimating a cardinality estimation of a final query plan to output an updated cardinality estimation; and

a predictor for applying the calibrated cost units and the updated cardinality estimation in the cost model to generate a prediction of an execution time of a given query.

2. The system of claim 1, wherein the given query, for which the prediction of the execution time thereof is generated, is previously unseen by the database system.

3. The system of claim 1, wherein the input/output cost units and the processor cost units are profiled separately to output the profiled input/output cost units and the profiled processor cost units.

4. The system of claim 1, wherein an error of the updated cardinality estimation providing by the sampling re-estimator is bounded.

5. The system of claim 1, wherein the given query is a structured query language query.

6. The system of claim 1, wherein the input/output cost units and the processor cost units that are profiled relate to one or more specific hardware and database configurations of the database system.

7. The system of claim 1, wherein the sampling re-estimator is configured to sample the cardinality estimation of the final query plan to output the updated cardinality estimation responsive to one or more specific hardware and database configurations of the database system.

8. The system of claim 1, wherein values of the cost units in the cost model that are calibrated by the calibrating device comprise default values.

9. The system of claim 1, wherein the sampling re-estimator estimates a query size of a particular query by conceptually partitioning an answer set of the particular query into a number of disjoint subsets, randomly and repeatedly selecting a respective one of the disjoint subsets to compute a respective subset size therefor, and generating an estimate of an answer set size based on the respective subset size of each of the disjoint subsets, and wherein the estimate of the answer set size is used to determine the updated cardinality estimation.

10. The system of claim 1, wherein the sampling re-estimator decouples a query answer set tuple sampling phase from an execution of corresponding sample queries, to determine and output the updated cardinality estimation.

11. A method for predicting query execution time in a database system, comprising:

determining a cost model of a database query optimizer for the database system, the cost model for modeling costs of queries applied to the database system, wherein the optimizer estimates a cost of each operator as a vector of cost units c=(c_s;

c_r;

c_t;

c_i;

c_o)^T|, wherein

c_s;

seq_page_cost, I/O cost to sequentially scan a page;

c_r;

random_page_cost, I/O cost to randomly access a page;

c_t;

cpu_tuple_cost, CPU cost to process a tuple;

c_i;

cpu_index_tuple_cost, CPU cost to process a tuple via index access;

or

c_o;

cpu_operator_cost, CPU cost to perform an operation,

and where a cost C_O of an operator O in a query plan is represented as a linear combination as;

C_O=n^Tc=n_s·

c_s+n_r·

c_r+n_t·

c_t+n_i·

c_i+n_o·

c_o.;

determining a group of profiling queries for profiling input/output cost units and processor cost units relating to the database system;

profiling the input/output cost units and the processor cost units using one or more of the profiling queries in the group to output profiled input/output cost units and profiled processor cost units;

calibrating cost units in the cost model responsive to the profiled input/output cost units and the profiled processor cost units to output calibrated cost units;

sampling and re-estimating a cardinality estimation of a final query plan to output an updated cardinality estimation; and

applying the calibrated cost units and the updated cardinality estimation in the cost model to generate a prediction of an execution time of a given query.

12. The method of claim 11, wherein the given query, for which the prediction of the execution time thereof is generated, is previously unseen by the database system.

13. The method of claim 11, wherein the input/output cost units and the processor cost units are profiled separately to output the profiled input/output cost units and the profiled processor cost units.

14. The method of claim 11, wherein an error of the updated cardinality estimation providing by the sampling and re-estimating step is bounded.

15. The method of claim 11, wherein the given query is a structured query language query.

16. The method of claim 11, wherein the input/output cost units and the processor cost units that are profiled relate to one or more specific hardware and database configurations of the database system.

17. The method of claim 11, wherein the sampling and re-estimating step is configured to sample the cardinality estimation of the final query plan to output the updated cardinality estimation responsive to one or more specific hardware and database configurations of the database system.

18. The method of claim 11, wherein values of the cost units in the cost model that are calibrated by the calibrating step comprise default values.

19. The method of claim 11, wherein the sampling and re-estimating step estimates a query size of a particular query by conceptually partitioning an answer set of the particular query into a number of disjoint subsets, randomly and repeatedly selecting a respective one of the disjoint subsets to compute a respective subset size therefor, and generating an estimate of an answer set size based on the respective subset size of each of the disjoint subsets, and wherein the estimate of the answer set size is used to determine the updated cardinality estimation.

20. The method of claim 11, wherein the sampling and re-estimating step decouples a query answer set tuple sampling phase from an execution of corresponding sample queries, to determine and output the updated cardinality estimation.