US5548754A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Optimization of SQL queries using early-out join transformations
Assignee: International Business Machines Corp
•
Filing: 1995-02-07
•
Granted: 1996-08-20
•
Expires: 2015-02-07
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-27 17:08
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: 12
Claim 1
Independent Claim
198 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 (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 no columns of the inner table are referenced after the join operation, 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
198 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 (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 no columns of the inner table are referenced after the join operation, 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
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 4
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 5
Independent Claim
254 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 (e) means, performed by the computer, for executing an early-out join operation in place of the join operation when the query includes the requirement for distinctiveness and no columns of the inner table are referenced after the join operation, 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 6
Independent Claim
254 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 (e) means, performed by the computer, for executing an early-out join operation in place of the join operation when the query includes the requirement for distinctiveness and no columns of the inner table are referenced after the join operation, 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 7
Dependent Claim
25 words
The apparatus of claim 4, 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 apparatus of claim 4, wherein the requirement for distinctiveness in the result columns for the join operation is implicitly set forth in the query.
Claim 9
Dependent Claim
218 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 (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 no columns of the inner table are referenced after the join operation, further comprising the steps of scanning the inner table for a match for each row of the outer table and terminating the scanning seep when the match is found.
Claim 10
Dependent Claim
218 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 (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 no columns of the inner table are referenced after the join operation, further comprising the steps of scanning the inner table for a match for each row of the outer table and terminating the scanning seep when the match is found.
Claim 11
Dependent Claim
27 words
The program storage device of claim 7, wherein the requirement for distinctiveness in the result columns for the join operation is explicitly set forth in the query.
Claim 12
Dependent Claim
27 words
The program storage device of claim 7, 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 |