Can someone decipher this deadlock for me? We don't have a real DBA in our shop at this time, I'm filling in the best I can.  It looks like the INSERT has taken place first and is holding a lock the SELECT FOR UPDATE needs.  But the INSERT is also waiting on another lock, is that other lock already held by the SELECT FOR UPDATE, or is there another transaction not being shown in INNODB STATUS.

INNODB STATUS:
------------------------
LATEST DETECTED DEADLOCK
------------------------
2015-11-24 11:42:33 0x1470
*** (1) TRANSACTION:
TRANSACTION 191471, ACTIVE 0 sec fetching rows
mysql tables in use 1, locked 1
LOCK WAIT 7 lock struct(s), heap size 1136, 9 row lock(s)
MySQL thread id 7, OS thread handle 7700, query id 57301 localhost 127.0.0.1 resonant Creating sort index
select this_.Id as Id80_0_, this_.Queue as Queue80_0_, this_.OriginalQueueName as Original3_80_0_, this_.Message as Message80_0_, this_.Retries as Retries80_0_, this_.Locked as Locked80_0_, this_.Failed as Failed80_0_, this_.LastTryDate as LastTryD8_80_0_, this_.Context as Context80_0_, this_.CreateDate as CreateDate80_0_ from sys_messages this_ where this_.Queue&lt;&gt;'QDead' and this_.Locked=0 and this_.Failed=0 and this_.CreateDate&lt;='2015-11-24 11:42:31.24' order by this_.CreateDate asc for update
*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 675 page no 5 n bits 296 index idx_sys_messages_Locked_Failed_Queue of table `hmuw`.`sys_messages` trx id 191471 lock_mode X waiting
Record lock, heap no 226 PHYSICAL RECORD: n_fields 4; compact format; info bits 0
0: len 1; hex 00; asc  ;;
1: len 1; hex 00; asc  ;;
2: len 9; hex 515365727669636573; asc QServices;;
3: len 30; hex 323235383235656633623034643933343061303130613261326465353733; asc 225825ef3b04d9340a010a2a2de573; (total 32 bytes);

*** (2) TRANSACTION:
TRANSACTION 191469, ACTIVE 2 sec inserting, thread declared inside InnoDB 5000
mysql tables in use 1, locked 1
7 lock struct(s), heap size 1136, 3 row lock(s), undo log entries 9
MySQL thread id 5, OS thread handle 5232, query id 57358 localhost 127.0.0.1 resonant update
insert into sys_messages (Queue, OriginalQueueName, Message, Retries, Locked, Failed, LastTryDate, Context, CreateDate, Id) values ('QEvents', 'QEvents', x'ACED000573720037636F6D2E7265736F6E616E742E6875622E6576656E74732E6E6F74696669636174696F6E732E4576656E744E6F74696669636174696F6E00000000000000010200024C0004646174617400104C6A6176612F7574696C2F4C6973743B4C0007737464446174617400454C636F6D2F7265736F6E616E742F6875622F6576656E74732F6E6F74696669636174696F6E732F4576656E745374616E646172644E6F74696669636174696F6E446174613B7870737200136A6176612E7574696C2E41727261794C6973747881D21D99C7619D03000149000473697A657870000000157704000000157372003B636F6D2E7265736F6E616E742E6875622E6576656E74732E6E6F74696669636174696F6E732E4576656E744E6F74696669636174696F6E4461746100000000000000010200014C000673704461746171007E000178707371007E00040000000177040000000173720043636F6D2E7265736F6E616E742E6875622E6576656E74732E6E6F74696669636174696F6E732E4576
*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 675 page no 5 n bits 296 index idx_sys_messages_Locked_Failed_Queue of table `hmuw`.`sys_messages` trx id 191469 lock_mode X locks rec but not gap
Record lock, heap no 226 PHYSICAL RECORD: n_fields 4; compact format; info bits 0
0: len 1; hex 00; asc  ;;
1: len 1; hex 00; asc  ;;
2: len 9; hex 515365727669636573; asc QServices;;
3: len 30; hex 323235383235656633623034643933343061303130613261326465353733; asc 225825ef3b04d9340a010a2a2de573; (total 32 bytes);

*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 675 page no 5 n bits 296 index idx_sys_messages_Locked_Failed_Queue of table `hmuw`.`sys_messages` trx id 191469 lock_mode X locks gap before rec insert intention waiting
Record lock, heap no 191 PHYSICAL RECORD: n_fields 4; compact format; info bits 0
0: len 1; hex 00; asc  ;;
1: len 1; hex 00; asc  ;;
2: len 7; hex 514576656e7473; asc QEvents;;
3: len 30; hex 396263626431636533623034636563383061303130613261326465353733; asc 9bcbd1ce3b04cec80a010a2a2de573; (total 32 bytes);

*** WE ROLL BACK TRANSACTION (1)
-
2 Types of deadlocks. 
    1. true cycle in the waits-for graph
    2. waits-for graph that is too expensive to check for cycles.

If InnoDB has to check more than a million locks in a graph, or if it recurses 
through more than 200 transactions while checking, it gives up and says there's a deadlock. These numbers are hardcoded constants and cannot be configured (although recompile is possible). 

The last line suggests Transaction 1 was chosen as a deadlock victim and was rolled back. 

Thus when you re-run the transaction that was rolled back, it might have to wait for other transactions to complete, but typically the deadlock does not recur. Please try...