US5544355A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for query optimization in a relational database system having foreign functions
Assignee: Hewlett Packard Development Co LP
•
Filing: 1993-06-14
•
Granted: 1996-08-06
•
Expires: 2013-06-14
Abstract
Abstract Database applications typically need to invoke foreign functions or to access data that is not stored in the database. The invention provides a comprehensive approach to cost-based optimization of relational queries in the presence of such foreign functions. The optimization takes into account semantic information about foreign functions using a declarative rule language (e.g., SQL) to express such semantics. Procedures for applying the rewrite rules and for generating the execution space of equivalent queries are described. Procedures to obtain an optimal plan from this enriched execution space are also described. Moreover, necessary extensions to the cost model that are needed in the presence of foreign functions are described.
Inventors
- 👤 Surajit Chaudhuri
- 👤 Kyuseok Shim
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 11:17
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24534; G06F16/24542; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
94 words
A method for optimization of a query invoking relational database tables and foreign functions, said method comprising: (a) providing rewrite rules for the foreign functions; (b) receiving an input query to be executed; (c) generating alternative queries from the input query and the rewrite rules by determining if a left-side of at least one of the rewrite rules is equivalent to at least a portion of the query using substitution mapping; (d) generating an optimal plan for each said alternative query; and (e) selecting for execution a lowest cost plan among said optimal plans.
Claim 2
Independent Claim
94 words
A method for optimization of a query invoking relational database tables and foreign functions, said method comprising: (a) providing rewrite rules for the foreign functions; (b) receiving an input query to be executed; (c) generating alternative queries from the input query and the rewrite rules by determining if a left-side of at least one of the rewrite rules is equivalent to at least a portion of the query using substitution mapping; (d) generating an optimal plan for each said alternative query; and (e) selecting for execution a lowest cost plan among said optimal plans.
Claim 3
Dependent Claim
43 words
A method as recited in claim 1, wherein said generating step (d) comprises: (d1) generating optimal plans for the input query and for at least one of the alternative queries; and (d2) selecting for execution a lowest cost plan among said optimal plans.
Claim 4
Dependent Claim
19 words
A method as recited in claim 2, wherein said generating step (d1) exploits commonality among queries across multiple queries.
Claim 5
Dependent Claim
105 words
A relational database management system, comprising: A relational database having a plurality of tuples; means for accessing at least one foreign function having declarative rewrite rules associated therewith; and an optimizer for optimizing a query accessing said relational database and said at least one foreign function using cost information; wherein said rewrite rules associated with each of said at least one foreign functions are expressed in a high-level declarative language which is an extension of SQL having the form REWRITE Query 1 AS Query 2; and wherein said optimizer uses said rewrite rules to generate equivalent queries by making substitutions indicated by said rewrite rules.
Claim 6
Dependent Claim
105 words
A relational database management system, comprising: A relational database having a plurality of tuples; means for accessing at least one foreign function having declarative rewrite rules associated therewith; and an optimizer for optimizing a query accessing said relational database and said at least one foreign function using cost information; wherein said rewrite rules associated with each of said at least one foreign functions are expressed in a high-level declarative language which is an extension of SQL having the form REWRITE Query 1 AS Query 2; and wherein said optimizer uses said rewrite rules to generate equivalent queries by making substitutions indicated by said rewrite rules.
Claim 7
Dependent Claim
20 words
A relational database management system as recited in claim 4, wherein an optimal plan is selected from said equivalent queries.
Claim 8
Dependent Claim
21 words
A relational database management system as recited in claim 4, wherein the cost information comprises cost information on the foreign functions.
Claim 9
Dependent Claim
83 words
A relational database management system, comprising: a relational database having a plurality of tuples; at least one foreign function having declarative rewrite rules associated therewith; and an optimizer for optimizing a query accessing said relational database and said at least one foreign function using cost information; wherein said rewrite rules are used to generate equivalent queries by substituting a right-hand side of a rewrite rule for at least a portion of the query which corresponds to a left-hand side of the rewrite rule.
Claim 10
Dependent Claim
83 words
A relational database management system, comprising: a relational database having a plurality of tuples; at least one foreign function having declarative rewrite rules associated therewith; and an optimizer for optimizing a query accessing said relational database and said at least one foreign function using cost information; wherein said rewrite rules are used to generate equivalent queries by substituting a right-hand side of a rewrite rule for at least a portion of the query which corresponds to a left-hand side of the rewrite rule.
Claim 11
Dependent Claim
34 words
A relational database management system as recited in claim 7, wherein said optimizer uses substitution mapping to determine if one of the rewrite rules is applicable to at least a portion of the query.
Claim 12
Dependent Claim
33 words
A relational database management system as recited in claim 7, wherein the rewrite rules are stored in a rule table indexed on the conjuncts that appear on the left-side of the rewrite rules.
Claim 13
Dependent Claim
20 words
A relational database management system as recited in claim 7, wherein said optimizer exploits commonality among queries across multiple queries.
Claim 14
Dependent Claim
32 words
A relational database management system as recited in claim 10, wherein said relational database system further comprises a plan table which stories previously determined optimal plans for subqueries to exploit the commonality.
Claim 15
Dependent Claim
28 words
A relational database management system as recited in claim 10, wherein said plan table is a hash-table where each subquery is represented as a sorted list of integers.
Claim 16
Dependent Claim
92 words
A query optimization system for optimizing a query invoking relational database tables and foreign functions, said system comprising: means for providing, in a high-level declarative language which is an extension of SQL, rewrite rules for the foreign functions of the form REWRITE Query 1 AS Query 2; means for providing cost information for the foreign functions; means for receiving a query to be executed; means for generating alternative queries from the query and the rewrite rules; means for generating an optimal plan using the cost information; means for executing said optimal plan.
Claim 17
Dependent Claim
92 words
A query optimization system for optimizing a query invoking relational database tables and foreign functions, said system comprising: means for providing, in a high-level declarative language which is an extension of SQL, rewrite rules for the foreign functions of the form REWRITE Query 1 AS Query 2; means for providing cost information for the foreign functions; means for receiving a query to be executed; means for generating alternative queries from the query and the rewrite rules; means for generating an optimal plan using the cost information; means for executing said optimal plan.
References Cited (Backward Citations)
US4829427A
Cited
US5091852A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-08-06 | 2000-02-05 | 2000-08-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-08-06 | 2004-02-05 | 2004-08-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-08-06 | 2008-02-05 | 2008-08-06 | $7700.00 | Window Closed / Lapsed |