¿Cómo debo indexar una consulta con dos condiciones de rango?

IN es una especie de entre = y un 'rango'. Por lo tanto, discuto con el título de la pregunta. Dos rangos es virtualmente imposible de optimizar; un IN además, un rango tiene alguna posibilidad de optimización.

Basado en

WHERE `StartedAt` >= FROM_UNIXTIME(1518990000)  
AND   `StartedAt` <  FROM_UNIXTIME(1518998400) 
AND `DeviceId` IN (
    UNHEX('00030000000000000000000000000000'),
    UNHEX('000300000000000000000000000181cd'),
    UNHEX('000300000000000000000000000e7cf6'),
    UNHEX('000300000000000000000000000e7cf7'),
    UNHEX('000300000000000000000000000f423f')
) AND `MarkedForDeletion` = FALSE

Proporcionaría 2 índices y dejaría que el Optimizador decida cuál usar:

INDEX(MarkedForDeletion, StartedAt, DeviceId)
INDEX(MarkedForDeletion, DeviceId, StartedAt)

Algunas versiones más nuevas de MySQL/MariaDB pueden saltar y hacer uso de las 3 columnas en el segundo índice. En todas las versiones, las 2 primeras columnas de cualquiera de los índices lo convierten en un candidato. La elección puede estar determinada por las estadísticas y puede (o no) ser la elección "correcta".

Desde AlarmId no puede ser NULL , usa el patrón:COUNT(*) .

Después de realizar ese cambio, cada uno de mis índices está "cubriendo", lo que brinda un impulso adicional en el rendimiento.