Dynamic optimization for processing a restartable sub-tree of a query execution plan

• US 7,051,034 B1
• Filed: 12/18/2002
• Issued: 05/23/2006
• Est. Priority Date: 12/18/2002
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Ghosh, Bhaskar, Cruanes, Thierry, Dageville, Benoit
• Primary Examiner(s): Corrielus, Jean M.
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US10/325,782
• Time in Patent Office: 1,252 Days
• Field of Search: 707 1- 5, 707/10, 707/100, 707/101, 707/104.1
• US Class Current: 707/718
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: G06F 16/90335 Query processing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Execution of a restartable sub-tree of a query execution plan comprises determining whether use of parallel processes is a preferred or optimal mode of executing the sub-tree. The determination is based, at least in part, on how long it takes to restart the sub-tree using two or more parallel processes and/or how long it takes to probe the sub-tree, i.e., to fetch a row that meets one or more conditions or correlations associated with the sub-query, using the two or more parallel processes. Thus, a dynamic computational cost-based operation is described, which determines at query runtime whether to execute the restartable sub-tree using a single server process or multiple parallel server processes.

Claims

1. A computer-implemented method for managing execution of a restartable sub-tree of a query execution plan, the method comprising the steps of:

generating a query execution plan for a query that includes a sub-query, wherein the execution plan includes a restartable sub-tree associated with the sub-query;

performing at query execution runtime one or more determinations from a set of determinations that consists of;

determining the amount of time to restart the sub-tree using two or more parallel processes, wherein restarting the sub-tree comprises initiating the two or more parallel processes to execute the sub-tree and allocating the two or more processes to perform various parts of the sub-tree, and

determining the amount of time to probe the sub-tree using the two or more parallel processes, wherein probing the sub-tree comprises determining whether a row meets one or more conditions specified in the sub-query to which the sub-tree is associated; and

determining at query execution runtime whether using two or more parallel processes is a preferred mode of executing the sub-tree based, at least in part, on the outcome of the one or more determinations.

2. The method of claim 1, wherein the step of performing one or more determinations includes determining the amount of time to restart the sub-tree using two or more parallel processes and determining the amount of time to probe the sub-tree using the two or more parallel processes.

3. The method of claim 1, wherein the query specifies a first table and the sub-query includes a predicate that specifies a correlation between a second table and the first table, and wherein the step of generating the execution plan generates an execution plan for the query.

4. The method of claim 1, further comprising the steps of:

executing the sub-tree using two or more parallel processes each time the sub-tree is probed; and

based on the step of determining whether using two or more parallel processes is the preferred mode, executing the sub-tree using a single process each time the sub-tree is probed when determined that use of two or more parallel processes is not the preferred mode of executing the sub-tree.

5. The method of claim 1, further comprising the steps of:

executing the sub-tree using two or more parallel processes for each of a plurality of instances in which the sub-tree is probed; and

based on the step of determining whether using two or more parallel processes are the preferred mode, executing the sub-tree with a single process when determined that the sum of an average of the amount of time to restart the sub-tree using two or more parallel processes and an average of the amount of time to probe the sub-tree using two or more parallel processes is greater than the product of the average of the amount of time to probe the sub-tree using the two or more parallel processes and the number of processes of the two or more parallel processes.

6. The method of claim 1, further comprising the steps of:

executing the sub-tree using a single process;

determining the amount of time to probe the sub-tree using a single process;

determining that using two or more parallel processes is a preferred mode of executing the sub-tree based, at least in part, on the amount of time to probe the sub-tree using a single process being greater than the sum of the amount of time to restart the sub-tree using two or more parallel processes and the amount of time to probe the sub-tree using two or more parallel processes.

7. The method of claim 1, further comprising the steps of:

executing the sub-tree using a single process;

determining the amount of time to probe the sub-tree using a single process;

determining that using a single process is a preferred mode of executing the sub-tree based, at least in part, on the amount of time to probe the sub-tree using a single process being less than the sum the amount of time to restart the sub-tree using two or more parallel processes and the amount of time to probe the sub-tree using two or more parallel processes.

8. The method of claim 1, further comprising the steps of:

executing the sub-tree using a single process for each of a plurality of instances in which the sub-tree is probed;

determining, for at least two of the plurality of instances, the amount of time to probe the sub-tree using the single process;

determining that a single process is a preferred mode of executing the sub-tree based, at least in part, on an average of the amount of time to probe the sub-tree using a single process being less than the sum of an average of the amount of time to restart the sub-tree using two or more parallel processes and an average of the amount of time to probe the sub-tree using two or more parallel processes.

9. A computer-readable medium carrying one or more sequences of instructions for managing execution of a correlation sub-query, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

generating a query execution plan for a query, wherein said query includes a sub-query, and wherein the query execution plan includes a restartable sub-tree associated with the sub-query;

performing at query execution runtime one or more determinations from a set of determinations that consists of

determining the amount of time to restart the sub-tree using two or more parallel processes, wherein restarting the sub-tree comprises initiating the two or more parallel processes to execute the sub-tree and allocating the two or more processes to perform various parts of the sub-tree, and

determining the amount of time to probe the sub-tree using the two or more parallel processes, wherein probing the sub-tree comprises determining whether a row meets one or more conditions specified in the sub-query to which the sub-tree is associated; and

determining at query execution runtime whether using two or more parallel processes is a preferred mode of executing the sub-tree based, at least in part, on the outcome of the one or more determinations.

10. The computer-readable medium of claim 9, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of performing one or more determinations by determining the amount of time to restart the sub-tree using two or more parallel processes and determining the amount of time to probe the sub-tree using the two or more parallel processes.

11. The computer-readable medium of claim 9, wherein the query specifies a first table and the sub-query includes a predicate that specifies a correlation between a second table and the first table, and wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of generating the execution plan by generating an execution plan for the query.

12. The computer-readable medium of claim 9, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

executing the sub-tree using two or more parallel processes each time the sub-tree is probed; and

based on the step of determining whether using two or more parallel processes is the preferred mode, executing the sub-tree using a single process each time the sub-tree is probed when determined that use of two or more parallel processes is not the preferred mode of executing the sub-tree.

13. The computer-readable medium of claim 9, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

executing the sub-tree using two or more parallel processes for each of a plurality of instances in which the sub-tree is probed; and

based on the step of determining whether using two or more parallel processes is the preferred mode, executing the sub-tree with a single process when determined the sum of an average of the amount of time to restart the sub-tree using two or more parallel processes and an average of the amount of time to probe the sub-tree using two or more parallel processes is greater than the product of the average of the amount of time to probe the sub-tree using the two or more parallel processes and the number of processes of the two or more parallel processes.

14. The computer-readable medium of claim 9, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

executing the sub-tree using a single process;

determining the amount of time to probe the sub-tree using a single process;

determining that using two or more parallel processes is a preferred mode of executing the sub-tree based, at least in part, on the amount of time to probe the sub-tree using a single process being greater than the sum of the amount of time to restart the sub-tree using two or more parallel processes and the amount of time to probe the sub-tree using two or more parallel processes.

15. The computer-readable medium of claim 9, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

executing the sub-tree using a single process;

determining the amount of time to probe the sub-tree using a single process;

determining that using two or more parallel processes is a preferred mode of executing the sub-tree based, at least in part, on the amount of time to probe the sub-tree using a single process being greater than the sum of the amount of time to restart the sub-tree using two or more parallel processes and the amount of time to probe the sub-tree using two or more parallel processes.

16. The computer-readable medium of claim 9, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

executing the sub-tree using a single process for each of a plurality of instances in which the sub-tree is probed;

determining, for at least two of the plurality of instances, the amount of time to probe the sub-tree using the single process;

determining that using a single process is a preferred mode of executing the sub-tree based, at least in part, on an average of the amount of time to probe the sub-tree using a single process being less than the sum of an average of the amount of time to restart the sub-tree using two or more parallel processes and an average of the amount of time to probe the sub-tree using two or more parallel processes.

17. An apparatus for managing execution of a correlation sub-query, comprising:

means for generating a query execution plan for a query, wherein said query includes a sub-query, and wherein the query execution plan includes a restartable sub-tree associated with the sub-query;

means for performing at query execution runtime one or more determinations from a set of determinations that consists of

determining the amount of time to restart the sub-tree using two or more parallel processes, wherein restarting the sub-tree comprises initiating the two or more parallel processes to execute the sub-tree and allocating the two or more processes to perform various parts of the sub-tree, and

determining the amount of time to probe the sub-tree using the two or more parallel processes, wherein probing the sub-tree comprises determining whether a row meets one or more conditions specified in the sub-query to which the sub-tree is associated; and

means for determining at query execution runtime whether using two or more parallel processes is a preferred mode of executing the sub-tree based, at least in part, on the outcome of the one or more determinations.

18. A computer apparatus, comprising:

a memory; and

one or more processors coupled to the memory and configured to execute one or more sequence of instructions for managing execution of a correlation sub-query, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of;

generating a query execution plan for a query, wherein said query includes a sub-query, and wherein the query execution plan includes a restartable sub-tree associated with the sub-query;

performing at query execution runtime one or more determinations from a set of determinations that consists of

determining the amount of time to restart the sub-tree using two or more parallel processes, wherein restarting the sub-tree comprises initiating the two or more parallel processes to execute the sub-tree and allocating the two or more processes to perform various parts of the sub-tree, and

determining the amount of time to probe the sub-tree using the two or more parallel processes, wherein probing the sub-tree comprises determining whether a row meets one or more conditions specified in the sub-query to which the sub-tree is associated; and

determining at query execution runtime whether using two or more parallel processes is a preferred mode of executing the sub-tree based, at least in part, on the outcome of the one or more determinations.