explain analyze <sql>
и смотри, где идёт seq scan и в целом тратится больше всего времени.
Если лень разбираться с темой, попробуй метод научного тыка. На реплике базы поиграйся с индексами на order.order_id и order.order_status_id, а потом на order_id других джойнящихся таблиц, начиная с самых жирных.
Может и наоборот, таблицы излишне заиндексированы, удаление строки приводит к тяжёлой перестройке индексов.
Так что делай explain и гугли.