System and methodology for generating bushy trees using a left-deep tree join enumeration algorithm

In a database system, a method for generating a bushy trees during optimization of a database query, the method comprising:

• receiving a database query specifying at least one join condition between two or more database tables;
• identifying each query block within said query, said query block comprising an atomic block of said query;
• building a query optimization graph for each query block, said query optimization graph including plan nodes representing subplans and quantifiers of each query block;
• constructing a join tree for each subplan based upon selecting access methods, join methods, and join order for plan nodes of said query optimization graph having favorable execution costs;
• constructing an optimal access plan for each query block based upon said join tree constructed for each subplan;
• and
• generating a bushy execution tree based upon the optimal access plan determined for each query block.

In a database system, a method for optimizing execution of a query, the method comprising:

• receiving a query specifying selection of data from a plurality of database tables;
• enumerating candidate plan segments for inclusion in an access plan for selecting data specified by the query, said candidate plan segments representing alternative strategies for joining relations and selecting data;
• for each query block comprising an atomic portion of said query, determining an optimal access plan by performing the substeps of:
• placing a candidate plan segment in a partial access plan being generated for said query block;
• evaluating said partial access plan including said candidate plan segment;
• if said partial access plan is less favorable than a complete access plan previously identified for said query block, pruning said candidate plan segment;
• otherwise, adding an additional candidate plan segment to said partial access plan and repeating the above steps until a complete access plan for said query block is generated;
• retaining a complete access plan if it is more favorable than other complete access plans previously generated for the query block;
• and
• otherwise pruning a complete access plan which is less favorable than other complete access plans;
• and
• generating a query execution plan based upon the optimal access plan determined for each query block.