Multiple-stage evaluation of user-defined predicates

• US 6,192,358 B1
• Filed: 07/09/1998
• Issued: 02/20/2001
• Est. Priority Date: 07/10/1997
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wang, Yun, Pan, Hsin, Fuh, Gene Y. C., Jou, Michelle Mei-Chiou
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US09/112,301
• Time in Patent Office: 957 Days
• Field of Search: 707/3, 707/2, 707/4, 707/104, 707/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2291 User-Defined Types; Storage management thereof
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• 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 method, apparatus, and article of manufacture for a computer-implemented multiple-stage evaluation of a user-defined predicate. A statement is executed in a database stored on a data storage device connected to a computer. The statement is received containing a user-defined predicate with a user-defined function. Then, multiple-stage evaluation of the user-defined predicate is performed.

Claims

1. A method of executing a statement in a database stored on a data storage device connected to a computer, the method comprising the steps of:

receiving the statement, wherein the statement contains a user-defined predicate with a user-defined function; and

performing multiple-stage evaluation of the user-defined predicate wherein at least one stage comprises performing index exploitation as specified in the user-defined function.

2. The method of claim 1, wherein multiple-stage evaluation comprises multiple stages, further comprising the step of identifying the multiple stages based on a filter factor ratio of each of the multiple stages and a cost factor of evaluation at each of the multiple stages.

3. The method of claim 2, wherein the step of performing multiple-stage evaluation further comprises the step of performing index exploitation to identify a subset of records.

4. The method of claim 3, wherein the index exploitation is performed using a user-defined index exploitation function with a plurality of options.

5. The method of claim 3, wherein the step of performing multiple-stage evaluation further comprises the step of filtering the identified subset of records.

6. The method of claim 5, wherein the step of filtering further comprises the step of evaluating an approximation function for each record in the identified subset of records to identify records that fit an approximation of the approximation function.

7. The method of claim 6, wherein the approximation function is a user-defined function.

8. The method of claim 6, wherein the step of performing multiple-stage evaluation further comprises the step of evaluating the user-defined predicate for each record that fits the approximation.

9. An apparatus for executing a statement, comprising:

a computer having a data storage device connected thereto, wherein the data storage device stores a database;

one or more computer programs, performed by the computer, for receiving the statement, wherein the statement contains a user-defined predicate with a user-defined function and performing multiple-stage evaluation of the user-defined predicate, wherein at least one stage comprises performing index exploitation as specified in the user-defined function.

10. The apparatus of claim 9, wherein multiple-stage evaluation comprises multiple stages and further comprising the means for identifying the multiple stages based on a filter factor ratio of each of the multiple stages and a cost factor of evaluation at each of the multiple stages.

11. The apparatus of claim 10, wherein the means for performing multiple-stage evaluation further comprises the means for performing index exploitation to identify a subset of records.

12. The apparatus of claim 11, wherein the index exploitation is performed using a user-defined index exploitation function with a plurality of options.

13. The apparatus of claim 11, wherein the means for performing multiple-stage evaluation further comprises the means for filtering the identified subset of records.

14. The apparatus of claim 13, wherein the means for filtering further comprises the means for evaluating an approximation function for each record in the identified subset of records to identify records that fit an approximation of the approximation function.

15. The apparatus of claim 14, wherein the approximation function is a user-defined function.

16. The apparatus of claim 14, wherein the means for performing multiple-stage evaluation further comprises the means for evaluating the user-defined predicate for each record that fits the approximation.

17. An article of manufacture comprising a computer program carrier readable by a computer and embodying one or more instruction executable by the computer to perform method steps for executing a statement in a database stored in a data storage device connected to the computer, the method comprising the steps of:

receiving the statement, wherein the statement contains a user-defined predicate with a user-defined function; and

performing multiple-stage evaluation of the user-defined predicate wherein at least one stage comprises performing index exploitation as specified in the user-defined function.

18. The article of manufacture of claim 17, wherein multiple-stage evaluation comprises multiple stages, further comprising the step of identifying the multiple stages based on a filter factor ratio of each of the multiple stages and a cost factor of evaluation at each of the multiple stages.

19. The article of manufacture of claim 17, wherein the step of performing multiple-stage evaluation further comprises the step of performing index exploitation to identify a subset of records.

20. The article of manufacture of claim 19, wherein the index exploitation is performed using a user-defined index exploitation function with a plurality of options.

21. The article of manufacture of claim 19, wherein the step of performing multiple-stage evaluation further comprises the step of filtering the identified subset of records.

22. The article of manufacture of claim 21, wherein the step of filtering further comprises the step of evaluating an approximation function for each record in the identified subset of records to identify records that fit an approximation of the approximation function.

23. The article of manufacture of claim 22, wherein the approximation function is a user-defined function.

24. The article of manufacture of claim 22, wherein the step of performing multiple-stage evaluation further comprises the step of evaluating the user-defined predicate for each record that fits the approximation.