Microsoft patents faster database tuning by stopping search early

1. A data processing system for database management system (DBMS), comprising: at least one processor; and a memory in communication with the at least one processor, the memory comprising executable instructions that, when executed by the processor alone or in combination with other processors, cause the data processing system to perform operations of: receiving a workload to be performed on a database at the DBMS for the database, the workload including a plurality of queries; generating a set of candidate indexes for performing the workload using a candidate index generating component of the DBMS; performing an index tuning process using a configuration enumeration component of the DBMS to select a recommended index configuration to use to execute the queries in the workload, the configuration enumeration component being configured to: use a configuration enumeration algorithm to identify index configurations from the set of candidate indexes for each query in the workload that can potentially improve performance of the DBMS in processing the workload; and make what-if calls to a query optimizer of the DBMS with query-index configuration pairs to determine what-if costs for the query-index configuration pairs; and select the recommended index configuration based on the determined what-if costs for the query-index configuration pairs; deriving a workload lower bound and a workload upper bound on the what-if cost for an index tuning curve for the workload using an early stopping checker (ESC) component of the DBMS, the index tuning curve representing a function that maps a number of what-if calls allocated at time t to the index tuning process for the workload to a percentage improvement of a best index configuration found so far during the index tuning process, the workload upper bound at a time point t corresponding to a derived what-if cost for the workload based on the index configurations found by the configuration enumerator at the time point t after t what-if calls have been allocated, the workload lower bound being derived from a sum of marginal cost improvement (MCI) upper bounds for a predetermined number of indexes with a largest MCI upper bound; and performing early stopping checks at a current time point to determine when early stopping of the index tuning process should be invoked, the early stopping checks including: determining an improvement rate for the what-if cost of the workload at the current time point, the improvement rate being determined with reference to a gap between the upper bound and the lower bound for the index tuning curve at the current time point using the ESC component, wherein the gap corresponds to a difference between an overall improvement rate and a latest improvement rate for the what-if cost of the index tuning process at the current time point; comparing the overall improvement rate to the latest improvement rate to determine whether the index tuning curve is convex, concave, or flat at the current time point, continuing the early stopping checks in response to the index tuning curve being convex or flat at the current time point, comparing the improvement rate to a predefined improvement rate threshold using the ESC component in response to the index tuning curve being concave at the current time point, to identify an early stopping point for the index tuning process; causing the configuration enumeration component to end the index tuning process before all budgeted what-if calls have been performed in response to the early stopping point being identified; and continuing to perform the early stopping checks until the early stopping point is identified in response the early stopping point not being identified at the current time point.