Database index design based upon request importance and the reuse and modification of similar existing indexes

• US 5,404,510 A
• Filed: 05/21/1992
• Issued: 04/04/1995
• Est. Priority Date: 05/21/1992
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Smith, Gregory S., Pant, Sangam
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Lintz, Paul R.
• Application Number:
  US07/886,751
• Time in Patent Office: 1,048 Days
• Field of Search: 345/600, 345/425, 364/419.07, 364/419.19
• US Class Current: 1/1
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: Y10S 706/934 Information retrieval or Information management
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

Design of indexes in a relational database management system is based on a workload analysis of all requests in a system. Each request is assigned a value of importance, and requests are broken into expressions, contexts and columns to facilitate identification of candidate indexes. Candidate indexes are compared to existing indexes to determine whether the existing indexes can be reused or modified. Candidate indexes are classified as hashed or sorted. Based on the index design, record placement is selected to be hashed, sorted or by default. Related indexes and tables are clustered and the clusters are sized to fit file areas. Cache buffers are also defined.

Claims

1. For a database having plural tables, each of plural columns, stored in memory, a processor controlled method of generating indexes comprising:

identifying importance values for individual database requests; and

designing indexes to tables for the requests by identifying, by order of request importance, candidate indexes for requests, searching previously identified indexes for an index that is similar to each candidate index, and building upon previously identified indexes by reusing existing indexes and modifying existing indexes based upon match between indexes and upon importance values of requests for which the indexes are created.

2. A method as claimed in claim 1 wherein the importance value of a request is identified from expected frequency of processing and from individual importances of the request, a transaction which includes the request and a program which includes the transaction, with greater weighting toward transaction importance and greatest weighting toward program importance.

3. A method as claimed in claim 1 further comprising the steps of:

identifying columns and associated operators for individual table contexts within each expression of each request; and

identifying candidate indexes from the identified columns for individual contexts.

4. A method as claimed in claim 3 wherein the candidate indexes are ordered by request value of importance, the method further comprising, with identification of each candidate index, searching previously identified indexes for an existing index that is similar to the candidate index and choosing from the steps of a) creating a new index, b) reusing the best existing index and c) modifying the best existing index to satisfy the context of the candidate index, choice of steps a, b and c being dependent on match between the candidate index and the best existing index and the value of importance of the requests for which the indexes are identified.

5. A method as claimed in claim 4 wherein a best existing index is determined as a function of match of columns and keys of indexes, with greater weight being given toward match of keys.

6. A method as claimed in claim 4 wherein a candidate index is chosen only where the database management system uses indexes for the operators and data types of a respective context.

7. A method as claimed in claim 4 wherein a candidate index is identified only where the table of the context has sufficient cardinality.

8. A method as claimed in claim 4 wherein a candidate index is selected only where a column size is above a threshold size.

9. A method as claimed in claim 4 wherein the best existing index is reused for a candidate index if both indexes are hashed, both indexes have the same number of columns and all the columns match.

10. A method as claimed in claim 4 wherein the best existing index is reused if the best existing index is sorted, the candidate index is hashed, both indexes have the same number of columns and all the columns match in identity.

11. A method as claimed in claim 4 wherein the best existing index is reused if both indexes are sorted, both indexes have the same number of columns and all the columns match in identity and in position.

12. A method as claimed in claim 4 wherein the best existing index is reused if the best index is sorted, the candidate index is either hash or sorted, the best existing index has more columns and the columns of the candidate index match, in identity and in position, leading segments of the best existing index.

13. A method as claimed in claim 4 wherein the best existing index is changed to the candidate index if the best existing index is hash, the candidate index is sorted, the indexes have the same number of columns, the columns match in identity, and if importance of the candidate index exceeds a threshold relative to importance of the best existing index.

14. A method as claimed in claim 4 wherein the best existing index is changed to include the candidate index if the best existing index is hash, the candidate index is either hash or sorted, the best existing index has a lesser number of columns, all the columns of the best existing index match in identity to columns of the candidate index and the importance of the candidate index exceeds a threshold relative to importance of the best existing index.

15. A method as claimed in claim 4 wherein the best existing index is changed to the order and type of the candidate index if the best existing index is hash, the candidate index is either hash or sorted, the best existing index has more columns, all columns of the candidate index match in identity to columns of the best existing index and the importance of the candidate index is greater than a threshold relative to the importance of the best existing index.

16. A method as claimed in claim 4 wherein the best existing index is changed to the candidate index if the best existing index is sorted, the candidate index is either hash or sorted, the best existing index has a lesser number of columns, the columns of the best existing index match in identity and position, and the importance of the candidate index is greater than a threshold relative to the importance of the best existing index.

17. A method as claimed in claim 4 wherein the best existing index is reused if only some of the columns between the indexes match and the importance of the candidate index is less than a threshold relative to the importance of the best existing index.

18. A method as claimed in claim 1 further comprising the step of identifying index retrieval modes based on context operators.

19. A method as claimed in claim 18 wherein indexes are reused and modified as a function of importance and retrieval mode of an existing index and a candidate index.

20. A method as claimed in claim 1 further comprising the step of pruning indexes where a benefit of an index is determined to be less than a cost of the index in operation of the database management system.

21. A method as claimed in claim 20 wherein benefits are derived from importance of requests for which the index is identified and cost is derived from the importance of requests which result in changes to the indexed table.

22. A method as claimed in claim 21 wherein cost is derived from the importance of insert and delete requests on the indexed table.

23. A method as claimed in claim 21 wherein cost is derived from the importance of update requests on indexed columns.

24. A method as claimed in claim 1 further comprising the step of adding columns to indexes for index only retrieval.

25. A method as claimed in claim 1 further comprising the step of adding columns to indexes where the cardinality of the index is below a threshold.

26. A method as claimed in claim 1 further comprising the step of establishing hashed or sorted record placement strategy within selected tables dependent on importance and retrieval mode of indexes to the table and data types within the table.

27. A method as claimed in claim 26 further comprising establishing record placement strategy as a function of table volatility.

28. A method as claimed in claim 1 further comprising the step of establishing cluster groups including tables and indexes.

29. A method as claimed in claim 28 further comprising clustering together tables and hashed indexes where the tables are placed via the hashed indexes and the tables are joined using columns in the hashed indexes.

30. A method as claimed in claim 28 comprising clustering together tables and hashed indexes where the tables are placed via the hashed indexes.

31. A method as claimed in claim 28 further comprising assigning clusters to a plurality of devices as a function of importance of data within the clusters.

32. A method of physically designing a database having plural tables, each of plural columns, the method comprising:

A) identifying an absolute importance value for each database request based on the individual importance of the request, a transaction which includes the request and the program which includes the transaction, with greater weighting toward transaction importance and with greatest weighting toward program importance;

B) in a table index design;

1. by order of request importance, identifying candidate indexes from the identified columns for individual contexts where;

a. operator type of an associated operator is such that the database management system uses an index,

b. column size is less than a threshold size, and

c. column data type is permissible in an index;

2. identifying candidate index retrieval modes, including by sorting and hash, as a function of operator;

33. with identification of each candidate index, searching previously identified indexes for a best existing index that is similar to the candidate index and, where no best existing index is located, creating a new existing index from the candidate index and, where a best existing index is located, choosing from the steps of a) creating a new index, b) revising the best existing index and c) modifying the best existing index to satisfy the context of the candidate index, choice of steps a, b and c being dependent on importance of and retrieval mode of the candidate index and the best existing index, importance of an index being derived from absolute importance of requests for which the index is identified;

and

4. pruning indexes where benefit of an index, derived from importance of the requests for which the index is identified, is less than cost of the index, derived from importance of insert and delete requests on the indexed table and update requests on indexed columns.

35. A method as claimed in claim 33 further comprising the step of adding columns to indexes where the cardinality of the index is below a threshold.

36. A method as claimed in claim 33 wherein:

the best existing index is reused for a candidate index if both indexes are hashed, both indexes have the same number of columns and all the columns match;

the best existing index is reused if the best existing index is sorted, the candidate index is hashed, both indexes have the same number of columns and all the columns match in identity;

the best existing index is reused if both indexes are sorted, both indexes have the same number of columns and all the columns match in identity and in position;

the best existing index is reused if the best index is sorted, the candidate index is either hash or sorted, the best existing index has more columns and the columns of the candidate index match, in identity and in position, leading segments of the best existing index;

the best existing index is changed to the candidate index if the best existing index is hash, the candidate index is sorted, the indexes have the same number of columns, the columns match in identity, and if importance of the candidate index exceeds a threshold relative to importance of the best existing index;

the best existing index is changed to include the candidate index if the best existing index is hash, the candidate index is either hash or sorted, the best existing index has a lesser number of columns, all the columns of the best existing index match in identity to columns of the candidate index and the importance of the candidate index exceeds a threshold relative to importance of the best existing index;

the best existing index is changed to the order and type of the candidate index if the best existing index is hash, the candidate index is either hash or sorted, the best existing index has more columns, all columns of the candidate index match in identity to columns of the best existing index and the importance of the candidate index is greater than a threshold relative to the importance of the best existing index;

the best existing index is changed to the candidate index if the best exiting index is sorted, the candidate index is either hash or sorted, the best existing index has a lesser number of columns, the columns of the best exiting index match in identity and position, and the importance of the candidate index is greater than a threshold relative to the importance of the best existing index; and

the best existing index is reused if only some of the columns between the indexes match and the importance of the candidate index is less than a threshold relative to the importance of the best existing index.

37. A method as claimed in claim 33 further comprising clustering segmented string data types together.

38. A method as claimed in claim 33 further comprising assigning clusters to storage areas as a function of importance of data within the clusters.

40. A system as claimed in claim 38 wherein the means for identifying importance values identifies an importance value of a request from expected frequency of processing and from individual importances of the request, a transaction which includes the request and a program which includes the transaction, with greater weighting toward transaction importance and greatest weighting toward program importance.

41. A system as claimed in claim 38 wherein the means for designing indexes comprises:

means for identifying columns and associated operators for individual table contexts within each expression of each request; and

means for identifying candidate indexes from the identified columns for individual contexts.

42. A system as claimed in claim 40 wherein the candidate indexes are ordered by the means for designing and further comprising means for, with identification of each candidate index, searching previously identified indexes for an existing index that is similar to the candidate index and a) creating a new index, b) reusing the best existing index or c) modifying the best existing index to satisfy the context of the candidate index dependent on match between the candidate index and the best existing index and the values of importance of the requests for which the indexes are identified.

43. A system as claimed in claim 38 further comprising means for identifying index retrieval modes based on context operators.

44. A system as claimed in claim 42 wherein the means for designing reuses and modifies indexes as a function of importance and retrieval mode of an existing index and a candidate index.

45. A system as claimed in claim 38 further comprising means for pruning indexes where the benefit of an index is determined to be less than the cost of the index in operation of the database management system.

46. A system as claimed in claim 44 wherein benefits are derived from importance of requests for which the index is identified and cost is derived from the importance of requests which result in changes to the indexed table.

47. A system as claimed in claim 38 further comprising means for adding columns to indexes for index only retrieval.

48. A system as claimed in claim 38 further comprising means for adding columns to indexes where the cardinality of the index is below a threshold.

49. A system as claimed in claim 38 further comprising means for establishing hashed or sorted record placement strategy within selected tables dependent on importance and retrieval mode of indexes to the table and data types within the table.

34. A method of physically designing a database having plural tables, each of plural columns, the method comprising:

A) identifying an absolute importance value for each database request based on the individual importance of the request, a transaction which includes the request and the program which includes the transaction, with greater weighting toward transaction importance and with greatest weighting toward program importance;

B) in a table index design;

1. by order of request importance, identifying candidate indexes from the identified columns for individual contexts where;

a. the table of the context has sufficient cardinality,

b. operator type of an associated operator is such that the database management system uses an index,

c. column size is less than a threshold size, and

d. column data type is permissible in an index;

2. identifying candidate index retrieval modes, including by sorting and hash, as a function of operator;

3. with identification of each candidate index, searching previously identified indexes for a best existing index that is similar to the candidate index and, where no best existing index is located, creating a new existing index from the candidate index and, where a best existing index is located, choosing from the steps of a) creating a new index, b) revising the best existing index and c) modifying the best existing index to satisfy the context of the candidate index, choice of steps a, b and c being dependent on importance of and retrieval mode of the candidate index and the best existing index, importance of an index being derived from absolute importance of requests for which the index is identified;

4. identifying a benefit of an index, derived from importance of the requests for which the index is identified, and identifying a cost of the index, derived from importance of insert and delete requests on the indexed table and update requests on the indexed table and update requests on indexed columns, and pruning indexes where the benefit is less than the cost;

5. adding columns to indexes for index only retrieval;

C) establishing hashed or sorted record placement strategy within tables, dependent on importance and retrieval mode of indexes to the table, data types within the table and table volatility;

D) establishing cluster groups including;

1. clustering together tables and hashed indexes where the tables are placed via the hashed indexes and the tables are joined using columns in the hashed indexes;

2. clustering together tables and hashed indexes where the tables are placed via the hashed indexes and not clustered in step 1;

3. clustering tables and indexes in separate clusters where the tables are placed via sorted indexes;

4. establishing a cluster for each hash index not clustered in step 1 and 2;

5. establishing clusters for tables of importance over a threshold which are not clustered in steps 1 through 4; and

6. establishing clusters for tables of volatility over a threshold; and

7. establishing clusters for system files; and

E) sizing the clusters of step D to fit available storage areas and assigning clusters to storage areas.

39. In a physical design system for a database having plural tables, each of plural columns, stored in memory, a processor and a physical design program stored in memory comprising:

means for identifying importance values for individual database requests; and

means for designing indexes to tables for the requests by identifying by order of request importance, candidate indexes, searching previously identified indexes for an index that is similar to each candidate index, and building upon previously identified indexes by reusing existing indexes and modifying existing indexes based upon match between indexes and upon importance values of requests for which the indexes are created.

50. In a physical design system for a database having plural tables, each of plural columns, stored in memory, a processor and a physical design program stored in memory comprising:

A) means for identifying an absolute importance value for each database request based on the individual importance of the request, a transaction which includes the request and the program which includes the transaction;

B) means for designing a table index including;

1. means for identifying, by order of request importance, candidate indexes from the identified columns for individual context;

2. means for identifying candidate index retrieval modes, including by sorting and hash, as a function of operator;

3. means for searching with identification of each candidate index, previously identified indexes for a best existing index that is similar to the candidate index and, where no best existing index is located, creating a new existing index from the candidate index and, where a best existing index is located, a) creating a new index, b) revising the best existing index or c) modifying the best existing index to satisfy the context of the candidate index dependent on importance of and retrieval mode of the candidate index and the best existing index, importance of an index being derived from absolute importance of requests for which the index is identified; and

4. means for pruning indexes where benefit of an index, derived from importance of the requests for which the index is identified, is less than cost of the index, derived from importance of insert and delete requests on the indexed table and update requests on indexed columns.

52. A method as claimed in claim 50 wherein the step of designing indexes comprises:

identifying columns and associated operators for individual table contexts within each expression of each request; and

identifying candidate indexes from the identified columns for individual contexts.

51. For a database having records stored in memory which are organized to include logically grouped and indexable data elements, a processor controlled method of generating indexes comprising:

identifying importance values for individual database requests; and

designing indexes to the database for the requests based upon importance values of requests for which the indexes are created by ordering requests by importance values, identifying, by order of request importance, candidate indexes for requests, searching previously identified indexes for an index that is similar, to each candidate index, and building previously identified indexes by reusing existing indexes and modifying existing indexes based upon match between indexes.