Automated query tuning. A database query to be executed against a database is received. The database query is analyzed to determine one or more potential indexes to be evaluated. The one or more potential indexes are evaluated to determine if an optimization utilizing a selected potential index provides improved performance over performing the database query without the selected potential index. The one or more potential indexes are scored based on results of the evaluating. A recommendation of one or more of the potential indexes is provided to a source of the database query.