Linear programming approach to assigning benefit to database physical design structures

For use in a relational database system, a computer readable medium comprising computer-executable instructions for performing 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.

For use in a relational database system, an apparatus 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 apparatus comprising:

• an entry selector for selecting a workload entry from the workload;
• a candidate identification tool for identifying a set of candidate structures relevant to the workload entry;
• a benefit assignment tool for 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
• a design enumerator for enumerating the set of physical design structures based on the determined benefit for each candidate structure.

For use in a relational database system, an apparatus 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 apparatus comprising:

• means for selecting a workload entry from the workload;
• means for identifying a set of candidate structures relevant to the workload entry;
• means for 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
• means for enumerating the set of physical design structures based on the determined benefit for each candidate structure.