US5548758A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Optimization of SQL queries using early-out join transformations of column-bound relational tables
Assignee: International Business Machines Corp
•
Filing: 1995-06-05
•
Granted: 1996-08-20
•
Expires: 2015-06-05
Abstract
Abstract A method and apparatus for optimizing SQL queries in a relational database management system uses early-out join transformations. An early-out join comprises a many-to-one existential join, wherein the join scans an inner table for a match for each row of the outer table and terminates the scan for each row of the outer table when a single match is found in the inner table. To transform a many-to-many join to an early-out join, the query must include a requirement for distinctiveness, either explicitly or implicitly, in one or more result columns for the join operation. Distinctiveness can be specified using the DISTINCT keyword in the SELECT clause or can be implied from the predicates present in the query. The early-out join transformation also requires that no columns of the inner table be referenced after the join, or if an inner table column is referenced after the join, that each referenced column be "bound". A referenced column can be bound in one of three ways: (1) an inner table column can be bound to a constant through an equality predicate, (2) an inner table column can be bound to an outer table column, or (3) an inner table column can be bound to a correlated value, wherein the correlated value originates outside the query block. In all three cases, an inner table column can be bound through the transitivity of equality predicates.
Inventors
- 👤 Mir H. Pirahesh
- 👤 Ting Y. Leung
- 👤 Guy M. Lohman
- 👤 Eugene J. Shekita
- 👤 David E. Simmen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 13:46
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24534; G06F16/24537; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99935
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
230 words
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 an electronic storage device coupled to the computer, and the SQL query including a join operation for an outer table and an inner table in the relational database, the method comprising the steps of: (a) examining the query in the memory of the computer to determine whether the query includes a requirement for distinctiveness in one or more result columns of the join operation; (b) examining the query in the memory of the computer to determine whether one or more columns of the inner table are referenced in the query after the join operation is performed by the computer and whether each referenced column of the inner table is bound and is not involved in any length-sensitive expressions yet to be evaluated; and (c) performing, in the memory of the computer, an early-out join operation in place of the join operation when the query includes the requirement for distinctiveness and the referenced columns of the inner table are bound and are not involved in any length-sensitive expressions yet to be evaluated, further comprising the steps of scanning the inner table for a match for each row of the outer table and terminating the scanning step when the match is found.
Claim 2
Independent Claim
230 words
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 an electronic storage device coupled to the computer, and the SQL query including a join operation for an outer table and an inner table in the relational database, the method comprising the steps of: (a) examining the query in the memory of the computer to determine whether the query includes a requirement for distinctiveness in one or more result columns of the join operation; (b) examining the query in the memory of the computer to determine whether one or more columns of the inner table are referenced in the query after the join operation is performed by the computer and whether each referenced column of the inner table is bound and is not involved in any length-sensitive expressions yet to be evaluated; and (c) performing, in the memory of the computer, an early-out join operation in place of the join operation when the query includes the requirement for distinctiveness and the referenced columns of the inner table are bound and are not involved in any length-sensitive expressions yet to be evaluated, further comprising the steps of scanning the inner table for a match for each row of the outer table and terminating the scanning step when the match is found.
Claim 3
Dependent Claim
18 words
The method of claim 1, wherein the referenced column of the inner table is bound to a constant.
Claim 4
Dependent Claim
22 words
The method of claim 1, wherein the referenced column of the inner table is bound to a column of the outer table.
Claim 5
Dependent Claim
19 words
The method of claim 1, wherein the referenced column of the inner table is bound to a correlated value.
Claim 6
Dependent Claim
20 words
The method of claim 1, wherein the referenced column of the inner table is bound through a transitive equality predicate.
Claim 7
Dependent Claim
25 words
The method of claim 1, wherein the requirement for distinctiveness in the result columns for the join operation is explicitly set forth in the query.
Claim 8
Dependent Claim
25 words
The method of claim 1, wherein the requirement for distinctiveness in the result columns for the join operation is implicitly set forth in the query.
Claim 9
Independent Claim
286 words
An apparatus for optimizing an SQL query, comprising: (a) a computer having a memory and an electronic storage device coupled thereto, wherein the electronic storage device stores a relational database; (b) means, performed by the computer, for accepting an SQL query into the memory of the computer, the SQL query including a join operation for an outer table and an inner table stored in the relational database; (c) means, performed by the computer, for examining the query in the memory of the computer to determine whether the query includes a requirement for distinctiveness in one or more result columns of the join operation; (d) means, performed by the computer, for examining the query in the memory of the computer to determine whether one or more columns of the inner table are referenced in the query after the join operation is performed and whether each referenced column of the inner table is bound and is not involved in any length-sensitive expressions yet to be evaluated; and (e) means, performed by the computer, for performing an early-out join operation in place of the join operation when the query includes the requirement for distinctiveness and the referenced columns of the inner table are bound and are not involved in any length-sensitive expressions yet to be evaluated, the means for executing further comprising means for retrieving the inner and outer tables from the relational database stored in the electronic storage device, means for storing the inner and outer tables in the memory of the computer, means for scanning the inner table in the memory of the computer for a match for each row of the outer table, and means for terminating the means for scanning when the match is found.
Claim 10
Independent Claim
286 words
An apparatus for optimizing an SQL query, comprising: (a) a computer having a memory and an electronic storage device coupled thereto, wherein the electronic storage device stores a relational database; (b) means, performed by the computer, for accepting an SQL query into the memory of the computer, the SQL query including a join operation for an outer table and an inner table stored in the relational database; (c) means, performed by the computer, for examining the query in the memory of the computer to determine whether the query includes a requirement for distinctiveness in one or more result columns of the join operation; (d) means, performed by the computer, for examining the query in the memory of the computer to determine whether one or more columns of the inner table are referenced in the query after the join operation is performed and whether each referenced column of the inner table is bound and is not involved in any length-sensitive expressions yet to be evaluated; and (e) means, performed by the computer, for performing an early-out join operation in place of the join operation when the query includes the requirement for distinctiveness and the referenced columns of the inner table are bound and are not involved in any length-sensitive expressions yet to be evaluated, the means for executing further comprising means for retrieving the inner and outer tables from the relational database stored in the electronic storage device, means for storing the inner and outer tables in the memory of the computer, means for scanning the inner table in the memory of the computer for a match for each row of the outer table, and means for terminating the means for scanning when the match is found.
Claim 11
Dependent Claim
18 words
The apparatus of claim 8, wherein the referenced column of the inner table is bound to a constant.
Claim 12
Dependent Claim
22 words
The apparatus of claim 8, wherein the referenced column of the inner table is bound to a column of the outer table.
Claim 13
Dependent Claim
19 words
The apparatus of claim 8, wherein the referenced column of the inner table is bound to a correlated value.
Claim 14
Dependent Claim
20 words
The apparatus of claim 8, wherein the referenced column of the inner table is bound through a transitive equality predicate.
Claim 15
Dependent Claim
25 words
The apparatus of claim 8, wherein the requirement for distinctiveness in the result columns for the join operation is explicitly set forth in the query.
Claim 16
Dependent Claim
25 words
The apparatus of claim 8, wherein the requirement for distinctiveness in the result columns for the join operation is implicitly set forth in the query.
Claim 17
Dependent Claim
250 words
A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for 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 an electronic storage device coupled to the computer, and the SQL query including a join operation for an outer table and an inner table in the relational database, the method comprising the steps of: (a) examining the query in the memory of the computer to determine whether the query includes a requirement for distinctiveness in one or more result columns of the join operation; (b) examining the query in the memory of the computer to determine whether one or more columns of the inner table are referenced in the query after the join operation is performed by the computer and whether each referenced column of the inner table is bound and is not involved in a length-sensitive expression yet to be evaluated; and (c) performing, in the memory of the computer, an early-out join operation in place of the join operation when the query includes the requirement for distinctiveness and the referenced columns of the inner table are bound and are not involved in a length-sensitive expression yet to be evaluated, further comprising the steps of scanning the inner table for a match for each row of the outer table and terminating the scanning step when the match is found.
Claim 18
Dependent Claim
250 words
A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for 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 an electronic storage device coupled to the computer, and the SQL query including a join operation for an outer table and an inner table in the relational database, the method comprising the steps of: (a) examining the query in the memory of the computer to determine whether the query includes a requirement for distinctiveness in one or more result columns of the join operation; (b) examining the query in the memory of the computer to determine whether one or more columns of the inner table are referenced in the query after the join operation is performed by the computer and whether each referenced column of the inner table is bound and is not involved in a length-sensitive expression yet to be evaluated; and (c) performing, in the memory of the computer, an early-out join operation in place of the join operation when the query includes the requirement for distinctiveness and the referenced columns of the inner table are bound and are not involved in a length-sensitive expression yet to be evaluated, further comprising the steps of scanning the inner table for a match for each row of the outer table and terminating the scanning step when the match is found.
Claim 19
Dependent Claim
20 words
The program storage device of claim 15, wherein the referenced column of the inner table is bound to a constant.
Claim 20
Dependent Claim
24 words
The program storage device of claim 15, wherein the referenced column of the inner table is bound to a column of the outer table.
Claim 21
Dependent Claim
21 words
The program storage device of claim 15, wherein the referenced column of the inner table is bound to a correlated value.
Claim 22
Dependent Claim
22 words
The program storage device of claim 15, wherein the referenced column of the inner table is bound through a transitive equality predicate.
Claim 23
Dependent Claim
27 words
The program storage device of claim 15, wherein the requirement for distinctiveness in the result columns for the join operation is explicitly set forth in the query.
Claim 24
Dependent Claim
27 words
The program storage device of claim 15, wherein the requirement for distinctiveness in the result columns for the join operation is implicitly set forth in the query.
References Cited (Backward Citations)
US4506326A
Cited
US4829427A
Cited
US4769772A
Cited
US5091852A
Cited
US5317742A
Cited
US5367675A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-08-20 | 2000-02-19 | 2000-08-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-08-20 | 2004-02-19 | 2004-08-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-08-20 | 2008-02-19 | 2008-08-20 | $7700.00 | Window Closed / Lapsed |