Method, system, and program for selecting a join order for tables subject to a join operation

A system for selecting a join order for tables subject to a join operation, comprising:

• a computer readable medium;
• a database implemented in the computer readable medium including a plurality of database tables;
• means for estimating a join cost to perform joins on permutations of at least two of the tables, wherein each join permutation indicates an order of joining the tables;
• means for determining whether sufficient computational resources are available to perform a cost analysis of further join permutations of the tables;
• means for determining a restricted subset of remaining join permutations of at least two of the tables for which join costs have not been estimated that is less than all the remaining join permutations if sufficient computational resources are not available;
• means for estimating the join cost to perform joins on permutations of tables in the restricted subset;
• and
• means for using the estimated join costs to select one join permutation of all the tables having a lowest estimated cost.

An article of manufacture for selecting a join order for tables subject to a join operation, wherein the article of manufacture causes operations to be performed, the operations comprising:

• estimating a join cost to perform joins on permutations of at least two of the tables, wherein each join permutation indicates an order of joining the tables;
• determining whether sufficient computational resources are available to perform a cost analysis of further join permutations of the tables;
• determining a restricted subset of remaining join permutations of at least two of the tables for which join costs have not been estimated that is less than all the remaining join permutations if sufficient computational resources are not available;
• estimating the join cost to perform joins on permutations of tables in the restricted subset;
• and
• using the estimated join costs to select one join permutation of all the tables having a lowest estimated cost.