What SQL was running, and what was the query plan?
ActiveRecord is notorious for generating terrible, terrible SQL.
Edit: What I would expect to see would be index scan on device id, then sort + limit. So the important factor would be rows per device, not total rows.
Queries like that should be very, very fast even with low amounts of ram. Good article, but consider using EXPLAIN a few times first before embarking on such adventures. :)
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.
