Speed up ORDER BY and LIMIT in MySQL I have a table with contact records, and clients wish to search this table to find records with a matching email address (filtered by account ID). The results are paginated by a RESTful API.

This results in queries like the below being run:

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


In this table, there are indexes on email, accountid, and lastname. Overall, this table has 3.6 million rows, and in this particular example this accountid has 170,000 rows. This particular query is taking around 2 minutes 30 seconds to complete. 

If I change the query to remove the ORDER BY clause, the query finishes in about 0.6 seconds. If I change the query to remove the LIMIT clause, the query finishes in about 0.23 seconds. 

I have read this article but I'm not sure what else I can do to improve this query. I know that the email index won't be used because of the full wildcard search, but I thought the lastname index would help things with the ORDER BY anyway.

mysql&gt; 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)


How can I improve this query to finish quicker with the ORDER BY and LIMIT 0,50 clauses?
This composite index may help:

INDEX(account_id, lastname)


When adding it, you may as well remove INDEX(account_id), since it will then be redundant.

This may be even better, but I am not sure:

INDEX(deleted, account_id, lastname)


However it does not supersede INDEX(account_id).