Method and apparatus for optimizing execution of database queries containing user-defined functions

• US 20060026116A1
• Filed: 07/29/2004
• Published: 02/02/2006
• Est. Priority Date: 07/29/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Day, Paul Reuben, Muras, Brian Robert
• Granted Patent: US 7,447,680 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A query engine (or optimizer) which supports database queries having user-defined functions maintains historical execution data with respect to each of multiple user-defined functions. The historical execution data is dynamically updated based on query execution performance. When executing a query having user-defined functions, the query engine uses the historical execution data to predict an optimal evaluation ordering for the query conditions and, preferably, to dynamically adjust the evaluation order when appropriate. Preferably, the historical execution data includes historical execution time of the user-defined function and proportion of evaluated records which satisfied the query parameters.

Claims

1. A method for database query optimization in a computer system, comprising the steps of:

maintaining historical execution data with respect to each of a plurality of user-defined functions;

receiving a database query having a plurality of logical conditions, said database query including at least one of said user-defined functions in at least one of said logical conditions;

using said historical execution data to predict an optimal ordering of evaluation of said plurality of logical conditions; and

evaluating said database query in accordance with said predicted optimal ordering of evaluation of said plurality of logical conditions.

2. The method for database query optimization of claim 1, wherein said database query includes a plurality of said user-defined functions, and wherein said step of using said historical execution data to predict an optimal ordering of evaluation comprises using said historical execution data to predict an optimal ordering of evaluation of said plurality of user-defined functions included in said database query.

3. The method for database query optimization of claim 1, wherein said historical execution data comprises average cost of evaluation of each of said user-defined functions.

4. The method for database query optimization of claim 1, wherein said historical execution data comprises average proportion of database query logical conditions evaluating to “

true”

for each of said user-defined functions.

5. The method for database query optimization of claim 1, wherein said historical execution data comprises data from evaluation of said user-defined functions in satisfying said database query.

6. The method for database query optimization of claim 5, wherein said step of using historical execution data to predict an optimal ordering of evaluation comprises:

periodically re-determining an optimal ordering of evaluation a plurality of times while evaluating said database query, wherein each successive periodic re-determination of an optimal ordering uses said data from evaluation of said user-defined functions in satisfying said database query, said data from evaluation of said user-defined functions in satisfying said database query being updated from each previous periodic re-determination of an optimal ordering.

7. The method for database query optimization of claim 5, wherein said step of using historical execution data to predict an optimal ordering of evaluation comprises using a weighted average of said data from evaluation of said user-defined functions in satisfying said database query and data from execution of said user-defined functions prior to evaluating said database query.

8. The method for database query optimization of claim 1, wherein said historical execution data comprises data from execution of said user-defined functions prior to evaluating said database query.

9. The method for database query optimization of claim 1, wherein said step of using said historical execution data to predict an optimum order of evaluation comprises predicting that logical conditions not containing user-defined functions be evaluated first, and, among multiple logical conditions containing respective user-defined functions, predicting an optimal order of evaluation using said historical execution data.

10. A computer program product for database query optimization comprising:

a plurality of processor executable instructions recorded on signal-bearing media, wherein said instructions, when executed by at least one processor of at least one computer system, cause the at least one computer system to perform the steps of;

maintaining historical execution data with respect to each of a plurality of user-defined functions;

receiving a database query having a plurality of logical conditions, said database query including at least one of said user-defined functions in at least one of said logical conditions;

using said historical execution data to predict an optimal ordering of evaluation of said plurality of logical conditions; and

evaluating said database query in accordance with said predicted optimal ordering of evaluation of said plurality of logical conditions.

11. The computer program product of claim 10, wherein said database query includes a plurality of said user-defined functions, and wherein said step of using said historical execution data to predict an optimal ordering of evaluation comprises using said historical execution data to predict an optimal ordering of evaluation of said plurality of user-defined functions included in said database query.

12. The computer program product of claim 10, wherein said historical execution data comprises average cost of evaluation of each of said user-defined functions.

13. The computer program product of claim 10, wherein said historical execution data comprises average proportion of database query logical conditions evaluating to “

true”

for each of said user-defined functions.

14. The computer program product of claim 10, wherein said historical execution data comprises data from evaluation of said user-defined functions in satisfying said database query.

15. The computer program product of claim 14, wherein said step of using historical execution data to predict an optimal ordering of evaluation comprises:

periodically re-determining an optimal ordering of evaluation a plurality of times while evaluating said database query, wherein each successive periodic re-determination of an optimal ordering uses said data from evaluation of said user-defined functions in satisfying said database query, said data from evaluation of said user-defined functions in satisfying said database query being updated from each previous periodic re-determination of an optimal ordering.

16. The computer program product of claim 14, wherein said step of using historical execution data to predict an optimal ordering of evaluation comprises using a weighted average of said data from evaluation of said user-defined functions in satisfying said database query and data from execution of said user-defined functions prior to evaluating said database query.

17. The computer program product of claim 10, wherein said historical execution data comprises data from execution of said user-defined functions prior to evaluating said database query.

18. The computer program product of claim 10, wherein said step of using said historical execution data to predict an optimum order of evaluation comprises predicting that logical conditions not containing user-defined functions be evaluated first, and, among multiple logical conditions containing respective user-defined functions, predicting an optimal order of evaluation using said historical execution data.

19. A computer system, comprising:

at least one processor;

a data storage for storing a database;

a database management facility embodied as a plurality of instructions executable on said at least one processor, said database management facility including a query engine which executes logical queries against said database, each logical query containing a respective set of logical conditions, at least some of said respective sets of logical conditions containing one or more logical conditions including respective one or more user-defined functions;

wherein said database management facility automatically predicts a respective optimal ordering of evaluation of each a plurality of said respective sets containing one or more logical conditions including respective one or more user-defined functions using respective historical execution data for each said user-defined function, and automatically executes the query containing the respective set according to the predicted optimal ordering of evaluation.

20. The computer system of claim 19, wherein said historical execution data comprises average cost of evaluation of each of said user-defined functions.

21. The computer system of claim 19, wherein said historical execution data comprises average proportion of logical conditions evaluating to “

true”

for each of said user-defined functions.

22. The computer system of claim 19, wherein said historical execution data used for predicting an optimal ordering of evaluation of each respective query comprises data from evaluation of said user-defined functions in satisfying the respective query.