A method is provided for tuning a database to recommend a set of physical design structures for the database that optimize database performance for a given workload given a total time bound that defines a maximum amount of time that can be spent tuning the database. A cumulative set of recommended structures is maintained and incrementally updated based on tuning that is performed in intervals over portions of the workload. The cumulative set of recommended structures is updated by tuning the database by examining a predetermined portion of the workload during a time slice that is a fraction of the total time bound. At the end of the time slice, a set of recommended structures has been enumerated that is based on the workload portions that have been examined thus far. The set of recommended structures is updated until all queries in the workload have been examined or until the time bound is reached.