Database system index selection using index configuration enumeration for a workload

• US 5,913,207 A
• Filed: 12/01/1997
• Issued: 06/15/1999
• Est. Priority Date: 08/15/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chaudhuri, Surajit, Narasayya, Vivek
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US08/982,046
• Time in Patent Office: 561 Days
• Field of Search: 707/1, 707/2, 707/3, 707/101, 707/186, 707/205, 385/102, 385/124, 349/33, 349/86, 340/825.35, 156/256
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• 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/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

An index selection tool helps reduce costs in time and memory in selecting an index configuration or set of indexes for use by a database server in accessing a database in accordance with a workload of queries. The index selection tool attempts to reduce the number of indexes to be considered, the number of index configurations to be enumerated, and the number of invocations of a query optimizer in selecting an index configuration for the workload.

Claims

1. A method for selecting an index configuration from a set of indexes based on a workload of queries to be executed against a database, the method comprising the steps of:

(a) determining based on the workload of queries a seed index configuration comprising at most a predetermined number m of indexes from the set of indexes, wherein the predetermined number m is greater than or equal to one; and

(b) successively adding one or more indexes from the set of indexes to the seed index configuration based on the workload of queries to produce the selected index configuration.

2. The method of claim 1, wherein the predetermined number m is two.

3. The method of claim 1, wherein the determining step (a) comprises the steps of:

(i) determining estimated costs to execute queries of the workload against the database for a set of index configurations each comprising at most the predetermined number m of indexes from the set of indexes, and

(ii) selecting the seed index configuration from the set of index configurations based on the determined estimated costs.

4. The method of claim 3, wherein the database comprises a plurality of tables and wherein the determining step (a)(i) comprises the steps of:

(A) determining one or more atomic index configurations for the workload from the set of index configurations such that each determined atomic index configuration comprises only indexes on at most a predetermined number j of the tables of the database,

(B) determining estimated costs to execute queries of the workload against the database for each determined atomic index configuration using a query optimizer of a database server that is to execute queries of the workload against the database, and

(C) determining estimated costs to execute queries of the workload against the database for index configurations of the set of index configurations other than the determined one or more atomic index configurations based on the estimated costs determined for the determining step (a)(i)(B).

5. The method of claim 4, wherein the predetermined number j is two.

6. The method of claim 4, wherein the determining step (a)(i)(B) comprises the step of invoking the query optimizer of the database server to determine estimated costs as needed in performing the determining step (a)(i)(C).

7. The method of claim 3, wherein the selecting step (a)(ii) comprises the step of selecting the seed index configuration as an index configuration from the set of index configurations having a minimum total estimated cost for the workload.

8. The method of claim 1, wherein the seed index configuration is a current index configuration and wherein the adding step (b) comprises the steps of:

(i) adding an index from the set of indexes to the current index configuration such that a total estimated cost of the workload for the current index configuration is reduced, and

(ii) repeating step (b)(i) until the addition of any index from the set of indexes to the current index configuration does not reduce the total estimated cost of the workload for the current index configuration.

9. The method of claim 8, wherein the adding step (b)(i) comprises the step of selecting from the set of indexes for addition to the current index configuration an index that would reduce the total estimated cost of the workload for the current index configuration the most.

10. The method of claim 1, wherein the adding step (b) comprises the step of adding one or more indexes from the set of indexes to the seed index configuration such that the selected index configuration comprises at most a predetermined number k of indexes.

11. The method of claim 1, comprising the step of selecting candidate indexes from a plurality of indexes for inclusion in the set of indexes.

12. The method of claim 1, comprising the step of determining an index configuration for use by a database server to execute queries of the workload against the database as the selected index configuration.

13. A computer readable medium having computer-executable instructions for performing the steps of claim 1.

14. A computer readable medium having computer-executable instructions for performing the steps of claim 4.

15. A computer readable medium having computer-executable instructions for performing the steps of claim 8.

16. A method for selecting an index configuration from a set of indexes based on a workload of queries to be executed against a database, the method comprising the steps of:

(a) determining based on the workload of queries one or more seed index configurations each comprising at most a predetermined number m of indexes from the set of indexes, wherein the predetermined number m is greater than or equal to one;

(b) successively adding one or more indexes from the set of indexes to each seed index configuration based on the workload of queries to produce one or more corresponding index configurations; and

(c) selecting one of the one or more corresponding index configurations produced for step (b) based on the workload of queries.

17. The method of claim 16, wherein the predetermined number m is two.

18. The method of claim 16, wherein the determining step (a) comprises the steps of:

(i) determining estimated costs to execute queries of the workload against the database for a set of index configurations each comprising at most the predetermined number m of indexes from the set of indexes, and

(ii) selecting from the set of index configurations an index configuration having a least estimated cost for the workload and any other index configurations having for the workload an estimated cost within a predetermined percent of the least estimated cost.

19. The method of claim 18, wherein the predetermined percent is approximately ten percent.

20. The method of claim 16, wherein each seed index configuration is a corresponding current index configuration and wherein the adding step (b) comprises the steps of:

(i) adding an index from the set of indexes to each corresponding current index configuration such that a total estimated cost of the workload for the corresponding current index configuration is reduced, and

(ii) repeating step (b)(i) until the addition of any index from the set of indexes to the corresponding current index configuration does not reduce the total estimated cost of the workload for the corresponding current index configuration.

21. The method of claim 20, wherein the adding step (b)(i) comprises the step of selecting from the set of indexes for addition to each corresponding current index configuration an index that would reduce the total estimated cost of the workload for the corresponding current index configuration the most.

22. The method of claim 16, wherein the selecting step (c) comprises the step of selecting from the one or more corresponding index configurations produced for step (b) an index configuration having a minimum total estimated cost for the workload.

23. The method of claim 16, wherein the adding step (b) comprises the step of adding one or more indexes from the set of indexes to each seed index configuration such that each corresponding index configuration produced for step (b) comprises at most a predetermined number k of indexes.

24. The method of claim 16, comprising the step of selecting candidate indexes from a plurality of indexes for inclusion in the set of indexes.

25. The method of claim 16, comprising the step of determining an index configuration for use by a database server to execute queries of the workload against the database as the selected index configuration.

26. A computer readable medium having computer-executable instructions for performing the steps of claim 16.

27. A computer readable medium having computer-executable instructions for performing the steps of claim 18.

28. A computer readable medium having computer-executable instructions for performing the steps of claim 20.

29. A method for selecting an index configuration from a first set of indexes based on a workload of queries to be executed against a database, the method comprising the steps of:

(a) determining a first seed index configuration comprising at most a predetermined number m of indexes from the first set of indexes, wherein the predetermined number m is greater than or equal to one;

(b) successively adding one or more indexes from the first set of indexes to the first seed index configuration to produce a second set of indexes;

(c) determining a second seed index configuration comprising at most a predetermined number n of indexes from the second set of indexes, wherein the predetermined number n is greater than or equal to one; and

(d) successively adding one or more indexes from the second set of indexes to the second seed index configuration to produce the selected index configuration.

30. The method of claim 29, wherein the determining step (a) comprises the steps of:

(i) determining estimated costs to execute queries of the workload against the database for a set of index configurations each comprising at most the predetermined number m of indexes from the first set of indexes, and

(ii) selecting the first seed index configuration from the set of index configurations based on the determined estimated costs.

31. The method of claim 30, wherein the database comprises a plurality of tables and wherein the determining step (a)(i) comprises the steps of:

(A) determining one or more atomic index configurations for the workload from the set of index configurations such that each determined atomic index configuration comprises only indexes on at most a predetermined number j of the tables of the database,

(B) determining estimated costs to execute queries of the workload against the database for each determined atomic index configuration using a query optimizer of a database server that is to execute queries of the workload against the database, and

(C) determining estimated costs to execute queries of the workload against the database for index configurations of the set of index configurations other than the determined one or more atomic index configurations based on the estimated costs determined for the determining step (a)(i)(B).

32. The method of claim 31, wherein the predetermined number m is two, the predetermined number j is two, and the predetermined number n is two.

33. The method of claim 30, wherein the selecting step (a)(ii) comprises the step of selecting the first seed index configuration as an index configuration from the set of index configurations having a minimum total estimated cost for the workload.

34. The method of claim 29, wherein the first seed index configuration is a current index configuration and wherein the adding step (b) comprises the steps of:

(i) adding an index from the first set of indexes to the current index configuration such that a total estimated cost of the workload for the current index configuration is reduced, and

(ii) repeating step (b)(i) until the addition of any index from the first set of indexes to the current index configuration does not reduce the total estimated cost of the workload for the current index configuration.

35. The method of claim 34, wherein the adding step (b)(i) comprises the step of selecting from the first set of indexes for addition to the current index configuration an index that would reduce the total estimated cost of the workload for the current index configuration the most.

36. The method of claim 29, wherein the determining step (c) comprises the steps of:

(i) determining estimated costs to execute queries of the workload against the database for a set of index configurations each comprising at most the predetermined number n of indexes from the second set of indexes, and

(ii) selecting the second seed index configuration from the set of index configurations based on the determined estimated costs.

37. The method of claim 36, wherein the determining step (c)(i) comprises the steps of:

(A) determining one or more atomic index configurations for the workload from the set of index configurations,

(B) determining estimated costs to execute queries of the workload against the database for each determined atomic index configuration using a query optimizer of a database server that is to execute queries of the workload against the database, and

(C) determining estimated costs to execute queries of the workload against the database for index configurations of the set of index configurations other than the determined one or more atomic index configurations based on the estimated costs determined for the determining step (c)(i)(B).

38. The method of claim 37, wherein the database comprises a plurality of tables and wherein each determined atomic index configuration may comprise indexes on any number of the tables of the database.

39. The method of claim 36, wherein the selecting step (c)(ii) comprises the step of selecting the second seed index configuration as an index configuration from the set of index configurations having a minimum total estimated cost for the workload.

40. The method of claim 29, wherein the second seed index configuration is a current index configuration and wherein the adding step (d) comprises the steps of:

(i) adding an index from the second set of indexes to the current index configuration such that a total estimated cost of the workload for the current index configuration is reduced, and

(ii) repeating step (d)(i) until the addition of any index from the second set of indexes to the current index configuration does not reduce the total estimated cost of the workload for the current index configuration.

41. The method of claim 40, wherein the adding step (d)(i) comprises the step of selecting from the second set of indexes for addition to the current index configuration an index that would reduce the total estimated cost of the workload for the current index configuration the most.

42. The method of claim 29, wherein the adding step (d) comprises the step of adding one or more indexes from the second set of indexes to the second seed index configuration such that the selected index configuration comprises at most a predetermined number k of indexes.

43. The method of claim 29, comprising the step of selecting candidate indexes from a plurality of indexes for inclusion in the first set of indexes.

44. The method of claim 29, comprising the step of determining an index configuration for use by a database server to execute queries of the workload against the database as the selected index configuration.

45. A computer readable medium having computer-executable instructions for performing the steps of claim 29.

46. A computer readable medium having computer-executable instructions for performing the steps of claim 31.

47. A computer readable medium having computer-executable instructions for performing the steps of claim 34.

48. A computer readable medium having computer-executable instructions for performing the steps of claim 37.

49. A computer readable medium having computer-executable instructions for performing the steps of claim 40.

50. A method for selecting an index configuration from a set of indexes based on a workload of queries to be executed against a database, the method comprising the steps of:

(a) determining a set of index configurations each comprising indexes of the set of indexes such that an estimated cost of the workload for a partial index configuration of each index configuration of the set of index configurations is within a predetermined factor of an estimated cost of the workload for a corresponding reference index configuration; and

(b) determining the selected index configuration from the set of index configurations based on an estimated cost of the workload for each index configuration of the set of index configurations.

51. The method of claim 50, wherein the determining step (a) determines the set of index configurations such that an estimated cost of the workload for every partial index configuration of each index configuration of the set of index configurations is within the predetermined factor of an estimated cost of the workload for a corresponding reference index configuration.

52. The method of claim 50, wherein the determining step (a) comprises the steps of:

(i) determining an initial current set of index configurations each comprising at most a predetermined number i of indexes from the set of indexes,

(ii) determining a current reference index configuration from the set of indexes,

(iii) determining whether an estimated cost of the workload for each index configuration of the current set is within the predetermined factor of an estimated cost of the workload for the current reference index configuration,

(iv) determining a new current set of index configurations comprising;

(A) each index configuration of the current set determined for the determining step (iii) to have an estimated cost within the predetermined factor of the estimated cost for the current reference index configuration, and

(B) index configurations comprising the indexes of each index configuration of the current set determined for the determining step (iii) to have an estimated cost within the predetermined factor of the estimated cost for the current reference index configuration and comprising an additional index from the set of indexes,

(v) incrementing the predetermined number i, and

(vi) repeating steps (ii) through (v) until the predetermined number i is equal to a predetermined number k such that each index configuration of the new current set comprises less than or equal to the predetermined number k of indexes from the set of indexes.

53. The method of claim 52, wherein the determining step (ii) comprises the steps of:

(A) determining the current reference index configuration as comprising at most the lesser of the predetermined number i or a predetermined number m of indexes from the set of indexes based on estimated costs to execute queries of the workload against the database for index configurations from the set of indexes, and

(B) if the predetermined number i is greater than the predetermined number m, successively adding one or more indexes from the set of indexes to the current reference index configuration such that the current reference index configuration comprises at most the predetermined number i of indexes.

54. The method of claim 50, wherein the determining step (b) comprises the step of determining the selected index configuration as an index configuration of the set of index configurations having a minimum total estimated cost for the workload.

55. The method of claim 50, comprising the step of selecting candidate indexes from a plurality of indexes for inclusion in the set of indexes.

56. The method of claim 50, comprising the step of determining an index configuration for use by a database server to execute queries of the workload against the database as the selected index configuration.

57. A computer readable medium having computer-executable instructions for performing the steps of claim 50.

58. A computer readable medium having computer-executable instructions for performing the steps of claim 52.