Left outer join elimination on key

• US 20030009450A1
• Filed: 06/21/2001
• Published: 01/09/2003
• Est. Priority Date: 06/21/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kiernan, Gerald George, Shanmugasundaram, Jayavel
• Granted Patent: US 6,721,730 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A query optimization technique that determines whether any column from a right quantifier of a left outer join query is projected out of the query. If not, then all predicates in an ON clause are removed from the left outer join query, the right quantifier is removed from the left outer join query, and the left outer join query is converted to a simple select query. A number of steps are performed to determine whether any of the columns quantified by the right quantifier participate in a projection list of the query. A set of equivalence class columns is computed for the query, wherein the equivalence classes are derived from equi-join predicates in the query. A set of columns quantified by the right quantifier across the computed set of equivalence classes is computed. A determination is made whether a subset of the set of columns form a key for the right quantifier. If the right quantifier columns are not projected out of the query, then the optimization may be performed.

Claims

1. A method of performing a query in a computer to retrieve data from a database, comprising:

(a) determining whether any column from a right quantifier of a left outer join query is projected out of the query; and

(b) if not, then removing all predicates in an ON clause of the left outer join query, removing the right quantifier from the left outer join query, and converting the left outer join query to a simple select query.

2. The method of claim 1, wherein the determining step (a) comprises:

(1) determining whether a quantifier is in a SELECT operator that implements a left outer join;

(2) determining whether the quantifier is a right quantifier of the SELECT operator; and

(3) determining whether any of the columns quantified by the right quantifier participate in a projection list of the query, wherein the determining step (3) comprises;

(i) computing a set of equivalence class columns for the query, wherein the set of equivalence classes are derived from equi-join predicates in the query;

(ii) computing a set of columns quantified by the right quantifier across the computed set of equivalence classes; and

(iii) determining whether a subset of the set of columns form a key for the right quantifier.

3. A computer-implemented apparatus for performing a query, comprising:

a computer, wherein the query is performed in the computer to retrieve data from a database;

logic, performed by the computer system, for;

(a) determining whether any column from a right quantifier of a left outer join query is projected out of the query; and

(b) if not, then removing all predicates in an ON clause of the left outer join query, removing the right quantifier from the left outer join query, and converting the left outer join query to a simple select query.

4. The apparatus of claim 3, wherein the logic for determining (a) comprises logic for:

(1) determining whether a quantifier is in a SELECT operator that implements a left outer join;

(2) determining whether the quantifier is a right quantifier of the SELECT operator; and

(3) determining whether any of the columns quantified by the right quantifier participate in a projection list of the query, wherein the logic for determining (3) comprises logic for;

(i) computing a set of equivalence class columns for the query, wherein the set of equivalence classes are derived from equi-join predicates in the query;

(ii) computing a set of columns quantified by the right quantifier across the computed set of equivalence classes; and

(iii) determining whether a subset of the set of columns form a key for the right quantifier.

5. An article of manufacture embodying logic for performing a query in a computer to retrieve data from a database, the logic comprising:

(a) determining whether any column from a right quantifier of a left outer join query is projected out of the query; and

(b) if not, then removing all predicates in an ON clause of the left outer join query, removing the right quantifier from the left outer join query, and converting the left outer join query to a simple select query.

6. The article of manufacture of claim 5, wherein the determining step (a) comprises:

(1) determining whether a quantifier is in a SELECT operator that implements a left outer join;

(2) determining whether the quantifier is a right quantifier of the SELECT operator; and

(3) determining whether any of the columns quantified by the right quantifier participate in a projection list of the query, wherein the determining step (3) comprises;

(i) computing a set of equivalence class columns for the query, wherein the set of equivalence classes are derived from equi-join predicates in the query;

(ii) computing a set of columns quantified by the right quantifier across the computed set of equivalence classes; and

(iii) determining whether a subset of the set of columns form a key for the right quantifier.