Varför är min sökfråga med flera kolumner dramatiskt långsammare än motsvarande frågor med en kolumn, även med ett index med flera kolumner?

Har du skapat ett index stop_id, departure_time ? Eftersom departure_time, stop_id kommer att göra absolut ingenting.

Det här är en på riktigt svårt - det har alla möjliga dåliga saker för att hantera index :(

Du har ett intervall, ett OR och ett icke sammanhängande IN - det blir inte värre än så.

Testa stop_id, departure_time och om det inte hjälper så finns det inget du kan göra annat än att byta till PostgreSQL.

Du kan också prova att skriva om frågan som:

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' 
      ) 

eller:

    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' 
          )