Mysql deadlock on non unique index

I'm getting the deadlock on MySQL v8.0.32 which is very strange for me because of the following: 1. I'm trying to insert the data: parent-child record (users, user_roles) - each transactions inserts new user and record in join table with some role. 2. The index that is causing deadlock (on user_roles) is not unique and I see that gap lock is not used. 3. Sequence of statements is the same and not like in classical deadlock example (when T1 changes table A, then B and T2 vice versa - table B than table A)

CREATE TABLE user_roles (
  id int NOT NULL AUTO_INCREMENT,
  role_id int DEFAULT NULL,
  user_id int DEFAULT NULL,
  context_type varchar(255) NOT NULL,
  context_id int NOT NULL,
  created_by int DEFAULT NULL,
  updated_by int DEFAULT NULL,
  deleted_at datetime DEFAULT NULL,
  created_at datetime DEFAULT NULL,
  updated_at datetime DEFAULT NULL,
  PRIMARY KEY (id),
  KEY fk_rails_dcd6720bf9 (created_by),
  KEY index_user_roles_on_deleted_at (deleted_at),
  KEY index_user_roles_on_role_id (role_id),
  KEY fk_rails_3c5703b833 (updated_by),
  KEY index_user_roles_on_user_id (user_id),
  CONSTRAINT fk_rails_318345354e FOREIGN KEY (user_id) REFERENCES users (id) ON DELETE CASCADE,
  CONSTRAINT fk_rails_3369e0d5fc FOREIGN KEY (role_id) REFERENCES roles (id) ON DELETE CASCADE,
  CONSTRAINT fk_rails_3c5703b833 FOREIGN KEY (updated_by) REFERENCES users (id),
  CONSTRAINT fk_rails_dcd6720bf9 FOREIGN KEY (created_by) REFERENCES users (id)
) ENGINE=InnoDB AUTO_INCREMENT=450 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci

The code that is executed concurrently is the following (simplified):

BEGIN;

INSERT INTO users ...;
DELETE FROM user_roles WHERE user_roles.user_id = 'id of inserted user' AND user_roles.context_type = 'Trial' AND user_roles.context_id = 'some constant id'
INSERT INTO user_roles (role_id, user_id, context_type, context_id, created_at, updated_at) VALUES (...)


COMMIT;

Deadlock information:

------------------------
LATEST DETECTED DEADLOCK
------------------------
2023-10-10 16:49:52 0x70000ed4b000
*** (1) TRANSACTION:
TRANSACTION 23884460, ACTIVE 1 sec inserting
mysql tables in use 1, locked 1
LOCK WAIT 10 lock struct(s), heap size 1128, 6 row lock(s), undo log entries 3
MySQL thread id 1862, OS thread handle 123145570869248, query id 1067189 localhost 127.0.0.1 root update
INSERT INTO user_roles (role_id, user_id, context_type, context_id, created_at, updated_at) VALUES (85, 397, 'Trial', 6, '2023-10-10 13:49:52', '2023-10-10 13:49:52')

*** (1) HOLDS THE LOCK(S):
RECORD LOCKS space id 841074 page no 9 n bits 496 index index_user_roles_on_user_id of table tap-prototype-copy.user_roles trx id 23884460 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;;


*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 841074 page no 9 n bits 496 index index_user_roles_on_user_id of table tap-prototype-copy.user_roles trx id 23884460 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 23884464, ACTIVE 0 sec inserting
mysql tables in use 1, locked 1
LOCK WAIT 10 lock struct(s), heap size 1128, 6 row lock(s), undo log entries 3
MySQL thread id 1864, OS thread handle 123145565544448, query id 1067336 localhost 127.0.0.1 root update
INSERT INTO user_roles (role_id, user_id, context_type, context_id, created_at, updated_at) VALUES (85, 398, 'Trial', 6, '2023-10-10 13:49:52', '2023-10-10 13:49:52')

*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 841074 page no 9 n bits 496 index index_user_roles_on_user_id of table tap-prototype-copy.user_roles trx id 23884464 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 841074 page no 9 n bits 496 index index_user_roles_on_user_id of table tap-prototype-copy.user_roles trx id 23884464 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)

As we can see we're inserting data for different users (397, 398) and gap locking is not used. So what is the reason for the deadlock then? Seems like a very common and simple situation, but I can't understand what can we improve here. Thanks in advance! --------- **UPDATE**: in respond to Rick James: 1. By joint (join) tables I mean user_roles table as it join (many-to many) users and roles. 2. Yeah it was a simplistic description, I omitted the following detail. So no SELECT .. FOR UPDATE, but I have in between DELETE, eg:

DELETE FROM user_roles WHERE user_roles.user_id = 398 AND user_roles.context_type = 'Trial' AND user_roles.context_id = 64

I also updated pseudo code above. When I remove this DELETE - deadlock goes away. Looks like a root of the problem, but for some reason it is not mentioned in deadlock report. Were you inserting user rows and getting back 397 and 398 for user_id? - yes, insert into users is the first statement. 3. I can't get rid of id in favor of composite primary key - and it doesn't look like it can help here... ----- **UPDATE (2023-10-17)** I was able to explore locks that these statements produce and discovered that supremum pseudo-record lock is utilized. This is what I've found in documentation : > The supremum is not a real index record, so, in effect, this next-key lock locks only the gap following the largest index value Strange that gap locks are not mentioned in deadlock report, but this explanation looks like an explanation here: because we are adding new user record and insert data into related join table user_roles. This involves incrementing user ID - as well as largest index value in user_roles. This is how I treat the docs. If this is the case, then I'm frustrated by the fact that we can't workaround the deadlocks in such very simple situation...

mysql> select * from performance_schema.data_locks \G
*************************** 1. row ***************************
               ENGINE: INNODB
       ENGINE_LOCK_ID: 140575951646488:851842:140575916454504
ENGINE_TRANSACTION_ID: 24023562
            THREAD_ID: 4671
             EVENT_ID: 11
        OBJECT_SCHEMA: tap-test
          OBJECT_NAME: user_roles
       PARTITION_NAME: NULL
    SUBPARTITION_NAME: NULL
           INDEX_NAME: NULL
OBJECT_INSTANCE_BEGIN: 140575916454504
            LOCK_TYPE: TABLE
            LOCK_MODE: IX
          LOCK_STATUS: GRANTED
            LOCK_DATA: NULL
*************************** 2. row ***************************
               ENGINE: INNODB
       ENGINE_LOCK_ID: 140575951646488:851850:140575916454416
ENGINE_TRANSACTION_ID: 24023562
            THREAD_ID: 4671
             EVENT_ID: 9
        OBJECT_SCHEMA: tap-test
          OBJECT_NAME: users
       PARTITION_NAME: NULL
    SUBPARTITION_NAME: NULL
           INDEX_NAME: NULL
OBJECT_INSTANCE_BEGIN: 140575916454416
            LOCK_TYPE: TABLE
            LOCK_MODE: IX
          LOCK_STATUS: GRANTED
            LOCK_DATA: NULL
*************************** 3. row ***************************
               ENGINE: INNODB
       ENGINE_LOCK_ID: 140575951646488:850032:9:1:140576159006240
ENGINE_TRANSACTION_ID: 24023562
            THREAD_ID: 4671
             EVENT_ID: 11
        OBJECT_SCHEMA: tap-test
          OBJECT_NAME: user_roles
       PARTITION_NAME: NULL
    SUBPARTITION_NAME: NULL
           INDEX_NAME: index_user_roles_on_user_id
OBJECT_INSTANCE_BEGIN: 140576159006240
            LOCK_TYPE: RECORD
            LOCK_MODE: X
          LOCK_STATUS: GRANTED
            LOCK_DATA: supremum pseudo-record
3 rows in set (0.00 sec)