Если запрос всё равно медленный после добавления нескольких индексов - какой алгоритм диагностики и что делать?

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

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

EXPLAIN ANALYZE выполняет запрос, поэтому на нагруженной системе используйте его осторожно. Затем изменяйте один фактор: запрос, индекс, статистику или структуру данных — и сравнивайте результат на одинаковых условиях.