How can I avoid deadlock on indexes of a table with a compound primary key?

Question

I have a table thus:

CREATE TABLE `DeviceGrants` (
    `DeviceId` BINARY(16) NOT NULL
        COMMENT "128-bit UID",
    `Grant` ENUM("AcceleratedRead") NOT NULL
        COMMENT "The kind of grant this is",
    `ExpiryTime` DATETIME NOT NULL
        COMMENT "The date/time at which this grant will expire",

    PRIMARY KEY(`DeviceId`, `Grant`),
    KEY (`ExpiryTime`),
    FOREIGN KEY (`DeviceId`) REFERENCES `Devices` (`DeviceId`)
      ON DELETE CASCADE
) ENGINE=InnoDB;

^{(Grant may only take one value right now, but this list is very likely to grow in future versions so the column is in place for forward-compatibility.)}

I've witnessed a deadlock between this ^{(I think)}:

INSERT INTO `DeviceGrants` (`DeviceId`, `Grant`, `ExpiryTime`)
VALUES(
    UNHEX('<x>'),
    'AcceleratedRead',
    NOW() + INTERVAL 60 SECOND
)
ON DUPLICATE KEY UPDATE
    `ExpiryTime` = NOW() + INTERVAL 60 SECOND

and this:

DELETE FROM `DeviceGrants` WHERE `ExpiryTime` <= NOW()

Now, following the advice in this excellent answer, I wanted to avoid the deadlock by rewriting the second statement. However, since the table has no single-column, auto-increment primary key (which is semantically needless), I'm not sure how to go about it.

What is my best bet here?

Answer 1

I am not quite sure how the other solution guarantees that the keys are locked in the right order (the subquery could very well not use the primary key at all) but I suppose we can easily extend this solution to:

DELETE FROM DeviceGrants
WHERE (DeviceId, Grants) IN (
    -- the other solution did not mention: You can't specify target table 'xx' for update in FROM clause
    -- I used the workaround suggested in https://stackoverflow.com/a/45498/1446005
    -- hence the sub-sub-query
    SELECT * FROM (
      SELECT DeviceId, Grants
      FROM DeviceGrants
      WHERE expire <=  NOW()
    ) AS subq) ;

---

Since I do not fully understand the original solution, I can't prove the above is correct, but it seems to be. Running the below test for 10 minutes hasn't raised any deadlock (remove the ORDER BY clause and deadlocks occur):

mysql> CREATE TABLE t (id INT, gr INT, expire DATETIME, PRIMARY KEY(id, gr), KEY(expire));

bash#1> while 1; \
  do mysql test -e "insert into t values (2, 2, NOW()) on duplicate key update expire = NOW() + SLEEP(3);"; \
  done;

bash#2> while true; \
  do mysql test -e "delete from t where (id, gr) in (select * from (select id,gr from t where expire <=  now() order by id, gr ) as sub)" ; \
  done;