Solution for Insert Intention Locks in MySQL
I suspect the deadlock happens because InnoDB is conservative on dealing with "gaps". Note that 100 and 700 are both in the same nebulous area of untouched land. InnoDB can't (or at least does not) deal with the fact that "100" and "700" are different. InnoDB would like to tag individual rows but there are no rows already in the table with those ids.
Transaction 2 was probably going to timeout (see innodb_lock_wait_timeout). When you poked Transaction 1 a second time with #2 still wanting a lock, InnoDB punted and gave up.
Bottom Line: Live with deadlocks. When they happen, start back at the BEGIN. You have found yet-another obscure case where an unnecessary deadlock happens.
Furthermore, I suspect that fixing the code for this case would slow down most other cases, and lead to a series of errors that would take several releases to discover and fix.
Note that starting with MySQL 8.0.1, the performance schema exposes innodb data locks.
See https://dev.mysql.com/doc/refman/8.0/en/data-locks-table.html
See https://dev.mysql.com/doc/refman/8.0/en/data-lock-waits-table.html
In this example, after the first select in session 1 alone the locks are:
mysql> select * from performance_schema.data_locks \G
*************************** 1. row ***************************
ENGINE: INNODB
ENGINE_LOCK_ID: 1808:76
ENGINE_TRANSACTION_ID: 1808
THREAD_ID: 35
EVENT_ID: 13081
OBJECT_SCHEMA: test
OBJECT_NAME: d
PARTITION_NAME: NULL
SUBPARTITION_NAME: NULL
INDEX_NAME: NULL
OBJECT_INSTANCE_BEGIN: 139756088373592
LOCK_TYPE: TABLE
LOCK_MODE: IX
LOCK_STATUS: GRANTED
LOCK_DATA: NULL
*************************** 2. row ***************************
ENGINE: INNODB
ENGINE_LOCK_ID: 1808:2:5:1
ENGINE_TRANSACTION_ID: 1808
THREAD_ID: 35
EVENT_ID: 13111
OBJECT_SCHEMA: test
OBJECT_NAME: d
PARTITION_NAME: NULL
SUBPARTITION_NAME: NULL
INDEX_NAME: id
OBJECT_INSTANCE_BEGIN: 139756088370552
LOCK_TYPE: RECORD
LOCK_MODE: X
LOCK_STATUS: GRANTED
LOCK_DATA: supremum pseudo-record <--- HERE
2 rows in set (0.00 sec)
This is not a solution to the deadlock itself, but having visibility on the locks taken goes a long way to understand the problem.
Here, both SELECT FOR UPDATE lock the "suprenum" record, because id 100 and 700 are greater than the biggest ID in the table (it's empty).
Once more records are present (say at ID = 500), both queries should execute concurrently, as a different gap in IDs will be locked.
This deadlock error is a bug in the MySQL InnoDB engine that has not been fixed for 12 years. (Bug #25847: https://bugs.mysql.com/bug.php?id=25847, workaround: How do I lock on an InnoDB row that doesn't exist yet?) It is not related to Unique Key. Running this query will also result in the same Deadlock error.
Session #1: CREATE TABLE t (id int) ENGINE=InnoDB;
Session #1: SET AUTOCOMMIT = 0;
Session #1: SELECT id FROM t WHERE id = 1 FOR UPDATE;
Session #2: SET AUTOCOMMIT = 0;
Session #2: SELECT id FROM t WHERE id = 2 FOR UPDATE;
Session #1: INSERT INTO t (id) VALUES (1); -- Hang
Session #2: INSERT INTO t (id) VALUES (2); -- Session #1: OK, Session #2: Deadlock found when trying to get lock; try restarting transaction
InnoDB Status is the same:
------------------------
LATEST DETECTED DEADLOCK
------------------------
2019-10-24 00:25:31 0x1638
*** (1) TRANSACTION:
TRANSACTION 1287, ACTIVE 62 sec inserting
mysql tables in use 1, locked 1
LOCK WAIT 3 lock struct(s), heap size 1136, 2 row lock(s)
MySQL thread id 7, OS thread handle 9444, query id 143 localhost ::1 root update
INSERT INTO t (id) VALUES (1)
*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 23 page no 3 n bits 72 index GEN_CLUST_INDEX of table `test`.`t` trx id 1287 lock_mode X insert intention waiting
Record lock, heap no 1 PHYSICAL RECORD: n_fields 1; compact format; info bits 0
0: len 8; hex 73757072656d756d; asc supremum;;
*** (2) TRANSACTION:
TRANSACTION 1288, ACTIVE 19 sec inserting, thread declared inside InnoDB 5000
mysql tables in use 1, locked 1
3 lock struct(s), heap size 1136, 2 row lock(s)
MySQL thread id 9, OS thread handle 5688, query id 145 localhost ::1 root update
INSERT INTO t (id) VALUES (2)
*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 23 page no 3 n bits 72 index GEN_CLUST_INDEX of table `test`.`t` trx id 1288 lock_mode X
Record lock, heap no 1 PHYSICAL RECORD: n_fields 1; compact format; info bits 0
0: len 8; hex 73757072656d756d; asc supremum;;
*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 23 page no 3 n bits 72 index GEN_CLUST_INDEX of table `test`.`t` trx id 1288 lock_mode X insert intention waiting
Record lock, heap no 1 PHYSICAL RECORD: n_fields 1; compact format; info bits 0
0: len 8; hex 73757072656d756d; asc supremum;;
*** WE ROLL BACK TRANSACTION (2)