Method of optimizing a query having an existi subquery and a not-exists subquery
First Claim
Patent Images
1. A method of optimizing a query in a computer, the query being performed by the computer to retrieve data from a relational database stored in an electronic storage device coupled to the computer, the method comprising the steps of:
- (a) analyzing the query to determine whether the query includes a WHERE clause which contains an “
EXISTS”
subquery or the equivalent and a “
NOT EXISTS”
subquery or the equivalent;
(b) performing a subsumption test to determine whether the subqueries are subsumed or identical;
(c) if identical, adding a FALSE predicate to the WHERE clause of the query;
(d) if subsumed and not identical, performing a transformation of the query to merge the subqueries; and
(e) executing the query in the computer to retrieve data from the relational database.
1 Assignment
0 Petitions
Accused Products
Abstract
An optimization technique for SQL queries, a program storage device storing the optimization program, and an apparatus for optimizing a query is provided. A query is analyzed to determine whether it includes the WHERE clause which contains an “EXISTS” subquery and a “NOT EXISTS” subquery, or EXISTS-equivalent subqueries, in Boolean factor. If so, the subsumption test is performed on two subqueries. Then, the compensation predicate is applied to one of them, to perform the QGM transformation of the query. One subquery block is stacked on top of the other subquery block, in order to eliminate one subquery. This procedure allows the transformed query to perform more efficiently than the original query while providing same results. The query is then executed in the computer to efficiently retrieve data from the relational database.
121 Citations
12 Claims
-
1. A method of optimizing a query in a computer, the query being performed by the computer to retrieve data from a relational database stored in an electronic storage device coupled to the computer, the method comprising the steps of:
-
(a) analyzing the query to determine whether the query includes a WHERE clause which contains an “
EXISTS”
subquery or the equivalent and a “
NOT EXISTS”
subquery or the equivalent;
(b) performing a subsumption test to determine whether the subqueries are subsumed or identical;
(c) if identical, adding a FALSE predicate to the WHERE clause of the query;
(d) if subsumed and not identical, performing a transformation of the query to merge the subqueries; and
(e) executing the query in the computer to retrieve data from the relational database. - View Dependent Claims (2, 3, 4)
determining whether the “
EXISTS”
subquery is presented with an equivalent; and
if so, transforming the EXISTS-equivalent subquery into an “
EXISTS”
subquery.
-
-
3. The method according to claim 1, wherein the step (a) further comprises the steps of:
-
determining whether the “
NOT EXISTS”
subquery is presented with an equivalent; and
if so, transforming the NOT EXISTS-equivalent subquery into an “
NOT EXISTS”
subquery.
-
-
4. The method according to claim 1, wherein the step (d) of performing the transformation of the query including the QGM query transformation and the step (d) further comprises the steps of:
-
stacking the “
NOT EXISTS”
subquery block (A) on top of the “
EXISTS”
subquery block (B);
adding to output columns of the block B all columns necessary for the block A;
applying a nullability test to all said columns necessary for the block A;
if not all said columns nullable, designating a non-nullable column as a column C;
if all said columns nullable, adding a column C to said output columns of the block B and filling the column C with a pre-determined constant value;
transforming a compensation predicate CP, obtained during the subsumption test of the step (b), into the form of “
(C IS NULL) OR ((C IS NOT NULL) AND CP); and
applying the transformed compensation predicate to the block A to merge the subqueries.
-
-
5. An apparatus for optimizing a query, comprising:
-
a computer having an electronic storage device coupled thereto for storing a relational database, the query being performed by the computer to retrieve data from the relational database;
means, performed by the computer, for analyzing the query to determine whether the query includes a WHERE clause which contains an “
EXISTS”
subquery or the equivalent and a “
NOT EXISTS”
subquery or the equivalent;
means, performed by the computer, for performing a subsumption test to determine whether the subqueries are subsumed or identical;
means, performed by the computer, for adding a FALSE predicate to the WHERE clause of the query;
means, performed by the computer, for performing a transformation of the query to merge the subqueries; and
means, performed by the computer, for executing the query in the computer to retrieve data from the relational database. - View Dependent Claims (6, 7, 8)
means, performed by the computer, for determining whether the “
EXISTS”
subquery is presented with an equivalent; and
means, performed by the computer, for transforming the EXISTS-equivalent subquery into an “
EXISTS”
subquery.
-
-
7. The apparatus according to claim 5, wherein the means for analyzing the query further comprises:
-
means, performed by the computer, for determining whether the “
NOT EXISTS”
subquery is presented with an equivalent; and
means, performed by the computer, for transforming the NOT EXISTS-equivalent subquery into an “
NOT EXISTS”
subquery.
-
-
8. The apparatus according to claim 5, wherein the means for performing the transformation of the query further including the QGM query transformation means and comprises:
-
means, performed by the computer, for stacking the “
NOT EXISTS”
subquery block (A) on top of the “
EXISTS”
subquery block (B);
means, performed by the computer, for adding to output columns of the block B all columns necessary for the block A;
means, performed by the computer, for applying a nullability test to all said columns necessary for the block A;
means, performed by the computer, for designating a non-nullable column as a column C;
means, performed by the computer, for adding a column C to said output columns of the block B and filling the column C with a pre-determined constant value;
means, performed by the computer, for transforming a compensation predicate CP, obtained during the subsumption test, into the form of “
(C IS NULL) OR ((C IS NOT NULL) AND CP); and
means, performed by the computer, for applying the transformed compensation predicate to the block A to merge the subqueries.
-
-
9. A program storage device readable by a computer tangibly embodying a program of instructions executable by the computer to perform method steps for optimizing a query, the query being performed by the computer to retrieve data from a relational database stored in an electronic storage device coupled to the computer, the method comprising the steps of:
-
(a) analyzing the query to determine whether the query includes a WHERE clause which contains an “
EXISTS”
subquery or the equivalent and a “
NOT EXISTS”
subquery or the equivalent;
(b) performing a subsumption test to determine whether the subqueries are subsumed or identical;
(c) if identical, adding a FALSE predicate to the WHERE clause of the query;
(d) if subsumed and not identical, performing a transformation of the query to merge the subqueries; and
(e) executing the query in the computer to retrieve data from the relational database. - View Dependent Claims (10, 11, 12)
determining whether the “
EXISTS”
subquery is presented with an equivalent; and
if so, transforming the EXISTS-equivalent subquery into an “
EXISTS”
subquery.
-
-
11. The program storage device according to claim 9, wherein the step (a) further comprises the steps of:
-
determining whether the “
NOT EXISTS”
subquery is presented with an equivalent; and
if so, transforming the NOT EXISTS-equivalent subquery into an “
NOT EXISTS”
subquery.
-
-
12. The program storage device according to claim 9, wherein the step (d) of performing the transformation of the query including the QGM query transformation and the step (d) further comprises the steps of:
-
stacking the “
NOT EXISTS”
subquery block (A) on top of the “
EXISTS”
subquery block (B);
adding to output columns of the block B all columns necessary for the block A;
applying a nullability test to all said columns necessary for the block A;
if not all said columns nullable, designating a non-nullable column as a column C;
if all said columns nullable, adding a column C to said output columns of the block B and filling the column C with a pre-determined constant value;
transforming a compensation predicate CP, obtained during the subsumption test of the step (b), into the form of “
(C IS NULL) OR ((C IS NOT NULL) AND CP); and
applying the transformed compensation predicate to the block A to merge the subqueries.
-
Specification
-
- Resources
Litigation Campaign Assessment
Thank you for your request. You will receive a custom alert email when the Litigation Campaign Assessment is available.
×
-
Current AssigneeInternational Business Machines Corporation
-
Original AssigneeInternational Business Machines Corporation
-
InventorsTruong, Tuong Chanh, Leung, Ting Yu, Urata, Monica Sachiye
-
Primary Examiner(s)Homere, Jean R.
-
Assistant Examiner(s)Ali, Mohammad
-
Application NumberUS09/506,471Time in Patent Office1,111 DaysField of Search707/1-10, 707/103.RUS Class Current1/1CPC Class CodesG06F 16/24535 of sub-queries or viewsG06F 16/24542 Plan optimisationY10S 707/99932 Access augmentation or opti...
