Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-12-17
2003-09-02
Metjahic, Safet (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06615203
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 component of the query planning and optimization process in a heterogeneous database system is to determine the portions of the heterogeneous query that can be executed at the remote database system, i.e., pushdown analysis. Accurate pushdown analysis is important for heterogeneous query optimization because of the need to clearly identify the portions of the query that can be executed at the remote database systems in order to generate a complete query execution plan.
An optimizer will consider many alternatives as it generates query plans. Generally speaking, the more alternatives for an optimizer to explore, the better chances of arriving at the most optimal final plan. In the heterogeneous database environment, remotely executeable or “pushdownable” queries or portions of queries are in many instances very efficient and hence make good alternatives for an optimizer to consider.
Conservative pushdown analysis could result in query plans that are not optimal since potential alternatives are never considered by a query optimizer. When there is incorrect pushdown analysis, an optimizer could generate query plans that are infeasible due to the capability limitations of the remote database system.
In some heterogeneous database systems, the portions of the heterogeneous query that can be executed at the remote database system is determined by a pushdown analysis that is typically effective only for plan independent features of the query. In other words, only those features of the query that would always be pushdownable regardless of how the optimizer generated the query plan would in fact be considered pushed down.
This type pushdown analysis is performed before query optimization, and is not associated with the plan enumeration and evaluation. This approach of checking and indicating various portions of the query that can be executed at the remote database system cannot always accurately capture the portions of the query that are really pushdownable because some of the pushdownabilities are dependent upon how the query is planned for execution. What is needed are better ways to capture pushdownable portions of queries in a heterogeneous database environment.
SUMMARY OF THE INVENTION
One aspect of the present invention provides a way of increasing the amount of pushdownability by doing pushdown analysis during query plan generation that takes into account the actual query plan in determining what portions of a query may or may not be pushdownable. This in turn may lead to more optimal query execution plans since the optimizer may consider more alternatives.
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 pushdown analysis during query plan generation is provided.
Essentially, for each portion of the query plan that is generated by an optimizer, a test is made to see whether that portion of the query plan is pushdownable or not. If so, that portion of the query plan is “duplicated.” The original portion is processed and cost parameters are generated from the perspective of it being executed locally.
The duplicated portion is also processed but the cost parameters are generated from the perspective of it being pushed down and executed at the remote database system. The optimizer now has an extra alternative to evaluate as it continues plan generation and enumeration.
The optimizer considers the various permutations of the tables and subquery results to be combined along with the predicates that can be applied on the result. This allows for those pushdownabilities that are plan dependent to be evaluated under the specific context being planned.
REFERENCES:
patent: 5864840 (1999-01-01), Leung et al.
patent: 6134540 (2000-10-01), Carey et al.
patent: 6226637 (2001-05-01), Carey et al.
patent: 6285997 (2001-09-01), Carey 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/SOLBOL.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 Heterogeneous 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
Al-hashemi Sana
International Business Machines - Corporation
Metjahic Safet
Sughrue & Mion, PLLC
LandOfFree
Method, computer program product, and system for pushdown... 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 pushdown..., 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 pushdown... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3083253