Were those single indexes like
  CREATE INDEX index_1 ON Locations(id)
  CREATE INDEX index_2 ON Locations(user_id)
  ...?<p>If you have multiple single column indexes it won't help you here.  The mysql query planner probably correctly guessed the table scan was a better option than hash joining the results of two seeks given the machine's limited memory. It also probably underestimated the cost of disk IO on a virtual machine though.