Павел

При анализе результат не передается клиенту, время IO и передачи по сети не учитывается (а у Вас там 1.5 ляма строк, как сами сказали, к тому же относительно длинные строки могут быть).
И что Вы хотите добиться, сортируя огромный массив? Для дальнейшего анализа сортировка обычно не нужна, а для визуального анализа - нужна выборка поменьше. Уберете сортировку - сэкономите еще кучу времени. Это очень дорогая операция. (Хотя, если поставите ORDER BY device_id, time то сортировка может уйти из-за того, что сам по себе индекс хранит значения в отсортированном виде)

И вот это

CASE
    WHEN (duration > (extract(epoch from (time - '2015-08-29 12:36:50'))) )
    THEN extract(epoch from (time - '2015-08-29 12:36:50'))
    ELSE duration
  END AS trim_duration

Заменить на

LEAST(duration, extract(epoch from (time - '2015-08-29 12:36:50')))

Так чуть понятнее и короче, хотя сути и стоимости особо не меняет.

Положим у нас есть таблица clients с полями client_id и service_id.
Логика: находим всех, у кого есть услуга, делаем джойн и отсеиваем тех, кто под условие джойна не попал.

select distinct c.client_id
from clients c
left join (select client_id
                  from clients
                      where service_id = 5) s on s.client_id = c.client_id
where s.client_id is null