Early stopping scheme for budget aware index tuning

A method of performing index tuning with early stopping for a database, the method comprising:

• receiving a workload to be performed on the database at a database management system (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 the 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.

An index tuner for a database management system (DBMS), the index tuner comprising:

• a workload parsing/analysis component configured to receive a workload to be performed on a database, the workload including a plurality of queries;
• a candidate index generating component configured to generate a set of candidate indexes for performing the workload;
• a configuration enumeration component 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;
• make what-if calls to a query optimizer of the DBMS with query-index configuration pairs to determine what-if costs for each of the query-index configuration pairs, each of the query-index configuration pairs including a query and index configurations enumerated for the query;
• and
• combine the enumerated index configurations having a lowest what-if cost for each query in the workload to form a recommended index configuration for the DBMS to use to for the workload;
• and
• an early stopping checker (ESC) component configured to:
• perform early stopping checks at a current time point to determine when early stopping of an index tuning process should be invoked, the early stopping checks including:
• determine 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 an upper bound and a lower bound for an 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;
• compare 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,
• continue the early stopping checks in response to the index tuning curve being convex or flat at the current time point,
• compare 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;
• cause 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
• continue 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.