Method and apparatus for efficiently evaluating exists and not exists equivalent subqueries
First Claim
1. A computer-implemented method of transforming an EXISTS-equivalent subquery to query components that may be processed more efficiently than the EXISTS-equivalent subquery, the method comprising the steps of:
- A) removing at least one logical expression from a WHERE clause in said EXISTS-equivalent subquery to produce a revised EXISTS-equivalent subquery;
B) generating one or more substitute query components by performing the following steps for each of said at least one logical expression removed from said WHERE clause;
B1) determining whether said logical expression contains a reference to a table in a FROM list of a SELECT statement in said EXISTS-equivalent subquery,B2) determining a substitute query component for said logical expression based ona) whether said logical expression contains a reference to a table in said FROM list of said SELECT statement in said EXISTS-equivalent subquery, andb) whether said EXISTS-equivalent subquery is equivalent to an EXISTS subquery or to a NOT EXISTS subquery; and
C) replacing the EXISTS-equivalent subquery with said revised EXISTS-equivalent subquery and said one or more substitute query components.
3 Assignments
0 Petitions
Accused Products
Abstract
A method for transforming database queries that have EXISTS-equivalent subqueries (i.e. subqueries that are semantically equivalent to EXISTS or NOT EXISTS subqueries) is disclosed. Logical expressions are removed from a WHERE CLAUSE in the original EXISTS-equivalent subquery to produce a revised subquery. For each of the logical expressions that are removed, a substitute query component is generated based on whether (1) the logical expression contains any reference to any table in a FROM-list in the EXISTS-equivalent subquery and (2) the original EXISTS-equivalent subquery is equivalent to an EXISTS or a NOT EXISTS subquery. The transformed query is created by replacing the original EXISTS-equivalent subquery with the revised subquery and the query components that were generated for each of removed logical expressions. Some of the substitute query components, including the revised subquery, may be merged based on knowledge of access paths. These transformation techniques may be applied after converting the EXISTS-equivalent subquery to an EXISTS or NOT EXISTS subquery. Alternatively, the techniques may be applied directly to queries that contain EXISTS-equivalent subqueries without converting the EXISTS-equivalent subqueries to EXISTS or NOT EXISTS subqueries. The transformed queries produced by this technique may be processed more efficiently by database applications than the original queries.
-
Citations
18 Claims
-
1. A computer-implemented method of transforming an EXISTS-equivalent subquery to query components that may be processed more efficiently than the EXISTS-equivalent subquery, the method comprising the steps of:
-
A) removing at least one logical expression from a WHERE clause in said EXISTS-equivalent subquery to produce a revised EXISTS-equivalent subquery; B) generating one or more substitute query components by performing the following steps for each of said at least one logical expression removed from said WHERE clause; B1) determining whether said logical expression contains a reference to a table in a FROM list of a SELECT statement in said EXISTS-equivalent subquery, B2) determining a substitute query component for said logical expression based on a) whether said logical expression contains a reference to a table in said FROM list of said SELECT statement in said EXISTS-equivalent subquery, and b) whether said EXISTS-equivalent subquery is equivalent to an EXISTS subquery or to a NOT EXISTS subquery; and C) replacing the EXISTS-equivalent subquery with said revised EXISTS-equivalent subquery and said one or more substitute query components. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A computer-readable medium having stored thereon sequences of instructions, said sequences of instructions including instructions which, when executed by a processor, cause said processor to perform the steps of:
-
A) removing at least one logical expression from a WHERE clause in an EXISTS-equivalent subquery to produce a revised EXISTS-equivalent subquery; B) generating one or more substitute query components by performing the following steps for each of said at least one logical expression removed from said WHERE clause; B1) determining whether said logical expression contains a reference to a table in a FROM list of a SELECT statement in said EXISTS-equivalent subquery, B2) determining a substitute query component for said logical expression based on a) whether said logical expression contains a reference to a table in said FROM list of said SELECT statement in said EXISTS-equivalent subquery, and b) whether said EXISTS-equivalent subquery is equivalent to an EXISTS subquery or to a NOT EXISTS subquery; and C) replacing the EXISTS-equivalent subquery with said revised EXISTS-equivalent subquery and said one or more substitute query components. - View Dependent Claims (8, 9, 10, 11)
-
-
12. A computer-implemented method of transforming an EXISTS-equivalent subquery to query components that may be processed more efficiently than the EXISTS-equivalent subquery, the method comprising the steps of:
-
A) removing at least one logical expression from a clause in said EXISTS-equivalent subquery to produce a revised EXISTS-equivalent subquery; B) determining one or more substitute query components for said at least one logical expression; and C) replacing the EXISTS-equivalent subquery with said revised EXISTS-equivalent subquery and said one or more substitute query components. - View Dependent Claims (13, 14, 15, 16, 17, 18)
-
Specification