Acelere ORDER BY e LIMIT no MySQL

Tenho uma tabela com registros de contato e os clientes desejam pesquisar nessa tabela para encontrar registros com um endereço de e-mail correspondente (filtrado pelo ID da conta). Os resultados são paginados por uma API RESTful.

Isso resulta em consultas como as abaixo sendo executadas:

SELECT * FROM CONTACT
WHERE deleted is null AND email like '%Matt%' AND accountid=1 
ORDER BY lastname LIMIT 0,50;

Nesta tabela, existem índices em email, accountide lastname. No geral, esta tabela possui 3,6 milhões de linhas e, neste exemplo específico accountid, possui 170.000 linhas. Esta consulta específica está levando cerca de 2 minutos e 30 segundos para ser concluída.

Se eu alterar a consulta para remover a ORDER BYcláusula, a consulta terminará em cerca de 0,6 segundos. Se eu alterar a consulta para remover a LIMITcláusula, a consulta terminará em cerca de 0,23 segundos.

Eu li este artigo , mas não tenho certeza do que mais posso fazer para melhorar esta consulta. Sei que o emailíndice não será usado por causa da pesquisa curinga completa, mas achei que o lastnameíndice ajudaria nas coisas de ORDER BYqualquer maneira.

mysql> explain SELECT * FROM CONTACT WHERE deleted is null AND email like '%Matt%' AND accountid=1 ORDER BY lastname LIMIT 0,50;
+----+-------------+-------+-------+---------------+----------+---------+------+------+-------------+
| id | select_type | table | type  | possible_keys | key      | key_len | ref  | rows | Extra       |
+----+-------------+-------+-------+---------------+----------+---------+------+------+-------------+
|  1 | SIMPLE      | a     | index | accountid     | lastname | 53      | NULL | 5804 | Using where |
+----+-------------+-------+-------+---------------+----------+---------+------+------+-------------+
1 row in set (0.00 sec)

Como posso melhorar esta consulta para terminar mais rapidamente com as cláusulas ORDER BYe ?LIMIT 0,50