Query progress estimation based on processed value packets

Patent metadata

Field	Value
Publication number	US-9836504-B2
Application number	US-49562809-A
Country	US
Kind code	B2
Filing date	Jun 30, 2009
Priority date	Jun 30, 2009
Publication date	Dec 5, 2017
Grant date	Dec 5, 2017

Abstract

A data processing system performs query progress estimation based on processed value packets. In the illustrative data processing system, a database query processor comprises a query optimizer that creates a query plan, and a database plan executor that executes the query plan and observes intermediate result streams processed as the query plan is executed. A value packet manager anticipates value packets during query optimization, creates value packets as the intermediate result streams are processed, and compares anticipated value packets with created value packets to determine accuracy of the anticipated value packets and estimate query progress.

First claim

What is claimed is:

1. A system comprising:
a processor;
a query processor coupled to the processor to create a query plan;
a query plan executor coupled to the processor to:
execute the query plan; and
observe intermediate result streams processed as the query plan is executed;

a value packet manager coupled to the processor to:
anticipate value packets during query optimization, wherein:
a value packet is a common attribute value defining a group of records indicative of a query processing iterator's progress; and

the value packet includes two records determined to have a same key, wherein the key corresponds to a particular sort order;
create value packets as the intermediate result streams are processed;
compare anticipated value packets with created value packets to determine accuracy of the anticipated value packets;
estimate, using a first method of estimation, a progress of the query at a first point in the query, the value packet manager to:
determine an estimated value for anticipated value packets of:
an elapsed time;
a ratio of CPU time to latency;
a data piece count;
a key value distribution;
a row count; and
a data size; and

compare the estimated values of the anticipated value packets to corresponding actual values for created value packets;

based on the comparison of the estimated values of the anticipated value packets to the corresponding actual values for the created value packets, determine a confidence level indicator of the query progress estimate, wherein the confidence level indicator indicates a level of confidence in the estimate of progress of the query plan at an operator level at the first point in the query; and

a workflow manager coupled to the processor to:
receive the query progress estimate;
receive the confidence level indicator of the query progress estimate; and
modify a workflow of the query plan based on the query progress estimate and the confidence level indicator of the query progress estimate.

2. The system of claim 1 , further comprising the value packet manager to:
collect information about the data statistics;
analyze the collected information about the data statistics; and
dynamically correct the data statistics during query processing based on the analyzed information about the data statistics.

3. The system of claim 1 , further comprising the query plan executor to:
sort the intermediate result streams according to predetermined criteria; and
divide the intermediate result stream into value packets according to the sort order.

4. The system of claim 1 , further comprising the workload manager to:
determine a remaining run-time of active requests based on the estimate of query progress; and
modify an overall work schedule based on the estimate.

5. The system of claim 1 , further comprising the value packet manager preserve information in data structures available during query execution, wherein the information includes:
distribution of unique values in sort keys;
a number of items per unique value; and
a number of records per unique value.

6. The system of claim 1 , further comprising the value packet manager to:
determine that the anticipated value packets are incorrect during query execution; and
reassess query progress to:
estimate remaining work using processed unique values in sort keys;
adapt workload management policies through reallocation of resources;
selectively pause query execution for later resumption; and
selectively abort the query plan for re-invoking query optimization with improved information and an improved query plan.

7. The system of claim 1 , further comprising the value packet manager to:
adjust a number of unique values in the intermediate result stream, wherein the adjustment is based on:
the processing of a unique value in an intermediate query result's sort order; and
an individual record associated with the unique value; and

adjust a number of records and items associated with the unique value.

8. The system of claim 1 , further comprising the value packet manager to estimate the progress of the query at a second point in the query using a second method of estimation, wherein the second method of estimation is different than the first method of estimation.

9. The system of claim 1 , further comprising the value packet manager to:
analyze operator-level runtime statistics;
analyze overall system statistics; and
estimate query progress using a combination of operator-level runtime statistics and overall system statistics.

10. The system of claim 1 , further comprising the value packet manger to:
select the first method of estimation based on a first type of operator; and
select the second method of estimation based on a second type of operator.

11. The system of claim 10 , wherein:
the first type of operator includes a distribution of values of a sorted input; and
the second type of operator includes a tuple count and estimated cardinality.

12. A method comprising:
creating a query plan;
executing the query plan;
observing intermediate result streams processed as the query plan is executed;
anticipating value packets during query optimization, wherein:
a value packet is a common attribute value defining a group of records indicative of a query processing iterator's progress; and
the value packet includes two records determined to have a same key, wherein the key corresponds to a particular sort order;

creating value packets as the intermediate result streams are processed; and
comparing, by a hardware processor, anticipated value packets with created value packets to determine accuracy of the anticipated value packets and estimate query progress;
estimating, using a first method of estimation, a progress of the query at a first point in the query, wherein estimating a progress of the query includes:
determining an estimated value for anticipated value packets of:
an elapsed time;
a ratio of CPU time to latency;
a data piece count;
a key value distribution;
a row count; and
a data size; and

comparing the estimated values of the anticipated value packets to corresponding actual values for created value packets;

based on the comparison of the estimated values of the anticipated value packets to the corresponding actual values for the created value packets, determining a confidence level indicator of the query progress estimate, wherein the confidence level indicator indicates a level of confidence in the estimate of progress of the query plan at the first point in the query; and
modifying a workflow of the query plan based on the estimated progress of the query and the determined confidence level indicator of the query progress estimate, wherein modifying a workflow of the query plan includes reallocating memory resources and processing resources.

13. A system comprising:
a processor; and
a non-transitory computer readable medium containing instructions executable by the processor to:
create a query plan, wherein the instructions to create a query plan include instructions to:
verify compliance of a subset of records from a relational database with a query criteria as the query plan is executed; and
generate intermediate result streams based on the compliance verification;

execute the query plan, wherein the instructions to execute the query plan include instructions to:
observe the intermediate result streams;
sort the intermediate result streams according to predetermined criteria; and
divide the intermediate result stream into value packets according to a sort order, wherein:
a value packet is a common attribute value defining a group of

Assignees

• Graefe Goetz
• Kuno Harumi
• Hewlett Packard Entpr Dev Lp

Inventors

• Graefe Goetz
• Kuno Harumi

Classifications

• G06F16/24542 Primary

  Plan optimisation · CPC title

• G06F17/30463 Primary

  Physics · mapped topic