InnoDB deadlock with INSERT .. SELECT
the deadlock message sometimes will not show the full picture. It could be some other query is holding the lock which is not any of those two showed in the log. As you said, you have delete query in the beginning, that properly would be the case. 

Here is a way I normally use to troubleshoot the deadlocks when you can not get all the info from the log.

mysql&gt; set global log_output = 'table';
mysql&gt; set global general_log=on;


Then you reproduce the problem, when the deadlock happens, turn off the general log. Find those two queries in the mysql.general_log, then use thread_id to find the start and end of the transaction. You will have all the queries in the transaction, then you can go through the logic, to find out which is the query or logic caused the problem.