[tom_pinckney]

Definitely want to second the advice to use EXPLAIN.

MySQL has a lot of very specific limitations about when it will and will not use the available indices. It also matters how you created the indices (one index on multiple columns vs multiple indices on individual columns).

For example, if you created a single index with the columns (date_added, device_id) MySQL would not be able to use the index since device_id is the second part of the index, not the first and thus not available for use in the WHERE clause.

See http://dev.mysql.com/doc/refman/5.1/en/mysql-indexes.html for more limitations.