Eliminar datos de InnoDB es la operación más costosa que puede solicitarle. Como ya descubrió, la consulta en sí no es el problema; de todos modos, la mayoría de ellos se optimizarán con el mismo plan de ejecución.
Si bien puede ser difícil entender por qué los DELETES de todos los casos son los más lentos, hay una explicación bastante simple. InnoDB es un motor de almacenamiento transaccional. Eso significa que si su consulta se abortó a la mitad, todos los registros aún estarían en su lugar como si nada hubiera pasado. Una vez que se complete, todo desaparecerá en el mismo instante. Durante la ELIMINACIÓN, otros clientes que se conecten al servidor verán los registros hasta que se complete la ELIMINACIÓN.
Para lograr esto, InnoDB utiliza una técnica llamada MVCC (Multi Version Concurrency Control). Básicamente, lo que hace es dar a cada conexión una vista instantánea de toda la base de datos tal como estaba cuando comenzó la primera declaración de la transacción. Para lograr esto, cada registro en InnoDB internamente puede tener múltiples valores, uno para cada instantánea. Esta es también la razón por la que COUNTing en InnoDB lleva algo de tiempo; depende del estado de la instantánea que vea en ese momento.
Para su transacción DELETE, todos y cada uno de los registros que se identifican de acuerdo con las condiciones de su consulta se marcan para su eliminación. Como otros clientes pueden estar accediendo a los datos al mismo tiempo, no puede eliminarlos inmediatamente de la tabla, porque tienen que ver su instantánea respectiva para garantizar la atomicidad de la eliminación.
Una vez que se han marcado todos los registros para su eliminación, la transacción se confirma con éxito. E incluso entonces, no se pueden eliminar inmediatamente de las páginas de datos reales, antes de que todas las demás transacciones que funcionaron con un valor de instantánea antes de su transacción DELETE también hayan finalizado.
De hecho, sus 3 minutos no son realmente tan lentos, considerando el hecho de que todos los registros deben modificarse para prepararlos para su eliminación de una manera segura para las transacciones. Probablemente "escuchará" el funcionamiento de su disco duro mientras se ejecuta la sentencia. Esto se debe al acceso a todas las filas. Para mejorar el rendimiento, puede intentar aumentar el tamaño del grupo de búfer de InnoDB para su servidor e intentar limitar otros accesos a la base de datos mientras ELIMINA, lo que también reduce la cantidad de versiones históricas que InnoDB tiene que mantener por registro. Con la memoria adicional, InnoDB podría leer su tabla (principalmente) en la memoria y evitar el tiempo de búsqueda del disco.