Patent ID: 7139778

Claim:
In a relational database system, a computer implemented method for enumerating a set of physical design structures that optimizes database performance over a given workload consisting of workload entries comprising queries and updates that have been executed against the database, the method comprising the steps of: selecting a workload entry from the workload; identifying a set of candidate structures relevant to the workload entry; assigning a benefit to each of the candidate structures by evaluating the workload entry in the presence of subsets of a candidate structure to obtain an actual benefit for each subset of the candidate structure, forming a set of constraints on the benefit of the candidate structure, the set of constraints comprising a set of simultaneous linear inequations including a minimum value and a maximum value based on the actual benefit obtained for each subset of the candidate structure, the minimum value comprising the actual benefit divided by a first constant and the maximum value comprising the actual benefit multiplied by a second constant, and determining the benefit of the candidate structure by resolving the set of constraints; and enumerating the set of physical design structures based on the determined benefit for each of the candidate structures.