Approaches, techniques, and mechanisms are disclosed for maintaining a history of query plans executed for a database command, along with information related to each query plan. A database server receives a request to execute a particular command. The database server determines a plan for executing the particular command. The database server adds first information to a plan history associated with the particular command. The plan history comprises information related to a plurality of plans that have been generated for the particular command. The first information may include, for example, properties of the plan (including an outline of the plan) as well as statistics collected during execution of the plan. The database server may implement techniques for periodically refreshing information in a plan history. The database server may also implement techniques for purging old or less important plans.