In a relational database system, a set of physical design structures is enumerated that optimizes database performance over a given workload consisting of workload entries that include queries and updates that have been executed against the database. An individual benefit is calculated for each candidate structure relevant to a given workload entry and these individual benefits are summed over the entries in the workload examined thus far. A workload entry is selected from the workload and a set of candidate structures relevant to the workload entry is identified. A benefit is assigned to each of the candidate structures by 1) evaluating the workload entry in the presence of subsets of candidate structures to obtain an actual benefit for each subset of candidate structures; 2) 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 3) determining the individual benefit of each candidate structure by resolving the constraints. The set of physical design structures is enumerated based on the determined benefit for each candidate structure.