I'm seeing some odd (to me) behavior in MySQL. Let's start with the table that I'll be talking about.

CREATE TABLE `active_foo` (
  `active_foo_id` bigint(20) NOT NULL AUTO_INCREMENT,
  `c_id` bigint(20) NOT NULL,
  `aa_id` bigint(20) NOT NULL,
  `bar` varchar(60) DEFAULT NULL,
  `foo_string` varchar(60) NOT NULL,
  `handle_id` bigint(20) NOT NULL DEFAULT '-1',
  `hostname` varchar(64) DEFAULT NULL,
  `usage` int(11) DEFAULT NULL,
  `foo_id` int(11) NOT NULL,
  `bucket_id` int(11) NOT NULL,
  PRIMARY KEY (`active_foo_id`),
  KEY `idx_active_foo_foo_config` (`foo_id`),
  KEY `idx_active_foo_aa` (`aa_id`),
  KEY `foo_index` (`c_id`,`foo_id`,`foo_string`),
  KEY `idx_active_foo_buckets1` (`bucket_id`),
  KEY `handle_idx` (`handle_id`),
  KEY `host_idx` (`hostname`),
  CONSTRAINT `fk_active_foo_aa_idx` FOREIGN KEY (`aa_id`) REFERENCES `aa` (`access_id`) ON DELETE CASCADE,
  CONSTRAINT `fk_active_foo_buckets1` FOREIGN KEY (`bucket_id`) REFERENCES `foo_buckets` (`bucket_id`) ON DELETE NO ACTION ON UPDATE NO ACTION,
  CONSTRAINT `fk_active_foo_foo_config` FOREIGN KEY (`foo_id`) REFERENCES `foo_config` (`foo_id`) ON DELETE CASCADE ON UPDATE CASCADE
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=latin1;

I have two inserts that look something like this:

insert into active_foo(c_id, foo_string, `usage`, foo_id, bucket_id, aa_id) 
values(6, '#TAG', 1, 1, 2, 3268192)

and

insert into active_foo(c_id, foo_string, `usage`, foo_id, bucket_id, aa_id) 
values(7, '#TAG', 1, 1, 1, 3268193)

Somehow they appear to be deadlocking on the same index, but I'm puzzled because I'd expect a deadlock to happen only if there is a second index involved that one holds and the other waits for. The latest deadlock report seems to indicate that they are in fact waiting on the same index, which I would think would just cause a small delay, not a deadlock.

180904 12:32:02
*** (1) TRANSACTION:
TRANSACTION 34018365, ACTIVE 1 sec inserting
mysql tables in use 1, locked 1
LOCK WAIT 23 lock struct(s), heap size 3112, 17 row lock(s), undo log entries 3
MySQL thread id 459744, OS thread handle 0x2b42d5470700, query id 603275321     someotherip myuser update
insert into active_foo(c_id, foo_string, `usage`, foo_id, bucket_id, aa_id) values(6, '#TAG', 1, 1, 2, 3268192)
*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 60 page no 4 n bits 152 index `foo_index` of table `mydb`.`active_foo` trx id 34018365 lock_mode X locks gap before rec insert intention waiting
Record lock, heap no 34 PHYSICAL RECORD: n_fields 4; compact format; info bits 0
 0: len 8; hex 80000000000000b7; asc         ;;
 1: len 4; hex 80000001; asc     ;;
 2: len 23; hex 23544147; asc #TAG;;
 3: len 8; hex 800000000005b184; asc         ;;

*** (2) TRANSACTION:
TRANSACTION 3401837B, ACTIVE 1 sec inserting
mysql tables in use 1, locked 1
21 lock struct(s), heap size 3112, 13 row lock(s), undo log entries 3
MySQL thread id 460530, OS thread handle 0x2b415579b700, query id 603275331 someip myuser update
insert into active_foo(c_id, foo_string, `usage`, foo_id, bucket_id, aa_id) values(7, '#TAG', 1, 1, 1, 3268193)
*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 60 page no 4 n bits 152 index `foo_index` of table `mydb`.`active_foo` trx id 3401837B lock_mode X locks gap before rec
Record lock, heap no 34 PHYSICAL RECORD: n_fields 4; compact format; info bits 0
 0: len 8; hex 80000000000000b7; asc         ;;
 1: len 4; hex 80000001; asc     ;;
 2: len 23; hex 23544147; asc #TAG;;
 3: len 8; hex 800000000005b184; asc         ;;

*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 60 page no 4 n bits 152 index `foo_index` of table `mydb`.`active_foo` trx id 3401837B lock_mode X locks gap before rec insert intention waiting
Record lock, heap no 34 PHYSICAL RECORD: n_fields 4; compact format; info bits 0
 0: len 8; hex 80000000000000b7; asc         ;;
 1: len 4; hex 80000001; asc     ;;
 2: len 23; hex 23544147; asc #TAG;;
 3: len 8; hex 800000000005b184; asc         ;;

*** WE ROLL BACK TRANSACTION (2)

Note that foo_index is not only the lock held by transaction 2, it's also the lock waiting to be granted. I can't tell which row in particular is locked based on the latest deadlock report, I just know that it contains #TAG for the foo_string column in both cases. I suppose one lock might be for c_id 6 and the other for c_id 7.

This is where I start to question my understanding of how index locking works exactly, particularly when it comes to multi column indexes. Is the order of the columns used to determine which row to lock ever undefined? For example, with the following index:

KEY `foo_index` (`c_id`,`foo_id`,`foo_string`)

Could one insert be first locking the row that matches the columns going left->right and the second insert be locking the row that matches the columns going right->left? It seems like that could create a deadlock because foo_string #TAG is locked first for one query but last for another. Any ideas as to why I'm deadlocking when it seems like I should merely be locking, waiting, and moving on?