There is a big table in a statement-based parallel replication setup, like this:
Usually status is updated for several ids in a single UPDATE like this:
So, we have range access and reasonable estimation of rows in range. We may get this plan hundreds of times in a row, but sometimes we end up with a totally different plan while this same query is executed by slave:
Optimizer used full index scan for the PRIMARY key (and estimated rows as 1), and this caused a very slow execution of the query and millions of locks set in the process that stalled all other parallel replication threads eventually in a "deadlock".
I suspect there is a bug/corner case somewhere in the optimizer when it decides about indexes available for range access. Maybe this is caused by bad InnoDB statistics etc, but in any case I think we should prevent such an execution path.