Global optimization of correlated subqueries and exists predicates
First Claim
1. A method of optimizing an SQL query in a computer having a memory, the SQL query being performed by the computer to retrieve data from a relational database stored in one or more electronic storage devices coupled to the computer, the method comprising the steps of:
- (a) reducing the query in the memory of the computer by labeling query blocks, relations and predicate operands in the query according to their scope using an ordered set of query block numbers, and by determining minimum relation sets for predicate operands and predicate properties in the query;
(b) generating a plurality of join plans in the memory of the computer by applying a predetermined set of rules to the labels of the query blocks, relations and predicate operands to determine which relations can be joined together and which predicates can be applied to a particular pair of relations; and
(c) selecting a join plan in the memory of the computer from the plurality of join plans, wherein the selected join plan has a least performance cost associated therewith.
2 Assignments
0 Petitions
Accused Products
Abstract
A method of optimizing a query and its subqueries together in a global manner regardless of the nesting levels. All joins in different nesting levels are effectively converted into joins in the same level by assigning a nesting level attribute to relations, assigning properties to the predicate, and assigning nesting level attributes and minimum relation set attributes to join predicate operands. The joins and their predicates are then considered as if they were contained in only the main query according to a set of rules based on the attributes of the relations and the join predicates.
85 Citations
18 Claims
-
1. A method of optimizing an SQL query in a computer having a memory, the SQL query being performed by the computer to retrieve data from a relational database stored in one or more electronic storage devices coupled to the computer, the method comprising the steps of:
-
(a) reducing the query in the memory of the computer by labeling query blocks, relations and predicate operands in the query according to their scope using an ordered set of query block numbers, and by determining minimum relation sets for predicate operands and predicate properties in the query; (b) generating a plurality of join plans in the memory of the computer by applying a predetermined set of rules to the labels of the query blocks, relations and predicate operands to determine which relations can be joined together and which predicates can be applied to a particular pair of relations; and (c) selecting a join plan in the memory of the computer from the plurality of join plans, wherein the selected join plan has a least performance cost associated therewith. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. An apparatus for optimizing an SQL query, comprising:
-
(a) a computer having a memory and one or more electronic storage devices coupled thereto, the data storage devices storing a relational database; (b) means, performed by the computer, for accepting the SQL query into the memory of the computer, the SQL query being performed by the computer to retrieve data from a relational database stored in the electronic storage devices; (c) means, performed by the computer, for reducing the query in the memory of the computer by labeling query blocks, relations and predicate operands in the query according to their scope using an ordered set of query block numbers, and by determining minimum relation sets for predicate operands and predicate properties in the query; (d) means, performed by the computer, for generating a plurality of join plans in the memory of the computer by applying a predetermined set of rules to the labels of the query blocks, relations and predicate operands to determine which relations can be joined together and which predicates can be applied to a particular pair of relations; and (e) means, performed by the computer, for selecting a join plan in the memory of the computer from the plurality of join plans, wherein the selected join plan has a least performance cost associated therewith. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
13. A program storage device, readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for executing an SQL query in a computer having a memory, the SQL query being performed by the computer to retrieve data from a relational database stored in one or more electronic storage devices coupled to the computer, the method comprising the steps of:
-
(a) reducing the query in the memory of the computer by labeling query blocks, relations and predicate operands in the query according to their scope using an ordered set of query block numbers, and by determining minimum relation sets for predicate operands and predicate properties in the query; (b) generating a plurality of join plans in the memory of the computer by applying a predetermined set of rules to the labels of the query blocks, relations and predicate operands to determine which relations can be joined together and which predicates can be applied to a particular pair of relations; and (c) selecting a join plan in the memory of the computer from the plurality of join plans, wherein the selected join plan has a least performance cost associated therewith. - View Dependent Claims (14, 15, 16, 17, 18)
-
Specification