A database monitor tracks performance statistics and information about the execution of different SQL statements. A query optimizer benefits from these statistics when generating an access plan. In particular, the query optimizer, upon receiving an SQL statement, searches the records of the database monitor for similar SQL statements that have previously been executed. As part of determining the best access plan for the current SQL statement, the query optimizer considers the information retrieved from the database monitor. In this way, the access plan that is generated can automatically be tuned based on empirical performance evidence.