Database System with Methodology for Automated Determination and Selection of Optimal Indexes

• US 20050203940A1
• Filed: 04/27/2004
• Published: 09/15/2005
• Est. Priority Date: 03/12/2004
• Status: Active Grant

• Current Assignee: iAnywhere Solutions Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Farrar, Daniel J., Nica, Anisoara
• Granted Patent: US 7,406,477 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/2228 Indexing structures
• 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
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A database system with methodology for automated determination and selection of optimal indexes is described. In one embodiment, for example, in a database system, a method of the present invention is described for recommending database indexes to be created for optimizing system performance, the method comprises steps of: capturing a workload representative of database queries employed during system use; creating virtual indexes for optimizing system performance during execution of the database queries captured in the workload; computing cost benefits for different combinations of the virtual indexes; and recommending physical indexes to be created based on virtual indexes that have favorable cost benefits for the captured workload.

Claims

1. In a database system, a method for recommending database indexes to be created for optimizing system performance, the method comprising:

capturing a workload representative of database queries employed during system use;

creating virtual indexes for optimizing system performance during execution of the database queries captured in the workload;

computing cost benefits for different combinations of the virtual indexes; and

recommending physical indexes to be created based on virtual indexes that have favorable cost benefits for the captured workload.

2. The method of claim 1, wherein said virtual indexes comprise in-memory data structures corresponding to sets of potential physical indexes.

3. The method of claim 1, wherein the capturing step includes:

displaying a screen input button that a user may invoke to record a usage session as a workload.

4. The method of claim 1, wherein the workload represents user execution of a database application with a typical workload that is contemplated for the application.

5. The method of claim 1, wherein the workload includes information recording text of all the queries operating during the capture of the workload.

6. The method of claim 1, wherein the workload includes information recording settings for certain options that affect how queries are optimized.

7. The method of claim 1, wherein the capturing step includes:

capturing information about a set of workloads to define a problem instance.

8. The method of claim 1, further comprising:

setting a limit on how much disk space is available for physical indexes.

9. The method of claim 8, wherein the recommending step takes into account the limit on disk space available for physical indexes.

10. The method of claim 8, wherein the recommending step includes:

if the physical indexes to be recommended for creation exceed the limit on disk space available for physical indexes, removing some of the physical indexes from consideration.

11. The method of claim 10, wherein the physical indexes removed from consideration are ones having less favorable cost benefits for the captured workload.

12. The method of claim 10, wherein the physical indexes removed from consideration comprise at least 20 percent of bottom performing indexes considered for recommendation.

13. The method of claim 1, further comprising:

specifying whether certain types of indexes should be considered at all.

14. The method of claim 1, wherein the creating virtual indexes step includes:

searching for relevant indexes that will help the system'"'"'s optimizer use sargable predicates for partial index scans.

15. The method of claim 14, wherein the optimizer creates virtual indexes without specifying ordering of columns used in sargable equality predicates.

16. The method of claim 1, wherein the creating virtual indexes step includes:

searching for relevant indexes that will help provide useful orderings.

17. The method of claim 16, wherein columns of virtual indexes may be order-independent “

don'"'"'t care”

columns that satisfy some interesting ordering wish list of the system'"'"'s optimizer.

18. The method of claim 16, wherein columns of virtual indexes may have an unspecified sortedness.

19. The method of claim 1, further comprising:

collapsing some of the virtual indexes together, if feasible for the workload.

20. The method of claim 19, wherein the collapsing step includes:

identifying that columns of one virtual index are a superset of another the columns of another virtual index, and that both indexes may be combined into a single virtual index that is feasible for the workload; and

identifying that sortedness of a column of a virtual index, if unspecified, may be specified to allow it to be combined with an index with identical columns but specified sortedness; and

identifying that a virtual index that has columns of opposite sortedness of a second virtual index, and that both indexes may be combined into a single virtual index.

21. The method of claim 1, further comprising:

polling periodically in the method to ensure that the system is working with accurate cost information.

22. A computer-readable medium having processor-executable instructions for performing the method of claim 1.

23. A downloadable set of processor-executable instructions for performing the method of claim 1.

24. A system that recommends database indexes to be created for optimizing system performance, the system comprising:

a database system that executes database queries; and

an index consultant for capturing a workload representative of database queries executed during typical system use;

creating virtual indexes for optimizing system performance during execution of the database queries captured in the workload;

computing cost benefits for different combinations of the virtual indexes; and

recommending physical indexes to be created based on virtual indexes that have favorable cost benefits for the captured workload.

25. The system of claim 24, wherein said virtual indexes comprise in-memory data structures corresponding to sets of potential physical indexes.

26. The system of claim 24, wherein the index consultant displays a screen input button that a user may invoke to record a usage session as a workload.

27. The system of claim 24, wherein the workload represents user execution of a database application with a typical workload that is contemplated for the application.

28. The system of claim 24, wherein the workload includes information recording text of all the queries operating during the capture of the workload.

29. The system of claim 24, wherein the workload includes information recording settings for certain options that affect how queries are optimized.

30. The system of claim 24, wherein the index consultant captures information about a set of workloads to define a problem instance.

31. The system of claim 24, wherein the index consultant may receive information specifying a limit on how much disk space is available for physical indexes.

32. The system of claim 31, wherein the index consultant takes into account the limit on disk space available for physical indexes.

33. The system of claim 31, wherein the index consultant removes some of the physical indexes from consideration, when sufficient disk space is unavailable.

34. The system of claim 33, wherein the physical indexes removed from consideration are ones having less favorable cost benefits for the captured workload.

35. The system of claim 33, wherein the physical indexes removed from consideration comprise at least 20 percent of bottom performing indexes considered for recommendation.

36. The system of claim 24, wherein the index consultant allows user input specifying whether certain types of indexes should be considered at all.

37. The system of claim 24, wherein the index consultant searches for relevant indexes that will help the system'"'"'s optimizer use sargable predicates for partial index scans.

38. The system of claim 37, wherein the optimizer creates virtual indexes without specifying ordering of columns used in sargable equality predicates.

39. The system of claim 24, wherein the index consultant searches for relevant indexes that will help provide useful interesting (order or grouping) properties.

40. The system of claim 39, wherein columns of indexes created may reflect order-independent “

don'"'"'t care”

columns that satisfy some interesting ordering wish lists of the system'"'"'s optimizer.

41. The system of claim 24, wherein the index consultant attempts to collapse some of the virtual indexes together, if feasible for the workload.

42. The system of claim 41, wherein the index consultant attempts to identify that columns of one index are a superset of the columns of another index, and that both indexes may be combined into a single index that is feasible for the workload.

43. The system of claim 24, wherein operation of the index consultant may be polled during operation to ensure that the system is working with accurate cost information.