Were those single indexes like CREATE INDEX index_1 ON Locations(id) CREATE INDEX index_2 ON Locations(user_id) ...? If you have multiple single column i

Were those single indexes like CREATE INDEX index_1 ON Locations(id) CREATE INDEX index_2 ON Locations(user_id) ...? 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.