A method and system for eliminating unnecessary statistics collections for query optimization in a database stored on a computer. Statistics are unnecessary when a re-generated query execution plan that does not use the statistics is equivalent to an original query execution plan that uses the statistics. To determine this, an original query execution plan is created for each query in a specified workload using the statistics in the database. A search is performed of the statistics in order to enumerate one or more candidate sets of statistics to be eliminated. One or more of the candidate sets of statistics are removed from consideration prior to creating the re-generated query execution plan for each query in the specified workload. The re-generated query execution plan, which was created with one or more of the candidate sets of statistics removed from consideration, is compared with the original query execution plan, which was created using the statistics, in order to determine whether the re-generated query execution plan and the original query execution plan are equivalent. The one or more of the candidate sets of statistics removed from consideration are identified as unnecessary when the re-generated query execution plan and the original query execution plan are equivalent.