Всегда ли для ускорения запроса к базе данных нужно индексировать таблицу?

Нет. Узким местом могут быть лишние строки, неудачный JOIN, сортировка, блокировки, N+1 или передача данных. Индекс полезен только если план запроса сможет выгодно его использовать.

Начните с плана и измерений, актуальной статистики и реальных параметров. Иногда достаточно выбрать меньше колонок, убрать повторные запросы, изменить способ агрегации или ограничить выборку. Для маленькой таблицы или чтения значительной доли строк sequential scan может быть оптимальным. Каждый индекс занимает место и замедляет изменения данных; лишние индексы не бесплатны. После исправления проверьте не только один SELECT, но и общую нагрузку, чтобы ускорение чтения не ухудшило запись.