The subject technology receives a first query plan corresponding to a first query, the first query plan comprising a new query plan different than a previous query plan for the first query. The subject technology determines a value indicating an estimated improvement in execution time of the first query plan in comparison to a previous execution time of the previous query plan. The subject technology determines that the value is greater than a threshold value. The subject technology, in response to the value being greater than the threshold value, executes the first query using the first query plan.