¿Por qué mi consulta de varias columnas es considerablemente más lenta que las correspondientes consultas de una sola columna, incluso con un índice de varias columnas?

¿Creó un índice stop_id, departure_time? ? Porque departure_time, stop_id no hará absolutamente nada.

Esto es un realmente difícil:tiene todas las cosas malas posibles para tratar con índices :(

Tiene un rango, un OR y un IN no contiguos; no hay nada peor que eso.

Prueba stop_id, departure_time y si no ayuda, entonces no hay mucho que pueda hacer salvo cambiar a PostgreSQL.

También puede intentar reescribir la consulta como:

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

o:

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