Back to results
US 9,767,150 B2Granted
System and method for processing database queries
AssigneeParAccel LLC
InventorsRichard L. Cole, Yijou Chen, William J. McKenna, Sergei Perfilov, Aman Sinha, Eugene Szedenits, Jr.
Life of this patent
Estimating the term…
Abstract
A system and/or method are implemented to process queries to a database. In particular, the processing of queries to the database is enhanced by enhancing the determination of join orders of tables implicated in queries. Join orders between relatively large numbers of tables are determined by dividing the set of tables to be ordered into a plurality of subsets of tables, and ordering the individual subsets of tables.
Claims26
A method for processing database queries, the method comprising:
- receiving, by a database system storing a set of tables, a database query specifying a join of the 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 including nodes and edges, the nodes corresponding to the tables and the edges corresponding to the relationships between the tables,
- assigning weights to the edges, a weight of an edge determined based on parameters describing a set of relationships between tables corresponding to the edge, and
- performing a weighted depth first traversal of the graph to combine the tables into the plurality of subsets of tables;
- for each of the plurality of subsets of tables, determining subset join order for the tables within the subset of tables;
- responsive to determining the subset join order for each of the plurality of tables, determining a final join order for all the tables of the set of tables by ordering the subset join orders;
- and
- generating an execution plan for the database query responsive to determining the final join order.
6 more elements
A non-transitory computer readable storage medium storing instructions for:
- receiving, by a database system storing a set of tables, a database query specifying a join of the 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 including nodes and edges, the nodes corresponding to the tables and the edges corresponding to the relationships between the tables,
- assigning weights to the edges, a weight of an edge determined based on parameters describing a set of relationships between tables corresponding to the edge, and
- performing a weighted depth first traversal of the graph to combine the tables into the plurality of subsets of tables;
- for each of the plurality of subsets of tables, determining subset join order for the tables within the subset of tables;
- responsive to determining the subset join order for each of the plurality of tables, determining a final join order for all the tables of the set of tables by ordering the subset join orders;
- and
- generating an execution plan for the database query responsive to determining the final join order.
6 more elements
A computer-implemented system for processing database queries, the system comprising:
- a computer processor;
- and
- a non-transitory computer-readable storage medium storing instructions for:
- receiving, by a database system storing a set of tables, a database query specifying a join of the 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 including nodes and edges, the nodes corresponding to the tables and the edges corresponding to the relationships between the tables,
- assigning weights to the edges, a weight of an edge determined based on parameters describing a set of relationships between tables corresponding to the edge, and
- performing a weighted depth first traversal of the graph to combine the tables into the plurality of subsets of tables;
- for each of the plurality of subsets of tables, determining subset join order for the tables within the subset of tables;
- responsive to determining the subset join order for each of the plurality of tables, determining a final join order for all the tables of the set of tables by ordering the subset join orders;
- and
- generating an execution plan for the database query responsive to determining the final join order.
9 more elements
Dependencies are inferred from the claim text.