— Скопируйте всю вашу таблицу в temporary table и повыполняйте Ваш update с ней. Это исключит диск.
— Меряете время где? В клиентском скрипте? Попробуйте запустить его на машине с мусклом (пусть хостер сам запустит, если Вас не пускает на машину с мусклом).