Generalized model for the exploitation of database indexes

• US 6,253,196 B1
• Filed: 07/09/1998
• Issued: 06/26/2001
• Est. Priority Date: 07/10/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kazimierowicz, Kamilla, Wang, Yun, Tran, Brian Thinh-Vinh, Fuh, Gene Y. C., Jou, Michelle Mei-Chiou
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): MIZRAHI, DIANE D
• Application Number:
  US09/112,307
• Time in Patent Office: 1,083 Days
• Field of Search: 707/1, 707/3, 707/2, 707/5, 707/6, 707/204, 707/102, 707/4, 717/5, 706/46
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/24553 of query operations
• CPC Class Codes: G06F 16/24557 Efficient disk access during query execution
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• 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
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method, apparatus, and article of manufacture for computer-implemented exploitation of database indexes. A statement is executed in a database stored on a data storage device connected to a computer. The database contains data. A model based on pattern matching for a user-defined predicate and selection of an index exploitation rule based on a matched user-defined predicate is provided to be used for exploiting an index to retrieve data from the database.

Claims

1. A method of enabling exploitation of an index in a database stored on a data storage device connected to a computer, wherein the database contains data, the method comprising the step of:

providing a model based on pattern matching for a user-defined predicate, which is used to select data from the database, and selection of an index exploitation rule, comprising a search method for exploiting an index, based on a matched user-defined predicate, wherein the model is to be used for exploiting an index to retrieve data from the database.

2. The method of claim 1, wherein the pattern matching is generalized pattern matching.

3. The method of claim 2, wherein the index is based on a user-defined index type, further comprising the step of predicate cloning.

4. The method of claim 2, wherein the generalized pattern matching is used for generalized key expressions for indexing on expressions.

5. The method of claim 1, wherein the selection of an index exploitation rule is based on a definition of an associated user-defined function.

6. The method of claim 1, wherein the index is a B-tree index.

7. The method of claim 1, wherein index is a user-defined index.

8. The method of claim 1, further comprising the step of indexing on expressions.

9. The method of claim 1, wherein the pattern matching further comprises the step of determining that the index is based on at least one user-defined relationship.

10. The method of claim 9, wherein the pattern matching further comprises the step of determining that an index pattern matches a combination of arguments of the predicate.

11. The method of claim 10, wherein the step of selecting an index exploitation rule further comprises the step of using the matched combination of arguments of the predicate to delimit a search range based on the user-defined relationship.

12. The method of claim 11, wherein the user-defined relationship is encapsulated within a user-defined index-type on which the index is based.

13. An apparatus for enabling exploitation of an index, comprising:

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

one or more computer programs, performed by the computer, for providing a model based on pattern matching for a user-defined predicate, which is used to select data from the database, and selection of an index exploitation rule, comprising a search method for exploiting an index, based on a matched user-defined predicate, wherein the model is to be used for exploiting an index to retrieve data from the database.

14. The apparatus of claim 13, wherein the pattern matching is generalized pattern matching.

15. The apparatus of claim 14, wherein the index is based on a user-defined index type, further comprising the means for predicate cloning.

16. The apparatus of claim 14, wherein the generalized pattern matching is used for generalized key expressions for indexing on expressions.

17. The apparatus of claim 13, wherein the selection of an index exploitation rule is based on a definition of an associated user-defined function.

18. The apparatus of claim 13, wherein the index is a B-tree index.

19. The apparatus of claim 13, wherein index is a user-defined index.

20. The apparatus of claim 13, further comprising the means for indexing on expressions.

21. The apparatus of claim 13, wherein the pattern matching further comprises the means for determining that the index is based on at least one user-defined relationship.

22. The apparatus of claim 21, wherein the pattern matching further comprises the means for determining that an index pattern matches a combination of arguments of the predicate.

23. The apparatus of claim 22, wherein the means for selecting an index exploitation rule further comprises the means for using the matched combination of arguments of the predicate to delimit a search range based on the user-defined relationship.

24. The apparatus of claim 23, wherein the user-defined relationship is encapsulated within a user-defined index-type on which the index is based.

25. An article of manufacture comprising a computer program carrier readable by a computer and embodying one or more instructions executable by the computer to perform method steps for enabling exploitation of an index in a database stored in a data storage device connected to the computer, wherein the database contains data, the method comprising:

providing a model based on pattern matching for a user-defined predicate, which is used to select data from the database and selection of an index exploitation rule, comprising a search method for exploiting an index, based on a matched user-defined predicate, wherein the model is to be used for exploiting an index to retrieve data from the database.

26. The article of manufacture of claim 25, wherein the pattern matching is generalized pattern matching.

27. The article of manufacture of claim 26, wherein the index is based on a user-defined index type, further comprising the step of predicate cloning.

28. The article of manufacture of claim 26, wherein the generalized pattern matching is used for generalized key expressions for indexing on expressions.

29. The article of manufacture of claim 25, wherein the selection of an index exploitation rule is based on a definition of an associated user-defined function.

30. The article of manufacture of claim 25, wherein the index is a B-tree index.

31. The article of manufacture of claim 25, wherein index is a user-defined index.

32. The article of manufacture of claim 25, further comprising the step of indexing on expressions.

33. The article of manufacture of claim 25, wherein the pattern matching further comprises the step of determining that the index is based on at least one user-defined relationship.

34. The article of manufacture of claim 33, wherein the pattern matching further comprises the step of determining that an index pattern matches a combination of arguments of the predicate.

35. The article of manufacture of claim 34, wherein the step of selecting an index exploitation rule further comprises the step of using the matched combination of arguments of the predicate to delimit a search range based on the user-defined relationship.

36. The article of manufacture of claim 35, wherein the user-defined relationship is encapsulated within a user-defined index-type on which the index is based.