Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-12-17
2003-02-25
Trammell, James P. (Department: 3621)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06526403
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the processing and optimization of database queries for increased execution performance. More particularly, the present invention relates to query optimization in a heterogeneous database environment where a local database system appears and responds to clients as if having at least some tables locally that are actually on remote database systems.
2. Present State of the Art
An important phase of query compilation is query rewrite, that is, to apply some heuristic rules to rewrite a complex SQL query into a generally efficient or convenient form so that the query optimizer can determine the best query plan for execution. Often, optimizing a rewritten query leads to significant improvement in query execution time, since the query optimizer can generate a better query plan based on the rewritten query.
While the traditional query rewrite mechanisms in a database system may improve query performance of queries directed against local tables, performance degradation can occur in a heterogeneous database system context where the queries may contain references to both remote tables and local tables. If queries posed on a heterogeneous database system are rewritten by the query compiler in the same fashion as queries directed to a local database system's local tables, the query compiler [compile] may produce query forms that are not supported by the remote databases. Execution times of queries in a heterogeneous database system context that undergo rewrite in this manner will suffer if the query processing abilities of the remote database systems are not taken into consideration.
In a heterogeneous database environment, the pushdownability of a heterogeneous query (i.e., the portions of the query that can be executed at the remote databases) might be decreased due to the changes made by the traditional query rewrite heuristic rules. In a heterogeneous database environment, maximizing the pushdownability of a heterogenerous query has been proven to be very important for allowing the heterogeneous query optimizer to make highly efficient decisions.
Therefore what is needed are ways to preserve the pushdownability of heterogeneous queries so that the optimizer can select more alternatives for generating query execution plans.
SUMMARY OF THE INVENTION
One aspect of the present invention is to extend traditional query rewrite rules so that they are effective in a heterogeneous environment.
Another aspect of the present invention is to not decrease the pushdownability of a query due to the application of a query rewrite rule.
Yet another aspect of the present invention is to present new query rewrite rules designed for the heterogeneous database environment.
Additional aspects and benefits of the invention will be set forth in the description that follows, and in part will be obvious from the description, or may be learned by the practice of the invention. The benefits of the invention may be realized and obtained by the combinations particularly pointed out in the appended claims.
In accordance with the invention as embodied and broadly described herein, a method, computer product, and system for rewriting database without decreasing pushdownability is provided.
First, a pushdown analysis of the query in its entirety is performed prior to the application of any query rewrite rules in order to establish a baseline on pushdownability for the query. The results of this analysis is stored with the internal query representation. After each rule is applied to rewrite a portion of a query, that rewritten portion is analyzed again for pushdownability. If pushdownability is not decreased, then the rewritten query remains and the internal representation of the query is updated to reflect the pushdownability of that portion. If pushdownability is decreased, then an undo operation is applied to the rewritten portion of the query to back out the effects of the rule and leave the query in the same state as before the rewrite.
By keeping the heterogeneous query in a form so that the portions that can be executed at the remote databases are not decreased, it provides the heterogenerous query optimizer more alternatives for generating the execution plans (i.e., to execute those portions remotely or to execute those portions locally). This way, a broader plan space can be explored by the optimizer to make the final decision either to evaluate some portions of the query remotely or locally based on a cost model that takes into account all the relevant factors such as CPU, I/O, and network costs in order to come up with the final query execution plan.
This invention extends query rewrite to a heterogeneous database system environment. It solves the problem of extending the traditional query rewrite mechanisms to a heterogeneous database environment so that the heterogeneous database queries can be rewritten into an efficient form to improve query execution times.
REFERENCES:
patent: 5544355 (1996-08-01), Chaudhuri et al.
patent: 5548755 (1996-08-01), Leung et al.
patent: 5590324 (1996-12-01), Leung et al.
patent: 5797136 (1998-08-01), Boyer et al.
patent: 5826077 (1998-10-01), Blakeley et al.
patent: 6032143 (2000-02-01), Leung et al.
patent: 6088524 (2000-07-01), Levy et al.
patent: 6122627 (2000-09-01), Carey et al.
patent: 6134540 (2000-10-01), Carey et al.
patent: 6199063 (2001-03-01), Colby et al.
patent: 6275818 (2001-08-01), Subramanian et al.
patent: 6285997 (2001-09-01), Carey et al.
patent: 6334128 (2001-12-01), Norcott et al.
Hamid Pirahesh et al., “Extensible/Rule Base Query Rewrite Optimization in Starburst”, Conference Proceedings for SIGMOD 1992, pp. 39-48.
Peter Gassner et al., “Query Optimization in the IBM DB2 Family” Data Engineering Bulletin 16 (4): 0-13 (1994).
Oracle 8i™ Distributed Data Access and Oracle Transparent Gateway®, Feb. 1999 pp. 1-4.
EDA Server,http://www.ibi.com/products/eda/server.htm.
Oracle 8i Distributed Database Systems Release 8.1.5, A67784-01, http://technet.oracle.com/doc/server.815/a67784/ds_chl.htm.
Optimizing Distributed Queries, SQL Server 7.0 Query Processor White Paper, Microsoft®,mk:@MSITStore:C:/TEMP/SQLBOL. CHM: : /html/ tun 1 103 . htm.
Laura M. Haas, et al., “Optimizing Queries across Diverse Data Sources,” IBM Almaden Research Center, VLDB 1997 Conference, Athens, Greece, Feb. 21, 1997.
Weimin Du, et al., “Query Optimization in Heterogenous DBMS,” Proceedings of the 18thVLDB Conference, Vancouver, British Columbia, Canada 1992, pp. 277-291.
Fernando de Ferreira Rezende, “The Heterogeneity Problem and Middleware Technology: Experiences with and Performance of Database Gateways,” Proceedings of the 24thVLDB Conference, New York, 1998.
Oracle7 Server Concepts Manual, http://teku.pspt.fi/~jkajala/oradoc/DOC/server/doc/ / SCN73/ch13.htm.
Lin Eileen Tien
Mukai Tina Louise
Venkataraman Shivakumar
Zhang Tian
Farrell Timothy M.
Foerster Ingrid M.
Kahler Mark P.
Trammell James P.
Wang Mary
LandOfFree
Method, computer program product, and system for rewriting... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method, computer program product, and system for rewriting..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, computer program product, and system for rewriting... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3179350