Patent ID: 8510291

Claim:
A method for processing queries to a database, the method comprising: receiving, from a client processing platform, a database query at a database server, wherein the query implicates a set of tables associated with the database that must be joined to satisfy the query; dividing the set of tables into a plurality of subsets of tables, the dividing comprising: representing the set of tables as a graph comprising nodes and edges, wherein nodes correspond to tables and edges correspond to relationships between tables; assigning weights to edges of the graph based on factors including one or more of, a type of join corresponding to the edge, constraints between tables, and estimated selectivity; performing a weighted depth first traversal of the graph to combine tables into subsets of tables based on weights of edges; determining ordering of tables within each subset comprising: determining a first subset join order and a second subset join order for the subset of tables, wherein the first subset join order results in a first final join order for the set of tables and the second subset join order results in a second final join order for the set of tables; responsive to the first final join order resulting in a more efficient query plan for the set of tables compared to the second final join order, selecting the first subset join order for the subset of tables in spite of the first subset join order having a less efficient plan compared to the second subset join order for the subset of tables considered in isolation; determining a plurality of subset join orders that separately order the tables within the subsets of tables; determining a final join order that orders the subset join orders, thereby ordering all of the tables in the set; and generating an execution plan for the query, wherein the execution plan is generated responsive to determining the final join order that orders all of the tables in the set.