¿Cuál es la forma más eficiente de actualizar consultas en MySQL?

Question

Estoy escribiendo una aplicación que necesita eliminar una gran cantidad de actualizaciones a la base de datos durante un período prolongado de tiempo, y me he quedado atrapado en cómo optimizar la consulta. Actualmente estoy usando INSERT INTO ... VALUES (..), (..) ON DUPLICATE KEY UPDATE, que funciona para llorar todos los valores en una consulta, pero se ejecuta insoportablemente lentamente en tablas grandes. Nunca necesito insertar filas.

Otros enfoques que he visto son actualizar usando SET value = CASE WHEN... (que sería difícil de generar debido a la forma en que estoy construyendo las consultas, y no estoy seguro sobre el rendimiento de CASE para cientos/miles de claves), y simplemente múltiples actualizaciones concatenadas. ¿O de estos sería más rápido que mi método actual?

Me desconcierta que, por lo que puedo decir, no hay una forma idiomática y eficiente de hacer esto en MySQL. Si realmente no hay una manera que sea más rápida que ON DUPLICATE KEY, valdría la pena cambiar a PostgreSQL y usar su UPDATE FROM ¿sintaxis?

¡Cualquier otra sugerencia también es muy apreciada!

EDITAR: Aquí está una de las tablas que se actualiza con frecuencia. He eliminado los nombres de la columna debido a que son 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;