1. Were the keys composite or not?  The correct key for the queries you listed is (device_id, date_added DESC).  In MySQL you'd add this by doing "ALTER TABLE location ADD INDEX (device_id, date_added DESC)"<p>MySQL uses one key per query, so having an index on (device_id) and an index on (date_added) individually will do no (or very little) good for the queries you listed.<p>2. MyISAM uses table-level locking.  This will block all reads (selects) while writes (insert, update, delete) are happening.  It does not prevent multiple selects from happening at the same time. If you have a write-heavy table that you are also reading from you need to be using InnoDB.<p>3. SELECT COUNT(*) FROM location should be instantaneous in MyISAM .  It will be slow(er) in InnoDB.  If this query was blocking it's because something was trying to write to the table.<p>4. Foreign key constraints have nothing to do with anything here.  That's one advantage of InnoDB, although most web apps I know don't use them, but not one that would help you.  Rather, what will help you is the table-level vs. row-level for MyISAM vs. InnoDB.<p>This allows selects to happen to unaffected rows while writes are happening.