System and method for processing database queries

A computer program product having a non-transitory computer-readable storage medium storing computer-executable code for processing queries to a database, the code comprising:

• a query reception module configured to receive a database query, wherein the query implicates a set of tables associated with the database that must be joined to satisfy the query;
• a subset module configured to divide the set of tables into a plurality of subsets of tables based on information describing relationships between tables in the set of tables, the subset module configured to:
• represent the set of tables as a graph comprising nodes and edges, wherein nodes correspond to tables and edges correspond to relationships between tables;
• assign 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;
• perform a weighted depth first traversal of the graph to combine tables into subsets of tables based on weights of edges;
• an intermediate join module configured to determine subset join orders that separately order the tables within the subsets of tables, the intermediate join module configured to:
• determine 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, select 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;
• and
• a final join module configured to determine a final join order that orders the subset join orders, thereby ordering all of the tables in the set;
• and
• an optimizer module configured to generate 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.

A system configured to process queries to a database, the system comprising:

• a database server comprising one or more processors configured to execute one or more computer program modules;
• and
• a memory storing a plurality of computer program modules comprising:
• a query reception module configured to receive a database query, wherein the query implicates a set of tables associated with the database that must be joined to satisfy the query;
• a subset module configured to divide the set of tables into a plurality of subsets of tables based on information describing relationships between tables in the set of tables, the subset module configured to:
• represent the set of tables as a graph comprising nodes and edges, wherein nodes correspond to tables and edges correspond to relationships between tables;
• assign 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;
• perform a weighted depth first traversal of the graph to combine tables into subsets of tables based on weights of edges;
• an intermediate join module configured to determine subset join orders that separately order the tables within the subsets of tables, the intermediate join module configured to:
• determine 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, select 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;
• and
• a final join module configured to determine a final join order that orders the subset join orders, thereby ordering all of the tables in the set;
• and
• an optimizer module configured to generate 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.

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 performs join operations based on a set of tables;
• 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, wherein a weight for an edge is assigned based on information describing a relationship between tables corresponding to the edge;
• performing a weighted depth first traversal of the graph to combine tables into subsets of tables based on weights of edges;
• 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.