Esta consulta SELECT tarda 180 segundos en finalizar

(¡Publicar mi comentario como respuesta ya que aparentemente marcó la diferencia!)

Si alguien quiere investigar esto más a fondo, acabo de hacer una prueba y encontré que es muy fácil de reproducir.

Crear tabla

CREATE TABLE `filler` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  PRIMARY KEY (`id`)
) 

Crear Procedimiento

CREATE PROCEDURE `prc_filler`(cnt INT)
BEGIN
        DECLARE _cnt INT;
        SET _cnt = 1;
        WHILE _cnt <= cnt DO
                INSERT
                INTO    filler
                SELECT  _cnt;
                SET _cnt = _cnt + 1;
        END WHILE;
END

Rellenar tabla

  call prc_filler(5000)

Consulta 1

SELECT id 
FROM filler 
WHERE id =  (SELECT MAX(id) FROM filler  WHERE id =   
 ( SELECT MIN(id) 
    FROM filler
    WHERE id between 2000 and 3000
    )
  )

Salida de explicación de Equals http://img689.imageshack.us/img689/5592/equals. png

Consulta 2 (mismo problema)

SELECT id 
FROM filler 
WHERE id in  (SELECT MAX(id) FROM filler  WHERE id in   
 ( SELECT MIN(id) 
    FROM filler
    WHERE id between 2000 and 3000
    )
  )

En la salida de explicación http://img291.imageshack.us/img291/8129/52037513. png