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.