Не получится, наверное, объяснить много, но хотя бы начну.
1) Включить логгирование медленных запросов в БД
2) Есть такая команда - EXPLAIN -
https://dev.mysql.com/doc/refman/8.0/en/using-expl...
Помогает понять как SQL-запрос должен работать
3) Индексами злоупотреблять тоже не надо. Обычно имеет смысл ставить индекс на поле в двух случаях: либо по этому полю связываются таблицы в JOIN'е, либо по нему происходит поиск. Больше индексов - больше потребление памяти.
4) Обычно настройка базы данных по моему опыту в итоге приходит к эмпирическому подбору размеров буферов и так далее, поскольку часто зависит от того, какие данные хранятся в базе и как обрабатываются
5) Все запросы надо посмотреть на предмет JOIN'ов и проанализировать при помощи EXPLAIN. Если две таблицы связаны по каким-то полям, не факт, что связывание будет в том направлении, в котором вы думаете. Тут на самом деле очень помогает построить схему SQL-запроса с таблицами и связями.
6) Иногда для того, чтобы индекс заработал, может потребоваться немного поменять SQL-запрос, зависит от БД и от планировщика запросов. Иногда помогает переписать запрос в обратном направлении или просто изменив порядок таблиц при связывании.
И т.д.
Я в данный момент решаю проблемы похожие вашим, но на PostgreSQL, принципы все те же. Иногда время выполнения запросов удается уменьшить до 15000 раз (на больших базах)