В процессе решения мигрировали на 5.6, лучше точно не стало
возможно производительность даже ухудшилась (ну или так совпало)

потом вышли на запрос, который обнулял 250 тыс строк (считай всю таблицу).
Сам запрос простейший: update a set a.x = 0;
Он выполнялся 20 секунд!. И в процессе выполнения в лог начинали сыпаться slow queries.

В реальности данные менялись у 1 тысячи строк, остальное оставалось нетронутым. Добавили условие по индексированному полю, чтобы менять только нужные и он стал менее секунды выполняться.

Остается вопрос, почему это все раньше работало....
подозреваю появление зависимостей которым нужна таблица, а она в этот момент обновляется. Пока они ждут, мгновенно вырастает очередь коннектов, они упираются в лимит и все падает

----

Все оказалось совсем не так. База не тормозила, тормозили веб-сервера

Цепочка примерно следующая
В час пик на веб серверах начинает увеличиваться время ответа. С 50-100ms до 1000-1500ms.
Каждый запрос висит дольше обычного и дольше занимает коннект к MySQL. В итоге все возможные коннекты выбираются и все упирается в max_mysql_connection

Веб-сервера хоть и работают медленнее, но все равно потихоньку шевелятся. У них количество допустимых процессов выше чем максимум коннектов к БД. В итоге мы думали что тормозит база. Там еще было некоторое количество slow запросов, но они видимо всегда были, просто пока не было ошибок мы на них внимания не обращали.

Проблему решаем следующим образом
1. Несколько перебалансировали раздачу нагрузки по веб-серверам, чтобы процессор равномернее использовался
2. Заказли еще один веб-сервер
3. Оптимизируем "тяжелые" страницы

P.S. Тем не менее TRIM на серверах бд все равно нужен и мы будем настоятельно просить инженеров хостера включить его