Mysql deadlock explanation needed

The first step is determining what the two queries are:

SELECT api_key, completed, compute_units, created, deleted, flags, func_name, group_id, hostname, is_meta, jid, label, language, num_children, parent_ujid, priority, process_id, restartable, status, type, uid, ujid, version, wid FROM jobs WHERE status='new' and is_meta=0 ORDER BY priority asc,jid asc FOR UPDATE

..and:

UPDATE jobs SET status='done' WHERE jid=10099

The first is a SELECT, the second is an UPDATE. But the key is the FOR UPDATE at the end of the SELECT, which I emphasized in bold.

The FOR UPDATE syntax is for a locking read - you can read the documentation about it here. The MySQL deadlock documentation suggestes using READ COMMITTED if you run into locking issues like these ones.

SHOW INNODB STATUS walk through

I'm not 100% sure but I believe they are not "the same lock".

* (1) WAITING FOR THIS LOCK TO BE GRANTED: RECORD LOCKS space id 0 page no 17549 n bits 128 index PRIMARY of table takeyourorder/jobs trx id 0 479286429 lock_mode X waiting Record lock, heap no 61 PHYSICAL RECORD: n_fields 26; compact format; info bits 0

* (2) HOLDS THE LOCK(S): RECORD LOCKS space id 0 page no 17549 n bits 128 index PRIMARY of table takeyourorder/jobs trx id 0 479286425 lock_mode X locks rec but not gap Record lock, heap no 61 PHYSICAL RECORD: n_fields 26; compact format; info bits 0

* (2) WAITING FOR THIS LOCK TO BE GRANTED: RECORD LOCKS space id 0 page no 17548 n bits 144 index PRIMARY of table takeyourorder/jobs trx id 0 479286425 lock_mode X locks rec but not gap waiting Record lock, heap no 73 PHYSICAL RECORD: n_fields 26; compact format; info bits 0

Tx(2) holds "heap no 61" record lock and is waiting for "heap no 73" record lock. Tx(1) is waiting for "heap no 61". The log doesn't tell who holds "heap no 73" but maybe it's just a limitation of "SHOW ENGINE INNODB STATUS".You can confirm that similar log will be generated by simple deadlock scenario.