Todas las consultas que no se ejecutan dentro de una transacción explícita se ejecutan en una transacción implícita que se confirma inmediatamente cuando finaliza la consulta o retrocede si ocurre un error... entonces, sí, está utilizando transacciones.

Los interbloqueos ocurren cuando al menos dos consultas están en proceso de adquirir bloqueos, y cada una de ellas tiene bloqueos de nivel de fila que adquirieron por casualidad en un orden tal que ahora cada una necesita otro bloqueo que tiene el otro, por lo que Estás "bloqueado". Existe una condición de espera infinita entre las consultas en ejecución. El servidor se da cuenta de esto.

El error no es tanto una falla como el servidor que dice: "Veo lo que hiciste, ahí... y, de nada, lo limpié por ti porque, de lo contrario, habrías esperado una eternidad".

Lo que no está viendo es que hay dos culpables, dos consultas diferentes que causaron el problema, pero solo uno de ellos es castigado. La consulta que haya realizado la menor cantidad de trabajo (ciertamente, este concepto es nebuloso) se eliminará con el error de interbloqueo, y la otra consulta continuará felizmente por su camino, sin tener idea de que fue el afortunado sobreviviente.

Esta es la razón por la que el mensaje de error de interbloqueo termina con "intente reiniciar la transacción", lo que, si no está utilizando transacciones explícitamente, solo significa "ejecutar su consulta nuevamente".

Consulte https://dev.mysql.com/doc/refman/5.6/en/innodb-deadlocks.html y examine el resultado de SHOW ENGINE INNODB STATUS; , que le mostrará la otra consulta, la que ayudó a causar el interbloqueo pero que no se eliminó, así como la que sí.