1. A method comprising: in response to receiving a first query, generating a first execution plan that is used to execute the first query and that involves accessing a particular database object; executing the first query by executing the first execution plan; storing a change threshold that indicates a first number of changes to the particular database object or a first change in size of the particular database object; receiving a second query, wherein the first execution plan may be used to execute the second query; in response to receiving the second query: determining a change metric that is associated with the particular database object, wherein the change metric indicates a second number of changes to the particular database object or a second change in size of the particular database object; and determining, based on a difference between the change metric and the change threshold, whether to generate an execution plan for the second query; in response to determining to generate an execution plan for the second query, generating a second execution plan; determining whether the second execution plan is the same as the first execution plan; and modifying the change threshold in response to determining that the second execution plan is the same as the first execution plan; wherein the method is performed by one or more computing devices.