Patent NL42984C successfully refreshed from Google Patents.
Patent US2850569A successfully refreshed from Google Patents.
US6493701B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Database system with methodogy providing faster N-ary nested loop joins
Assignee: Sybase Inc
•
Filing: 2001-07-05
•
Granted: 2002-12-10
•
Expires: 2021-07-05
Abstract
Abstract A database system implementing a methodology or technique that can be used to optimize processing of nested loop joins of three or more tables (n-ary NLJs for n>2) more efficiently is described. In implementation, upon encountering a failure condition (i.e., a given join condition does not hold true) from a join operator (scan child), context information (about the failure) is returned (to the n-ary nested-loop join operator) for indicating exactly which condition (i.e., join condition) failed. This information is tracked in a scan descriptor, which includes a “fail sarg” data field indicating exactly which particular search argument (“sarg”) failed. Based on this information, the system (operating through the n-ary nested-loop join operator) knows exactly which scan child to return back to (i.e., how far back to go in the join order to fetch the next row). In this manner, the methodology optimizes processing of n-ary nested loop joins by eliminating comparisons that will not hold true for the corresponding join condition (for which the comparisons were to be tested).
Inventors
- 👤 Nagavamsi Ponnekanti
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 11:40
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24534; G06F16/24542; G06F16/24544; G06F16/2455; G06F16/24553; G06F16/24558; G06F16/2456; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934; Y10S707/99935
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
250 words
In a database system for representing information in database tables and for retrieving information from database tables in response to database queries, each database table comprising data records storing information categorized into one or more database columns, each database column storing information as an attribute having a particular data type, a method for processing a database query specifying a join of three or more tables, the method comprising: in response to receiving a particular database query specifying a join of three or more tables, determining a join order for examining the tables during query processing, wherein said particular database query specifies selection criteria including at least one join condition that must exist between an inner table and an outer table that is not a directly preceding table in the join order; retrieving rows from successive tables per the join order, including: determining whether a join condition that is being tested refers back to a more-outer table that is not a directly preceding table, if the join condition is not met, fetching the next row, if any, from said more-outer table whose just-tested condition failed, and if the join condition is met, continuing down the join order to examine any subsequent tables in the join order, if any, applying any subsequent query conditions, if any, that must be met in order to qualify for the query; and in the instance that a set of rows under examination meets said selection criteria, qualifying those rows as having satisfied the particular database query.
Claim 2
Dependent Claim
250 words
In a database system for representing information in database tables and for retrieving information from database tables in response to database queries, each database table comprising data records storing information categorized into one or more database columns, each database column storing information as an attribute having a particular data type, a method for processing a database query specifying a join of three or more tables, the method comprising: in response to receiving a particular database query specifying a join of three or more tables, determining a join order for examining the tables during query processing, wherein said particular database query specifies selection criteria including at least one join condition that must exist between an inner table and an outer table that is not a directly preceding table in the join order; retrieving rows from successive tables per the join order, including: determining whether a join condition that is being tested refers back to a more-outer table that is not a directly preceding table, if the join condition is not met, fetching the next row, if any, from said more-outer table whose just-tested condition failed, and if the join condition is met, continuing down the join order to examine any subsequent tables in the join order, if any, applying any subsequent query conditions, if any, that must be met in order to qualify for the query; and in the instance that a set of rows under examination meets said selection criteria, qualifying those rows as having satisfied the particular database query.
Claim 3
Dependent Claim
25 words
The method of claim 1 , wherein said join order specifies a particular order for retrieving rows from the tables for examination during query execution.
Claim 4
Dependent Claim
22 words
The method of claim 2 , wherein the rows retrieved for examination are retrieved from a particular sequence of the database tables.
Claim 5
Dependent Claim
27 words
The method of claim 2 , wherein the rows retrieved for examination includes at least some rows retrieved from an index for one of the database tables.
Claim 6
Dependent Claim
20 words
The method of claim 1 , wherein said particular database query comprises an SQL-based query from a client database application.
Claim 7
Dependent Claim
24 words
The method of claim 1 , wherein those rows that are qualified as having satisfied the selection criteria are returned as a query result.
Claim 8
Dependent Claim
22 words
The method of claim 1 , wherein said step of retrieving rows is performed by accessing successive tables per the join order.
Claim 9
Dependent Claim
19 words
The method of claim 1 , wherein said step of retrieving rows is performed using nested loop join technique.
Claim 10
Dependent Claim
22 words
The method of claim 1 , wherein, when the join condition is not met, subsequent comparisons for the join condition are eliminated.
Claim 11
Dependent Claim
29 words
The method of claim 1 , further comprising: when the join condition is not met, storing information in a scan descriptor that indicates why the condition is not met.
Claim 12
Dependent Claim
29 words
The method of claim 10 , wherein the information stored in the scan descriptor includes information indicating that a particular search argument failed during testing of the join condition.
Claim 13
Dependent Claim
16 words
The method of claim 1 , wherein the join condition tests for equality between two values.
Claim 14
Dependent Claim
16 words
The method of claim 1 , wherein the join condition tests for inequality between two values.
Claim 15
Dependent Claim
16 words
The method of claim 1 , wherein the join condition compares two fields from the tables.
Claim 16
Dependent Claim
191 words
An improved method for performing nested loop join query execution for a database query received by a database system, said query execution including examination of values from rows retrieved from successive tables pursuant to a join order, the improvement comprising: determining that the database query specifies a join of three or more tables, where at least one join condition exists between an inner table and an outer table that is not a directly preceding table in the join order; while performing query execution using nested loop join technique, if a join condition which is not met refers back to a more-outer table that is not a directly preceding table, fetching the next row, if any, from that more-outer table whose just-tested join condition failed; if the join condition is met, continuing down the join order to examine any subsequent tables in the join order, if any, applying any subsequent query conditions, if any, that must be met in order to qualify for the query; and in the instance that a set of rows under examination meets all conditions of the database query, qualifying those rows as having satisfied the database query.
Claim 17
Dependent Claim
191 words
An improved method for performing nested loop join query execution for a database query received by a database system, said query execution including examination of values from rows retrieved from successive tables pursuant to a join order, the improvement comprising: determining that the database query specifies a join of three or more tables, where at least one join condition exists between an inner table and an outer table that is not a directly preceding table in the join order; while performing query execution using nested loop join technique, if a join condition which is not met refers back to a more-outer table that is not a directly preceding table, fetching the next row, if any, from that more-outer table whose just-tested join condition failed; if the join condition is met, continuing down the join order to examine any subsequent tables in the join order, if any, applying any subsequent query conditions, if any, that must be met in order to qualify for the query; and in the instance that a set of rows under examination meets all conditions of the database query, qualifying those rows as having satisfied the database query.
Claim 18
Dependent Claim
23 words
The improved method of claim 15 , further comprising: providing a scan descriptor for indicating why a particular join condition is not met.
Claim 19
Dependent Claim
22 words
The improved method of claim 16 , wherein said scan descriptor allows determination of said more-outer table whose just-tested join condition failed.
Claim 20
Dependent Claim
23 words
The method of claim 15 , wherein each join condition specifies a comparison of reference values retrieved from rows of the database tables.
References Cited (Backward Citations)
US5600831A
Cited
US5590324A
Cited
US6134546A
Cited
US5991754A
Cited
US6374235B1
Cited
US6397204B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-12-09 | 2006-06-10 | 2006-12-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-12-09 | 2010-06-10 | 2010-12-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-12-09 | 2014-06-10 | 2014-12-10 | $7700.00 | Window Closed / Lapsed |