1. In a relational database system, a 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 the candidate structures to obtain an actual benefit for each subset of candidate structures, forming a set of constraints on the structure benefits of candidate structures based on the actual benefits determined for each subset of candidate structures, and determining the benefit of each candidate structure by resolving the constraints; and enumerating the set of physical design structures based on the determined benefit for each candidate structure.