Patent ID: 8402469

Claim:
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 comprising query-sub plans until the query plan segments have no more than one query sub-plan level, thereby forming a provisional allocation; computing sub-plan workload densities for respective query sub-plan levels of a query plan segment comprising the query plan; wherein the splitting the query plan into query plan segments comprises: splitting the query plan segment comprising the query plan at a point in the query plan segment comprising the query plan where a summation of level workload densities of different consecutive query sub-plan levels of the query sub-plan levels exceeds half of a total workload density for the query plan segment comprising the query plan; wherein the computing resources in the grid comprise a first computing resource and a second computing resource and the query plan segments comprise a first query plan segment and a second query plan segment; wherein provisionally allocating computing resources in the grid to the query plan segments comprises: finding a shortest path between a source and a sink in a graph, the shortest path in the graph comprising a first edge representing a cost of processing the first query plan segment at the first computing resource and a second edge representing a cost of processing the second query plan segment at the second computing resource; 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.