Mysql deadlock on non unique index

Question

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)

• Rick James: What do you mean by "and joint tables"? Sounds like we need more details.
• Rick James: Are there any SELECTs in the transaction? Do they have FOR UPDATE on them? Were you inserting user rows and getting back 397 and 398 for urser_id?
• Rick James: Is the combo (user_id, role_id) unique? If so, do you think it reasonable to get rid of id and make that pair the PRIMARY KEY?
• Andrey Khataev: @RickJames, thanks for the response! I answered your questions in the question body
• Rick James: How did you get the new user_id after the initial INSERT INTO users? I assume it was something like 'SELECT LAST_INSERT_ID();?

Answer 1

ALTER TABLE user_roles
 DROP PRIMARY KEY,
 DROP COLUMN id,
 DROP INDEX index_user_roles_on_role_id,
 DROP INDEX index_user_roles_on_user_id,
 ADD PRIMARY KEY(user_id, role_id),
 ADD INDEX(role_id, user_id),
 ADD INDEX(context_id, context_type, user_id) ;

Benefits:

• The last index will at least make the DELETE faster, and possibly lock fewer rows.

  Alas, I don't think that "LATEST DETECTED DEADLOCK" gives any clues about the locks caused by the DELETE.

• Since this is a many-to-many table, id is a waste of performance; most of the suggestions are for replacing it with better indexes. (See also Many-to-many )

  I assume no other table references user_roles.id?

• Andrey Khataev: unfortunately, we can't transform separate indexes index_user_roles_on_role_id/index_user_roles_on_user_id into composite, because they correspond to foreign keys and we want to have fast search by these keys. While query by user_id won't use index on (role_id, user_id).
• Andrey Khataev: also I didn't still understand why DELETE from user_roles for user_id = X blocks INSERT into user_roles for user_id = Y. Your suggestions do not answer this question. (I'm still trying to understand how we read ID of inserted record, because it is done under the hood by ORM)
• Rick James: @AndreyKhataev - Drop those indexes and at the same time you build the new indexes; the FK definition should realize that the new keys are sufficient. Also, the Optimizer failed to use the longer index when the shorter one is there: INDEX(a), INDEX(a,b). If there is further trouble, DISABLE the FKs while changing the indexes, then re-enable.
• Rick James: I don't know whether the DELETE interferes; I was running out of ideas. Improving the index will at least help its speed.
• Rick James: @AndreyKhataev - If you are unwilling to change the PK, try adding ADD INDEX(context_id, context_type, user_id).