Slow sql query in Openstack

We ran into a slow sql query on openstack (essex) yesterday. Our setup produces roughly 100k rows/month in the instances table and since nova doesn't prune old instance data from the database it will continue to grow.

The slow query was selecting all instance metadata with the where clause:
WHERE instances.deleted = 0 AND instances.host = 'prodnc16';

instances.deleted is unindexed, so mysql did a disk search on almost all rows. Adding an index on the column fixed the problem:
create index deleted_index on instances(deleted);

edit: I found another query that seemed to require an index on instances.host.

+----+-------------+---------------------------------------+--------+---------------+-------------+---------+--------------------------------------------------------------+--------+-------------+
| id | select_type | table                                 | type   | possible_keys | key         | key_len | ref                                                          | rows   | Extra       |
+----+-------------+---------------------------------------+--------+---------------+-------------+---------+--------------------------------------------------------------+--------+-------------+
|  1 | SIMPLE      | instances                             | ALL    | NULL          | NULL        | NULL    | NULL                                                         | 360705 | Using where |
|  1 | SIMPLE      | instance_types_1                      | eq_ref | PRIMARY       | PRIMARY     | 4       | nova.instances.instance_type_id                              |      1 |             |
|  1 | SIMPLE      | instance_info_caches_1                | eq_ref | instance_id   | instance_id | 110     | nova.instances.uuid                                          |      1 |             |
|  1 | SIMPLE      | instance_metadata_1                   | ref    | instance_id   | instance_id | 4       | nova.instances.id                                            |      1 |             |
|  1 | SIMPLE      | security_group_instance_association_1 | ref    | instance_id   | instance_id | 5       | nova.instances.id                                            |      1 |             |
|  1 | SIMPLE      | security_groups_1                     | eq_ref | PRIMARY       | PRIMARY     | 4       | nova.security_group_instance_association_1.security_group_id |      1 |             |
+----+-------------+---------------------------------------+--------+---------------+-------------+---------+--------------------------------------------------------------+--------+-------------+

After creating index on instances.host

+----+-------------+---------------------------------------+--------+---------------+-------------+---------+--------------------------------------------------------------+------+-------------+
| id | select_type | table                                 | type   | possible_keys | key         | key_len | ref                                                          | rows | Extra       |
+----+-------------+---------------------------------------+--------+---------------+-------------+---------+--------------------------------------------------------------+------+-------------+
|  1 | SIMPLE      | instances                             | ref    | eriktest2     | eriktest2   | 768     | const                                                        |  100 | Using where |
|  1 | SIMPLE      | instance_types_1                      | eq_ref | PRIMARY       | PRIMARY     | 4       | nova.instances.instance_type_id                              |    1 |             |
|  1 | SIMPLE      | instance_info_caches_1                | eq_ref | instance_id   | instance_id | 110     | nova.instances.uuid                                          |    1 |             |
|  1 | SIMPLE      | instance_metadata_1                   | ref    | instance_id   | instance_id | 4       | nova.instances.id                                            |    1 |             |
|  1 | SIMPLE      | security_group_instance_association_1 | ref    | instance_id   | instance_id | 5       | nova.instances.id                                            |    1 |             |
|  1 | SIMPLE      | security_groups_1                     | eq_ref | PRIMARY       | PRIMARY     | 4       | nova.security_group_instance_association_1.security_group_id |    1 |             |
+----+-------------+---------------------------------------+--------+---------------+-------------+---------+--------------------------------------------------------------+------+-------------+