Как оптимизировать базу данных MySQL (innoDB)?

Включить логирование медленных запросов MySQL, после чего оптимизировать, добавить индексы.
Обратить внимание на то, что индексы могут приводить и к падению производительности, так что неиспользуемые лучше удалять.
Убедиться, что не просто индексы проставлены, а проставлены правильно.
Включить логирование atop на несколько дней, чтобы была возможность понаблюдать, что происходить в системе, когда "начинает виснуть всё". Может быть, вообще не в MySQL дело?
В Laravel запросы делаются к базе с помощью Active Record - бывает так, что вместо JOIN в базу летит гора запросов циклом - это не оптимально.
Как уже выше писали, нужно использовать кеширование - это ощутимо снизит нагрузку.

Вопрос закрыт, проблема была в конфигурации MySQL, как я и предполагал, а не в индексах, или построении запросов. 
Изменили под наш конфиг машины данные параметры MySQL:
1) max_allowed_packet увеличили (до 64мб)
2) key_buffer_size увеличен (до 64мб)
3) innodb_buffer_pool_size значительно уменьшен (до 4гб)
4) max_connections значительно увеличены (до 10000)
5) query_cache_size увеличен (до 16мб)
А также добавили и включили файл подкачки, но он пока не задействован, т.е конфиг сделал главное дело.