System and methods for predicting query execution time for concurrent and dynamic database workloads

Patent metadata

Field	Value
Publication number	US-9477707-B2
Application number	US-201314073817-A
Country	US
Kind code	B2
Filing date	Nov 6, 2013
Priority date	Jan 29, 2013
Publication date	Oct 25, 2016
Grant date	Oct 25, 2016

Abstract

Systems and methods for predicting query execution time for concurrent and dynamic database workloads include decomposing each query into a sequence of query pipelines based on the query plan from a query optimizer, and predicting an execution time of each pipeline with a progress predictor for a progress chart of query pipelines.

First claim

What is claimed is:

1. A method for predicting query execution time for concurrent and dynamic database workloads, comprising:
receiving a plurality of database queries;
decomposing each query into a sequence of query pipelines based on the query plan from a query optimizer, and
predicting an execution time T i for a pipeline i determined as T i =V cpu,i R cpu,i +V disk,i R disk,j of each pipeline with a progress predictor for a progress chart of query pipelines, with visit V at the disk or the CPU respectively, and residence time R at the disk or the CPU, respectively; and
modifying the database workload to satisfy a service level agreement with a user.

2. The method of claim 1 , comprising determining a lifetime of a mixture of queries whose execution time is to be predicted as multiple stages, where each stage contains a specific mixture of pipelines.

3. The method of claim 1 , comprising decomposing an optimizer query plan into one or more pipelines and building a pipeline-based progress chart for a texture of concurrently running queries.

4. The method of claim 3 , comprising generating a progress chart for a set of concurrently running queries by vertically stacking ordered pipelines of the queries.

5. The method of claim 1 , wherein the progress predictor predicts a stage transition order and a sojourn time at each stage in the progress chart.

6. The method of claim 5 , comprising predicting an execution time of a pipeline given other concurrently running pipelines.

7. The method of claim 5 , wherein the progress predictor predicts a whole stage transition sequence of the progress chart and a time when each transition occurs.

8. The method of claim 5 , comprising applying machine learning based prediction models that use different feature sets and learning models.

9. The method of claim 5 , comprising applying one or more analytical models that models a queuing process and a buffer pool hit ratio.

10. The method of claim 9 , comprising modeling with a queueing network and resident times per visit of pipelines within a network.

11. A system for predicting query execution time for concurrent and dynamic database workloads, comprising:
a computer;
a database executed by the computer;
code for decomposing each query into a sequence of query pipelines based on the query plan from a query optimizer, and
code for predicting an execution time T i for a pipeline i determined as T i =V cpu,i R cpu,i +V disk,i R disk,i of each pipeline with a progress predictor for a progress chart of query pipelines, with visit V at the disk or the CPU respectively, and residence time R at the disk or the CPU, respectively, and for modifying the database workload to satisfy a service level agreement with a user.

12. The system of claim 11 , comprising code for determining a lifetime of a mixture of queries whose execution time is to be predicted as multiple stages, where each stage contains a specific mixture of pipelines.

13. The system of claim 11 , comprising code for decomposing an optimizer query plan into one or more pipelines and building a pipeline-based progress chart for a texture of concurrently running queries.

14. The system of claim 13 , comprising code for generating a progress chart for a set of concurrently running queries by vertically stacking ordered pipelines of the queries.

15. The system of claim 11 , wherein the progress predictor predicts a stage transition order and a sojourn time at each stage in the progress chart.

16. The system of claim 15 , comprising code for predicting an execution time of a pipeline given other concurrently running pipelines.

17. The system of claim 15 , wherein the progress predictor predicts a whole stage transition sequence of the progress chart and a time when each transition occurs.

18. The system of claim 15 , comprising code for applying machine learning based prediction models that use different feature sets and learning models.

19. The system of claim 15 , comprising code for applying one or more analytical models that models a queuing process and a buffer pool hit ratio.

20. The system of claim 19 , comprising code for modeling with a queueing network and resident times per visit of pipelines within a network.

Assignees

• Nec Lab America Inc
• Nec Corp

Inventors

• Chi Yun
• Wu Wentao
• Hacigumus Vahit Hakan
• Naughton Jeffrey F

Classifications

• G06F16/2453 Primary

  Query optimisation · CPC title

• G06F17/30442 Primary

  Physics · mapped topic