Как ускорить выполнение запроса?
Тормозит, потому что MyISAM делает table lock для каждого такого запроса. Используйте InnoDB.
Смотрите какая у вас нагрузка на IO, возможно затык в этом (особенно если это сервер от Hetzner).