Optimization of joined table expressions by extended access...

Details Optimization of joined table expressions by extended access... Optimization of joined table expressions by extended access...

1999-06-14

2002-07-16

Mizrahi, Diane D. (Department: 2171)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

06421663

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to database management systems performed by computers, and in particular, to the optimization of joined table expressions during query processing in database management systems by extended access path selection.
2. Description of Related Art
Computer systems incorporating Relational DataBase Management System (RDBMS) software using a Structured Query Language (SQL) interface are well known in the art. The SQL interface has evolved into a standard language for RDBMS software and has been adopted as such by both the American Nationals Standard Institute (ANSI) and the International Standards Organization (ISO).
There are a number of well-known and widely-applied optimization methods for queries available in the prior art. Some examples of these optimization methods include Dynamic Programming, Greedy Algorithm, etc. Generally, these optimization methods attempt to find the best execution strategy for a query based on a cost estimation over a range of possible execution strategies in the search space.
Many SQL query compilation and optimization techniques use a parse tree or other representation. A query can be represented as a binary operator tree with operators as the intermediate tree nodes and table references as leaf tree nodes. A straightforward query execution plan is to perform the operators one by one from the bottom up of the tree. This is termed an access path selection.
While optimization via access path selection is well known, it has not been successfully applied to joined table expressions. Joined table expressions are found in FROM clauses of SELECT statements, and generally take the form of “table-reference join-operator table-reference ON join-condition.” The join-operator can be INNER JOIN, LEFT OUTER JOIN, RIGHT OUTER JOIN or FULL OUTER JOIN, the table-reference represents a base table or intermediate result table, and the join-condition is a boolean expression that results in a true, false, or unknown value. More complex joined table expressions can be a sequence of simple joined table expressions combined by join operators, parentheses, and nested table expressions.
There is a need in the art for improved methods of optimizing joined table expressions and complex join operations. Specifically, there is a need in the art for improved methods of optimizing joined table expressions and complex join operations using access path selection.
SUMMARY OF THE INVENTION
To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention discloses a method, apparatus, and article of manufacture for analyzing a query and extending an access path selection for the query, in order to optimize joined table expressions and complex join operations in the query. The extension of the access path selection occurs in two phases: (1) an access path selection router analyzes and divides the query into portions, so that the overall access path selection is divided into smaller access path selections for processing by a join enumerator; and (2) the join enumerator is provided to handle joined table expressions and complex join operators, wherein the join enumerator can be continuously enhanced as more powerful query optimization techniques become available.


REFERENCES:
patent: 5241648 (1993-08-01), Cheng et al.
patent: 5301317 (1994-04-01), Lohman et al.
patent: 5617567 (1997-04-01), Doktor
patent: 5742806 (1998-04-01), Reiner et al.
patent: 5802357 (1998-09-01), Li et al.
patent: 5826261 (1998-10-01), Spencer
patent: 5930785 (1999-07-01), Lohman et al.
patent: 6275818 (2001-08-01), Subramanian et al.
Hamid Pirahesh et al., “Extensible/Rule Based Query Rewrite Opitimization in Starburst”, Proceedings of ACM SIGMOD '92 International Conference on Management of Data, Sand Diego, CA, 1992, pp. 39-48.
Software Patent Institute Database of Software Technologies Record Display, IBM Corporation ©1995, 1996, Serial No.: TDB0288.0025, “Access Path Selection in Relational Database Systems”, pp. 420-421 (2pp).

Affiliated with

Also associated with

Rating

Optimization of joined table expressions by extended access... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Optimization of joined table expressions by extended access..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimization of joined table expressions by extended access... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2861675