ALLOCATING RESOURCES FOR PARALLEL EXECUTION OF QUERY PLANS

• US 20090254916A1
• Filed: 08/14/2008
• Published: 10/08/2009
• Est. Priority Date: 04/08/2008
• Status: Active Grant

• Current Assignee: Infosys Limited
• Original Assignee: Infosys Technologies Limited (Infosys Limited)
• Inventors: Krishnamoorthy, Srikumar, Bose, Sumit Kumar, Ranade, Nilesh Dilip
• Granted Patent: US 8,402,469 B2
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

Computing resources can be assigned to sub-plans within a query plan to effect parallel execution of the query plan. For example, computing resources in a grid can be represented by nodes, and a shortest path technique can be applied to allocate machines to the sub-plans. Computing resources can be provisionally allocated as the query plan is divided into query plan segments containing one or more sub-plans. Based on provisional allocations to the segments, the computing resources can then be allocated to the sub-plans within respective segments. Multiprocessor computing resources can be supported. The techniques can account for data locality. Both pipelined and partitioned parallelism can be addressed. Described techniques can be particularly suited for efficient execution of bushy query plans in a grid environment. Parallel processing will reduce the overall response time of the query.

Claims

1. A method of allocating computing resources in a grid to an executable query plan, wherein the executable query plan is dividable into a plurality of query sub-plans at a plurality of query sub-plan levels in the executable query plan, the method comprising:

repeatedly splitting the query plan into query plan segments and provisionally allocating computing resources in the grid to the query plan segments until the query plan segments have only one query sub-plan level, thereby forming a provisional allocation; and

distributing the computing resources in the grid among the query sub-plans in respective of the query plan segments according to the provisional allocation.

2. The method of claim 1 wherein distributing the computing resources in the grid among the query sub-plans comprises:

dividing computing resources provisionally allocated to a query plan segment among query sub-plans of the query plan segment.

3. The method of claim 2 wherein dividing the computing resources comprises:

constructing a table storing process cost values for respective permutations of query sub-plans and computing resources;

finding a minimum process cost value in the table; and

allocating a computing resource associated with the minimum process cost value to a query sub-plan associated with the minimum process cost value.

4. The method of claim 3 wherein the process cost values are normalized via an amount of processing estimated for respective query sub-plans.

5. The method of claim 1 wherein distributing the computing resources in the grid among the query sub-plans comprises:

responsive to determining that allocating a computing resource to a particular query sub-plan does not improve performance, ceasing to allocate further computing resources to the particular query sub-plan.

6. The method of claim 1 wherein provisionally allocating computing resources in the grid to the query plan segments comprises:

representing the computing resources in the grid as nodes in a graph;

representing a pair of the query plan segments in the graph;

representing a cost of communicating between the computing resources in the grid as edges in the graph;

representing a computing cost of processing the query plan segments as edges in the graph;

finding a shortest path in the graph from one query plan segment to an other query plan segment; and

responsive to finding the shortest path, provisionally allocating computing resources represented by nodes in the shortest path to respective query plan segments in the graph.

7. The method of claim 6 wherein:

multiprocessor computing resources are represented in the graph as separate computing resources.

8. The method of claim 6 further comprising:

adjusting the graph to account for data locality.

9. The method of claim 1 further comprising:

accounting for data locality, wherein accounting for data locality comprises;

excluding from allocation considerations computing resources at which data tables accessed by the query plan reside initially.

10. The method of claim 1 wherein the method further comprises:

imposing a constraint of only those query sub-plans that belong to adjacent levels of the query plan can be allocated to a same multiprocessor machine.

11. The method of claim 1 wherein provisionally allocating computing resources in the grid to the query plan segments comprises:

provisionally allocating resources until all allocable resources are allocated or allocation of resources does not improve performance.

12. The method of claim 1 wherein allocating computing resources addresses both pipelined parallelism and partitioned parallelism.

13. The method of claim 1 further comprising:

computing sub-plan workload densities for respective levels of a query plan segment;

wherein splitting the query plan into query plan segments comprises;

splitting the query plan segment at a point in the query plan segment where a summation of workload densities of different consecutive levels exceeds half of a total workload density for the query plan segment.

14. A computer-implemented method of allocating resources for executing a query according to a query plan, the method comprising:

receiving a representation of the query plan, wherein the query plan is dividable into a plurality of query sub-plans;

dividing the query plan into a plurality of segments of the query plan having respective one or more query sub-plans of the query plan;

creating a graph representation of connections between the plurality of segments of the query plan, wherein the graph representation comprises a plurality of nodes representing respective computing resources and a plurality of connecting edges representing respective resource costs;

finding a shortest path between two of the segments;

responsive to finding the shortest path, allocating computing resources associated with the shortest path to respective segments of the query plan; and

allocating the computing resources to query sub-plans of the query plan according to allocations to the segments of the query plan, thereby forming an allocation of the computing resources to the query sub-plans; and

outputting the allocation of the computing resources to the query sub-plans.

15. A computer-implemented method of indicating an allocation of computing resources to a query plan comprising a plurality of query sub-plans, the method comprising:

receiving a representation of the query plan;

constructing a graph representing connections between segments of the query plan and the computing resources;

performing a shortest path search on the graph;

based on results of the shortest path search, determining an allocation of computing resources to respective query sub-plans, removing allocated computing resources from the graph, and repeating the shortest path search; and

outputting the allocation of computing resources to the respective query sub-plans.

16. The computer-implemented method of claim 15 wherein:

pipelined parallelism is addressed via evaluation of communication costs between the computing resources; and

partitioned parallelism is addressed via assigning a plurality of computing resources to a single query sub-plan of the query plan.

17. One or more computer-readable storage media comprising computer-executable instructions causing a computer to perform a method comprising:

receiving a query plan;

initially considering the query plan as a single query segment;

repeatedly any splitting query segment of the query plan having more than one level into child query segments until the child query segments have one level;

after splitting a query segment, allocating machines to the child segments of the query plan via repeatedly finding a shortest path in a graph representing a cost of processing the segments at various machines in a grid and a cost of communicating between machines in the grid, wherein nodes representing the allocated machines are removed from the graph after allocation;

when the query segments have been reduced to one level, distributing machines allocated to respective segments among query sub-plans within the respective segments based at least on consideration of a total time for respective of the machines to process respective of the query sub-plans, wherein the distributing comprises repeatedly performing (a)-(e);

(a) constructing a table storing process cost values for respective permutations of query sub-plans and computing resources;

(b) finding a minimum process cost value in the table;

(c) allocating a computing resource associated with the minimum process cost value to a query sub-plan associated with the minimum process cost value;

(d) removing the computing resource and the query sub-plan associated with the minimum cost value from the table; and

(e) determining whether allocating further resources to the query sub-plan associated with the minimum process cost value is profitable, and responsive to determining that allocating further computing resources to the query sub-plan is not profitable, ceasing to allocate further computing resources to the query sub-plan.

18. A system configured to allocate machines in a grid to a query plan, the system comprising:

a stored query plan comprising a plurality of query sub-plans and associated stored estimates of an amount of data to be processed by respective sub-plans of the query plan;

a machine allocator comprising a graph representation of query segments of the query plan and the machines, wherein the graph representation represents a cost of processing a query segment at respective of the machines and a cost of communicating between the machines, wherein the machine allocator finds a shortest path in the graph representation and allocates machines in the shortest path to respective query segments of the query plan; and

a stored allocation of computing resources to respective sub-plans of the query plan.

19. The system of claim 18 wherein the graph representation comprises a representation of intra-processor communication cost for a multi-processor machine.

20. The system of claim 18 wherein the machine allocator is operable to cease allocating machines to a particular query sub-plan responsive to determining that there are no further estimated performance gains.