Systems and methods for estimating query response times in a computer system

• US 6,026,391 A
• Filed: 10/31/1997
• Issued: 02/15/2000
• Est. Priority Date: 10/31/1997
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Fragapane, Paolo, Osborn, Andrew P.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US08/962,538
• Time in Patent Office: 837 Days
• Field of Search: 707/3, 707/2, 707/4, 707/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/217 Database tuning G06F16/2282 takes precedence; database performance monitoring G06F11/3409
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A query performance prediction ("QPP") module is provided as part of an applications layer residing on respective user stations operating in conjunction with a centralized host computer system. The QPP module correlates estimated system cost information for a database query provided from a database management system associated with the computer system with statistics compiled from previous queries in order to estimate the system response time. In particular, an estimated CPU time for executing the present query is derived by extrapolating actual CPU times recorded for past queries having the closest estimated costs for accessing the same, or similar, tables and items in the database, using a form of a "nearest neighbor" algorithm to match the present query to either identical or statistically closest past queries. The estimated CPU time for the present query is then multiplied by a current ratio of total elapsed times-to-CPU times for the system to produce an estimated total elapsed time for responding to the query.

Claims

1. A method for estimating the time for a computer system to respond to a database query, comprising:

determining an estimated cost for executing the database query;

identifying, using the estimated cost, previously executed queries comprising characteristics the same as, or similar to, the database query; and

deriving an estimate of the time required for responding to the database query based on information associated with the previously executed queries.

2. The method of claim 1, in which identifying previously executed queries comprises comparing specific data sought in the database query with specific data sought in queries previously executed.

3. The method of claim 1, in which deriving an estimate of the time required for responding to the database query comprises

generating an estimated processing time for the database query using an actual CPU processing time for a previously executed query, and

applying a current ratio to the estimated processing time, the current ratio comprising a ratio of elapsed time for the computer system to respond to one or more prior queries to actual CPU time to process the one or more prior queries.

4. The method of claim 3, in which the actual CPU processing time for a previously executed query comprises the actual CPU processing time to process a previously executed query identified as comprising characteristics the same as, or similar to, the database query, and the one or more prior queries comprises one or more of the most current executed database queries.

5. The method of claim 4, in which the current ratio further comprises a weighted average of elapsed time to actual CPU time.

6. A method for estimating the time required for a computer system to respond to a present query, comprising:

identifying a plurality of previously executed queries comprising characteristics the same as, or similar to, the present query; and

deriving an estimate of the time required for responding to the present query based on information associated with the plurality of previously executed queries.

7. The method of claim 6, in which identifying a plurality of previously executed queries comprises

comparing an estimated cost for executing the present query with estimated costs of executing a plurality of prior queries, and

comparing a result set of the present query with result sets of the plurality of prior queries, a result set comprising an identification of the tables accessed in a database to respond to the respective present query or respective prior query.

8. The method of claim 6, further comprising determining an estimated cost for executing the present query, and in which deriving an estimate of the time required for responding to the present query comprises determining whether a prior executed query has an identical estimated cost as the estimated cost for executing the present query.

9. The method of claim 6, in which deriving an estimate of the time required for responding to the present query comprises

generating an estimated processing time for the present query using an actual CPU processing time of a previously executed query, and

applying a current ratio to the estimated processing time, the current ratio comprising a ratio of elapsed times to actual times, the elapsed times comprising the times for the computer system to respond to a set of one or more prior queries and the actual times comprising the actual CPU processing times of the set of one or more prior queries.

10. The method of claim 8, in which deriving an estimate of the time required for responding to the present query further comprises

extrapolating an estimated processing time for executing the present query based on the actual processing times of the plurality of previously executed queries, if no prior executed query has an estimated cost equal to the estimated cost for executing the present query.

11. The method of claim 10, in which extrapolating an estimated processing time comprises determining an estimated processing time based on a weighted average of the actual processing times of the plurality of previously executed queries.

12. A machine readable medium having stored thereon a program for causing a computer to:

determine an estimated cost for executing a present query;

identify, using the estimated cost, one or more previously executed queries comprising characteristics the same as, or similar to, the present query; and

derive an estimate of the time required for responding to the present query based on information associated with the one or more previously executed queries.

13. A machine readable medium having stored thereon a program for causing a computer to:

identify one or more previously executed queries comprising characteristics the same as, or similar to, a present query; and

derive an estimate of the time to respond to the present query based on information associated with the one or more previously executed queries.

14. The machine readable medium of claim 13, in which to identify one or more previously executed queries, the program further causes the computer to

compare an estimated cost for executing the present query with estimated costs of executing a plurality of prior queries, and

compare a result set of the present query with result sets of the plurality of prior queries, a result set comprising an identification of the database tables accessed to respond to the respective present query or respective prior query.

15. The machine readable medium of claim 13, in which to derive an estimate of the time to respond to the present query, the program further causes the computer to

generate an estimated processing time for the present query using an actual CPU processing time of a previously executed query, and

apply a current ratio to the estimated processing time, the current ratio comprising a ratio of elapsed time to actual CPU time, the elapsed time comprising one or more elapsed times for the computer system to respond to one or more prior executed queries, and the actual CPU time comprising one or more actual CPU processing times of the one or more prior executed queries.

16. A computer system, comprising:

a computer; and

a data storage device, said data storage device comprising a program residing thereon for causing said computer to estimate a time for the computer system to respond to a present database query by

determining an estimated cost for executing the present database query,

identifying, using the estimated cost, previously executed queries comprising characteristics the same as, or similar to, the present database query, and

deriving an estimate of the time required for responding to the present database query based on information associated with the previously executed queries.

17. A computer system, comprising:

a computer; and

a data storage device, said data storage device comprising a program residing thereon for causing said computer to estimate a time for the computer system to respond to a present query by

identifying a previously executed query comprising characteristics the same as, or similar to, the present query, and

deriving an estimate of a time for responding to the present query based on information associated with the previously executed query.

18. The computer system of claim 17, in which said program further causes said computer to

compare an estimated cost for executing the present query with estimated costs of executing a plurality of prior queries, and

compare a result set of the present query with result sets of the plurality of prior queries, a result set comprising an identification of the database tables accessed to respond to the respective present query or respective prior query.

19. The computer system of claim 18, in which said program further causes said computer to

generate an estimated processing time for the present query using an actual CPU processing time of a previously executed query, and

apply a current ratio to the estimated processing time, the current ratio comprising a ratio of one or more elapsed times for the computer system to respond to a set of prior queries to one or more actual CPU processing times for the set of prior queries.

20. The computer system of claim 19, in which the actual CPU processing time of a previously executed query comprises the actual CPU processing time to process the previously executed query comprising characteristics the same as, or similar to, the present query, and the set of prior queries comprises one or more of the most current executed queries.