Database query optimization apparatus and method that represents queries as graphs
First Claim
1. An apparatus comprising:
- at least one processor;
a memory coupled to the at least one processor; and
an optimizer residing in the memory and executed by the at least one processor, the optimizer analyzing an expression and generating from the expression a graph that includes at least one node, the optimizer generating from the graph an execution plan for the expression, the execution plan comprising a plurality of execution plans that correspond to different portions of the graph.
1 Assignment
0 Petitions
Accused Products
Abstract
A database query optimizer constructs a graph comprising nodes, relations, and expressions. The query optimizer then constructs execution plans for sub-parts of the graph. The combination of execution plans make up the overall execution plan for the query. The execution plan information is appended to the graph itself, allowing changing an execution plan in one portion of the graph without necessarily changing execution plans in other portions of the graph. By representing a query using the graph of the preferred embodiments that includes execution plan information, the query optimizer is able to evaluate the execution plans of different options quickly and efficiently, thereby enhancing the performance of the query optimizer.
147 Citations
20 Claims
-
1. An apparatus comprising:
-
at least one processor;
a memory coupled to the at least one processor; and
an optimizer residing in the memory and executed by the at least one processor, the optimizer analyzing an expression and generating from the expression a graph that includes at least one node, the optimizer generating from the graph an execution plan for the expression, the execution plan comprising a plurality of execution plans that correspond to different portions of the graph. - View Dependent Claims (2, 3, 4)
-
-
5. An apparatus comprising:
-
at least one processor;
a memory coupled to the at least one processor;
a database residing in the memory;
a database query optimizer residing in the memory and executed by the at least one processor, the database query optimizer processing a query to the database, the database query optimizer comprising;
a graph builder that generates from the query a graph that includes at least one node; and
an execution plan generator that generates from the graph an execution plan for the query, the execution plan comprising a plurality of execution plans that correspond to different portions of the graph. - View Dependent Claims (6, 7, 8, 9)
-
-
10. A method for evaluating an expression comprising the steps of:
-
reading the expression;
generating from the expression a graph that includes at least one node;
generating from the graph an execution plan for the expression, the execution plan comprising a plurality of execution plans that correspond to different portions of the graph. - View Dependent Claims (11, 12, 13)
-
-
14. A program product comprising:
-
(A) an optimizer that analyzes an expression and generates from the expression a graph that includes at least one node, the optimizer generating from the graph an execution plan for the expression, the execution plan comprising a plurality of execution plans that correspond to different portions of the graph; and
(B) computer-readable signal bearing media bearing the optimizer. - View Dependent Claims (15, 16, 17, 18, 19, 20)
-
Specification