Optimización de indexación simple

Como se explica en el comentario anterior, el INDEX(Dob) no se usa, ya que se trata de un índice en año-mes-día . Tienes que crear un índice el mes-día .

Probablemente no sea la solución más elegante, pero:

CREATE TABLE `birthdayCard`(`Email` VARCHAR(255), `FirstName` CHAR(30), `LastName` CHAR(30),
                            `Mob` int, `Dob` int, 
                            PRIMARY KEY (Email), INDEX(`Mob`, `Dob`));

Consulte http://sqlfiddle.com/#!2/db82ff/1

Para una respuesta mejor (?):como MySQL no admite columnas calculadas, es posible que necesite activadores para completar columnas de "mes-día" y tener un índice en él:

CREATE TABLE `birthdayCard`(`Email` VARCHAR(255), `FirstName` CHAR(30), `LastName` CHAR(30),
                            `Dob` DATE,
                            `Birthday` CHAR(5),
                            PRIMARY KEY (Email), INDEX(`Birthday`));

CREATE TRIGGER ins_bithdayCard BEFORE INSERT ON `birthdayCard`
FOR EACH ROW
    SET NEW.`birthday` = DATE_FORMAT(NEW.`Dob`, "%m%d");

CREATE TRIGGER upd_bithdayCard BEFORE UPDATE ON `birthdayCard`
FOR EACH ROW
    SET NEW.`birthday` = DATE_FORMAT(NEW.`Dob`, "%m%d");

Esto permite inserciones "simples", preservando si es necesario el Dob completo como en su ejemplo original:

insert into birthdayCard (Email, FirstName, LastNAme, Dob) 
   values ("[email protected]", "Sylvain", "Leroux", '2013-08-05');

El SELECT la consulta debe modificarse para usar la nueva columna de "búsqueda":

SELECT * FROM `birthdayCard` WHERE Birthday = DATE_FORMAT(NOW(), "%m%d");

Establecer http://sqlfiddle.com/#!2/66111/3