Какие вы знаете методы оптимизации времени выполнения запроса (кроме оптимизации самого запроса)?

Это сильно зависит от СУБД и от запроса. Возможно, оптимизировать действительно нечего.
Старший БД Разработчик должен был сам создать нужные индексы.
Какие ещё есть средства:
- параметры БД
- написать план выполнения запроса (hint) https://ru.wikipedia.org/wiki/Подсказка_(SQL)
- обновить статистику, добавить больше статистики
- создать materialized view https://ru.wikipedia.org/wiki/Материализованное_представление
- изменить опции физического хранения таблиц, но для этого надо пересоздавать таблицы, что слишком сложно и потому не всегда возможно.

"Какими средствами БД мы можем еще больше оптимизировать время выполнения запроса?
Я знаю только один - добавить недостающие индексы.
А вы? :)"
Подумать,
0 разумна ли структура базы
1 а нужен ли этот запрос
2 а что на самом деле нужно

Мазай дело говорит. Однако, "оптимизировать уже нечего" - это весьма редкий случай. Сам не раз ускорял за архитекторами. :) План исполнения выложи - точнее скажу.

По методу реализации могут быть тормоза, например на pl написано то, что чистым sql можно сделать и параллельность страдает. Ещё если запрос сложный, СУБД не всегда может адекватный план построить. Тогда его нужно разделить через materialize или temporary table. Второе допускает индексы. Ещё можно добавить параллелизму на стороне сервера. Также можно долить параллелизму на стороне клиента, если запрос асинхронный и сервер с сетью позволяют. У меня целая методика есть, только публиковать ее нельзя. :)