Concurrent update queries locking rows when `where` clause doesn’t match

My application sends messages to Slack. On very rare occasions we may need to retract the message going out. These retractions are handled by queueing a job for each messageId that has been created thus far.

I noticed during our last retraction about a week ago that we saw about 2k:

try restarting transaction (SQL: update `message` set `deleted_at` = 2018-12-04 04:47:44 where (`slack_channel_id` = xxxxxxxxxxxxxxxx and message_id = xxxxxxxxxxxxxxxx))"

It seems like the queue jobs (which are absolutely happening concurrently) are stepping on each other’s toes. My expectation is that this query would only put a lock on the individual row it needs (we have a compound unique index on slack_server_id, slack_channel_id and message_id), but it seems like more than one job is locking this record.

Why are these concurrent update queries locking rows that don’t match the where clause?