Como devo proceder para indexar uma consulta com duas condições de intervalo?

Próximo da série…

CREATE TABLE `Alarms` (
  `AlarmId` INT(10) UNSIGNED NOT NULL AUTO_INCREMENT,
  `DeviceId` BINARY(16) NOT NULL,
  `Code` BIGINT(20) UNSIGNED NOT NULL,
  `Ended` TINYINT(1) NOT NULL DEFAULT '0',
  `NaturalEnd` TINYINT(1) NOT NULL DEFAULT '0',
  `Pinned` TINYINT(1) NOT NULL DEFAULT '0',
  `Acknowledged` TINYINT(1) NOT NULL DEFAULT '0',
  `StartedAt` TIMESTAMP NOT NULL DEFAULT '0000-00-00 00:00:00',
  `EndedAt` TIMESTAMP NULL DEFAULT NULL,
  `MarkedForDeletion` TINYINT(1) NOT NULL DEFAULT '0',
  PRIMARY KEY (`AlarmId`),
  KEY `Key1` (`Ended`,`Acknowledged`),
  KEY `Key2` (`Pinned`),
  KEY `Key3` (`DeviceId`,`Pinned`),
  KEY `Key4` (`DeviceId`,`StartedAt`,`EndedAt`),
  KEY `Key5` (`DeviceId`,`Ended`,`EndedAt`),
  KEY `Key6` (`MarkedForDeletion`,`DeviceId`,`Acknowledged`,`Ended`,`StartedAt`),
  KEY `Key7` (`MarkedForDeletion`,`DeviceId`,`Ended`,`Pinned`,`EndedAt`)
) ENGINE=INNODB;

Essa consulta é bastante lenta quando os carimbos de data e hora são escolhidos de modo que muitas linhas sejam correspondidas:

SELECT (((UNIX_TIMESTAMP(`StartedAt`)) DIV 900) * 900) AS `Period_TS`,
COUNT(`AlarmId`) AS `n`
FROM `Alarms`
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
GROUP BY `Period_TS` ASC;

Acredito nisso porque estou misturando condições de faixa em dois campos (DeviceId eStartedAt)

Se isso for verdade, o que posso fazer para resolver o problema? Talvez algo para acionar o uso de uma mesclagem de índice?

questionAnswers(2)

yourAnswerToTheQuestion