Identifying preferred indexes for databases

Claim 3

A method according to claim 1 , wherein said step of analyzing a sample of user queries includes an identification of indexable predicate sets.

Claim 4

A method according to claim 1 , wherein said step of analyzing a sample of user queries includes an identification of patterns for index-only access.

Claim 5

A method according to claim 1 , wherein said permutations include indexes suitable for index-only access.

Claim 6

A method according to claim 1 , wherein said database is a relational database.

Claim 7

A method according to claim 5 , wherein said preferred index set is identified for each table in said relational database.

Claim 8

A method according to claim 1 , wherein said steps of identifying index permutations and identifying a new preferred index set are repeated, and intermediate results are discarded in response to a change in the rate of preferred index set improvement.

Claim 9

A method according to claim 1 , wherein earlier permutations of indexes chosen progressively guide and restrict the search path of the process.

Claim 10

A method according to claim 1 , wherein said steps of identifying index permutations and identifying a new preferred index set are repeated and a later found preferred index, which has a much higher cost saving than an earlier preferred index causes said earlier preferred index to be discarded.

Claim 11

A method according to claim 1 , wherein said steps of identifying index permutations and identifying a new preferred index set are repeated and a later found preferred index, which has a higher cost saving than an earlier preferred index, causes preferred indexes from said earlier preferred index onwards to be discarded.

Claim 12

A method according to claim 1 , wherein said initial preferred index set comprises one index only.

Claim 13

A method according to claim 11 , wherein said initial preferred index set comprises one single column index only.

Claim 14

Preferred index identification apparatus configured to identify preferred indexes for a database system, comprising: input means configured to receive queries from users; analyzing means configured to analyze a sample of said user queries to identify candidate indexes; identifying means configured to (a) identify an initial preferred index set by processing said candidate indexes; (b) identify a first index permutation comprising said, initial preferred index set and a separate one of said candidate indexes: and (c) identify a second index permutation by processing said initial preferred index set and one of said candidate indexes such that said second index permutation includes a composite index of said candidate index and an index of said initial preferred index set; and comparison means configured to compare performances of said first and second index permutations and thereby identify a new preferred index set.

Claim 15

Preferred index identification apparatus configured to identify preferred indexes for a database system, comprising: input means configured to receive queries from users; analyzing means configured to analyze a sample of said user queries to identify candidate indexes; identifying means configured to (a) identify an initial preferred index set by processing said candidate indexes; (b) identify a first index permutation comprising said, initial preferred index set and a separate one of said candidate indexes: and (c) identify a second index permutation by processing said initial preferred index set and one of said candidate indexes such that said second index permutation includes a composite index of said candidate index and an index of said initial preferred index set; and comparison means configured to compare performances of said first and second index permutations and thereby identify a new preferred index set.

Claim 16

Apparatus according to claim 13 , wherein said analyzing means analyzes said user queries to identify patterns for index only access.

Claim 17

Apparatus according to claim 13 , wherein said analyzing means analyzes said user queries to identify patterns for index-only access.

Claim 18

Apparatus according to claim 13 , wherein said identifying means identifies index permutations for index only access.

Claim 19

Apparatus according to claim 13 , configured to identify preferred indexes for a relational database.

Claim 20

Apparatus according to claim 17 , configured to identify a preferred index set for each table in said relational database.

Claim 21

Apparatus according to claim 13 , wherein said identifying means is configured to repeatedly identify index permutations and preferred index sets, including means for discarding intermediate results in response to a change in the rate of preferred index set improvement.

Claim 22

Apparatus according to claim 13 , wherein said identifying means is configured to identify an initial preferred index set comprising only one index.

Claim 23

Apparatus according to claim 20 , wherein said initial preferred index set comprises one single column index only.

Claim 24

A computer-readable medium having computer-readable instructions executable by a computer such that, when executing said instructions, a computer will perform the steps of: analyzing a sample of user queries to identify candidate indexes; identifying an initial preferred index set by processing said candidate indexes; identifying a first index permutation comprising said initial preferred index set and a separate one of said candidate indexes; identifying a second index permutation by processing said initial preferred index set and one of said candidate indexes such that said second index permutation includes a composite index of said candidate index and an index of said initial preferred index set; and identifying a new preferred index set by comparing performance of said first and second index permutations.

Claim 25

A computer-readable medium having computer-readable instructions executable by a computer such that, when executing said instructions, a computer will perform the steps of: analyzing a sample of user queries to identify candidate indexes; identifying an initial preferred index set by processing said candidate indexes; identifying a first index permutation comprising said initial preferred index set and a separate one of said candidate indexes; identifying a second index permutation by processing said initial preferred index set and one of said candidate indexes such that said second index permutation includes a composite index of said candidate index and an index of said initial preferred index set; and identifying a new preferred index set by comparing performance of said first and second index permutations.

Claim 26

A computer-readable medium having computer-readable instructions according to claim 22 , such that when executing said instructions to analyze a sample of user queries, indexable predicate sets are identified.

Claim 27

A computer-readable medium having computer-readable instructions according to claim 22 , such that when executing said instructions to analyze a sample of user queries, patterns for index-only access are identified.

Claim 28

A computer-readable medium having computer-readable instructions according to claim 22 , such that when executing said instructions to compare the performance of index permutations, indexes suitable for index-only access are included.

Claim 29

A computer-readable medium having computer-readable instructions according to claim 22 , executable within the environment of a relational database.

Claim 30

A computer-readable medium having computer-readable instructions according to claim 26 , such that when executing said instructions, a computer will identify a preferred index set for each table in said relational database.

Claim 31

A computer-readable medium having computer-readable instructions according to claim 22 , such that when executing said instructions said steps of identifying index permutations and identifying a preferred index set are repeated.

Claim 32

A computer-readable medium having computer-readable instructions according to claim 28 , wherein intermediate results are discarded in response to a change in the rate of preferred index set improvement.

Claim 33

A computer-readable medium having computer-readable instructions according to claim 28 , such that when executing said instructions, a computer will stop repeating said repeated steps when new index permutations do not have a substantially increased performance.