Method for optimizing processing of join queries by determining optimal processing order and assigning optimal join methods to each of the join operations

A computer-implemented join optimization method for optimizing processing of a query for retrieval of data from a relational computer database wherein said database comprises a plurality of relations, and said data retrieval comprises performing a plurality of join operations on a plurality of said relations, said join optimization method comprising the steps of:

• (a) randomly assigning a join method to each of said join operations to produce a current join method scheme;
• (b) selecting a subset of said join operations to produce a current join order scheme of said join operations;
• (c) using a Krishanmurthy, Boral and Zaniolo (KBZ) Algorithm on said current join order scheme to produce a KBZ ordered sequence of join operations;
• (d) arranging said KBZ ordered sequence of join operations into said current join order scheme using a cost optimization ordering process;
• (e) selecting join methods for each of said join operations in said current join order scheme using a cost optimization join method process to produce said current join method scheme;
• (f) calculating a cost value for said current join order scheme said current join method scheme repeating steps (c) through (e) until there is no decrease in the cost value for said current join order scheme and said current join method scheme;
• and
• (g) repeating steps (a) through (f) a plurality of times to produce a set of current join order scheme with associated current join method schemes for each order in said set and identifying an optimal join order sequence with associated join methods, wherein said optimal join order sequence is a sequence in said set of current join order having a lowest cost.

A computer-implemented method for optimizing processing of a query to retrieve relations from a relational database wherein said query calls for performing a plurality of join operations on a plurality of said relations, said join optimization method comprising the steps of:

• (a) selecting a subset of said join operations to provide a maximum acyclic grouping to form a current join order scheme;
• (b) randomly assigning a join method to each of said join operations to form a current join method scheme;
• (c) using a Krishanmurthy, Boral and Zaniolo (KBZ) Algorithm on said current join order scheme with said current join method scheme to produce a KBZ ordered sequence of join operations;
• (d) determining a cost for said KBZ ordered join sequence;
• (e) determining costs for a plurality of alternate permutations of said KBZ ordered join sequence;
• (f) repeating step (e) until said cost of a permutation is less than the cost of said KBZ ordered join sequence or all permutations have been tried, and assigning to said current join order scheme said permutation having a lowest cost;
• (g) for each of the join operations in said current join order scheme assigning a candidate join method and determining a cost for said join operations with said candidate join method, and assigning the join methods producing a lowest cost for the current join order scheme as said current join method scheme;
• (h) repeating steps (c) through (g) until there is no decrease in the cost for the current join order scheme and current join method scheme;
• and
• (i) repeating steps (a) through (h) a polynomial number of times to produce a set of current join order scheme and current join method schemes, wherein steps (c) through (g) are repeated R.sup.2 times, where R is the number of said relations.