Защо моята заявка с няколко колони е драматично по-бавна от съответните заявки с една колона, дори и с индекс от няколко колони?

Създадохте ли индекс stop_id, departure_time ? Тъй като departure_time, stop_id няма да направи абсолютно нищо.

Това е наистина труден - има всички възможни лоши неща за работа с индекси :(

Имате диапазон, ИЛИ и несвързан IN - няма да стане по-лошо от това.

Опитайте stop_id, departure_time и ако не помогне, тогава не можете да направите нищо друго освен да преминете към PostgreSQL.

Можете също да опитате да пренапишете заявката като:

SELECT * 
from stop_times 
WHERE ( stop_times.stop_id IN(51511,51509,51508,51510,6,53851,51522,51533)
      AND departure_time BETWEEN '02:41' AND '05:41'
      )
   OR ( stop_times.stop_id IN(51511,51509,51508,51510,6,53851,51522,51533)
      AND departure_time BETWEEN '26:41' AND '29:41' 
      ) 

или:

    SELECT * 
    from stop_times 
    WHERE ( stop_times.stop_id IN(51511,51509,51508,51510,6,53851,51522,51533)
          AND departure_time BETWEEN '02:41' AND '05:41'
          )
UNION ALL
    SELECT * 
    from stop_times 
    WHERE ( stop_times.stop_id IN(51511,51509,51508,51510,6,53851,51522,51533)
          AND departure_time BETWEEN '26:41' AND '29:41' 
          )