Что делать, если база данных сильно замедлилась?

Добрый день. У нас в компании база данных MySQL, и с недавнего времени она начала сильно тормозить. Запросы, которые раньше выполнялись за доли секунды, теперь могут выполняться по несколько минут. В таблицах около 1 миллиона записей, но раньше проблем с производительностью не было. Я попробовал оптимизировать запросы и создал индексы, но это не помогло. Возможно, проблема связана с самим сервером или настройками базы данных? Посоветуйте, что можно сделать, чтобы улучшить скорость работы базы данных.