Qual é a maneira mais eficiente de agrupar consultas UPDATE no MySQL?

Estou escrevendo um aplicativo que precisa liberar um grande número de atualizações no banco de dados por um longo período de tempo e fiquei preso em como otimizar a consulta. Atualmente estou usando INSERT INTO ... VALUES (..), (..) ON DUPLICATE KEY UPDATE, que funciona para agrupar todos os valores em uma consulta, mas é executado de forma extremamente lenta em tabelas grandes. Na verdade, eu nunca preciso inserir linhas.

Outras abordagens que vi são atualizar usando SET value = CASE WHEN...(o que seria difícil de gerar devido à maneira como estou construindo as consultas e não tenho certeza sobre o desempenho de CASEcentenas/milhares de chaves) e simplesmente várias concatenadas atualizações. Algum deles seria mais rápido que o meu método atual?

Fico perplexo que, até onde eu saiba, não exista uma maneira idiomática e eficiente de fazer isso no MySQL. Se realmente não houver uma maneira mais rápida que ON DUPLICATE KEY, valeria a pena mudar para o PostgreSQL e usar sua UPDATE FROMsintaxe?

Quaisquer outras sugestões também são muito apreciadas!

Edit: aqui está uma das tabelas que são atualizadas com frequência. Eu removi os nomes das colunas por serem irrelevantes.

CREATE TABLE IF NOT EXISTS `table` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `a` bigint(20) unsigned NOT NULL DEFAULT '0',
  `b` bigint(20) unsigned NOT NULL DEFAULT '0',
  `c` enum('0','1','2') NOT NULL DEFAULT '0',
  `d` char(32) NOT NULL,
  -- trimmed --
  PRIMARY KEY (`id`),
  KEY `a` (`a`),
  KEY `b` (`b`),
  KEY `c` (`c`),
  KEY `d` (`d`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8;