MySQL параллельные запросы на изменение

К производительности это отношение имеет довольно косвенное, по-моему.

Ничего себе у вас там запросы (-:Е

Используйте таблицы типа InnoDB вместо MyISAM. У них блокировка построчная. Собственно, в доках примерно это и написано

А что вы хотели? Если у вас есть запросы на модификацию, которые длятся по 10-20-30 минут, то тут ничего не сделаешь, производить две модицикации одновременно невозможно. На сегодняшний день существует следуюшие варианты:
1) При модификации отношение целиком блокируется. Именно целиком, если блокировка построчная, то другой процесс может изменить строку так, что первый вроде бы как и не должен её менять, но у него это уже заложено, или наоборот, пропустить строку, которую надо поменять.
2) Использовать транзакции. Тогда возможно одновременное выполнение произвольного числа запросов. Только надо учитывать, что в случае конфликта, например попытка модификации одного значений двумя транзакциями приведет к авайному останову одной из них. Т.е. в результате того, что кто-то чуток поменяет базу ваша 20 минутная транзакция может ёкнуться на 29 минуте.
3) Блокировки построчные. Работать будет быстрее, однако то, что после операции СУБД будет в том состоянии, в котором вы ожидали гарантировать нельзя. Например после UPDATE aaa SET bbb=1 WHERE bbb=0 не герентировано отсутсвие нулевых значений в bbb/
3) Отключить блокировки нафиг. Работать будет совсем быстро, однако в такос случае СУБД не может гарантировать чего-либо. Вообще чего-либо, даже сохранности данных.