Iterative dynamic programming system for query optimization with bounded complexity

• US 5,671,403 A
• Filed: 12/30/1994
• Issued: 09/23/1997
• Est. Priority Date: 12/30/1994
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Young, Honesty Cheng, Shekita, Eugene Jon
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Homere, Jean Raymond
• Application Number:
  US08/367,502
• Time in Patent Office: 998 Days
• Field of Search: 395/600, 395/602, 395/603, 395/604, 395/605, 395/611, 364/DIG. 1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A query optimizer for optimizing join queries in a relational database system by iterative application of dynamic programming (DP) to select optimal subgraph join execution plans. Unlike traditional DP optimization methods, bounds on search space time and space complexity can be established and adjusted by imposing a subgraph threshold. Each bounded subgraph is selected using a greedy heuristic (GH) hill-climbing procedure or other similarly useful technique to build a low-cost execution plan. The low-cost GH subgraph execution plan is then discarded in favor of an optimal DP subgraph execution plan selected by a dynamic programming optimizer for each subgraph identified by the bounded GH optimization process. The complexity bound may be dynamically tuned to improve execution plan quality responsive to changes in query complexity.

Claims

1. A method for selecting an execution plan P for a N-way join query in a computer-implemented database system having a plurality of stored database relations, wherein said N-way join query is represented by a join graph G connecting each R_i of a plurality N+1 of relation nodes by a predicate edgeE_ij to another R_j of said relation node plurality to form a plurality N of connected node pairs (R_i, R_i) and wherein 1≦

i,j≦

N+1and N>

1 are positive integers, said method comprising the steps of;

(a) selecting from said join graph G for a threshold value T_L a subgraph G_L connecting a plurality N_L ≦

T_L of said relation nodes;

(b) selecting the optimal execution plan P_L from among all feasible execution plans for joining said subgraph G_L of said relation nodes;

(c) replacing said relation node subgraph G_L in said join graph G with a relation node R_L representing the relation produced by said optimal execution plan P_L ; and

(d) repeating said selecting steps (a)-(b) and said replacing step (c) until said execution plan P is selected for said join graph G.

2. The method of claim 1 wherein the first said selecting step is performed according to a greedy heuristic procedure for minimizing the join execution cost for said subgraph G_L.

3. A method for selecting an execution plan P for a N-way join query in a computer-implemented database system having a plurality of stored database relations, wherein said N-way join query is represented by a join graph G connecting each R₁ of a plurality N+1 of relation nodes by a predicate edge E_ij to another R_j of said relation node plurality to form a plurality N of connected node pairs (R_i, R_j), wherein each said relation node R_i has a joinder number J_i corresponding to the number of said relations embraced thereby and wherein 1≦

i, j≦

N+1 and N>

1 are positive integers, said method comprising the steps of;

(a) selecting from said join graph G the connected node pair (R_i, R_j) having the lowest join execution cost of all said connected node pairs in said join graph G;

(b) comparing to a threshold T_L the sum J_k =J_i +J_j of the joinder numbers associated with said selected node pair (R_i, R_j), wherein J_i ≧

J_j ;

(c) if J_k >

T_L selecting the optimal execution plan P_i from among all feasible execution plans for joining the plurality J_i of said relations embraced by said relation node R_i and resetting said joinder number J_i =1 therefor to indicate that said relation node R_i now embraces only the relation produced by said plan P_i, wherein 1≦

k≦

N+1 is a positive integer;

otherwise

(d) replacing said connected node pair (R_i, R_j) with a replacement node R_k having a joinder number J_k =J_i +J_j in said join graph G; and

(e) if at least one said connected node pair (R_i, R_j) remains in said join graph G, repeating said steps (a)-(d);

otherwise

(f) repeating said selecting step (c) for said replacement node R_k to select said execution plan P for said join graph G.

4. A query optimizer subsystem for selecting an execution plan P for a N-way join query in a computer-implemented database system having a data processor and a plurality of stored database relations, said subsystem comprising:

input means for accepting said N-way join query represented as a join graph G connecting each R_i of a plurality N+1 of relation nodes by a predicate edge E_ij to another R_j of said relation node plurality to form a plurality N of connected node pairs (R_i, R_j) and wherein 1<

i, j<

N+1 and N>

1 are positive integers;

greedy heuristic means coupled to said input means for selecting from said join graph G for a threshold value T_L a subgraph G_L connecting a plurality N_L ≦

T_L of said relation nodes according to a greedy heuristic procedure for minimizing the join execution cost for said subgraph G_L ;

dynamic programming means coupled to said greedy heuristic means for selecting the optimal execution plan P_L from among all feasible execution plans for joining said subset G_L of said relation nodes;

merger means coupled to said greedy heuristic means for replacing said relation node subgraph G_L in said join graph G with a relation node R_L representing the relation produced by said optimal execution plan P_L ; and

iteration means in said data processor for causing said greedy heuristic means, said dynamic programming means and said merger means to repeatedly select and replace said subgraph G_L until said optimal execution plan P is selected for said join graph G.

5. A query optimizer subsystem for selecting an execution plan P for a N-way join query in a computer-implemented database system having a data processor and a plurality of stored database relations, said subsystem comprising:

input means in said data processor for accepting said N-way join query represented as a join graph G connecting each R_i of a plurality N+1 of relation nodes by a predicate edge E_ij to another R_i of said relation node plurality to form a plurality N of connected node pairs (R_i, R_x), wherein each said relation node R_i has a joinder number J_i corresponding to the number of said relations embraced thereby and wherein 1≦

i, j≦

N+1 and N>

1 are positive integers;

two-way plan selection means coupled to said input means for selecting from said join graph G the connected node pair (R_i, R_j) having the lowest join execution cost of all said connected node pairs in said join graph G;

threshold means coupled to said two-way plan selection means for comparing to a threshold T_L the sum J_k =J_i +J_j of the joinder numbers associated with said selected node pair (R_i, R_x), wherein J_i ≧

J_j ;

dynamic programming means coupled to said thresholding means for selecting, when J_k >

T_L, the optimal execution plan P_i from among all feasible execution plans for joining the plurality J_i of said relations embraced by said relation node R_i and for resetting said joinder number J_i =1 therefor to indicate that said relation node R_i now embraces only the relation produced by said plan P_i, wherein 1≦

k≦

N+l is a positive integer;

first merger means coupled to said thresholding means for replacing, when J_k ≦

T_L, said connected node pair (R₁, R_j) with a replacement node R_k having a joinder number J_k =J_i +J_j in said join graph G; and

iteration means for causing said two-way plan selection means, said thresholding means, said dynamic programming means and said merger means to repeatedly select, compare, select and replace said connected node pairs until said execution plan P is selected for said join graph G.

6. A computer program product for use with a query optimizer system for selecting an execution plan P for a N-way join query in a computer-implemented database system having a plurality of stored database relations, wherein said N-way join query is represented by a join graph G connecting each R_i of a plurality N+1 of relation nodes by a predicate edge E_ij to another R_i of said relation node plurality to form a plurality N of connected node pairs (R_i, R_l) and wherein 1<

i, j<

N+1 and N>

1 are positive integers, said computer program product comprising;

a recording medium;

first means, recorded on said recording medium, for directing said system to select from said join graph G for a threshold value T_L a subgraph G_F connecting a plurality N_L ≦

T_L of said relation node;

second means, recorded on said recording medium, for directing said system to select the optimal execution plan P_L from among all feasible execution plans for joining said subgraph G_L of said relation nodes;

means, recorded on said recording medium, for directing said system to replace said relation node subgraph G_L in said join graph G with a relation node R_L representing the relation produced by said optimal execution plan P_L ; and

means, recorded on said recording medium, for directing said system to repeat operation of said first means for directing to select, said second means for directing to select and said means for directing to replace until said execution plan P is selected for said join graph G.