A cost estimator may estimate execution costs for execution of at least one query against a database, using at least one existing index, if any, and based on estimation criteria determined from analyzing the query execution. A candidate index provider may provide candidate indexes, based on the estimation criteria, and re-estimate the execution costs to obtain updated execution costs, using the candidate indexes. An index recommender may recommend a recommended index, based on the updated execution costs.