Your indexes look great.
The performance problems seem to come from the fact that you are JOIN all rows, and then filtering using HAVING .
This will probably work better:
SELECT * FROM ( SELECT email, COUNT(id) AS number_of_contacts FROM contacted_emails GROUP BY email HAVING COUNT(id) > 3 ) AS ce LEFT OUTER JOIN blacklist AS bl ON ce.email = bl.email LEFT OUTER JOIN submission_authors AS sa ON ce.email = sa.email LEFT OUTER JOIN users AS u ON ce.email = u.email WHERE bl.email IS NULL AND sa.email IS NULL AND u.email IS NULL
Here you limit your initial GROUP ed dataset to JOIN s, which is significantly more optimal.
Despite the context of your original query, the LEFT OUTER JOIN tables that appear to be used at all, so the ones below will probably return the same results with even less overhead:
SELECT email, COUNT(id) AS number_of_contacts FROM contacted_emails GROUP BY email HAVING count(id) > 3
What is the point of these JOIN ed tables? LEFT JOIN does not allow them to reduce data, and you look only at the aggregate data from contacted_emails . Did you mean to use INNER JOIN instead?
EDIT: You mentioned that the join point is to exclude messages in existing tables. I modified my first request to properly merge exceptions (this was a mistake in your originally published code).
Here is another possible option that may work well for you:
SELECT FROM contacted_emails LEFT JOIN ( SELECT email FROM blacklist UNION ALL SELECT email FROM submission_authors UNION ALL SELECT email FROM users ) AS existing ON contacted_emails.email = existing.email WHERE existing.email IS NULL GROUP BY contacted_emails.email HAVING COUNT(id) > 3
What I'm doing here is collecting existing letters in a subquery and making a single exception to this view.
Another way you can try to express this is as an uncorrelated subquery in the WHERE clause:
SELECT FROM contacted_emails WHERE email NOT IN ( SELECT email FROM blacklist UNION ALL SELECT email FROM submission_authors UNION ALL SELECT email FROM users ) GROUP BY email HAVING COUNT(id) > 3
Try them all and see what gives the best execution plan in MySQL.