Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-07-31
2001-04-03
Black, Thomas G. (Department: 2771)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06212514
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to automatic database query methods and, more particularly, to a system and method for estimating costs of database queries, when a trigger procedure is executed.
BACKGROUND OF THE INVENTION
As is well known, database queries are often posed in a non-procedural language such as “Standard Query Language” or SQL. Queries dispatched to relational databases include the following four actions: select, insert, update and delete. Such queries are used to interrogate and modify logical tables, arranged in rows and columns, in the relational databases. A query which is dispatched to a database interrogates a selected table(s) and, depending upon the syntax of the query, returns from none to many rows of the interrogated table(s) which fit the query condition and/or action.
Query optimizer functions are performed by relational database management systems and enable a choice to be made from among a plurality of query strategies so as to arrive at an efficiently executable plan. The computational complexity of the optimization process and the resulting execution efficiency of the plan chosen are dependent upon the number of possible primitive operator sequences that must be evaluated by the optimizer. U.S. Pat. No. 5,301,317 to Lohman et al., assigned to the same Assignee as this application, describes a system for automatic adjustment of resources devoted to query optimization, according to an estimated query execution time. The Lohman et al. system permits a query optimizer to automatically trade off the time spent estimating the execution cost of alternate query execution plans against the potential savings and execution time that one of those alternate plans may yield.
An aspect of query optimization is the resulting execution cost of the query in terms of utilized central processing unit (CPU) time, input/output (I/O) time, and minimum elapsed time that is required by execution of the query statement. An optimizer generally chooses the query plan which results in the least cost to accomplish the execution of the query statement.
U.S. Pat. No. 5,734,884 to Eberhard et al., assigned to the same Assignee as this Application, describes a software tool for estimating the costs of a program which accesses a relational database. The costs may include execution costs of the application or of a transaction, an SQL statement and/or a utility. Execution costs include CPU time, I/O time and minimum elapsed time, wherein minimum elapsed time is an estimation of the amount of time that the application, transaction, SQL or utility will take to execute. The execution costs may also reflect system performance effected by transactional accessing of the database, including batch processing. For estimating the execution costs of a transaction, the software tool generates a simplified transaction definition, including a simplified query statement definition, and a frequency of execution of the query statement in the transaction. The software tool then generates an estimated execution cost based upon the syntax of the simplified query statement and the frequency of execution thereof. The disclosure of both U.S. Pat. Nos. 5,301,317 and 5,734,884 are incorporated herein by reference.
As above indicated, a query statement causes dispatch of a select, insert, update or delete command to one or more tables in a relational database. In response, from 0 to N rows are returned which conform to the condition expressed in the query statement. If the returned data meets the terms of a condition that is associated with the query, a “trigger” procedure is or may be invoked.
A trigger procedure is a responsive program which is automatically executed in response to data, returned (in response to a dispatched query) which meets a condition associated with the trigger procedure. A trigger procedure may be executed in response to each row that is affected by the query or may be executed once for all rows that are affected. A simple example of a query is as follows. Assume that an SQL query statement requires the insertion of an employee name into a specified department that is listed in a database table. Assume further that the user neglects to enter the department number in the SQL query statement. Upon dispatch of the SQL query statement, the database management program causes a trigger procedure to be executed to cause display of a message to the user to enter a department number in the SQL statement.
Trigger procedures can be quite complex and may be dependent upon a number of conditions being met before they execute. Llirbat et al. in “Eliminating Costly Redundant Computations from SQL Trigger Executions”, Proceedings of the 1997 ACM Sigmod, Tucson, Ariz. May 13-15, 1997, pp. 428-439, describe a procedure which attempts to eliminate repeated calculations which result from certain types of SQL triggers, to reduce the processing cost thereof. More specifically, Llirbat et al. eliminate redundant computations of SQL triggers when they are costly. Invariant sub-queries are extracted from trigger conditions and actions and the most “profitable” invariants are memorized and utilized in a re-write of the SQL triggers.
As indicated above, a trigger may be caused to execute for each row of a table returned in response to an SQL query statement or may be caused to execute once per SQL query statement, irrespective of the number of rows returned in response to the SQL query statement. It is known, however, that the execution cost of a trigger may not be a linear function based upon the number of rows that are returned. Notwithstanding the potential complexity of estimating trigger costs, there is still a need, during the optimization process, to arrive at an estimate of trigger cost to enable a realistic view of the actual cost of the execution of an SQL query statement and the one or more resulting triggers which occur as a result of the execution thereof.
SUMMARY OF THE INVENTION
The method of the invention estimates a total processing cost incident to execution of a query statement in respect of a relational database, wherein execution of the query statement results in a further execution of a trigger procedure. The method first estimates the query statement's costs by analyzing components of the query statement to determine a processing time there for in relation to a database table that is the target of the query statement. The method then determines the number of rows that are affected in the database table as a result of execution of the query statement. Next, components of a trigger procedure that is invoked in response to execution of the query statement are analyzed to determine a “base cost” for a single execution of the trigger procedure vis-a-vis data that is contained in a single row of the database table. The components of the trigger procedure are next analyzed to determine a per row cost for execution of the trigger procedure. The per row cost is determined from an estimate of time required for execution of the trigger procedure for a single row and from an estimate of time required for execution of the trigger procedure for a plurality of rows. Thereafter, the total processing cost of a query statement is calculated by adding the query statement cost to a sum of the either (i) the base cost if only one row is subjected to the query statement or (ii) the per row cost, multiplied by the number of rows affected by the query statement.
REFERENCES:
patent: 5301317 (1994-04-01), Lohman et al.
patent: 5598559 (1997-01-01), Chaudhuri
patent: 5734884 (1998-03-01), Eberhard et al.
patent: 5758144 (1998-05-01), Eberhard et al.
patent: 5950186 (1999-09-01), Chaudhuri et al.
patent: 6003022 (1999-12-01), Eberhard et al.
patent: 6081801 (2000-06-01), Cochrane et al.
IEEE publication, “Estimating Recursive Query Costs for Various Parallel Environments” by Frédéric Andrés et al.pp. 365-372, Jan. 1991.*
Sigmod Record, vol. 20, No. 2, Jun. 1997, pp. 428-439, F. Llirbat et al., “Eliminating Costly Redundant Computations from SQL Trigger Executions”.
Eberhard Rainer
Hall, Jr. Harold H.
Youngberg Jon A.
Black Thomas G.
International Business Machines - Corporation
Mizrahi Diane D.
Ohlandt Greeley Ruggiero & Perle L.L.P.
LandOfFree
Data base optimization method for estimating query and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data base optimization method for estimating query and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data base optimization method for estimating query and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2483682